Research map / Optimization / Nonconvex and smooth optimization
Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes projection-free variance-reduced (STORM-based) methods for stochastic constrained multi-level compositional optimization, giving complexities under Frank-Wolfe gap, gradient mapping, and optimal gap criteria.
Problem
Projection-free stochastic optimization of nested multi-level compositional objectives over closed convex sets; prior methods only handle gradient mapping, nonconvex objectives, and have suboptimal SFO complexity.
Approach
Apply STORM variance reduction to the inner function values and to the overall nested gradient (rather than per-level gradients), combined with Frank-Wolfe linear minimization steps; for gradient mapping, use an inner Frank-Wolfe subproblem solver, and a stage-wise warm-start scheme for convex and strongly convex objectives.
Key results
- Gradient-mapping complexity improves from O(eps^-2) SFO and O(eps^-3) LMO (LiNASA+ICG) to O(eps^-1.5) SFO and O(eps^-2.5) LMO with constant batch, and O(eps^-1.5) SFO with O(eps^-2) LMO using batch O(eps^-0.5).
- Frank-Wolfe gap guarantees match single-level projection-free rates: O(eps^-3) SFO and LMO with constant batch, and O(eps^-3) SFO with O(eps^-2) LMO with large batch.
- Convex objectives reach O(eps^-2) SFO and LMO with constant batch; strongly convex reaches O(lambda^-1 eps^-1) SFO, the optimal rate for single-level strongly convex problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PMVR-v2 instead of LiNASA+ICG with constant batch size | Projection-free multi-level optimization · Gradient mapping, smooth | SFO complexity: \mathcal{O}(\epsilon^{-2}) -> \mathcal{O}(\epsilon^{-1.5}) | Helped |
| Use PMVR-v2 instead of LiNASA+ICG with constant batch size | Projection-free multi-level optimization · Gradient mapping, smooth | LMO complexity: \mathcal{O}(\epsilon^{-3}) -> \mathcal{O}(\epsilon^{-2.5}) | Helped |
| Increase batch size to O(ε⁻⁰·⁵) | PMVR-v2 · Gradient mapping, smooth | LMO complexity: \mathcal{O}(\epsilon^{-2.5}) -> \mathcal{O}(\epsilon^{-2}) | Helped |
| Increase batch size to O(ε⁻¹) | PMVR · Frank-Wolfe gap, smooth | LMO complexity: \mathcal{O}(\epsilon^{-3}) -> \mathcal{O}(\epsilon^{-2}) | Helped |
| Use large batches in Stage-wise PMVR | Stage-wise PMVR · Optimal gap, smooth convex | LMO complexity: \mathcal{O}(\epsilon^{-2}) -> \mathcal{O}(\epsilon^{-1}) | Helped |
| Use large batches in Stage-wise PMVR-v2 | Stage-wise PMVR-v2 · Optimal gap, smooth strongly convex | LMO complexity: \mathcal{O}(\epsilon^{-2}) -> \mathcal{O}(\epsilon^{-1}) | Helped |
| Use PMVR-v2 rather than the other evaluated algorithms | Matrix optimization with low-rank constraints · Frank-Wolfe gap and gradient mapping | convergence rate | Helped |
| Use PMVR-v2 rather than the other evaluated algorithms | Mean-variance risk-averse optimization · Industry-10 and Industry-12 | loss value | Helped |
| Use PMVR-v2 rather than the other evaluated algorithms | Mean-deviation risk-averse optimization · Industry-10 and Industry-12 | Frank-Wolfe gap | Helped |
Limitations
- Theoretical gains rely on batch-size choices; constant-batch rates for gradient mapping still have higher LMO cost than large-batch variants.
- Experiments are limited to portfolio and synthetic low-rank matrix tasks on a personal laptop.
Experimental setup
Datasets: Kenneth R. French Industry-10 portfolio data Industry-12 portfolio data synthetic matrix single-index data
Benchmarks: Industry-10 portfolio optimization Industry-12 portfolio optimization matrix optimization with low-rank constraints
Metrics: loss value Frank-Wolfe gap gradient mapping running time iterations
Baselines: LiNASA+ICG SMVR A-TSCGD NLASG Nested-SPIDER SCSC SGD+ICG NCGS SCGS 1-SFW SPIDER-FW
Builds on: STORM SMVR LiNASA Frank-Wolfe SPIDER-FW
Closest papers by meaning
- Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization (NeurIPS 2025 · similarity 0.88)
- Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization (NeurIPS 2024 · similarity 0.88)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.88)
- A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization (ICML 2025 · similarity 0.87)
- Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions (NeurIPS 2024 · similarity 0.87)
- Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.