Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

The Hybrid Momentum Stochastic Frank–Wolfe algorithm addresses fully composite optimization problems where the outer function F lacks continuous differentiability, which excludes many practically important applications like robust max-of-losses and Conditional Value-at-Risk.

The gist: This paper proposes the Hybrid Momentum Stochastic Frank–Wolfe algorithm, the first stochastic projection-free method for fully composite problems with non-smooth outer F, achieving an O(K−1/4) convergence rate in the generalized Frank–Wolfe gap for non-convex objectives under expected smoothness

Problem Formulation and Assumptions

The problem being solved is to minimize objectives of the form min x∈X F(f(x), x), where f is accessible only through noisy stochastic queries This formulation generalizes both classical compositional optimization F(f(x)) and additive composite optimization Solving this stochastically poses a fundamental challenge because naive plugin estimators are biased by Jensen’s inequality, meaning E[F(f˜(x; ξ), x)] ≠ F(E[f˜(x; ξ)], x) The algorithm operates under several key assumptions, including domain compactness where X ⊂ R d is convex and compact with diameter DX < ∞ Outer function regularity requires F: R n × X → R to be LF-Lipschitz in u, monotone non-decreasing in u, and subhomogeneous in u The inner function smoothness assumes f: X → R n has L-Lipschitz Jacobian: ∇f(x) − ∇f(y)op ≤ Lx − y for all x, y ∈ X Furthermore, the stochastic oracle is modeled by heavy-tailed noise with bounded r-th moments for r ∈ (1, 2]

Algorithm and Trackers

The core of the proposed method is Algorithm 1, which maintains two stochastic trackers: a Polyak Jacobian tracker Vk and a function-value tracker zk in one of two variants At each step, these trackers define an affine surrogate ˜lk(x):= zk + Vk(x − yk), which is then fed into the Generalized Linear Minimization Oracle (GLMO) The GLMO handles the non-smoothness of F directly without requiring a (sub)gradient, and it reduces to a small linear program or a second-order cone program depending on the specific outer function F The paper presents two tracker variants: Variant I (Polyak update; memoryless but requires f Lipschitz) and Variant II (Taylor-corrected; requires storing one previous iterate but eliminates the Lipschitz assumption)

Convergence Guarantees

The algorithm establishes convergence rates based on the noise level r Theorem 1 provides O(K−(r−1)/(3r−2)) convergence in the generalized Frank–Wolfe gap for non-convex objectives with LF-Lipschitz outer functions At r = 2, this rate matches the minimax-optimal rate for single-sample stochastic methods under expected smoothness Theorem 2 yields an O(K−(r−1)/(2r−1)) primal rate for convex objectives when Assumption 6 holds At r = 2, this recovers O(K−1/3), matching the optimal rate for convex stochastic FW with momentum The algorithm interpolates with the deterministic regime when the oracle is exact, reducing to the Basic Method of Vladarean et al. [2023]

Acceleration Techniques

The paper introduces two acceleration mechanisms that improve convergence rates under stronger smoothness assumptions Theorem 3 shows that replacing the Polyak Jacobian update with a stochastic finite-difference correction (STORM) achieves O(K−(r−1)/(2r−1)), recovering O(K−1/3) at r = 2 Alternatively, Hessian-corrected momentum using randomized Hessian–vector products shows that bounded Hessian-noise moments imply r-average smoothness, allowing the rate to reach O(K−(r−1)/(2r−1)) via Theorem 4

Empirical Validation

The effectiveness of the algorithm is demonstrated through numerical experiments on three real-world problems: robust minimax sparse regression, CVaR portfolio optimization, and robust matrix completion The results show that Vanilla SCFW fails to converge because plug-in stochastic estimates are biased through the non-linear F Both Variant I (Polyak) and Variant II (Taylor) achieve the predicted O(K−1/4) rate The framework requires only a single Generalized Linear Minimization Oracle call per iteration, making it more computationally efficient than methods like LiNASA+ICG which demand O(K3/2) standard LMO calls

Conclusion

