采样优化的限制
本文考虑在噪声下最大化单调子模函数,探讨在噪声和误差存在的情况下,是否能获得算法的可证明保证,结论是对于基数约束k>=2的函数,有一个近似算法,其近似比例任意接近1-1/e;对于基数约束k=1,有一种算法,其近似比率任意接近于1/2。没有随机算法可以获得比1/2+o(1)更好的近似度;如果噪声是对抗性的,则不能获得任何非平凡的近似保证。
Jan, 2016
本文介绍了针对具有限制条件的子模函数进行最大化的两种算法——Repeated Greedy和Sample Greedy,并比较了这两种算法在电影推荐方面的表现。结果表明,Sample Greedy在保证效用相同的情况下,性能至少比最佳基线提高了两个数量级。
Apr, 2017
通过直接优化偏差和方差的组合,该研究通过展示如何进行具有理论保证的高效算法,从而在次模函数中进行分布式鲁棒优化(DRO),从而实现在未知随机次模函数的情况下实现更好的性能和更好的推广。
Feb, 2018
本文提出一种针对子模函数的数据学习算法,可用于数据概括、特征选择和主动学习等机器学习领域。通过将贪婪最大化算法的输出解释为项目序列的分布,本文提出一种可微的方式对模型进行优化。实证研究表明,该方法对解决实际场景中的推荐和图像概括等问题有较好的效果。
Mar, 2018
本文研究次模函数的优化和算法问题,提出了一种在 $k$-cardinality 约束下最大化 $g-c$ 的算法,并通过实验设计对其进行了验证。
Apr, 2019
该论文研究贝叶斯学习中常见的最大后验估计和后验分布采样的计算任务,证明在非凸情况下后验分布采样有时比优化更快,并展示两者在计算复杂性上的不可比较性,呈现出计算复杂度的急剧相变。
Nov, 2019
本文提出了一种优化来自结构化样本的模型(OPSS)用于覆盖函数,证明在三种一般假设条件下,我们可以设计有效的OPSS算法以实现最大覆盖问题的常数逼近,同时,我们在这些假设下证明了一个常数下界,该下界在不考虑计算效率时是紧密的。
Jul, 2020
本研究解决了顺序子模最大化问题,即选择和排名项以优化复合子模函数。与之前大多数学者假设可以访问效用函数不同,我们仅拥有样本数据,并提出了一种新算法,依赖于样本的有限性,在实用场景中证明了有限数据在序列任务中的有效性。
Sep, 2024