The greedy algorithm for monotone submodular function maximization subject to cardinality constraint is guaranteed to approximate the optimal solution to within a $1-1/e$ factor. Although it is well known that this guarantee is essentially tight in the worst case -- for greedy and in fact any efficient algorithm, experiments show that greedy performs better in practice. We observe that for many applications in practice, the empirical distribution of the budgets (i.e., cardinality constraints) is supported on a wide range, and moreover, all the existing hardness results in theory break under a large perturbation of the budget. To understand the effect of the budget from both algorithmic and hardness perspectives, we introduce a new notion of budget smoothed analysis. We prove that greedy is optimal for every budget distribution, and we give a characterization for the worst-case submodular functions. Based on these results, we show that on the algorithmic side, under realistic budget distributions, greedy and related algorithms enjoy provably better approximation guarantees, that hold even for worst-case functions, and on the hardness side, there exist hard functions that are fairly robust to all the budget distributions.


翻译:单调子模块功能最大化的贪婪算法受到基本限制,可以保证将最佳解决办法接近于1-1/e美元因素。虽然众所周知,这种保证在最坏的情况下基本上很紧 -- -- 贪婪和事实上是有效的算法,但实验表明贪婪在实践中表现更好。我们观察到,对于许多应用,预算的经验分配(即最基本限制)在广泛的范围内得到支持,此外,理论在预算的大扰动下打破了所有现有的硬性结果。为了从算法和硬性角度理解预算的影响,我们引入了预算平稳分析的新概念。我们证明贪婪是每个预算分配的最佳办法,我们给最坏的子模块功能作了定性。基于这些结果,我们表明,在算法方面,根据现实的预算分配,贪婪和相关算法享有可被证实的更好近似保证,即使最坏的功能也存在,在硬性方面,存在对所有预算分配相当稳健的硬功能。

0
下载
关闭预览

相关内容

专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年11月7日
Arxiv
0+阅读 · 2021年11月5日
Arxiv
0+阅读 · 2021年11月4日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关资讯
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员