# Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs

arXiv: https://arxiv.org/abs/1711.00987 · HTML: https://mlsanity.com/paper/1711.00987/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

## Built on by (most cited first, 10 of 10)

- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [DYNAFED: Tackling Client Data Heterogeneity with Global Dynamics](https://mlsanity.com/paper/2211.10878/) (2022)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024)
- [Convex Programs and Lyapunov Functions for Reinforcement Learning: A Unified Perspective on the Analysis of Value-Based Methods](https://mlsanity.com/paper/2202.06922/) (2022)
- [Regularization for Adversarial Robust Learning](https://mlsanity.com/paper/2408.09672/) (2024)
- [R'enyi Divergence Deep Mutual Learning](https://mlsanity.com/paper/2209.05732/) (2022)
- [Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms](https://mlsanity.com/paper/2209.11920/) (2022)
- [Exact Formulas for Finite-Time Estimation Errors of Decentralized Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2204.09801/) (2022)
- [Communication-Efficient Federated Learning over Wireless Channels via Gradient Sketching](https://mlsanity.com/paper/2410.23424/) (2024)

## Abstract (arXiv)

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.