Performance of noisy Nesterov's accelerated method for strongly convex optimization problems
Performance of noisy Nesterov's accelerated method for strongly convex optimization problems
复制标题
DOI：
10.23919/acc.2019.8814680
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
Hesameddin Mohammadi;Meisam Razaviyayn;M. Jovanović
中科院分区：
文献类型：
--
作者：
Hesameddin Mohammadi;Meisam Razaviyayn;M. Jovanović
我们研究了噪声梯度下降和Nesterov的加速方法的性能与Lipschitz连续梯度的强凸目标函数。当梯度受均值为零协方差的加性白色噪声扰动时，分析了迭代误差的稳态二阶矩。对于任何给定的条件数$\kappa$，我们推导出显式上界噪声放大，只依赖于$\kappa$和问题的大小。我们使用二次目标函数来推导下界，并证明上界是紧的常数因子。Nesterov加速方法的上限比梯度下降的上限大$\sqrt{\kappa}$。这个差距确定了一个基本的权衡，在梯度评估中存在随机不确定性的情况下，加速。
We study the performance of noisy gradient descent and Nesterov's accelerated methods for strongly convex objective functions with Lipschitz continuous gradients. The steady-state second-order moment of the error in the iterates is analyzed when the gradient is perturbed by an additive white noise with zero mean and identity covariance. For any given condition number $\kappa$, we derive explicit upper bounds on noise amplification that only depend on $\kappa$ and the problem size. We use quadratic objective functions to derive lower bounds and to demonstrate that the upper bounds are tight up to a constant factor. The established upper bound for Nesterov's accelerated method is larger than the upper bound for gradient descent by a factor of $\sqrt{\kappa}$. This gap identifies a fundamental tradeoff that comes with acceleration in the presence of stochastic uncertainties in the gradient evaluation.