Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity
Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
J. Zhang;Hongzhou Lin;Subhro Das;S. Sra;A. Jadbabaie
中科院分区：
文献类型：
--
作者：
J. Zhang;Hongzhou Lin;Subhro Das;S. Sra;A. Jadbabaie
研究了随机逼近问题中基于梯度方法的oracle复杂度。虽然在许多情况下，已知的最优算法和紧下界可以解决这类问题，但在实际应用中，这些最优算法并没有达到最佳性能。我们通过关注实例依赖的复杂性而不是最坏情况的复杂性来解决这个理论与实践之间的差距。特别是，我们首先总结了已知的依赖实例的复杂性结果，并将它们分为三个级别。我们确定了不同层次之间的支配关系，并提出了支配现有层次的第四个实例依赖界。然后，我们提供了一个充分的条件，根据该条件，具有矩估计的自适应算法可以在不知道噪声水平的情况下达到所提出的界。我们提出的算法及其分析为矩估计的成功提供了理论依据，因为它提高了实例复杂度。
We study oracle complexity of gradient based methods for stochastic approximation problems. Though in many settings optimal algorithms and tight lower bounds are known for such problems, these optimal algorithms do not achieve the best performance when used in practice. We address this theory-practice gap by focusing on instance-dependent complexity instead of worst case complexity. In particular, we first summarize known instance-dependent complexity results and categorize them into three levels. We identify the domination relation between different levels and propose a fourth instance-dependent bound that dominates existing ones. We then provide a suf-ficient condition according to which an adaptive algorithm with moment estimation can achieve the proposed bound without knowledge of noise levels. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation as it achieves improved instance complexity.