🤖 machine learning

HORST: Composing Optimizer Geometries for Sparse Transformer Training

The paper introduces HORST, a modular optimizer that composes non-commutative operator steps to combine the stability of adaptive methods with an $L_1$ sparsity bias via a hyperbolic mirror map, significantly outperforming AdamW in sparse transformer training across vision and language tasks.

Original authors: Tom Jacobs, Rohan Jain, Rebekka Burkholz

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tom Jacobs, Rohan Jain, Rebekka Burkholz

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 Problem: The "Heavy" AI

Imagine you have built a massive, incredibly smart robot (a Transformer). It can write stories, translate languages, and recognize images. However, this robot is so heavy and bulky that it requires a giant warehouse (huge memory) and a massive power plant (huge computing cost) just to run.

To make this robot practical, we want to trim the fat. We want to remove the unnecessary muscles and gears (weights) so it becomes lightweight and fast. This is called sparsification.

The problem is that when we try to trim this specific type of robot, it often falls apart. It loses its intelligence. Why? Because the "trainer" we use to teach the robot (the Optimizer) is accidentally teaching it to be too balanced.

The Two Trainers: The "Equalizer" vs. The "Selector"

The paper argues that the way we train these robots creates a hidden bias. Think of it like two different coaches teaching an athlete:

The "Equalizer" Coach (Standard Optimizers like AdamW):
- How they work: This coach believes that to be stable and safe, every muscle should be roughly the same size. If one muscle gets too big, the coach shrinks it; if another gets too small, the coach grows it.
- The Result: The robot ends up with a body where every part is slightly active. It's very stable, but it's heavy. There are no "zero" muscles. You can't easily cut anything out because everything is doing a little bit of work.
- The Paper's term: This is an $L_\infty$ bias (everything equalizes).
The "Selector" Coach (Mirror Descent / Sparsity Bias):
- How they work: This coach believes in specialization. They want the robot to pick a few super-strong muscles and turn the rest off completely. They force the robot to concentrate all its energy on a tiny few parts.
- The Result: The robot becomes very light and sparse. However, if you use only this coach, the robot might become unstable or crash during training because it's too aggressive.
- The Paper's term: This is an $L_1$ bias (concentrating mass).

The Conflict: Standard AI training uses the "Equalizer" because it's stable. But to make the AI small (sparse), we need the "Selector." You can't just swap coaches; the "Selector" is too risky for the complex robot, and the "Equalizer" won't let you cut the fat.

The Solution: The "Composed" Coach (HORST)

The authors, Tom Jacobs and his team, realized that you don't have to choose one coach. You can create a hybrid training routine that uses both, but in a very specific order.

They call their new method HORST (Hyperbolic Operator for Robust Sparse Training).

The Analogy: The Sculptor and the Chisel
Imagine you are sculpting a statue out of a giant block of marble (the neural network).

Step 1 (The Equalizer/Adam): First, you use a wide, flat tool to smooth out the rough edges and ensure the statue stands upright without wobbling. This keeps the structure stable.
Step 2 (The Selector/Hyperbolic Mirror): Immediately after smoothing, you use a sharp, precise chisel to carve away the excess stone, forcing the shape to become thin and sparse.

The Secret Sauce: The order matters!

If you chisel first and then smooth, the smoothing tool fills in the holes you just made. The sparsity disappears.
If you smooth first and then chisel, the chisel gets to work on the stable shape and successfully removes the extra weight.

The paper proves mathematically that this specific order (Stable Step $\rightarrow$ Sparsity Step) allows the robot to stay stable while becoming incredibly light.

What They Found (The Results)

The team tested this new "Composed Coach" (HORST) on two types of robots:

Vision Transformers: Robots that look at pictures (like identifying cats or cars).
Language Transformers: Robots that understand text (like the ones that write this summary).

The Outcome:

When they tried to cut 80% to 90% of the robot's weight (making it very sparse), the standard coach (AdamW) made the robot perform terribly. It forgot how to see or speak.
The HORST coach kept the robot performing almost as well as the full, heavy version, even after cutting away most of the weight.
In simple terms: HORST found a way to make the robot tiny without breaking its brain.

Summary

The paper solves a puzzle: "How do we make AI models small without making them dumb?"

Old way: Use a stable trainer, but it won't let you make the model small.
New way (HORST): Combine a stable trainer with a sparsity trainer in the right order.
Result: You get a lightweight, efficient AI that still works perfectly, even when you remove 90% of its parts.

The authors didn't invent a new way to cut the weights (like pruning); they invented a new way to train the model so that the weights naturally want to be cut, without the model falling apart in the process.

Technical Summary: HORST: Composing Optimizer Geometries for Sparse Transformer Training

Problem Statement

Sparsifying Transformer models remains a fundamental challenge. While network sparsification (removing redundant weights) offers a promising route to model compression and efficient inference, it consistently leads to significant performance degradation in Transformers, particularly at high sparsity levels where compression is most valuable. In contrast, convolutional networks sparsify more effectively.

The authors argue that this disparity stems from the implicit bias of the optimizers used during training. Standard Transformers rely on adaptive optimizers like AdamW, which exhibit an $L_\infty$ implicit bias. This bias favors stability by equalizing weight magnitudes across parameters, a geometry fundamentally at odds with the $L_1$ bias required for sparsity, which necessitates concentrating weight mass on a small subset of parameters while driving the rest to zero. Conversely, standard gradient descent (used in CNNs) induces an $L_2$ bias, and coordinate descent (an $L_1$ -based steepest descent) is theoretically ideal for sparsity but computationally infeasible for large deep networks.

