论文标题
随机近似中的指数浓度
Exponential Concentration in Stochastic Approximation
论文作者
论文摘要
我们分析了随机近似算法的行为，在预期的情况下，迭代在每个步骤中朝着一个目标发展。当进度与算法的步长成正比时，我们证明了指数浓度界限。这些尾巴结合的对比渐近差异结果，它们与随机近似更常见。我们开发的方法依赖于几何形状的证明。这将由于Hajek（1982）引起的马尔可夫连锁店的结果扩展到了随机近似算法的区域。我们将结果应用于几种不同的随机近似算法，特别是投射的随机梯度下降，kiefer-Wolfowitz和随机的Frank-Wolfe算法。如果适用，我们的结果证明，预计随机梯度下降的$ O（1/T）$和线性收敛速率具有非呈梯度。
We analyze the behavior of stochastic approximation algorithms where iterates, in expectation, progress towards an objective at each step. When progress is proportional to the step size of the algorithm, we prove exponential concentration bounds. These tail-bounds contrast asymptotic normality results, which are more frequently associated with stochastic approximation. The methods that we develop rely on a geometric ergodicity proof. This extends a result on Markov chains due to Hajek (1982) to the area of stochastic approximation algorithms. We apply our results to several different Stochastic Approximation algorithms, specifically Projected Stochastic Gradient Descent, Kiefer-Wolfowitz and Stochastic Frank-Wolfe algorithms. When applicable, our results prove faster $O(1/t)$ and linear convergence rates for Projected Stochastic Gradient Descent with a non-vanishing gradient.
