研究加速梯度方法在梯度误差下的鲁棒性,给出收敛与抗错的权衡关系。
Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds
- 用风险敏感指标量化梯度误差对算法的影响
- 首次获得带偏置梯度的非渐近高概率保证
- 揭示收敛速度与鲁棒性的帕累托前沿,适合优化鲁棒性研究者
我们研究一阶优化方法中收敛速度与梯度误差鲁棒性之间的权衡。聚焦广义动量方法(GMMs),包括Nesterov加速梯度、Heavy-ball和梯度下降法,用于最小化光滑强凸目标函数。允许存在对抗性且有偏的随机梯度误差,并通过鲁棒控制中的风险敏感指数(RSI)量化其对算法的鲁棒性影响。对于具有i.i.d.高斯噪声的二次目标,我们推导出RSI的闭式表达,基于2×2矩阵Riccati方程,揭示了步长与动量参数选择下RSI与收敛率间的帕累托前沿。进一步证明了时间平均次优性在大迭代极限下的大偏差原理,其速率函数为RSI函数的凸共轭(缩放后)。我们还发现该速率函数与$H_\infty$-范数相关,表明更强的最坏情况鲁棒性(更小的$H_\infty$-范数)对应平均次优性的尾概率衰减更快。在非二次情况下,面对可能有偏的次高斯梯度误差,我们推导出有限时间的RSI类边界,从而得到非渐近高概率保证和大偏差界。对于光滑强凸函数,也观察到类似的风险敏感性与收敛率的权衡。据我们所知,这是首个针对带偏置梯度的GMMs的非渐近分析,也是首个对GMMs的风险敏感性分析。最后通过一个鲁棒回归问题的数值实验验证了结果。
原文摘要 · Abstract (English)
We study trade-offs between convergence rate and robustness to gradient errors in the context of first-order methods. Our focus is on generalized momentum methods (GMMs)--a broad class that includes Nesterov's accelerated gradient, heavy-ball, and gradient descent methods--for minimizing smooth strongly convex objectives. We allow stochastic gradient errors that may be adversarial and biased, and quantify robustness of these methods to gradient errors via the risk-sensitive index (RSI) from robust control theory. For quadratic objectives with i.i.d. Gaussian noise, we give closed form expressions for RSI in terms of solutions to 2x2 matrix Riccati equations, revealing a Pareto frontier between RSI and convergence rate over the choice of step-size and momentum parameters. We then prove a large-deviation principle for time-averaged suboptimality in the large iteration limit and show that the rate function is, up to a scaling, the convex conjugate of the RSI function. We further show that the rate function and RSI are linked to the $H_\infty$-norm--a measure of robustness to the worst-case deterministic gradient errors--so that stronger worst-case robustness (smaller $H_\infty$-norm) leads to sharper decay of the tail probabilities for the average suboptimality. Beyond quadratics, under potentially biased sub-Gaussian gradient errors, we derive non-asymptotic bounds on a finite-time analogue of the RSI, yielding finite-time high-probability guarantees and non-asymptotic large-deviation bounds for the averaged iterates. In the case of smooth strongly convex functions, we also observe an analogous trade-off between RSI and convergence-rate bounds. To our knowledge, these are the first non-asymptotic guarantees for GMMs with biased gradients and the first risk-sensitive analysis of GMMs. Finally, we provide numerical experiments on a robust regression problem to illustrate our results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。