🔢 mathematics

Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

This paper proposes the Hybrid Momentum Stochastic Frank--Wolfe algorithm, which achieves an optimal $\mathcal{O}(K^{-1/4})$ convergence rate for non-convex stochastic compositional optimization with non-smooth outer functions by combining momentum-based Jacobian tracking with Taylor-corrected function tracking to utilize stochastic linearizations in a generalized linear minimization oracle.

Original authors: El Mahdi Chayti

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: El Mahdi Chayti

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 find the lowest point in a vast, foggy valley (this is your optimization problem). You want to get to the bottom as quickly as possible, but you can't see the whole landscape. You can only take a step, look around, and get a noisy, blurry guess of where the ground is sloping.

Most modern machine learning algorithms are like hikers who have a very specific rule: "The ground must be smooth and slippery enough that I can calculate the exact slope at my feet." If the ground is jagged, rocky, or has sharp cliffs (mathematically, if the function is non-smooth), these hikers get stuck or take wrong turns.

This paper introduces a new kind of hiker: the Hybrid Momentum Stochastic Frank–Wolfe algorithm. Here is how it works, broken down into simple concepts:

1. The Problem: The "Jagged Cliff"

In many real-world scenarios, the goal isn't just to find a smooth slope. Sometimes the goal is to minimize the worst-case scenario (like "What is the maximum loss I could suffer?"), or to manage risk in a way that creates sharp corners in the math (like Conditional Value-at-Risk in finance).

The Old Way: Previous methods tried to smooth out these jagged cliffs to make them walkable. But this changes the problem, making the solution less accurate for the real-world goal.
The New Way: This paper says, "Let's walk on the jagged cliffs without smoothing them out." It handles the sharp corners directly.

2. The Solution: The "Blindfolded Guide" with Two Helpers

Since the hiker (the algorithm) can't see the whole map, they rely on two "trackers" (helpers) who run ahead to guess the terrain.

Helper A (The Jacobian Tracker): This helper guesses the direction of the slope.
Helper B (The Function Tracker): This helper guesses the height of the ground.

The paper proposes a Hybrid approach where these two helpers work together using "momentum." Think of momentum like a skier who doesn't just stop and re-evaluate every step; they carry their speed and direction forward, correcting their path only when they get a new, better signal.

There are two versions of this team:

Version I (Memoryless): The helper guesses the next height based purely on the current slope. It's fast and needs no memory, but it assumes the terrain isn't too wild.
Version II (Taylor-Corrected): The helper remembers where they were a moment ago and uses that to make a smarter guess about the next height. This is more robust and works even if the terrain is very wild, but it requires carrying a tiny bit of extra memory (the previous step).

3. The "Generalized Compass" (GLMO)

Once the helpers give their best guess of the terrain, the hiker needs to decide which way to step.

Old Compasses: Usually, these compasses require a smooth slope to point the way. If the ground is jagged, the compass spins wildly.
The New Compass (GLMO): This paper uses a "Generalized Linear Minimization Oracle." Imagine a compass that doesn't just look for a slope, but solves a small, quick puzzle to find the best direction even on jagged ground. It treats the jagged function as a "black box" and finds the best move without needing to calculate a smooth slope.

4. Handling the Fog (Heavy-Tailed Noise)

In the real world, the "noise" (the fog) isn't always gentle. Sometimes, a sudden gust of wind blows you off course violently (this is called heavy-tailed noise).

Many algorithms break when the wind is too strong.
This new algorithm is built to handle these violent gusts. It adjusts its step size and momentum based on how wild the wind is. Even if the noise is heavy, it still converges to the bottom of the valley.

5. The Results: How Fast Does It Go?

The paper proves mathematically that this new hiker is very efficient:

For tricky, non-smooth problems: It finds a good solution at a rate of roughly $1/\sqrt[4]{K}$ (where $K$ is the number of steps). This is the fastest possible speed theoretically allowed for this type of problem without using extra memory or assumptions.
For smooth, convex problems: It speeds up to $1/\sqrt[3]{K}$ .
The "Perfect World" Check: If the fog disappears (no noise), this algorithm seamlessly transforms into the best-known deterministic method, proving it works perfectly in ideal conditions too.

Real-World Tests

The authors tested this on three real-world "valleys":

Robust Regression: Finding a line that fits data even if some data points are extreme outliers.
Portfolio Optimization: Managing a stock portfolio to minimize the risk of the worst possible losses (CVaR).
Matrix Completion: Filling in missing data in a movie rating table (like Netflix) while handling noisy user ratings.

In all cases, their new algorithm (the Hybrid Momentum hiker) successfully navigated the jagged terrain and found the solution, while older methods either got stuck or failed to converge.

In summary: This paper gives us a new tool to solve complex, "jagged" optimization problems in machine learning. It combines smart memory (momentum) with a specialized compass (GLMO) to navigate rough, noisy landscapes that previous tools couldn't handle.

Technical Summary: Stochastic Compositional Optimization via Hybrid Momentum Frank–Wolfe

Problem Formulation
This work addresses the stochastic compositional optimization problem of minimizing objectives of the form:
$\min_{x \in X} \phi(x) := F(f(x), x)$
where $X \subset \mathbb{R}^d$ is a convex and compact set, $f: X \to \mathbb{R}^n$ is an inner mapping accessible only via noisy stochastic queries ( $f(x) = \mathbb{E}_\xi[\tilde{f}(x; \xi)]$ ), and $F: \mathbb{R}^n \times X \to \mathbb{R}$ is a deterministic outer function.

