通过将现有算法从顺序设定应用到分布式设定,仅利用恒定数量的 MapReduce 循环,在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。
Jul, 2015
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
本文研究自适应子模型优化的适应性和查询复杂度,提出了适用于最大基数约束的单调子模型函数的分布式算法,并将其推广到子模型覆盖问题。
Jul, 2018
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
Feb, 2015
本文介绍了通过使用广义子模函数代替较简单的目标函数获得的几个传统计算机科学问题的推广,包括子模型负载平衡,子模型最稀疏切割和子模型平衡切割等,并建立了这些问题的近似界限。
May, 2008
本研究在完全动态的环境下,旨在最大化基数约束下的单调子模函数,研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法,并结合经验研究证明了算法性能的优越性。
Jun, 2020
在此论文中,我们研究和改善了基于随机聚类的可组合核心集的构建方法,并将其应用于在计算复杂度受限制的分布式和流式处理设置下的覆盖和子模极大化问题,并采用改进的分析技术和新算法提出了首个能够在恒定轮数下打败因子 1/2 的 MapReduce 算法。
Jun, 2015
通过提出一种新颖的分布式界限算法,并使用多轮基于分区的分布式贪心算法,此论文解决了子集选择问题,能够在没有或极小损失质量的情况下,找到高质量的子集。
Feb, 2024
该篇论文提出了一种针对固定容量的分布式子模型最大化的框架,应用于广泛的算法和约束条件,并且为任何可用容量提供近似因子的理论保证,并在多个数据集上进行了实证评估,表现竞争性与中心化贪婪算法相当。
May, 2016
本文探讨了子模最大化算法的适应性,证明了一个新的算法可以在 O (log n) 自适应回合内实现接近于最优 1-1/e 近似。
Apr, 2018