🤖 machine learning

FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoo

This paper introduces FOAM, an adaptive damping method that dynamically adjusts the damping factor and eigendecomposition frequency based on staleness-oriented error to mitigate the numerical instability and performance degradation caused by stale preconditioner updates in the Shampoo optimizer, thereby reducing wall-clock training time while maintaining robust convergence.

Original authors: Kyunghun Nam, Sumyeong Ahn

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kyunghun Nam, Sumyeong Ahn

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: The "Stale Map" Problem

Imagine you are trying to navigate a massive, foggy mountain range (this is training a large AI model). To get to the bottom quickly, you need a map that shows you the steepness of the terrain so you know which way to step.

The Shampoo algorithm is a very smart navigator. It doesn't just look at the ground under your feet; it calculates a complex, 3D map of the entire mountain's shape (using something called "matrix inversion") to take the most efficient steps possible. This makes it incredibly fast at finding the bottom.

However, there's a catch: Calculating this perfect 3D map is like hiring a team of surveyors to climb every peak and measure every angle. It takes a huge amount of time and energy (computational power). If you do this every single step, your journey becomes painfully slow.

The Old Fix (Stale Shampoo): To save time, practitioners decided to stop updating the map so often. They would calculate the perfect map once, then use that same "stale" map for the next 30 or 50 steps.

The Good: It's much faster because you aren't constantly hiring surveyors.
The Bad: The mountain changes as you walk. The map gets "stale." Eventually, the map is so wrong that you might walk off a cliff (numerical instability) or wander in circles (slow convergence).

The Paper's Discovery: The "Shock Absorber"

The authors of this paper realized that the problem isn't just that the map is old; it's that using an old map creates a specific kind of error that makes the AI unstable.

They discovered a solution: Damping.
Think of damping as a shock absorber on a car.

If you drive over a bumpy road (using a stale map), a car without shock absorbers will bounce wildly and break.
A shock absorber (damping) smooths out the ride, allowing you to keep driving even on a bumpy road.

The Insight: You can use a stale map if you adjust the shock absorbers correctly. But here is the tricky part:

If the shock absorbers are too weak, the car crashes (instability).
If the shock absorbers are too strong, the car moves so slowly and stiffly that you never get anywhere (loss of learning efficiency).

The Solution: FOAM (The Smart Cruise Control)

The paper proposes a new method called FOAM (Frequency and Operator Error-Based Adaptive Damping Method).

Instead of using a fixed schedule (like "update the map every 30 steps") and a fixed shock absorber setting, FOAM acts like a smart cruise control system that constantly monitors the road.

Here is how it works in three simple steps:

The Sensor (Error Proxy): FOAM has a cheap, quick sensor that checks how "stale" the map has become. It doesn't need to hire the full survey team (which is expensive) to check this; it just looks at a few clues to estimate the error.
The Adjuster (Adaptive Damping):
- If the sensor says, "Hey, the map is getting very old and dangerous!", FOAM automatically tightens the shock absorbers (increases damping) to keep the car stable.
- If the sensor says, "The road is still smooth," FOAM loosens the shock absorbers (decreases damping) so the car can speed up and learn faster.
The Trigger (Smart Refresh):
- If the road gets too bumpy and the shock absorbers can't handle it anymore, FOAM knows it's time to hire the surveyors again. It triggers a full map update (Eigendecomposition) only when absolutely necessary.

Why This Matters

The paper shows that FOAM is better than the old "Stale Shampoo" method in two main ways:

It's Faster: Because it only updates the expensive map when the sensor says it's truly needed, it saves a massive amount of time (wall-clock time). In their tests, it reduced the time needed to train models on images (ViT) and speech (Conformer) significantly.
It's Safer: By constantly adjusting the damping, it prevents the AI from crashing into numerical instability, even when using old maps.

Summary Analogy

Old Way: You drive a car with a broken GPS. You check the map every 30 minutes. Sometimes you drive off a cliff because the map was too old. Sometimes you drive too slowly because you are scared to move.
FOAM Way: You have a car with a smart suspension system and a dashboard warning light.
- The dashboard checks the road conditions instantly.
- If the road is bumpy, the suspension stiffens automatically to keep you safe.
- If the road is smooth, the suspension softens so you can drive fast.
- You only stop to get a new map when the dashboard light turns red.

The Result: You get to your destination (the optimal AI model) faster and without crashing, using less fuel (computational resources).

Technical Summary: FOAM for Reducing Staleness-Oriented Error in Shampoo

1. Problem Statement

The Shampoo optimizer is recognized for its superior performance on large-scale optimization benchmarks due to its ability to capture within-layer parameter correlations via Kronecker-factored second-moment statistics. However, its practical application is hindered by a significant computational bottleneck: the prohibitive cost of computing the inverse $p$ -th roots of the Kronecker factors, which requires expensive eigendecompositions (EVD).

To mitigate this, practitioners typically employ stale Shampoo, where these expensive operations are performed at a fixed, infrequent interval rather than every iteration. While this improves computational efficiency, it introduces staleness—a delay in updating preconditioners. The paper identifies that staleness is not merely a convergence speed issue but a fundamental threat to training stability. Specifically, staleness-induced errors degrade numerical robustness and can lead to catastrophic training divergence. Existing heuristic strategies for choosing refresh frequencies lack theoretical justification and often fail to balance computational savings with the need for numerical stability.

2. Methodology: FOAM

