# SGD and Hogwild! Convergence Without the Bounded Gradients Assumption

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

## Key facts

- Cited by 95 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2018.

## Built on by (most cited first, 30 of 95)

- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [FedAvg with Fine Tuning: Local Updates Lead to Representation Learning](https://mlsanity.com/paper/2205.13692/) (2022)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Compressed-VFL: Communication-Efficient Learning with Vertically Partitioned Data](https://mlsanity.com/paper/2206.08330/) (2022)
- [Instrumental Variable Value Iteration for Causal Offline Reinforcement Learning](https://mlsanity.com/paper/2102.09907/) (2021)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [FedDR -- Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization](https://mlsanity.com/paper/2103.03452/) (2021)
- [On the Convergence of Black-Box Variational Inference](https://mlsanity.com/paper/2305.15349/) (2023)
- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Persia: An Open, Hybrid System Scaling Deep Learning-based Recommenders up to 100 Trillion Parameters](https://mlsanity.com/paper/2111.05897/) (2021)
- [A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updates](https://mlsanity.com/paper/2206.10189/) (2022)
- [Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information](https://mlsanity.com/paper/2109.05198/) (2021)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [A Bregman Learning Framework for Sparse Neural Networks](https://mlsanity.com/paper/2105.04319/) (2021)
- [Green, Quantized Federated Learning over Wireless Networks: An Energy-Efficient Design](https://mlsanity.com/paper/2207.09387/) (2022)
- [BAGUA: Scaling up Distributed Learning with System Relaxations](https://mlsanity.com/paper/2107.01499/) (2021)
- [Federated Learning with Bilateral Curation for Partially Class-Disjoint Data](https://mlsanity.com/paper/2405.18972/) (2024)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [On the Tradeoff between Energy, Precision, and Accuracy in Federated Quantized Neural Networks](https://mlsanity.com/paper/2111.07911/) (2021)
- [Nesterov Accelerated Shuffling Gradient Method for Convex Optimization](https://mlsanity.com/paper/2202.03525/) (2022)
- [FADAS: Towards Federated Adaptive Asynchronous Optimization](https://mlsanity.com/paper/2407.18365/) (2024)
- [Acceleration of stochastic gradient descent with momentum by averaging: finite-sample rates and asymptotic normality](https://mlsanity.com/paper/2305.17665/) (2023)
- [A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD](https://mlsanity.com/paper/2410.04458/) (2024)
- [Training Federated GANs with Theoretical Guarantees: A Universal Aggregation Approach](https://mlsanity.com/paper/2102.04655/) (2021)
- [Communication-Efficient Distributed Optimization with Quantized Preconditioners](https://mlsanity.com/paper/2102.07214/) (2021)

## Abstract (arXiv)

Stochastic gradient descent (SGD) is the optimization algorithm of choice in many machine learning applications such as regularized empirical risk minimization and training deep neural networks. The classical convergence analysis of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is always violated for cases where the objective function is strongly convex. In (Bottou et al.,2016), a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. Here we show that for stochastic problems arising in machine learning such bound always holds; and we also propose an alternative convergence analysis of SGD with diminishing learning rate regime, which results in more relaxed conditions than those in (Bottou et al.,2016). We then move on the asynchronous parallel setting, and prove convergence of Hogwild! algorithm in the same regime, obtaining the first convergence results for this method in the case of diminished learning rate.