🔢 mathematics

Sparse Training of Neural Networks based on Multilevel Mirror Descent

This paper introduces a dynamic sparse training algorithm based on multilevel mirror descent that alternates between static and dynamic sparsity updates to achieve highly accurate, sparse models with significantly reduced computational costs and training time compared to standard methods.

Original authors: Yannick Lunk, Sebastian J. Scott, Leon Bungert

Published 2026-05-19

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Yannick Lunk, Sebastian J. Scott, Leon Bungert

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: Too Much Clutter

Imagine you are trying to solve a massive jigsaw puzzle, but you have a box containing 10,000 pieces, and you only need about 100 of them to finish the picture. Currently, most AI training methods are like a person who grabs the whole box, tries to fit every single piece together, and then, after hours of work, realizes they only needed a few. This wastes a huge amount of energy (computing power) and time.

In the world of AI, these "pieces" are the connections between neurons in a neural network. The paper argues that we should stop trying to train every single connection and instead focus only on the ones that actually matter.

The Solution: A Smart "Freeze and Thaw" Strategy

The authors propose a new training algorithm called Multilevel LinBreg. To understand how it works, imagine you are a sculptor carving a statue out of a giant block of marble.

The Old Way (Standard Training): You chip away at the whole block constantly, checking every inch, even the parts you know are just going to be thrown away.
The Paper's Way (Multilevel LinBreg): You use a special technique that alternates between two phases:
- Phase 1: The "Thaw" (Exploration): You gently chip away at the marble, allowing new shapes to emerge. This is where the algorithm looks for good connections.
- Phase 2: The "Freeze" (Exploitation): Once a part of the statue looks promising, you put a "freeze" on it. You stop chipping at the empty space around it and only work on the parts that are already taking shape.

The Magic Trick: The algorithm uses a mathematical tool called Linearized Bregman Iterations (think of this as a very smart chisel). This chisel naturally creates "empty space" (sparsity) as it works. The authors' innovation is to periodically freeze the structure of the network. When the network is frozen, the computer ignores all the "empty" connections and only calculates the math for the "active" ones.

Why This is a Big Deal

The paper highlights three main benefits, using some fun comparisons:

Saving Energy (FLOPs): The authors claim their method is incredibly efficient. They say that compared to standard training, their method reduces the theoretical number of calculations (FLOPs) needed from about 38% down to just 6%.
- Analogy: If standard training is like driving a car with the engine running at full speed but in neutral, this new method is like shifting into a high gear where the engine only works when you actually press the gas pedal.
Saving Time: Because the computer does less math, it finishes the job faster. On a standard computer processor (CPU), they saw a 50% reduction in training time.
Better Results: Usually, when you make a model smaller (sparser), it gets dumber. However, this method manages to keep the model smart. In their tests on image recognition (identifying cats, dogs, cars, etc.), their sparse models were just as accurate as the big, heavy ones, and sometimes even better.

How They Proved It Works

The authors didn't just guess; they built a mathematical "safety net" around their method.

They placed their algorithm inside a Multilevel Optimization Framework. Think of this as a two-story building.
- The Ground Floor (Coarse Level): This is where the "frozen" work happens. The computer looks at a simplified version of the problem, focusing only on the active connections.
- The Second Floor (Fine Level): Every so often, the computer goes upstairs to check the whole building, ensuring the simplified work on the ground floor is still leading to the right destination.
They proved mathematically that if you keep switching between these floors, you will eventually reach the best possible solution (convergence).

The Results in the Lab

The team tested this on standard image datasets (like CIFAR-10 and TinyImageNet), which are like the "training wheels" for AI vision.

They trained networks to be 90% to 97% sparse (meaning 90-97% of the connections were zero/empty).
Despite being so empty, the networks still recognized images with high accuracy.
They compared their method to other popular "sparse training" techniques (like "RigL" or "Pruning") and found their method produced sparser models without losing accuracy.

Summary

In short, this paper introduces a smarter way to train AI. Instead of brute-forcing the math on every single connection, it uses a "freeze-and-thaw" rhythm to focus only on the connections that are doing the work. This makes training faster, cheaper, and more energy-efficient, while still producing highly accurate AI models.

Technical Summary: Sparse Training of Neural Networks based on Multilevel Mirror Descent

Problem Statement

Deep neural networks have achieved remarkable success in fields like computer vision and natural language processing but impose significant demands on memory and specialized hardware, raising concerns regarding their environmental impact and carbon footprint. While techniques such as pruning (removing connections from a pre-trained dense model) and sparse training (encouraging sparsity during training) exist, they face distinct challenges. Pruning often requires retraining and can suffer from performance drops. Existing sparse training methods, such as those based on linearized Bregman iterations (e.g., LinBreg), induce sparsity but typically allow the number of non-zero parameters to increase monotonically, potentially limiting the exploitation of sparsity early in training. Furthermore, many dynamic sparse training approaches lack rigorous convergence guarantees.

Methodology

