Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

summary

Video file (mp4)

The gist

The Hybrid Momentum Stochastic Frank–Wolfe algorithm addresses fully composite optimization problems where the outer function F lacks continuous differentiability, which excludes many practically

In short

The Hybrid Momentum Stochastic Frank–Wolfe algorithm solves optimization problems where an outer function F is not continuously differentiable, which excludes many practical applications like CVaR. It introduces a novel stochastic projection-free method that maintains two trackers to handle non-smoothness in the outer function, achieving optimal convergence rates of O(K^-1/4) for non-convex objectives.

Key concepts

Fully Composite Optimization
This refers to minimizing an objective function structured as min x∈X F(f(x), x). It combines a standard optimization problem (min f(x)) with another objective function F that depends on both the inner solution f(x) and the variable x itself. The challenge is that the outer function F often lacks continuous derivatives, making standard methods difficult to apply.
Generalized Linear Minimization Oracle (GLMO)
This is a specialized oracle used by the algorithm to handle non-smoothness in the outer function F directly, without needing a traditional gradient. Depending on F, this oracle simplifies into solving either a small linear program or a second-order cone program at each step. It allows the algorithm to proceed even when F is not smooth.
Stochastic Trackers (Polyak and Function-Value)
The algorithm uses two specific trackers: a Polyak Jacobian tracker to estimate the inner function's properties and a function-value tracker. These trackers define an affine surrogate used in the GLMO, which helps guide the optimization process through noisy stochastic queries, improving convergence compared to naive estimators.

Terminology used across episodes

This episode discusses

The paper

Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe · Read on arXiv

El Mahdi Chayti

EPFL

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe".

Jane: The Hybrid Momentum Stochastic Frank–Wolfe algorithm addresses fully composite optimization problems where the outer function F lacks continuous differentiability,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at the title and authors of this paper, "Stochastic Compositional Optimization via Hybrid Momentum Frank–Wolfe". It sounds technical, but the authors are from Machine Learning and Optimization Laboratory EPFL in Switzerland.

Jane: The core idea is that they address that open problem where existing methods assume F is continuously differentiable, which excludes many practically important applications.

Lu: They propose this Hybrid Momentum Stochastic Frank–Wolfe algorithm as a way to handle non-smooth outer functions without needing to differentiate through them black box rather than differentiating through it.

Meng: It seems like they are building something that can work where the standard machinery just breaks down because F isn't smooth.

Lalam: By combining a momentum-based Jacobian tracker with a Taylor-corrected function tracker, the algorithm feeds an entire stochastic linearization into a generalized linear minimization oracle which handles non-smooth F directly.

The paper's summary: Tom: So what exactly is the summary of this paper? Basically, they introduce Algorithm one which tracks both the Jacobian and function value of f, then feeds that into a GLMO that deals with non-smooth F directly <ref:2605.15350#pg1>.

Jane: They also present two tracker variants, Variant I which uses a Polyak update and requires f to be Lipschitz for memoryless tracking, or Variant II which uses Taylor extrapolation and doesn't need the Lipschitz assumption by storing one previous iterate.

Lu: Under heavy-tailed noise with bounded r-th moment where r is in the range of one to two, they establish an O(K−(r−one)/(3r−two)) convergence in the generalized Frank–Wolfe gap for non-convex objectives with LF-Lipschitz outer functions <ref:2605.15350#pg2,O(K−(r−1)/(3r−2)) convergence in the generalized Frank–Wolfe>.

Meng: If you look at that rate when r equals two, it gives you an O(K−one/four) convergence, which matches the minimax-optimal rate for single-sample projection-free stochastic methods under expected smoothness <ref:2605.15350#pg1,an O(K−1/4) convergence>.

The paper's improvements: Tom: The paper suggests a few key improvements over previous methods. First, they tackle the open problem by proposing this algorithm as the first stochastic projection-free method for fully composite problems with non-smooth outer F.

Jane: Second, they offer two tracker variants, Variant I and Variant II, which give us a choice between memoryless tracking that needs f Lipschitz or Taylor extrapolation that eliminates that assumption.

Lu: They also introduce acceleration mechanisms. Theorem three shows that replacing the Polyak Jacobian update with a stochastic finite-difference correction called STORM can achieve an O(K−(r−one)/(2r−one)) rate, recovering O(K−one/three) at r equals two <ref:2605.15350#pg2,recovering O(K−1/3) at r>.

Meng: And then there's Hessian-corrected momentum using randomized Hessian–vector products which shows that bounded Hessian-noise moments imply r-average smoothness, allowing the rate to reach O(K−(r−one)/(2r−one)) via Theorem four <ref:2605.15350#pg2,O(K−(r−1)/(2r−1>.

Conclusion: Tom: So to wrap up this paper on "Stochastic Compositional Optimization via Hybrid Momentum Frank–Wolfe", they show that they can handle non-smooth outer functions without needing smoothness assumptions on F itself.

Jane: They achieve an O(K−one/four) convergence rate for non-convex objectives under expected smoothness, and an O(K−one/three) primal rate for convex objectives when r equals two <ref:2605.15350#pg2>.

Lu: The paper is significant because it provides the only stochastic projection-free algorithm that does not require F to be smooth, and its O(K−one/four) rate matches the established state-of-the-art for projection-based stochastic compositional methods like SCSC and L-NASA <ref:2605.15350#pg1>.

Meng: It’s also computationally efficient because it only requires a single generalized linear minimization oracle call per iteration, which is much better than methods like LiNASA+ICG which demand O(K3/two) standard LMO calls <ref:2605.15350#pg2>.

Lalam: And it can adapt to the noise level, yielding a clean reduction to optimal deterministic rates when the stochastic noise vanishes.

Tom: This work on Stochastic Compositional Optimization via Hybrid Momentum Frank–Wolfe is definitely something we need to keep an eye on as we try to apply these techniques in real-world scenarios involving complex risk objectives.

More episodes

← Home