Research map / Optimization / Nonconvex and smooth optimization
SOREL: A Stochastic Algorithm for Spectral Risks Minimization
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 SOREL, a single-loop stochastic primal-dual variance-reduced algorithm with proximal stabilization for spectral risk minimization, claiming the first convergence guarantee for the unsmoothed problem with near-optimal O~(1/sqrt(eps)) rate.
Problem
Stochastic optimization of spectral risk measures (CVaR, ESRM, Extremile) over n samples, where sample weights depend on the full loss ordering, making unbiased stochastic subgradients costly and prior methods either lack convergence to the true optimum or are slow.
Approach
Reformulate the spectral risk as a max over a permutahedron of weighted losses, then run a primal-dual method with proximal terms on the dual variable (stabilizing the trajectory) and an SVRG-style variance-reduced proximal SGD on the primal, with momentum on losses, avoiding smoothing by a strongly concave term.
Key results
- Theory: SOREL achieves E||w_K - w*||^2 = O(G^2/(mu^2 K^2)), giving total sample complexity O~(n G/(mu sqrt(eps))) i.e. near-optimal O~(1/sqrt(eps)) rate.
- Experiments on five regression datasets with least squares and L2 regularization: SOREL outperforms SGD, LSVRG, and Prospect in sample complexity and runtime in most cases.
- SOREL converges to the true optimum in all settings, while LSVRG and Prospect often fail to reach it; in power dataset Prospect has better sample complexity but SOREL is faster in runtime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SOREL instead of existing baselines | Spectral risk minimization on yacht, energy, concrete, kin8nm, and power · Five regression benchmarks; ESRM, Extremile, and CVaR | sample complexity and runtime | Helped |
| Use SOREL instead of Prospect | Power · Power; spectral risks | sample complexity | Hurt |
| Use SOREL instead of Prospect | Power · Power; spectral risks | runtime | Helped |
| Use minibatching with batch size 64 | SOREL and baseline algorithms · Five regression benchmarks | convergence rate | Helped |
| Remove the proximal term from the lambda update (ablation) | Primal-dual spectral risk optimization · One-dimensional toy example | convergence | Hurt |
Surprising findings
- LSVRG and Prospect often fail to reach the true optimal point of the original spectral risk despite smoothing-based guarantees.
- Plain SGD fails to converge due to inherent bias in spectral risk subgradients.
Limitations
- Convergence analysis restricted to convex losses and strongly convex regularizer; nonconvex case left open.
- Theory uses a reference variant (averaged iterates) that differs from the practical last-iterate implementation; the remark leaves full rigor for the practical version beyond scope.
- Experiments limited to linear least-squares regression on five small/medium UCI datasets; SOREL lags Prospect in sample complexity on power and in CVaR on power with minibatching.
Experimental setup
Datasets: yacht energy concrete kin8nm power
Benchmarks: yacht energy concrete kin8nm power
Metrics: suboptimality vs passes suboptimality vs CPU runtime
Baselines: SGD LSVRG Prospect L-BFGS
Builds on: SVRG Prospect LSVRG L-BFGS
Closest papers by meaning
- On the Local Minima of the Empirical Risk (NeurIPS 2018 · similarity 0.87)
- Supervised Learning with General Risk Functionals (ICML 2022 · similarity 0.87)
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.85)
- f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization (ICLR 2024 · similarity 0.85)
- Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms (NeurIPS 2024 · similarity 0.85)
- Tight Lower Bounds and Improved Convergence in Performative Prediction (NeurIPS 2025 · similarity 0.84)
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.