The authors propose a Multilevel LinBreg algorithm, a dynamic sparse training method based on linearized Bregman iterations (equivalent to mirror descent with non-smooth mirror maps). The core innovation lies in alternating between periods of static and dynamic sparsity pattern updates.

Key Algorithmic Components

Linearized Bregman Iterations: The method minimizes a loss function $L(\theta)$ while implicitly minimizing a regularizer $J(\theta)$ (e.g., $\ell_1$ -norm) using iterations:
$v^{(k+1)} = v^{(k)} - \tau \nabla L(\theta^{(k)})$
$\theta^{(k+1)} = \text{prox}_{\delta J}(\delta v^{(k+1)})$
The proximal operator acts as a pruning step, setting parameters to zero if their dual variables do not exceed a threshold.
Multilevel Optimization Framework: The algorithm embeds the training process into a multilevel optimization scheme (inspired by multigrid techniques).
- Fine Level: Represents the full parameter space.
- Coarse Level: Represents a restricted subspace containing only a subset of parameters.
- Restriction and Prolongation: The algorithm uses a restriction operator $R^{(k)}$ to map the current iterate to a coarse level, selecting specific groups of parameters (e.g., entire convolutional kernels) based on their current activity (non-zero status). A prolongation operator $P^{(k)}$ maps updates back to the fine level.
Adaptive Freezing:
- The algorithm performs $m$ iterations on the coarse level where updates are restricted only to the currently active (non-zero) parameter groups.
- During these "frozen" phases, gradients are computed only for active parameters, significantly reducing computational cost.
- After $m$ coarse steps, a single update is performed on the fine level to potentially reactivate new parameters or adjust the structure, followed by another cycle of coarse updates.
Convergence Analysis: The method is analyzed under a Polyak–Łojasiewicz (PL)-type inequality and relative smoothness assumptions. The authors prove a sublinear convergence rate for the function values, utilizing exact gradients on the fine level and stochastic gradient estimators on the coarse level.

Key Contributions

Algorithm Proposal: A sparse training algorithm that periodically freezes the network structure, restricting updates to non-zero parameters during specific phases. This enforces stricter sparsity than standard LinBreg and enables computational savings.
Theoretical Framework: Interpretation of the method as a multilevel optimization scheme. The authors provide convergence guarantees in a mixed gradient regime (exact gradients for full updates, stochastic for frozen phases) under suitable assumptions.
Empirical Performance: Demonstration that the method produces highly sparse models with competitive or superior accuracy compared to standard LinBreg, pruning, and RigL on CIFAR-10 and TinyImageNet benchmarks.
Efficiency Gains:
- Theoretical FLOPs: Theoretical analysis shows a reduction in floating-point operations compared to standard SGD. For standard Bregman iterations, FLOPs are reduced to ~38% of SGD; the proposed multilevel method reduces this to ~6%.
- Training Time: Empirical results using a sparsity-aware CPU implementation (SparseProp) show a training time reduction of approximately 50% compared to standard Torch implementations.

Experimental Results

The authors evaluated the algorithm on CIFAR-10 and TinyImageNet datasets using architectures such as ResNet18, VGG16, and WideResNet28-10.

Accuracy vs. Sparsity: On CIFAR-10, the Multilevel LinBreg (ML LinBreg) achieved accuracy comparable to RigL and pruning methods while maintaining higher sparsity levels. For instance, on WideResNet28-10, ML LinBreg produced models that were sparser and equally accurate compared to both LinBreg and pruning approaches.
Comparison to Baselines:
- vs. LinBreg: ML LinBreg consistently outperformed standard LinBreg by yielding sparser models with maintained or improved accuracy.
- vs. Pruning: Unlike pruning, which requires training a dense model first, ML LinBreg trains directly from a sparse initialization.
- vs. RigL: Results were comparable, though RigL relies heavily on specific initialization schemes (ERK), whereas ML LinBreg showed greater robustness to different mask initialization schemes.
Computational Efficiency: Using the SparseProp library on a CPU, the method reduced per-epoch training time by 49% compared to a standard dense implementation, with forward and backward pass times reduced by 32% and 58%, respectively.

Significance and Claims

The paper claims that the proposed multilevel strategy offers a significant improvement over standard linearized Bregman iterations by effectively exploiting the induced sparsity of the optimization process. By freezing the network structure for extended periods, the method not only enforces higher sparsity but also drastically reduces the computational burden (FLOPs and wall-clock time) without sacrificing model accuracy.

The authors position their work as a bridge between the theoretical convergence guarantees of multilevel optimization and the practical efficiency of sparse training. They emphasize that their method avoids the need for a dense pre-training phase (unlike pruning) and provides a rigorous convergence analysis often lacking in evolutionary or dynamic sparse training methods. The work suggests that multilevel frameworks can be a powerful tool for developing efficient, environmentally friendly deep learning models.

Future work, as modestly noted by the authors, includes extending the convergence analysis to a fully stochastic setting (using stochastic gradients on both levels) and relaxing the PL-condition to local Kurdyka–Łojasiewicz conditions.