# Semi-Stochastic Gradient Descent Methods

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2013.

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

- [Physics-informed Dyna-Style Model-Based Deep Reinforcement Learning for Dynamic Control](https://mlsanity.com/paper/2108.00128/) (2021)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [Knowledge Distillation Performs Partial Variance Reduction](https://mlsanity.com/paper/2305.17581/) (2023)
- [Stochastic Gradient Methods with Preconditioned Updates](https://mlsanity.com/paper/2206.00285/) (2022)
- [Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients](https://mlsanity.com/paper/2404.14758/) (2024)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms](https://mlsanity.com/paper/2602.05304/) (2026)
- [Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction](https://mlsanity.com/paper/2605.08871/) (2026)
- [Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization](https://mlsanity.com/paper/2608.06563/) (2026)

## Abstract (arXiv)

In this paper we study the problem of minimizing the average of a large number (n) of smooth convex loss functions. We propose a new method, S2GD (Semi-Stochastic Gradient Descent), which runs for one or several epochs in each of which a single full gradient and a random number of stochastic gradients is computed, following a geometric law. The total work needed for the method to output an varepsilon-accurate solution in expectation, measured in the number of passes over data, or equivalently, in units equivalent to the computation of a single gradient of the loss, is O((kappa/n)log(1/varepsilon)), where kappa is the condition number. This is achieved by running the method for O(log(1/varepsilon)) epochs, with a single gradient evaluation and O(kappa) stochastic gradient evaluations in each. The SVRG method of Johnson and Zhang arises as a special case. If our method is limited to a single epoch only, it needs to evaluate at most O((kappa/varepsilon)log(1/varepsilon)) stochastic gradients. In contrast, SVRG requires O(kappa/varepsilon2) stochastic gradients. To illustrate our theoretical results, S2GD only needs the workload equivalent to about 2.1 full gradient evaluations to find an 10-6-accurate solution for a problem with n=109 and kappa=103.