In this work, the authors introduced the first stochastic projection-free algorithm for fully composite optimization capable of handling non-smooth outer functions The approach achieves the minimax optimal O(K−1/4) rate for non-convex objectives and an O(K−1/3) rate for convex objectives under standard finite-variance noise assumptions Furthermore, the algorithm seamlessly adapts to the noise level, yielding a clean reduction to optimal deterministic rates when the stochastic noise vanishes The work is first to handle a non-smooth outer function F in the stochastic projection-free regime This work is the only stochastic projection-free algorithm that does not require F to be smooth The O(K−1/4) rate of Theorem 1 matches the established state-of-the-art for projection-based stochastic compositional methods such as SCSC and L-NASA This work requires only a single Generalized Linear Minimization Oracle (GLMO) call per iteration, in contrast to LiNASA+ICG which relies on an inner Inverse Conditional Gradient (ICG) procedure that demands O(K3/2) standard LMO calls This work is the only stochastic projection-free algorithm that does not require F to be smooth The O(K−1/4) rate of Theorem 1 matches the established state-of-the-art for projection-based stochastic compositional methods such as SCSC and L-NASA This work requires only a single Generalized Linear Minimization Oracle (GLMO) call per iteration, in contrast to LiNASA+ICG which relies on an inner Inverse Conditional Gradient (ICG) procedure that demands O(K3/2) standard LMO calls This work is the only stochastic projection-free algorithm that does not require F to be smooth The O(K−1/4) rate of Theorem 1 matches the established state-of-the-art for projection-based stochastic compositional methods such as SCSC and L-NASA This work requires only a single Generalized Linear Minimization Oracle (GLMO) call per iteration, in contrast to LiNASA+ICG which relies on an inner Inverse Conditional Gradient (ICG) procedure that demands O(K3/2) standard LMO calls This work is the only stochastic projection-free algorithm that does not require F to be smooth The O(K−1/4) rate of Theorem 1 matches the established state-of-the-art for projection-based stochastic compositional methods such as SCSC and L-NASA This work requires only a single Generalized Linear Minimization Oracle (GLMO) call per iteration, in contrast to LiNASA+ICG which relies on an inner Inverse Conditional Gradient (ICG) procedure that demands O(K3/2) standard LMO calls <ref:26

1. This system can optimize risk-averse learning objectives like Conditional Value-at-Risk (CVaR) and robust minimax sparse regression by directly minimizing non-smooth outer functions F, which are common in these applications.

2. The Hybrid Momentum Stochastic Frank–Wolfe algorithm provides a stochastic projection-free method for fully composite problems with non-smooth outer functions, achieving an O(K−1/4) convergence rate for non-convex objectives under expected smoothness.

3. For convex objectives, the algorithm achieves an O(K−1/3) primal rate, matching the optimal rate for stochastic FW with momentum [Mokhtari et al., 2020], extended to the non-smooth fully composite setting.

4. The system can leverage two tracker variants: Variant I (Polyak update) for memoryless tracking requiring only f Lipschitz, or Variant II (Taylor-corrected) which eliminates the need for Assumption 5 by using a Taylor extrapolation to predict function values from previous iterates.

5. The algorithm's generalized linear minimization oracle (GLMO) is tractable for various non-smooth objectives, reducing the problem to a Linear Program (LP) or Second-Order Cone Program (SOCP), allowing efficient solution of complex optimization tasks like CVaR and Distributionally Robust Optimization (DRO).

Stochastic compositional optimization minimizes F(f(x), x) over a compact convex set when the inner map f is available only through noisy samples. We propose Hybrid Momentum Stochastic Frank--Wolfe, a projection-free method for outer functions F that are jointly convex and Lipschitz but not necessarily differentiable, such as maxima, CVaR, and norms. The method tracks the Jacobian and the value of f with momentum, using a Taylor correction for the value, and passes the tracked linearization to a generalized linear minimization oracle. Under finite-variance noise, it attains an expected generalized Frank--Wolfe gap of order K-1/4 for non-convex objectives and, when the linearized models minorize the objective, a last-iterate primal error of order K-1/3. The analysis extends to heavy-tailed noise without clipping, with separate moment orders for values and Jacobians. With an exact oracle, the method reduces to the deterministic method of Vladarean et al. (2023).