Smoothed Analysis with Adaptive Adversaries
Smoothed Analysis with Adaptive Adversaries
复制标题
使用自适应对手进行平滑分析
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Abhishek Shetty
中科院分区：
文献类型：
--
作者：
Nika Haghtalab;Tim Roughgarden;Abhishek Shetty
我们证明了在平滑分析模型中为几个在线问题提供新颖的算法保证。在此模型中，在每个时间步骤中，对手选择一个输入分布，密度函数在上面的密度函数上以均匀分布的乘法因子为界。然后，大自然从此分布中取出输入。这在最坏情况的极端和平均病例分析之间进行了插值。至关重要的是，我们的结果适用于自适应对手，可以基于在算法的决策中选择输入分布以及以前时间步骤中输入的实现。自适应对手可以在不同的时间步骤中与算法的当前状态在不同的时间步骤中进行非试验的输入；这似乎排除了平滑分析中的标准证明方法。本文提出了一种通用技术，用于证明对适应性对手的平滑算法保证，实际上将自适应对手的设置减少到更简单的遗漏对手的情况下（即，对对手提前投入到整个输入分布序列） 。我们将此技术应用于三种不同的问题：在线学习，在线差异和在线优化中的分散方面，证明了强大的平滑保证。我们表明，在这些环境中，我们可以获得符合非自适应对手可以获得的界限的界限。
We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time step an adversary chooses an input distribution with density function bounded above pointwise by a multiplicative factor from the uniform distribution; nature then samples an input from this distribution. This interpolates between the extremes of worst-case and average case analysis. Crucially, our results hold for adaptive adversaries that can base their choice of an input distribution on the decisions of the algorithm and the realizations of the inputs in the previous time steps. An adaptive adversary can nontrivially correlate inputs at different time steps with each other and with the algorithm's current state; this appears to rule out the standard proof approaches in smoothed analysis. This paper presents a general technique for proving smoothed algorithmic guarantees against adaptive adversaries, in effect reducing the setting of an adaptive adversary to the much simpler case of an oblivious adversary (i.e., an adversary that commits in advance to the entire sequence of input distributions). We apply this technique to prove strong smoothed guarantees for three different problems: Online learning, Online discrepancy and Dispersion in online optimization. We show that in these setting, we can get bounds that match bounds we can get for non-adaptive adversaries.
登录
查看更多内容
DOI：
--
发表时间：
2017-03
期刊：
ArXiv
影响因子：
--
作者：
Pranjal Awasthi;Avrim Blum;Nika Haghtalab;Y. Mansour
通讯作者：
Pranjal Awasthi;Avrim Blum;Nika Haghtalab;Y. Mansour
通过解耦实现无监督学习的平滑分析
DOI：
10.1109/focs.2019.00043
发表时间：
2019
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Bhaskara, Aditya;Chen, Aidao;Perreault, Aidan;Vijayaraghavan, Aravindan
通讯作者：
Vijayaraghavan, Aravindan
在线和差异化私人学习的平滑分析
DOI：
--
发表时间：
2020
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Haghtalab, Nika;Roughgarden, Tim;Shetty, Abhishek
通讯作者：
Shetty, Abhishek
DOI：
--
发表时间：
2017-12
期刊：
ArXiv
影响因子：
--
作者：
Aravindan Vijayaraghavan;Abhratanu Dutta;Alex L. Wang
通讯作者：
Aravindan Vijayaraghavan;Abhratanu Dutta;Alex L. Wang