# Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2015.

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

- [AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation](https://mlsanity.com/paper/2204.13170/) (2022)
- [AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods](https://mlsanity.com/paper/2102.09700/) (2021)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications](https://mlsanity.com/paper/2303.01370/) (2023)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [A Unified Theory of Stochastic Proximal Point Methods without Smoothness](https://mlsanity.com/paper/2405.15941/) (2024)
- [Regularization by Denoising Sub-sampled Newton Method for Spectral CT Multi-Material Decomposition](https://mlsanity.com/paper/2103.13909/) (2021)
- [The Stochastic Proximal Distance Algorithm](https://mlsanity.com/paper/2210.12277/) (2022)
- [Error estimates between SGD with momentum and underdamped Langevin diffusion](https://mlsanity.com/paper/2410.17297/) (2024)
- [Stochastic Primal-Dual Three Operator Splitting Algorithm with Extension to Equivariant Regularization-by-Denoising](https://mlsanity.com/paper/2208.01631/) (2022)

## Abstract (arXiv)

We propose mS2GD: a method incorporating a mini-batching scheme for improving the theoretical complexity and practical performance of semi-stochastic gradient descent (S2GD). We consider the problem of minimizing a strongly convex function represented as the sum of an average of a large number of smooth convex functions, and a simple nonsmooth convex regularizer. Our method first performs a deterministic step (computation of the gradient of the objective function at the starting point), followed by a large number of stochastic steps. The process is repeated a few times with the last iterate becoming the new starting point. The novelty of our method is in introduction of mini-batching into the computation of stochastic steps. In each step, instead of choosing a single function, we sample b functions, compute their gradients, and compute the direction based on this. We analyze the complexity of the method and show that it benefits from two speedup effects. First, we prove that as long as b is below a certain threshold, we can reach any predefined accuracy with less overall work than without mini-batching. Second, our mini-batching scheme admits a simple parallel implementation, and hence is suitable for further acceleration by parallelization.