论文标题
除了最糟糕的分析随机近似外：力矩估计提高了实例复杂性
Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity
论文作者
论文摘要
我们研究基于梯度的随机近似问题的甲骨文复杂性。尽管在许多设置中，最佳算法和紧密的下限以这些问题而闻名，但在实践中使用时，这些最佳算法并不能达到最佳性能。我们通过关注与实例有关的复杂性而不是最坏情况的复杂性来解决这个理论实践差距。特别是，我们首先总结了已知的实例依赖性复杂性结果，并将它们分为三个级别。我们确定不同级别之间的统治关系，并提出了一个依赖实例的第四个实例依赖性界限。然后，我们提供了足够的条件，根据该条件，具有时刻估计的自适应算法可以在不知道噪声水平的情况下达到拟议的结合。我们提出的算法及其分析为矩估计的成功提供了理论上的理由，因为它可以提高实例复杂性。
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 sufficient 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.