The authors propose FOAM (Frequency and Operator Error-Based Adaptive Damping Method), an adaptive algorithm designed to stabilize training by dynamically controlling both the damping factor ( $\epsilon$ ) and the eigendecomposition frequency based on an approximation of the staleness-oriented error.

Theoretical Foundation

The work establishes a theoretical link between staleness, convergence, and stability:

Operator Gap: Staleness creates a discrepancy (operator gap) between the ideal fresh preconditioner and its stale counterpart. This gap is shown to be inversely proportional to the damping factor $\epsilon$ and directly proportional to the refresh period $f$ .
Regret Bound: Theoretical analysis of discounted regret reveals a trade-off: while increasing $\epsilon$ suppresses staleness-induced instability, an excessively large $\epsilon$ hides useful preconditioning information, degrading learning efficiency.
Damping as a Stabilizer: Damping acts as a critical numerical stabilizer. The paper demonstrates that $\epsilon$ must be meticulously calibrated to counteract the sensitivity of the inverse-root map, which becomes hypersensitive as $\epsilon \to 0$ .

Algorithmic Mechanism

FOAM operates via a feedback control loop that avoids unnecessary EVDs while maintaining stability. The update rule for the Kronecker factors involves three phases:

Sensing (Error Proxy): Instead of computing a fresh EVD to evaluate the true operator gap, FOAM uses a computationally cheap error proxy ( $h_t$ ). This proxy estimates the relative inverse-root operator gap using the stale eigenspaces and the current drift in statistics. It is derived from matrix perturbation theory and specifically targets the sensitivity of low-spectrum directions, which are most prone to amplification by the inverse-root map.
Adapting (Dynamic Damping): Based on the proxy $h_t$ $h_{t}$ , FOAM dynamically adjusts the damping factor $\epsilon_t$ $ϵ_{t}$ .
- If the estimated error exceeds a threshold $\tau$ , $\epsilon_t$ is increased multiplicatively to suppress the operator gap and restore stability.
- If the error is low, $\epsilon_t$ is relaxed toward a base value $\epsilon_0$ to preserve preconditioning strength.
Frequency Control (Triggered Refresh): A maximum damping limit ( $\epsilon_{\max}$ ) is enforced. As long as the required damping stays below this limit, FOAM reuses old statistics. However, if the error grows so large that the required damping would exceed $\epsilon_{\max}$ , FOAM triggers a full EVD refresh, resets $\epsilon$ to $\epsilon_0$ , and updates the preconditioner. This ensures expensive updates occur only when damping alone is insufficient to maintain stability.

3. Key Contributions

Theoretical Insight: The paper is the first to theoretically demonstrate that damping acts as a numerical stabilizer specifically to counteract the inherent negative effects of staleness in optimization. It establishes that staleness simultaneously hinders convergence speed and degrades numerical robustness.
Adaptive Algorithm (FOAM): The authors propose an algorithm that dynamically regulates the damping factor to enhance numerical stability. Unlike static heuristics, FOAM adaptively increases damping as staleness increases but precisely modulates these values to avoid the side effects of over-damping (loss of preconditioning information).
Error Proxy Construction: The work introduces a tractable error proxy derived from matrix perturbation theory that estimates the relative inverse-root operator gap without requiring full eigendecomposition, enabling real-time stability monitoring.

4. Experimental Results

The framework was validated on large-scale benchmarks across three modalities:

Vision: ImageNet-1K classification using a Vision Transformer (ViT-small).
Speech: Automatic Speech Recognition (ASR) on LibriSpeech using a Conformer architecture.
Language: Language modeling on Wikitext-103-v1 using GPT-2.

Key Findings:

Wall-Clock Efficiency: FOAM consistently achieves significant wall-clock speedups compared to standard stale Shampoo. In ViT experiments, the frequency of EVD calls was reduced by approximately 80–90% (dropping to ~10% for the left factor and ~5% for the right factor) while maintaining or improving convergence.
Convergence Quality: FOAM achieves lower training loss and higher validation accuracy (or lower Word Error Rate) in less time compared to stale baselines.
Robustness: The performance gains were consistent across a wide range of hyperparameter settings (refresh frequency $f$ , threshold $\tau$ , and damping bounds), demonstrating that the method is not dependent on a single tuned configuration.
Ablation Studies: Experiments confirmed that the synergy between adaptive damping and selective EVD refreshes is essential. Using only adaptive damping without refreshes led to high wall-clock times, while increasing the refresh interval without adaptive damping caused training loss to increase significantly due to unmitigated spectral drift.

5. Significance and Claims

The paper claims that FOAM bridges the gap between the superior optimization trajectories of Shampoo-style methods and the practical efficiency required for large-scale deep learning. By decoupling spectral sensing from costly refreshes through an error-driven feedback controller, FOAM resolves the computational bottleneck of preconditioned optimization.

The authors emphasize that their approach:

Improves Resource Efficiency: By accelerating convergence and reducing the frequency of expensive EVD operations, the method contributes to lower energy consumption and carbon footprints in training large models.
Enhances Training Reliability: By providing a theoretical foundation for managing curvature staleness through adaptive damping, the method mitigates the risk of catastrophic divergence during resource-intensive training runs, making sophisticated optimization techniques more accessible and stable.

The work concludes that FOAM successfully maintains robust convergence and numerical stability while significantly reducing the computational overhead associated with matrix inversion in Shampoo, offering a practical solution for scaling second-order-like optimization methods.