Research map / Optimization / Nonconvex and smooth optimization
Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled 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 single-loop (SONEX) and double-loop (ALEXR2) stochastic momentum methods for non-smooth non-convex FCCO via outer/nested Moreau-envelope smoothing, achieving O(1/eps^5) complexity and applying them to smoothed-hinge penalty constrained optimization.
Problem
Non-smooth non-convex finite-sum coupled compositional optimization (FCCO) where outer functions are non-smooth weakly convex or convex and inner functions are smooth or weakly convex; prior best complexity O(eps^-6) with SGD-type updates unsuitable for deep learning.
Approach
Smooth non-smooth outer functions via Moreau envelope (or Nesterov smoothing when convex), optionally add a second Moreau envelope layer for weakly convex inner functions, then optimize the smoothed objective with stochastic momentum (or Adam-type) updates using single-loop (SONEX) or double-loop (ALEXR2) estimators; apply to inequality constraints through a smoothed hinge penalty.
Key results
- SONEX achieves O(1/eps^5) complexity for non-smooth FCCO with smooth inner functions, improving on the O(1/eps^6) of SONX.
- ALEXR2 (double-loop) achieves O(1/eps^5) for convex outer and smooth or weakly convex inner functions, and the smoothed hinge penalty gives O(1/eps^5) for nearly eps-KKT points in constrained optimization, versus O(eps^-6) prior.
- Experiments on GDRO with CVaR, fairness-constrained AUC maximization, and CLIP continual learning show SONEX/ALEXR2 outperform SONX, OOA, SOX, and ICPPAC in the reported settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace vanilla SGD-type updates with stochastic momentum updates | SONEX for non-smooth non-convex FCCO · Non-smooth non-convex FCCO | iteration complexity: O(1/\epsilon^6) -> O(1/\epsilon^5) | Helped |
| Use smoothed hinge penalty with SONEX or ALEXR2 rather than prior constrained-optimization methods | Non-convex inequality constrained optimization · Non-convex inequality constrained optimization | iteration complexity: O(\epsilon^{-6}) -> O(\epsilon^{-5}) | Helped |
| Use ALEXR2 with smoothed hinge penalty instead of the compared baseline methods | AUC maximization with ROC fairness constraints · Adult and COMPAS | AUC | Helped |
| Use ALEXR2 with smoothed hinge penalty rather than the compared baseline methods | AUC maximization with ROC fairness constraints · Adult and COMPAS | constraint violation | No clear effect |
| Use SONEX rather than SONX or OOA | GDRO with CVaR divergence · Camelyon17, Amazon, and CelebA | training loss and test accuracy | Helped |
| Use SONEX with the modified objective gradient estimator rather than SOX with squared hinge loss | Continual learning with non-forgetting constraints · BDD100K | target-task accuracy | Helped |
| Use SONEX rather than SOX with squared hinge loss | Continual learning with non-forgetting constraints · BDD100K | constraint violation | No clear effect |
Surprising findings
- The MLC0 / Lipschitz-in-expectation assumption used by variance-reduced MSVR-style analysis does not improve convergence here, since complexity is dominated by the smoothness of the smoothed outer function.
Limitations
- Single-loop SONEX has worse complexity than double-loop ALEXR2 in terms of inner batch size dependence.
- The approximate-to-nearly stationarity conversion relies on an empirically justified assumption that the minimum eigenvalue of the stacked Jacobian is bounded below.
- Results for ALEXR2 with smooth inner functions require additional inner ALEXR iterations to recover a nearly stationary point of the original problem.
Experimental setup
Datasets: Camelyon17 Amazon CelebA Adult COMPAS BDD100K
Benchmarks: Camelyon17 Amazon CelebA Adult COMPAS BDD100K
Metrics: training loss test accuracy AUC constraint violation accuracy improvement
Baselines: SONX OOA SOX ICPPAC SOX with squared hinge
Builds on: SOX MSVR SONX ALEXR ICPPAC
Closest papers by meaning
- Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization (NeurIPS 2024 · similarity 0.91)
- A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization (ICML 2025 · similarity 0.90)
- Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization (ICML 2024 · similarity 0.88)
- Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.87)
- Random Scaling and Momentum for Non-smooth Non-convex Optimization (ICML 2024 · similarity 0.87)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · 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.