Feb, 2015

随机化的威力：大规模数据集上的分布式子模最大化

PDF
TL;DR该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题，该算法可以并行运行并且提供可证明的常数近似保证，即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
machine learningconstrained submodular maximizationdistributed algorithmparallelapproximation guarantees
发现论文，激发创造
  • 分布式次模最大化的新框架

    通过将现有算法从顺序设定应用到分布式设定，仅利用恒定数量的 MapReduce 循环，在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。

    Jul, 2015

  • 水平可扩展次模最大化

    该篇论文提出了一种针对固定容量的分布式子模型最大化的框架，应用于广泛的算法和约束条件，并且为任何可用容量提供近似因子的理论保证，并在多个数据集上进行了实证评估，表现竞争性与中心化贪婪算法相当。

    May, 2016

  • 分布式子模最大化

    本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi，该方法可在 MapReduce 框架下实现，初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题，如稀疏高斯过程推断和样例聚类等问题，且在一定的自然条件下，可以达到接近于传统集中式计算模式下的性能表现。

    Nov, 2014

  • 通过随机化实现子模函数最大化的长期公平性

    通过开发近似算法解决具有组内公平性约束的单调子模函数最大化问题。

    Apr, 2023

  • 分布式基于配对次模函数的大于内存子集选择

    通过提出一种新颖的分布式界限算法，并使用多轮基于分区的分布式贪心算法，此论文解决了子集选择问题，能够在没有或极小损失质量的情况下，找到高质量的子集。

    Feb, 2024

  • 子模最大化问题的确定性算法

    证明了在许多计算机科学中随机化的作用，以及针对次模函数最大化领域的一种新的去随机化算法技术

    Aug, 2015

  • 大规模下具有删除鲁棒性的子模最大化

    本文主要研究如何在保护用户隐私和确保公平性的同时，高效地从大型用户生成的数据集中提取有用信息。该问题被描述成删除鲁棒子模型最大化的一个实例，我们提出了第一种内存高效的集中式、流式和分布式方法，对任意数量的敌对删除具有常数逼近保证。我们对我们的算法在真实世界的应用进行了广泛评估，包括：（i）具有位置隐私限制的 Uber 接送点；（ii）收入预测和犯罪率预测的公平性限制的特征选择；以及 (iii) 由 2,458,285 个特征向量组成的人口普查数据的删除汇总结果的健壮性。

    Nov, 2017

  • 满足背包约束的敌对鲁棒次模最大化

    该研究提出了针对单个和多个背包约束下的单调次模最大化的首个对抗鲁棒算法，具有可扩展的分布式和流式实现。性能评估结果表明，与现有非鲁棒算法的自然鲁棒化相比，该算法对于大型社交网络图等输入具有最佳的目标结果，并表现出极强的性能，即使与提前给出拆除集合的线下算法相比也是如此。

    May, 2019

  • 分布式子模最大化的随机组合核心集

    在此论文中，我们研究和改善了基于随机聚类的可组合核心集的构建方法，并将其应用于在计算复杂度受限制的分布式和流式处理设置下的覆盖和子模极大化问题，并采用改进的分析技术和新算法提出了首个能够在恒定轮数下打败因子 1/2 的 MapReduce 算法。

    Jun, 2015

  • 在 Matroid 约束下流式子模最大化中的公平性

    论文研究流式子模最大化算法中公平性的应用，提出了针对劣模最大化算法的公平机器学习算法，包括在鸽子数量受限的情况下的流式算法以及无法实现的结果。最后，通过社会网络中的最大覆盖，电影推荐和样本聚类等应用的实验验证了其有效性。

    May, 2023