Research map / Optimization / Optimizers
Demystifying SGD with Doubly Stochastic Gradients
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Establishes convergence of SGD with doubly stochastic gradients (subsampling over components plus Monte Carlo estimates of each component), including dependent (shared-randomness) estimators and random reshuffling, and derives a variance bound showing how correlation affects the m-vs-b budget trade-off.
Problem
Doubly stochastic gradient SGD for finite sums of intractable expectations ("finite sum with infinite data") lacks convergence guarantees under realistic assumptions, especially when Monte Carlo samples are shared (dependent) across minibatch components.
Approach
Derives a general variance bound for subsampled averages of correlated unbiased estimators, parameterized by a correlation constant rho, and uses expected-residual and bounded-variance conditions to prove convergence of doubly SGD and doubly SGD with random reshuffling under weaker assumptions than uniform smoothness or bounded variance.
Key results
- General variance bound for doubly stochastic estimators: O((1/n)sum sigma_i^2/(mb) + rho((1/n)sum sigma_i)^2/m + tau^2/b), showing increasing b is preferable to increasing m for fixed budget.
- Random reshuffling improves strongly convex iteration complexity from O(sigma_mc^2/eps + sigma_sub^2/eps) to O(sigma_mc^2/eps + sigma_sub/sqrt(eps)).
- For dependent estimators under random reshuffling, doubly SGD-RR achieves an n/b tighter asymptotic sample complexity than full-batch SGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use random reshuffling instead of independent subsampling | Doubly SGD · Strongly convex objectives | iteration complexity dependence on subsampling noise: \mathcal{O}\left( \frac{1}{\epsilon} \sigma^2_{\mathrm{sub}} \right) -> \mathcal{O}\left( \frac{1}{\sqrt{\epsilon}} \sig | Helped |
| Increase batch size b rather than Monte Carlo sample count m at fixed budget m × b | Doubly SGD with dependent gradient estimators · Dependent gradient estimators; fixed budget m × b | gradient variance: \mathcal{O}\left(\nicefrac{1}{m b}\right) | Helped |
| Increase batch size b | Doubly SGD with independent gradient estimators · Independent gradient estimators | gradient variance: \mathcal{O}(1/b) | Helped |
| Increase Monte Carlo sample count m | Doubly SGD with independent gradient estimators · Independent gradient estimators | gradient variance | No clear effect |
| Use random reshuffling instead of independent subsampling | Doubly SGD with dependent gradient estimators · Strongly convex objectives; dependent gradient estimators | asymptotic sample complexity versus full-batch SGD: n/b tighter | Helped |
Surprising findings
- Reducing subsampling variance also reduces Monte Carlo variance when estimators are dependent, so increasing b is always preferred over increasing m for a fixed budget m x b.
Limitations
- Results are for strongly convex / smooth settings with theoretical analysis; no large-scale experiments reported in the excerpt.
- Some analyses rely on assumptions like bounded variance on the solution set and stationarity of the minimizer.
Experimental setup
Metrics: iteration complexity variance bound
Baselines: doubly SGD with independent minibatching full-batch SGD
Builds on: expected smoothness SGD with random reshuffling black-box variational inference random features doubly SGD
Closest papers by meaning
- SGD: General Analysis and Improved Rates (ICML 2019 · similarity 0.90)
- Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD (NeurIPS 2021 · similarity 0.89)
- Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite Sum Structure (NeurIPS 2017 · similarity 0.89)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.89)
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.88)
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.