🔢 mathematics

Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction

This paper proposes Rennala MVR, a momentum-based variance reduction extension of Rennala SGD that theoretically and empirically improves time complexity for parallel stochastic optimization in heterogeneous environments under mean-squared smoothness assumptions.

Original authors: Zhirayr Tovmasyan, Artavazd Maranjyan, Peter Richtárik

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhirayr Tovmasyan, Artavazd Maranjyan, Peter Richtárik

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

Imagine you are trying to solve a massive jigsaw puzzle, but instead of working alone, you have a team of 100 people helping you. However, this team is a bit chaotic: some people are fast, some are slow, some get distracted by phone calls, and others are just naturally slower at finding pieces. This is exactly what happens when modern AI models are trained on clusters of computers. The computers (workers) have different speeds and face different delays.

For a long time, computer scientists measured how good an algorithm was by counting how many steps it took to solve the puzzle. They assumed everyone worked at the same speed. But in the real world, counting steps doesn't tell the whole story. If you have 100 people, but 99 of them are stuck waiting for the 1 slowest person to finish a step, you've wasted a lot of time.

This paper introduces a new way to measure success: Time. Instead of asking "How many steps did we take?", it asks "How long did it actually take to finish?"

The Old Way: Rennala SGD

The current best method, called Rennala SGD, is like a very efficient team leader. Instead of waiting for everyone to finish one piece at a time, the leader says, "Everyone, grab a handful of pieces and bring them back to me." The team leader then waits for the fastest group of workers to return their handful, takes a step, and moves on. This is great because it doesn't get stuck waiting for the slowest person.

However, there's a catch. To make sure the team doesn't get confused by bad guesses (noise), the team leader has to ask everyone to bring back a huge handful of pieces every single time. This is safe, but it takes a long time to gather such a large handful, especially if some workers are slow.

The New Idea: Rennala MVR

The authors of this paper asked: "Can we use a trick called Variance Reduction to make this faster?"

In the world of math, "variance reduction" is like giving your team a memory. Instead of just guessing what the next piece looks like based on the current one, the team remembers what the pieces looked like a moment ago. This allows them to make much better guesses with fewer pieces.

The authors created a new method called Rennala MVR (Momentum-Based Variance Reduction). Here is how it works in our analogy:

The Memory Trick: Instead of asking the team to bring back a giant handful of pieces every time, the team leader uses the "memory" trick. Because the guesses are better, the team only needs to bring back a smaller handful of pieces to make a good move.
The Speed Boost: Since the team only needs to gather a small handful, they can do it much faster. Even though the team leader might have to ask for a few more "rounds" of gathering pieces compared to the old method, each round is so much quicker that the total time to finish the puzzle is shorter.

The Catch (The "Smoothness" Rule)

There is one rule for this new method to work: The puzzle pieces must be somewhat predictable. In math terms, the paper assumes the problem has a property called "mean-squared smoothness."

Think of it like this: If you are walking down a hill, "smoothness" means the ground doesn't have sudden, jagged cliffs. If the ground is smooth, you can use your memory of the last step to guess where the next step is. If the ground is full of random, jagged spikes, your memory won't help much. The paper proves that if the "ground" (the math problem) is smooth enough, Rennala MVR is faster than the old method.

What They Found

The authors did two things to prove their idea:

The Math Proof: They wrote down the rules of the game and proved that, under the right conditions, Rennala MVR will finish the puzzle in less time than Rennala SGD. They also figured out the absolute fastest time any method could possibly achieve in this setting and showed that their new method gets very close to that limit.
The Experiments: They tested their method on two things:
- A simple math puzzle: They simulated a team of 10 workers with different speeds. The new method (Rennala MVR) finished the task faster than the old method.
- A real-world task: They trained a small neural network (a simple AI brain) on a subset of handwritten digits (MNIST). Even though this was a "rougher" version of their perfect math method, it still finished the training faster than the old method.

