子模最大化问题的确定性算法
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
Feb, 2015
本文提出了一种随机贪心算法来最大化弱次模函数在一般拟阵约束下的值,其中距离次模性的距离由参数 γ 衡量,该算法在实践中表现良好,并且是第一个能够约束弱次模函数最大化具有非平凡逼近保证的算法。
Jul, 2017
本文考虑在噪声下最大化单调子模函数,探讨在噪声和误差存在的情况下,是否能获得算法的可证明保证,结论是对于基数约束 k>=2 的函数,有一个近似算法,其近似比例任意接近 1-1/e; 对于基数约束 k=1,有一种算法,其近似比率任意接近于 1/2。没有随机算法可以获得比 1/2+o (1) 更好的近似度;如果噪声是对抗性的,则不能获得任何非平凡的近似保证。
Jan, 2016
本研究在完全动态的环境下,旨在最大化基数约束下的单调子模函数,研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法,并结合经验研究证明了算法性能的优越性。
Jun, 2020
本研究以连续贪心算法为基础,研究了具有一般性骨架约束的随机子模最大化问题,主要应用于在线学习,团队形成,设施位置,影响最大化,主动学习和感知目标函数。实验表明,使用多项式梯度估计代替样本估计,可有效减少随机性并缩短执行时间。
Mar, 2023
通过将现有算法从顺序设定应用到分布式设定,仅利用恒定数量的 MapReduce 循环,在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。
Jul, 2015
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
研究使用机会约束的子模型优化问题,探讨贪心算法在应用对 Chernoff 边界进行约束违规估计的替代函数后,能高效地获得高品质解,同时在社交网络问题中也能保持有效性。
Nov, 2019