Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions
Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions
复制标题
DOI：
10.1137/19m1244925
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
N. Aybat;Alireza Fallah;M. Gürbüzbalaban;A. Ozdaglar
中科院分区：
文献类型：
--
作者：
N. Aybat;Alireza Fallah;M. Gürbüzbalaban;A. Ozdaglar
在设计一阶算法时，我们研究了收敛速度和对梯度误差的稳健性之间的权衡。我们重点研究了当梯度具有加性白噪声形式的随机误差时，最小化强凸函数的梯度下降(GD)和加速梯度(AG)方法。有了梯度误差，迭代的函数值不需要收敛到最优值；因此，我们将算法对噪声的稳健性定义为迭代序列对输入噪声功率的渐近期望次优性。对于这种稳健性度量，我们利用鲁棒控制理论的工具，给出了二次情形的精确表达式，并利用通过矩阵不等式证明的Lyapunov函数，给出了光滑强凸情形的严格上界。我们在优化问题中使用这些特征，该优化问题选择每个算法的参数以在速率和稳健性之间实现特定的折衷。我们的结果表明，AG可以实现加速，同时对随机梯度误差具有更强的鲁棒性。此行为与之前在确定性渐变噪波设置中报告的行为完全不同。我们还建立了算法的稳健性和当它受到确定性噪声干扰时，它能以多快的速度收敛到最优解之间的联系。我们的框架还导致了实用的算法，在存在随机梯度噪声的情况下，这些算法可以比其他最先进的方法执行得更好。
We study the trade-offs between convergence rate and robustness to gradient errors in designing a first-order algorithm. We focus on gradient descent (GD) and accelerated gradient (AG) methods for minimizing strongly convex functions when the gradient has random errors in the form of additive white noise. With gradient errors, the function values of the iterates need not converge to the optimal value; hence, we define the robustness of an algorithm to noise as the asymptotic expected suboptimality of the iterate sequence to input noise power. For this robustness measure, we provide exact expressions for the quadratic case using tools from robust control theory and tight upper bounds for the smooth strongly convex case using Lyapunov functions certified through matrix inequalities. We use these characterizations within an optimization problem which selects parameters of each algorithm to achieve a particular trade-off between rate and robustness. Our results show that AG can achieve acceleration while being more robust to random gradient errors. This behavior is quite different than previously reported in the deterministic gradient noise setting. We also establish some connections between the robustness of an algorithm and how quickly it can converge back to the optimal solution if it is perturbed from the optimal point with deterministic noise. Our framework also leads to practical algorithms that can perform better than other state-of-the-art methods in the presence of random gradient noise.