Analysis of biased stochastic gradient descent using sequential semidefinite programs

Bin Hu, Peter Seiler, Laurent Lessard

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)383-408
Number of pages26
JournalMathematical Programming
Issue number1-2
StatePublished - May 2021


  • Biased stochastic gradient
  • Convergence rates
  • Convex optimization
  • First-order methods
  • Robustness to inexact gradient

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Analysis of biased stochastic gradient descent using sequential semidefinite programs'. Together they form a unique fingerprint.

Cite this