The Bottom Line

In a world where computers are messy and have different speeds, simply counting steps isn't enough. By giving the optimization algorithm a "memory" (variance reduction), the authors showed that we can gather information faster, wait less time for slow computers, and train AI models in less total time.

Important Note: The paper strictly focuses on the math and theory of training these models. It does not claim this will cure diseases, predict the weather, or change how we use AI in daily life right now. It simply proves that, mathematically and in controlled tests, this new way of organizing the work is faster.

Technical Summary: Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction

Problem Statement

Large-scale machine learning training increasingly relies on distributed clusters of machines exhibiting heterogeneous performance due to hardware variability, network delays, and system instabilities. In such environments, the traditional metric of iteration complexity (the number of steps to convergence) is insufficient. Instead, time complexity (actual wall-clock time) becomes the critical performance metric, as it accounts for idle time, synchronization overhead, and worker speed disparities.

While recent work by Tyurin and Richtárik [2023] established the first time-complexity lower bounds for parallel first-order stochastic optimization and proposed Rennala SGD as a time-optimal method for smooth nonconvex problems, it remains an open question whether variance reduction techniques—which are known to improve iteration complexity—can also yield improvements in time complexity within heterogeneous systems.

Methodology

The authors propose Rennala MVR, a variance-reduced extension of Rennala SGD that leverages Momentum-based Variance Reduction (MVR), a technique originally introduced in the STORM algorithm [Cutkosky and Orabona, 2019].

Core Algorithmic Design

Rennala MVR operates in a distributed setting with $n$ workers, where worker $i$ requires $\tau_i$ seconds to compute a stochastic gradient. The algorithm follows an asynchronous paradigm:

Gradient Pair Computation: Unlike standard SGD which computes a single gradient per sample, Rennala MVR requires workers to compute a pair of gradients, $\nabla f(x_k; \xi)$ and $\nabla f(x_{k+1}; \xi)$ , for the same data sample $\xi$ .
Asynchronous Aggregation: The server continuously aggregates these gradient pairs as they arrive from workers. It forms two minibatch averages: $g_-$ (gradients at $x_k$ ) and $g_+$ (gradients at $x_{k+1}$ ).
MVR Update: The gradient estimator is updated using the momentum-based variance reduction formula:
$g_{k+1} = \frac{g_+}{B} + (1-p)\left(g_k - \frac{g_-}{B}\right)$
where $B$ is the minibatch size and $p$ is a momentum parameter.
Model Update: The model is updated as $x_{k+1} = x_k - \gamma g_k$ .

Theoretical Assumptions

The analysis relies on the Mean-Squared Smoothness assumption (Assumption 2.4), which is stronger than standard $L$ -smoothness. It posits that there exists a constant $\bar{L}$ such that:
$\mathbb{E}_{\xi}[\|\nabla f(x; \xi) - \nabla f(y; \xi)\|^2] \leq \bar{L}^2 \|x - y\|^2$
This assumption is crucial for enabling variance reduction to improve convergence rates.

Key Contributions

Proposal of Rennala MVR: The authors introduce a distributed, variance-reduced optimization method tailored for heterogeneous systems under the mean-squared smoothness assumption.
Time Complexity Analysis: They derive upper bounds on both iteration and time complexity. The analysis clarifies the specific parameter regimes where variance reduction yields time complexity gains over Rennala SGD. Specifically, they show that while Rennala MVR may require more iterations (scaling with $\bar{L}\Delta/\varepsilon$ ), the reduced per-iteration waiting time (scaling with $\sigma/\sqrt{\varepsilon}$ rather than $\sigma^2/\varepsilon$ ) can lead to superior overall time complexity when $\bar{L} = O(L)$ .
New Lower Bound: The paper establishes a new lower bound on the achievable time complexity for this problem class. This bound matches the oracle complexity of Rennala MVR but highlights a gap in the current time complexity upper bound, suggesting that optimal time complexity in heterogeneous settings may require fundamentally different algorithmic ideas beyond simple extensions of variance reduction.
Extension to Varying Speeds: The time complexity analysis is extended to a universal computation model where worker speeds vary arbitrarily over time.
Empirical Validation: Experiments on stochastic quadratic benchmarks and asynchronous neural network training (using an inexact practical variant) demonstrate that Rennala MVR consistently outperforms Rennala SGD across various delay models.

