# SOREL: A Stochastic Algorithm for Spectral Risks Minimization

arXiv: https://arxiv.org/abs/2407.14618 · HTML: https://mlsanity.com/paper/2407.14618/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 36 of its 66 references that are in the map.
- First posted on arXiv 19 Jul 2024.

## Builds on (most cited first, 30 of 36)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Risk-Constrained Reinforcement Learning with Percentile Risk Criteria](https://mlsanity.com/paper/1512.01629/) (2015)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [Fairness risk measures](https://mlsanity.com/paper/1901.08665/) (2019)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Learning with Average Top-k Loss](https://mlsanity.com/paper/1705.08826/) (2017)
- [Ordered SGD: A New Stochastic Optimization Framework for Empirical Risk Minimization](https://mlsanity.com/paper/1907.04371/) (2019)
- [Understanding the Role of Momentum in Stochastic Gradient Methods](https://mlsanity.com/paper/1910.13962/) (2019)
- [Distributionally Robust Learning](https://mlsanity.com/paper/2108.08993/) (2021)
- [Variance Reduced Stochastic Gradient Descent with Neighbors](https://mlsanity.com/paper/1506.03662/) (2015)
- [Adaptive Sampling for Stochastic Risk-Averse Learning](https://mlsanity.com/paper/1910.12511/) (2019)
- [A Wasserstein distance approach for concentration of empirical risk estimates](https://mlsanity.com/paper/1902.10709/) (2019)
- [Stochastic Primal-Dual Algorithms with Faster Convergence than O(1/√T) for Problems without Bilinear Structure](https://mlsanity.com/paper/1904.10112/) (2019)
- [Stop Wasting My Gradients: Practical SVRG](https://mlsanity.com/paper/1511.01942/) (2015)
- [Risk-Aware Planning and Assignment for Ground Vehicles using Uncertain Perception from Aerial Vehicles](https://mlsanity.com/paper/2003.11675/) (2020)
- [Spectral risk-based learning using unbounded losses](https://mlsanity.com/paper/2105.04816/) (2021)
- [Level Constrained First Order Methods for Function Constrained Optimization](https://mlsanity.com/paper/2205.08011/) (2022)
- [Stochastic Optimization for Spectral Risk Measures](https://mlsanity.com/paper/2212.05149/) (2022)

## Abstract (arXiv)

The spectral risk has wide applications in machine learning, especially in real-world decision-making, where people are not only concerned with models' average performance. By assigning different weights to the losses of different sample points, rather than the same weights as in the empirical risk, it allows the model's performance to lie between the average performance and the worst-case performance. In this paper, we propose SOREL, the first stochastic gradient-based algorithm with convergence guarantees for the spectral risk minimization. Previous algorithms often consider adding a strongly concave function to smooth the spectral risk, thus lacking convergence guarantees for the original spectral risk. We theoretically prove that our algorithm achieves a near-optimal rate of widetildeO(1/√ε) in terms of ε. Experiments on real datasets show that our algorithm outperforms existing algorithms in most cases, both in terms of runtime and sample complexity.