Analysis of biased stochastic gradient descent using sequential semidefinite programs
From MaRDI portal
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.
Recommendations
- scientific article; zbMATH DE number 7625177
- Asymptotic bias of stochastic gradient search
- Nonasymptotic Bounds for Stochastic Optimization With Biased Noisy Gradient Oracles
- scientific article; zbMATH DE number 1322672
- Strong error analysis for stochastic gradient descent optimization algorithms
- Convergence analysis of gradient descent stochastic algorithms
- Semi-stochastic coordinate descent
- Analysis of stochastic gradient descent in continuous time
- scientific article; zbMATH DE number 6936843
Cites work
- A Stochastic Approximation Method
- Analysis and design of optimization algorithms via integral quadratic constraints
- Convergence rate of incremental subgradient algorithms
- Convex optimization: algorithms and complexity
- Exact worst-case performance of first-order methods for composite convex optimization
- First-order methods of smooth convex optimization with inexact oracle
- Graph implementations for nonsmooth convex programs
- Guaranteed Matrix Completion via Non-Convex Factorization
- Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
- Large-scale machine learning with stochastic gradient descent
- Minimizing finite sums with the stochastic average gradient
- On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
- Optimization methods for large-scale machine learning
- Performance of first-order methods for smooth convex minimization: a novel approach
- Smooth Optimization with Approximate Gradient
- Smooth strongly convex interpolation and exact worst-case performance of first-order methods
- Stochastic dual coordinate ascent methods for regularized loss minimization
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
Cited in
(12)- Asymptotic bias of stochastic gradient search
- Analysis of optimization algorithms via sum-of-squares
- A frequency-domain analysis of inexact gradient methods
- Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition
- Cocoercivity, smoothness and bias in variance-reduced stochastic gradient methods
- scientific article; zbMATH DE number 2040718 (Why is no real title available?)
- scientific article; zbMATH DE number 7625177 (Why is no real title available?)
- scientific article; zbMATH DE number 7267112 (Why is no real title available?)
- Implicit regularization with strongly convex bias: Stability and acceleration
- Conditions for linear convergence of the gradient method for non-convex optimization
- Stochastic composition optimization of functions without Lipschitz continuous gradient
- Entropic risk-averse generalized momentum methods
This page was built for publication: Analysis of biased stochastic gradient descent using sequential semidefinite programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2020610)
