🤖 machine learning

SVRG and Beyond via Posterior Correction

This paper establishes the first fundamental connection between Stochastic Variance Reduced Gradient (SVRG) and Bayesian posterior correction, demonstrating that SVRG is a special case of this framework and leveraging it to derive novel, more flexible extensions like Newton-like and Adam-like variants.

Original authors: Nico Daheim, Thomas Möllenhoff, Ming Liang Ang, Mohammad Emtiyaz Khan

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nico Daheim, Thomas Möllenhoff, Ming Liang Ang, Mohammad Emtiyaz Khan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Fixing a Noisy Compass

Imagine you are trying to find the lowest point in a vast, foggy valley (this represents training an AI model to make fewer mistakes). You have a compass that tells you which way is "down," but the compass is very shaky and unreliable. This is how standard AI training works: it looks at just a tiny slice of data at a time, so the direction it gets is often "noisy" or wrong.

For over a decade, researchers have used a trick called SVRG (Stochastic Variance Reduced Gradient) to fix this. SVRG is like a smart navigator who occasionally stops, climbs a hill to get a clear, wide-angle view of the whole valley (a "full-batch" calculation), and then uses that clear view to steady the shaky compass for the next few steps. This makes the journey faster and more stable.

However, until now, nobody knew why this trick worked from a "Bayesian" (probabilistic) perspective. It was just a clever math hack.

The Paper's Discovery:
The authors found a surprising connection. They discovered that SVRG is actually a special case of a newer, more general method called Posterior Correction (PoCo).

The Analogy: Think of "Posterior Correction" as a way to update your knowledge. You have an old map (old knowledge) and a new observation. Instead of just throwing away the old map, you blend it with the new observation to create a better, corrected map.
The Breakthrough: The authors realized that the "shaky compass" correction used in SVRG is exactly the same math as "correcting" an old map with new data. This connects two previously unrelated worlds: fast optimization (SVRG) and Bayesian knowledge updating.

What They Did With This Discovery

Once they realized SVRG was just a specific type of "map correction," they asked: "If we use different types of maps, can we build even better navigators?"

They tried using more complex "maps" (mathematical distributions) instead of the simple ones SVRG usually uses. This led to two new, powerful tools:

1. The "Newton-Like" Navigator (VON-PoCo)

The Problem: Standard SVRG only corrects the direction (the gradient). It's like knowing which way is down, but not knowing how steep the slope is.
The Solution: By using a more complex "map" (a full Gaussian distribution), their new method corrects both the direction and the steepness (the Hessian).
The Analogy: Imagine you are skiing. Standard SVRG tells you which way to turn. The new Newton-like method also tells you how sharp the turn needs to be based on how steep the hill is. This allows for much more precise and efficient movement down the mountain.

2. The "Adam-Like" Navigator for Giants (IVON-PoCo)

The Problem: The "Newton-like" method is too heavy and slow for massive AI models (like those used for deep learning) because it requires too much memory to store the "steepness" of every single path.
The Solution: They created a simplified version that only tracks the steepness of individual paths (diagonal covariance), similar to how the popular Adam optimizer works.
The Analogy: This is like giving a giant cargo ship a navigation system. You can't calculate the exact wave height for every single drop of water (too heavy), so you calculate the average wave height for the ship's hull. It's lighter, faster, and scales up to massive problems like training large language models.

What the Experiments Showed

The authors tested these new methods on various tasks:

Simple Tasks (Logistic Regression): On standard, smaller problems, the new methods worked beautifully. They were significantly faster and more accurate than the old methods, just like SVRG is faster than standard training.
Deep Learning (Image Classification & Language Models): When they tried these methods on huge models (like GPT-2 or ResNets for image recognition), the results were mixed.
- The Good News: The new methods did improve the final accuracy of the models.
- The Catch: They didn't necessarily make the training faster in terms of real-world time. Because these methods require extra calculations (like checking the "steepness" or running "mega-batches"), they sometimes took just as long, or even longer, to finish than standard methods, even if they reached a better destination.

The Bottom Line

This paper is a "Rosetta Stone" moment. It translates a decades-old optimization trick (SVRG) into the language of Bayesian probability (Posterior Correction).

Why it matters: It proves that SVRG is a form of "knowledge transfer" (using old data to stabilize new data).
The Result: This insight allowed the authors to invent new, smarter algorithms that correct not just direction, but also the "shape" of the problem. While these new tools are very promising for smaller, precise tasks, the paper admits that for the massive AI models of today, they don't yet offer a "free lunch" in terms of speed, though they do improve the final quality of the model.

In short: They found the secret recipe behind a famous cooking technique, and used that recipe to invent two new, more sophisticated dishes. One is a gourmet meal for small kitchens, and the other is a massive feast for industrial kitchens that tastes better but takes just as long to cook.

Technical Summary: SVRG and Beyond via Posterior Correction

Problem Statement

Stochastic Variance Reduced Gradient (SVRG) and its variants are established techniques for accelerating stochastic optimization by utilizing full-batch gradients to stabilize mini-batch updates. Despite over a decade of research and numerous practical variants (e.g., SAGA, SARAH, Spider), these methods have never been fundamentally connected to Bayesian inference. While variance reduction has been applied to speed up Bayesian procedures (e.g., stochastic variational inference), a deeper theoretical link explaining SVRG through Bayesian principles, or using Bayesian methods to derive new SVRG extensions, has been absent. Furthermore, existing Newton-style SVRG variants typically correct only the gradient, neglecting Hessian corrections, and standard SVRG struggles to provide speed-ups in deep learning settings compared to convex problems.