Existing attempts to induce sparsity via mirror descent (e.g., using hyperbolic entropy) often fail in the Transformer setting because they directly replace the gradient, losing the stability provided by adaptive methods. The core problem is a geometric tension: the stability of adaptive optimizers ( $L_\infty$ ) conflicts with the sparsity requirements ( $L_1$ ).

Methodology

The paper proposes HORST (Hyperbolic Operator for Robust Sparse Training), a modular optimizer that resolves this tension by composing optimization steps as non-commutative functional operators.

1. Operator Composition Framework

The authors treat optimization updates as operators acting on parameter vectors and gradients. They identify two distinct classes of operators:

Steepest Descent Operators: Bounded and scale-invariant (e.g., Sign Descent, which approximates Adam). These provide stability but induce an $L_\infty$ bias.
Mirror Descent Operators: Linear but generally unbounded. Specific mirror maps, such as the hyperbolic entropy mirror map, induce an $L_1$ bias promoting sparsity.

2. Non-Commutativity and Order of Operations

A key theoretical insight is that these operator classes are non-commutative.

Applying a mirror step followed by a steepest step ( $S \circ M$ ) results in the steepest operator dominating, effectively nullifying the sparsity bias.
Applying a steepest step followed by a mirror step ( $M \circ S$ ) allows the mirror map to act on the sign-based update, successfully inheriting the stability of the steepest descent while inducing the $L_1$ sparsity bias.

3. The HORST Algorithm

HORST implements the composition $M_R \circ S$ in a discrete, practical setting:

Stable Update: It first performs a standard adaptive update (AdamW), which provides the necessary stability and $L_\infty$ -type regularization.
Sparsity Induction: It then applies an exponential update derived from the hyperbolic entropy mirror map. This step effectively reparameterizes the weights to favor sparsity.
Decoupled Regularization: The algorithm incorporates decoupled weight decay and an additional regularization term ( $\beta$ ) to further control the sparsity bias.

The update rule is defined as:
$\theta_{k+1/2} = \theta_k - \text{Adam}(g(\theta_k), \eta) - \eta \lambda \theta_k$
$\theta_{k+1} = \theta_{k+1/2} \exp\left( -\alpha \cdot \text{sign}(\theta_{k+1/2}) \cdot \text{Adam}(g(\theta_k), \eta) - \eta \beta \right)$
Here, $\alpha$ controls the relative strength of the sparsity bias. Setting $\alpha=0$ recovers standard AdamW.

Key Contributions

Geometric Dichotomy: The paper formalizes the structural dichotomy between steepest descent (bounded, stable, $L_\infty$ bias) and mirror descent (linear, unbounded, $L_1$ bias), illustrating why neither alone suffices for robust sparse Transformer training.
Operator Composition: It introduces the composition of optimizer operators as a design principle, proving that the order of composition is critical. The specific ordering ( $M \circ S$ ) allows the system to inherit stability from adaptive methods while overwriting their implicit bias with a sparsity-promoting $L_1$ bias.
Theoretical Guarantee: The authors prove (Theorem 4.7) that composing steepest descent (with respect to an $L_p$ norm, $p \ge 2$ ) with a hyperbolic entropy mirror map causes the iterates to converge in direction to the solution of an $L_1$ -minimization problem, effectively overwriting the $L_\infty$ bias of the base optimizer.
HORST Optimizer: They propose HORST, a modular optimizer that integrates seamlessly with standard adaptive methods (like AdamW) and requires no additional gradient evaluations, only a per-parameter exponential update.

Experimental Results

The authors evaluate HORST on vision and language tasks using the AC/DC (Alternating Compressed/Decompressed) sparsification pipeline.

Vision Transformers (DeiT): On ImageNet, HORST-AdamW consistently outperforms AdamW baselines across all sparsity levels (70%, 80%, 90%). The gains are most pronounced at high sparsity (80–90%), where AdamW performance degrades sharply. For example, at 90% sparsity on DeiT-base, HORST achieves 76.83% accuracy compared to 68.86% for AdamW.
Language Models (GPT-2 Small): In one-shot layerwise unstructured magnitude pruning on SlimPajama-6B, models trained with HORST-AdamW exhibit significantly lower validation perplexity after pruning compared to AdamW and the HAM optimizer. The gap widens at higher sparsity levels.
Comparison with HAM: HORST substantially outperforms HAM (a previous alternating optimizer) on DeiT-small at 90% sparsity (70.5% vs 60.06%). The authors attribute this to HORST's composition of the exponential update with the AdamW update itself, rather than applying a gradient-based exponential step as HAM does.
Weight Distribution: Visualizations confirm that HORST induces a weight distribution sharply concentrated around zero (indicating $L_1$ bias), whereas AdamW retains a broader, near-Gaussian profile.

Significance and Claims

The paper claims that the implicit bias of the optimizer is a primary bottleneck for sparse Transformer training. By treating optimization steps as composable operators, the authors demonstrate that it is possible to decouple the stability of adaptive methods from their geometric bias.

The significance of HORST lies in its ability to:

Enable high-sparsity training of Transformers without the severe performance degradation typically associated with such compression.
Provide a principled, modular framework for designing optimizers that can simultaneously satisfy conflicting geometric requirements (stability vs. sparsity).
Offer a practical solution that requires minimal computational overhead (no extra gradient evaluations) and integrates with existing sparse training pipelines.

The authors conclude that while the $L_\infty$ limit of steepest descent and its interaction with mirror updates remains an open theoretical question, the proposed framework successfully bridges the gap between adaptive training stability and sparse solution geometry.