The primary challenge in the stochastic setting is that naive plug-in estimators are biased due to Jensen's inequality ( $\mathbb{E}[F(\tilde{f}(x; \xi), x)] \neq F(\mathbb{E}[\tilde{f}(x; \xi)], x)$ ). While existing stochastic methods (e.g., SCGD, NASA, SCSC) address this bias using momentum-based trackers and the chain rule, they fundamentally require the outer function $F$ to be continuously differentiable. This assumption excludes many critical applications involving non-smooth outer functions, such as robust max-of-losses, Conditional Value-at-Risk (CVaR), and norm regularizers. Furthermore, existing projection-free stochastic methods (e.g., LiNASA+ICG) also rely on the smoothness of $F$ .

Methodology
The authors propose the Hybrid Momentum Stochastic Frank–Wolfe algorithm, the first projection-free method for fully composite problems that handles non-smooth outer functions. The core innovation lies in replacing the standard gradient-based update with a Generalized Linear Minimization Oracle (GLMO) that operates on a stochastic affine surrogate.

The algorithm maintains two stochastic trackers at each iteration $k$ :

Jacobian Tracker ( $V_k$ ): A Polyak-style momentum estimator for the Jacobian $\nabla f(y_k)$ .
Function Tracker ( $z_k$ ): An estimator for the function value $f(y_k)$ .

The algorithm offers two variants for the function tracker to balance memory usage and assumptions:

Variant I (Polyak): Memoryless but requires the inner function $f$ to be Lipschitz continuous.
Variant II (Taylor-corrected): Requires storing the previous iterate but eliminates the Lipschitz assumption on $f$ by using a first-order Taylor extrapolation ( $V_k(y_k - y_{k-1})$ ) to predict the function value, reducing tracking error to a quadratic remainder.

At each step, the algorithm constructs an affine surrogate $\tilde{l}_k(x) = z_k + V_k(x - y_k)$ and feeds this into the GLMO:
$x_{k+1} \in \arg\min_{x \in X} F(\tilde{l}_k(x), x)$
Crucially, the GLMO treats $F$ as a black box, minimizing it directly over the linearized inner function without requiring a subgradient of $F$ . This allows the method to handle non-smooth $F$ (e.g., $\ell_p$ -norms, max-functions) efficiently, often reducing the oracle call to a Linear Program (LP) or Second-Order Cone Program (SOCP).

Key Contributions

Algorithmic Novelty: Introduction of the first stochastic projection-free algorithm for fully composite optimization with non-smooth outer functions.
Theoretical Guarantees under Heavy-Tailed Noise: The analysis assumes the stochastic oracle has bounded $r$ $r$ -th moments ( $r \in (1, 2]$ $r \in (1, 2]$ ), covering heavy-tailed noise scenarios.
- Non-Convex Case: The algorithm achieves a convergence rate of $O(K^{-(r-1)/(3r-2)})$ in the generalized Frank–Wolfe gap. For finite variance ( $r=2$ ), this yields $O(K^{-1/4})$ , matching the minimax-optimal lower bound for single-sample projection-free stochastic methods under expected smoothness.
- Convex Case: Under joint convexity assumptions, the primal rate is $O(K^{-(r-1)/(2r-1)})$ , recovering $O(K^{-1/3})$ when $r=2$ .
Deterministic Interpolation: The algorithm seamlessly interpolates with the deterministic regime. When the oracle is exact (zero noise), setting momentum parameters to 1 recovers the deterministic Basic Method of Vladarean et al. [2023] with its optimal rates ( $O(1/K)$ for convex, $\tilde{O}(1/\sqrt{K})$ for non-convex).
Acceleration: Under stronger $r$ -average smoothness assumptions (or bounded Hessian noise moments), the framework integrates with STORM variance reduction or Hessian-corrected momentum to accelerate the non-convex rate to $O(K^{-1/3})$ (at $r=2$ ).

Results and Experiments
The paper validates the theoretical findings through numerical experiments on three real-world problems featuring non-smooth $F$ and heavy-tailed noise:

Robust Minimax Sparse Regression: Minimizing the worst-case loss over data subsets.
CVaR Portfolio Optimization: Risk-averse optimization on S&P 500 returns.
Robust Matrix Completion: Using $\ell_1$ loss on the MovieLens-100K dataset.

Experimental results demonstrate that standard stochastic compositional Frank–Wolfe (Vanilla SCFW) fails to converge due to bias, and clipped variants plateau. In contrast, both proposed variants (Polyak and Taylor) achieve the predicted $O(K^{-1/4})$ convergence rate. The Taylor variant (Variant II) is shown to be theoretically robust even when the Lipschitz assumption on $f$ cannot be verified, though the Polyak variant performs slightly better in regimes where the assumption holds.

Significance
The paper claims to resolve an open problem identified by Vladarean et al. [2023] regarding the stochastic extension of projection-free methods for fully composite optimization. By removing the smoothness requirement on the outer function $F$ , this work enables the application of projection-free optimization to a broader class of risk-averse, robust, and fairness-constrained learning problems. The method achieves optimal complexity rates for projection-free stochastic methods while maintaining computational efficiency (requiring only a single GLMO call per iteration, unlike previous methods requiring expensive inner loops).