Overcoming the Full Batch Computational Bottleneck

220 concepts204 papers2 proposals

When optimizing machine learning models over large datasets, we traditionally face a harsh trade-off between stability and speed.

On one hand, deterministic Full Gradient Descent (GD) provides highly stable updates and excellent theoretical convergence rates (such as linear or exponential convergence). However, it requires computing the gradient across every single sample in the dataset before making a single parameter update. As noted by Jakub Konecný et al. in Semi-Stochastic Gradient Descent Methods, evaluating these full sums becomes computationally intractable when datasets scale into the millions.

On the other hand, Stochastic Gradient Descent (SGD) bypasses this bottleneck by estimating the gradient using a single randomly chosen data point or a small mini-batch. While the per-iteration cost of SGD is cheap and independent of the dataset size, the random sampling introduces massive variance. This noise causes the optimization trajectory to wander, forcing the algorithm to use decaying step sizes and resulting in a much slower, sublinear convergence rate.

The core research direction explored here focuses on breaking this bottleneck: How can we achieve the fast, stable convergence of full-batch optimization while maintaining the cheap per-iteration computational cost of stochastic methods?


Why the Full-Batch Bottleneck Suffocates Scale

The requirement to process an entire dataset simultaneously is a pervasive bottleneck that restricts scaling across diverse domains:

Historically, achieving high-precision solutions required full gradient information (Nicolas Le Roux in A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets). To scale further, we need a mechanism to systematically eliminate the noise of stochastic updates without paying the full-batch price.


The Core Mechanism: Predictive Variance Reduction

The landmark solution to this problem is Stochastic Variance Reduced Gradient (SVRG), introduced by Rie Johnson et al. in Accelerating Stochastic Gradient Descent using Predictive Variance Reduction.

SVRG operates in a clever dual-loop structure. At the start of an epoch, it takes a snapshot of the current parameters, denoted as an "anchor" point $\tilde{x}$, and computes the exact full gradient $\nabla F(\tilde{x})$ just once.

During the inner loop iterations, instead of updating the parameters using a standard noisy stochastic gradient $\nabla f_i(x)$, the algorithm uses a variance-corrected estimate:

$$\nabla_{\text{scaled}} = \nabla f_i(x) - \nabla f_i(\tilde{x}) + \nabla F(\tilde{x})$$

Why This Works Intuitively

To understand why this simple modification is so powerful, consider what happens as the optimization progresses and $x$ converges toward the anchor point $\tilde{x}$:

  1. The term $\nabla f_i(x)$ is the standard, noisy stochastic gradient for a random sample $i$.
  2. The term $\nabla f_i(\tilde{x})$ evaluates the gradient of that same sample $i$, but at the anchor point.
  3. As $x \to \tilde{x}$, the difference $[\nabla f_i(x) - \nabla f_i(\tilde{x})]$ explicitly approaches zero.

By subtracting $\nabla f_i(\tilde{x})$, we are using the anchor snapshot to cancel out the sample-specific variance of the current step. Adding back the full deterministic gradient $\nabla F(\tilde{x})$ ensures that the overall estimate remains unbiased.

This explicit variance reduction allows the algorithm to use a constant step size rather than a decaying one, yielding a fast linear convergence rate while keeping the per-step cost at $O(1)$. This framework is highly versatile; for instance, Zeyuan Allen Zhu et al. in Variance Reduction for Faster Non-Convex Optimization adapted this technique to prove that variance reduction theoretically outperforms standard GD even in complex, non-convex landscapes.


Bypassing the Periodic Full Pass

While SVRG drastically reduces the per-iteration cost, it still requires computing a full gradient at the beginning of every epoch to update the anchor. When datasets are exceptionally large, even this periodic full pass becomes a crippling computational bottleneck (Difan Zou et al. in Stochastic Variance-Reduced Hamilton Monte Carlo Methods).

To completely decouple optimization from the total number of data points, researchers developed two alternative strategies:

1. Subsampled Anchors

Instead of computing the anchor gradient over the entire dataset, we can estimate it using a large, smartly chosen subset. Lihua Lei et al. introduced this concept via Stochastically Controlled Stochastic Gradient (SCSG) in Less than a Single Pass: Stochastically Controlled Stochastic Gradient. By subsampling the anchor gradients, SCSG achieves high-accuracy solutions without ever needing to look at the entire dataset in a single pass.

2. Incremental Aggregation

Rather than performing periodic batch passes, we can maintain a running memory of individual component gradients and update only one component per step.


Generalizing Beyond Unconstrained Optimization

The push to eliminate the full-batch bottleneck has expanded into more complex optimization paradigms, including constrained optimization and Bayesian sampling.

Constrained Optimization and Projection-Free Methods

Standard projection-free algorithms, such as the Frank-Wolfe method, traditionally require iterating over an entire dataset to compute a single update step, creating a massive bottleneck for large-scale multi-class classification (Approximate Conditional Gradient Descent on Multi-Class Classification).

To resolve this, Aleksandr Beznosikov in Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features proposed stochastic variants that eliminate the requirement for expensive full gradient computations entirely. In a parallel effort, Robert M. Freund in Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization utilized Taylor-approximated gradients to dramatically reduce the algorithm's dependence on the total number of data points.

Scaling Bayesian Inference

The full-batch bottleneck is not unique to optimization; it also plagues Bayesian sampling. Calculating the true gradient of a target distribution across millions of data points makes standard Markov Chain Monte Carlo (MCMC) methods scale poorly.

By integrating subsampled variance reduction directly into Langevin dynamics, Difan Zou et al. in Subsampled Stochastic Variance-Reduced Gradient Langevin Dynamics demonstrated that sampling can achieve high accuracy on massive datasets without the prohibitive cost of full-batch processing.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_batch_optimization_scalability_a90cecbc,
  title = {batch optimization scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/batch-optimization-scalability/rdr_a90cecbc9adb4a35b4e8a7237fb362f9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_batch_optimization_scalability_a90cecbc_v1,
  title = {batch optimization scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/batch-optimization-scalability/rdr_a90cecbc9adb4a35b4e8a7237fb362f9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake