本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
本文提出了一种线性时间算法 STOCHASTIC-GREEDY 用于求解一般性单调子模函数最大化问题,旨在实现对数据的概括,比传统算法 lazy greedy 更快且表现基本一致。
Sep, 2014
通过将现有算法从顺序设定应用到分布式设定,仅利用恒定数量的 MapReduce 循环,在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。
Jul, 2015
该篇论文提出了一种针对固定容量的分布式子模型最大化的框架,应用于广泛的算法和约束条件,并且为任何可用容量提供近似因子的理论保证,并在多个数据集上进行了实证评估,表现竞争性与中心化贪婪算法相当。
May, 2016
通过提出一种新颖的分布式界限算法,并使用多轮基于分区的分布式贪心算法,此论文解决了子集选择问题,能够在没有或极小损失质量的情况下,找到高质量的子集。
Feb, 2024
针对大型数据集中贪心算法的运行时间会非常高的问题,本文介绍了 2 种运用分布式计算和随机评估技术的更快逼近贪心向前选择算法,并且证明了弱次模性的泛化概念足以为这 2 种算法提供乘性逼近保证。同时,研究者还表明这些快速贪心逼近算法在人工数据和真实数据集上的性能要优于多个已有的基线算法。
Mar, 2017
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
Feb, 2015
非单调子模最大化问题和打包约束下的子模并行算法设计优化和逼近
Aug, 2023
通过定义锐度作为子模函数改善贪心算法性能的候选解释,本文探讨了贪心算法在最大化单调子模函数下的性能问题,显示子模函数的锐度影响贪心算法的表现,通过计算实验和理论结果,支持本文的说法。
Feb, 2020
本文探讨了子模最大化算法的适应性,证明了一个新的算法可以在 O (log n) 自适应回合内实现接近于最优 1-1/e 近似。
Apr, 2018