Results

Theoretical Findings

Oracle Complexity: Rennala MVR achieves an oracle complexity of $O(\frac{\bar{L}\Delta\sigma}{\varepsilon^{3/2}} + \frac{\sigma^2}{\varepsilon})$ , matching the known lower bound for this problem class [Arjevani et al., 2022].
Time Complexity: The time complexity is shown to be:
$T = O\left( \left(\frac{\bar{L}\Delta}{\varepsilon} + \frac{\sigma}{\sqrt{\varepsilon}}\right) T\left(\frac{\sigma}{\sqrt{\varepsilon}}\right) + T\left(\frac{\sigma^2}{\varepsilon}\right) \right)$
where $T(B)$ represents the time to collect $B$ gradients asynchronously.
Comparison with Rennala SGD: Rennala MVR outperforms Rennala SGD in time complexity for sufficiently small $\varepsilon$ when $\bar{L} = O(L)$ . The improvement stems from the reduced batch size required per iteration ( $\sigma/\sqrt{\varepsilon}$ vs. $\sigma^2/\varepsilon$ ), which reduces the synchronization bottleneck in heterogeneous systems.
Gap to Lower Bound: The authors note a gap between their upper bound and the derived lower bound. The lower bound suggests an optimal time complexity scaling of $O(\frac{\bar{L}\Delta}{\sigma\sqrt{\varepsilon}} + 1) \cdot T(\frac{\sigma^2}{\varepsilon})$ . The current method does not fully match this because it uses smaller batches ( $\sigma/\sqrt{\varepsilon}$ ) to maintain convergence, whereas the lower bound implies that larger batches ( $\sigma^2/\varepsilon$ ) might be necessary for time optimality, a trade-off not yet resolved by their current proof techniques.

Empirical Findings

Quadratic Benchmark: On a stochastic tridiagonal quadratic problem with 10 and 100 workers under three delay models (square-root, mixture, and uniform), the exact Rennala MVR method consistently reached lower stationarity measures ( $\|\nabla f(x)\|^2$ ) in less time than the best-tuned Rennala SGD.
Neural Network Training: On a MNIST subset with a two-layer ReLU network, an inexact variant of Rennala MVR (inspired by MARS [Yuan et al., 2025]) demonstrated similar empirical gains over Rennala SGD, achieving lower training loss faster across all delay models.
Hyperparameter Sensitivity: The method was found to be relatively insensitive to the momentum parameter $p$ and the scaling parameter $\alpha$ in the inexact variant, suggesting that the primary tuning burden remains on the stepsize and batch size, similar to Rennala SGD.

Significance and Claims

The paper claims to initiate the systematic study of time complexity for distributed variance-reduced optimization. Its primary significance lies in demonstrating that oracle optimality does not automatically imply time optimality in heterogeneous parallel environments.

The authors emphasize that while momentum-based variance reduction is oracle-optimal in single-worker settings under stronger smoothness assumptions, its behavior in parallel heterogeneous systems is more nuanced. The time complexity depends critically on the interaction between optimization progress, worker time models, and the batch-size/time tradeoff.

The work provides the first theoretical understanding of momentum-based variance reduction in heterogeneous distributed systems, supported by a new lower bound. However, the authors remain modest regarding the gap between their upper and lower bounds, acknowledging that closing this gap likely requires "fundamentally different ideas" rather than routine extensions of existing variance-reduction analyses. They conclude that understanding the time complexity of such methods requires a dedicated theoretical framework distinct from iteration complexity analysis.