Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
arXiv:1711.00987
Abstract
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.
arXiv commentAccepted to Mathematical Programming
References in corpus (5)
- Guaranteed Matrix Completion via Non-convex Factorization
- Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
- Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints