Analysis of biased stochastic gradient descent using sequential semidefinite programs
Analysis of biased stochastic gradient descent using sequential semidefinite programs
复制标题
DOI：
10.1007/s10107-020-01486-1
复制
发表时间：
2017-11
影响因子：
2.7
通讯作者：
Bin Hu;P. Seiler;Laurent Lessard
中科院分区：
文献类型：
--
作者：
Bin Hu;P. Seiler;Laurent Lessard
我们给出了有偏随机梯度下降(SGD)的收敛速度分析，其中个体梯度更新受到计算误差的破坏。我们发展了随机二次约束来建立一个小的线性矩阵不等式(LMI)，它的可行点导致有偏SGD的收敛界。基于这种LMI条件，我们开发了一种序列最小化方法来分析步长选择、收敛速度、优化精度和对梯度不精度的稳健性之间的复杂权衡。我们还给出了这种LMI的可行点，并得到了在不同损失函数假设下有偏SGD的收敛性质的理论公式。
We present a convergence rate analysis for biased stochastic gradient descent (SGD), where individual gradient updates are corrupted by computation errors. We develop stochastic quadratic constraints to formulate a small linear matrix inequality (LMI) whose feasible points lead to convergence bounds of biased SGD. Based on this LMI condition, we develop a sequential minimization approach to analyze the intricate trade-offs that couple stepsize selection, convergence rate, optimization accuracy, and robustness to gradient inaccuracy. We also provide feasible points for this LMI and obtain theoretical formulas that quantify the convergence properties of biased SGD under various assumptions on the loss functions.