# New Convergence Aspects of Stochastic Gradient Algorithms

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

## Key facts

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

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

- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [On Almost Sure Convergence Rates of Stochastic Gradient Methods](https://mlsanity.com/paper/2202.04295/) (2022)
- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Scheduling and Aggregation Design for Asynchronous Federated Learning over Wireless Networks](https://mlsanity.com/paper/2212.07356/) (2022)
- [AsyncFedED: Asynchronous Federated Learning with Euclidean Distance based Adaptive Weight Aggregation](https://mlsanity.com/paper/2205.13797/) (2022)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information](https://mlsanity.com/paper/2109.05198/) (2021)
- [Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case](https://mlsanity.com/paper/2307.11782/) (2023)
- [Nesterov Accelerated Shuffling Gradient Method for Convex Optimization](https://mlsanity.com/paper/2202.03525/) (2022)
- [Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework](https://mlsanity.com/paper/2503.14353/) (2025)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Long-Short History of Gradients is All You Need: Detecting Malicious and Unreliable Clients in Federated Learning](https://mlsanity.com/paper/2208.10273/) (2022)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Almost sure convergence rates of stochastic gradient methods under gradient domination](https://mlsanity.com/paper/2405.13592/) (2024)
- [Finite-Sum Optimization: A New Perspective for Convergence to a Global Solution](https://mlsanity.com/paper/2202.03524/) (2022)
- [Learning from time-dependent streaming data with online stochastic algorithms](https://mlsanity.com/paper/2205.12549/) (2022)
- [On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithms](https://mlsanity.com/paper/2206.05869/) (2022)
- [Considerations on the Theory of Training Models with Differential Privacy](https://mlsanity.com/paper/2303.04676/) (2023)
- [AET-SGD: Asynchronous Event-triggered Stochastic Gradient Descent](https://mlsanity.com/paper/2112.13935/) (2021)
- [Generalizing DP-SGD with Shuffling and Batch Clipping](https://mlsanity.com/paper/2212.05796/) (2022)
- [Heterogeneity-Aware Client Sampling for Optimal and Efficient Federated Learning](https://mlsanity.com/paper/2505.11304/) (2025)
- [Stochastic Gradient Descent with Momentum is Algorithmically Stable](https://mlsanity.com/paper/2605.28517/) (2026)
- [Distributed Learning and its Application for Time-Series Prediction](https://mlsanity.com/paper/2106.03211/) (2021)
- [SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities](https://mlsanity.com/paper/2210.05994/) (2022)
- [Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes](https://mlsanity.com/paper/2507.07281/) (2025)
- [A Unified Convergence Analysis for Semi-Decentralized Learning: Sampled-to-Sampled vs. Sampled-to-All Communication](https://mlsanity.com/paper/2511.11560/) (2025)
- [Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds](https://mlsanity.com/paper/2604.10179/) (2026)
- [A Theoretical and Experimental Study of a Novel Adaptive Learning Algorithm](https://mlsanity.com/paper/2605.29273/) (2026)
- [Stochastic convergence of parallel asynchronous adaptive first-order methods](https://mlsanity.com/paper/2606.01787/) (2026)

## Abstract (arXiv)

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 violated for cases where the objective function is strongly convex. In Bottou et al. (2018), a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. 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. We then move on to the asynchronous parallel setting, and prove convergence of Hogwild! algorithm in the same regime in the case of diminished learning rate. It is well-known that SGD converges if a sequence of learning rates ηt satisfies sumt=0^∞ ηt rightarrow ∞ and sumt=0^∞ η2t < ∞. We show the convergence of SGD for strongly convex objective function without using bounded gradient assumption when ηt is a diminishing sequence and sumt=0^∞ ηt rightarrow ∞. In other words, we extend the current state-of-the-art class of learning rates satisfying the convergence of SGD.