Methodology

The authors bridge this gap by deriving SVRG as a special case of Posterior Correction (PoCo), a recently proposed Bayesian method for knowledge adaptation (Khan, 2025).

Theoretical Foundation

Bayesian Learning Rule (BLR) & Natural Gradients: The work utilizes the BLR, which unifies learning algorithms by optimizing over distributions $q(\theta)$ in the exponential family using natural gradients. The update rule in the natural parameter space $\lambda$ is given by:
$\lambda \leftarrow (1-\eta)\lambda - \eta \sum_{i=0}^N \tilde{\nabla} L_i(\lambda)$
where $\tilde{\nabla}$ denotes the natural gradient.
Posterior Correction (PoCo): PoCo generalizes the BLR by introducing an older posterior estimate $\hat{q}_{out}$ (derived from an older parameter $\lambda_{out}$ ) to correct future updates. The update rule becomes:
$q_{in} \leftarrow q_{in}^{1-\eta} \hat{q}_{out}^{\eta} \exp\left( -\eta N [\hat{\ell}_{i|in} - \hat{\ell}_{i|out}] \right)$
Here, $\hat{\ell}$ represents linear surrogate loss functions. This formulation effectively treats gradient corrections as a mechanism for transferring knowledge between old and new gradients.
Deriving SVRG from PoCo:
- By restricting the posterior $q$ to an isotropic Gaussian $N(\theta | m, I)$ and applying the delta method approximation ( $\mathbb{E}_q[\nabla \ell] \approx \nabla \ell(m)$ ), the PoCo update reduces exactly to the standard SVRG update rule.
- This establishes SVRG as a special case of Bayesian posterior correction where the "knowledge" is the mean of an isotropic Gaussian.
Novel Extensions via Flexible Posteriors:
The framework allows for deriving new algorithms by choosing different exponential-family posteriors:
- Newton-like Variant (VON-PoCo): By using full multivariate Gaussians $N(\theta | m, S^{-1})$ , the method naturally derives corrections for both the mean and the precision matrix (inverse covariance). This results in a Stochastic Variance-Reduced Hessian (SVRH) estimate, correcting the Hessian in addition to the gradient. This differs from prior Newton-SVRG works that only correct gradients.
- Adam-like Variant (IVON-PoCo): By using diagonal Gaussians, the authors derive a variance-reduced version of the Improved Variational Online Newton (IVON) optimizer. This variant, named IVON-PoCo (and its momentum version IVON-PoCoMo), scales to large problems. It utilizes "mega-batches" (large subsets of data) to estimate full-batch statistics, employing a down-weighting factor $\alpha$ to handle the deviation from strict full-batch assumptions.

Key Contributions

Theoretical Unification: The paper provides the first fundamental connection between SVRG and Bayesian methods, showing SVRG is a special case of Posterior Correction over isotropic Gaussians. This reframes gradient corrections as a knowledge-transfer mechanism.
Novel Algorithm Derivations:
- VON-PoCo: A Newton-style SVRG variant that automatically incorporates Hessian corrections, a feature not present in existing Newton-SVRG literature.
- IVON-PoCo: An Adam-like, scalable extension that applies variance reduction to the IVON optimizer, suitable for deep learning.
Empirical Evaluation: The authors evaluate these methods on logistic regression, image classification (ResNets on CIFAR-10 and ImageNet), and language model pretraining (GPT-2).

Results

Convex Problems (Logistic Regression): On datasets like MNIST, Covertype, and CIFAR-10, both VSGD-PoCo (first-order) and IVON-PoCo (second-order) significantly outperform their non-corrected counterparts (VSGD and IVON). They achieve accuracy comparable to full-batch L-BFGS with fewer gradient evaluations, mirroring the speed-up SVRG provides to SGD.
Deep Learning (ImageNet & GPT-2):
- On ImageNet (ResNet-50), IVON-PoCo shows clear improvements in test accuracy when measured by optimization steps, though gains diminish when measured by total data examples seen (consistent with previous findings on SVRG in deep learning).
- On GPT-2 (125M) pretraining, IVON-PoCoMo improves final validation perplexity compared to AdamW and standard IVON. However, the authors note that these improvements do not translate into tangible speed-ups in wall-clock time or gradient computation efficiency compared to simply increasing the batch size or using standard optimizers.
- The results align with Defazio & Bottou (2019), suggesting variance reduction methods currently face challenges in providing runtime speed-ups for deep learning compared to convex settings.

Significance and Claims

The paper claims to lay a foundation for future work by connecting SVRG to Bayesian principles.

New Perspective: It offers a novel interpretation of SVRG as a knowledge-adaptation method, generalizing it through the lens of Posterior Correction.
Algorithmic Innovation: It demonstrates that Bayesian principles can automatically generate complex extensions (like Hessian corrections) that are difficult to derive via standard SVRG heuristics.
Modest Claims on Deep Learning: The authors are explicit that while their methods improve final model performance (accuracy/perplexity) on deep learning tasks, they do not yet provide the same computational speed-ups observed in convex problems. They view this work as a step toward potentially improving the effectiveness of variance reduction for deep learning in the future, rather than an immediate solution to the runtime inefficiencies observed in current deep learning training.