# Fast Computation of Superquantile-Constrained Optimization Through Implicit Scenario Reduction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 55 references that are in the map.
- First posted on arXiv 13 May 2024.

## Builds on (most cited first, 21 of 21)

- [Training Region-based Object Detectors with Online Hard Example Mining](https://mlsanity.com/paper/1604.03540/) (2016)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [Optimizing the CVaR via Sampling](https://mlsanity.com/paper/1404.3862/) (2014)
- [Fairness risk measures](https://mlsanity.com/paper/1901.08665/) (2019)
- [Probabilistically Robust Learning: Balancing Average- and Worst-case Performance](https://mlsanity.com/paper/2202.01136/) (2022)
- [A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems](https://mlsanity.com/paper/1607.05428/) (2016)
- [An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems](https://mlsanity.com/paper/1712.05910/) (2017)
- [Superquantiles at Work: Machine Learning Applications and Efficient Subgradient Computation](https://mlsanity.com/paper/2201.00508/) (2022)
- [Risk Measures and Upper Probabilities: Coherence and Stratification](https://mlsanity.com/paper/2206.03183/) (2022)
- [An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for Linear Programming](https://mlsanity.com/paper/1903.09546/) (2019)
- [On efficiently solving the subproblems of a level-set method for fused lasso problems](https://mlsanity.com/paper/1706.08732/) (2017)
- [Certifiable Risk-Based Engineering Design Optimization](https://mlsanity.com/paper/2101.05129/) (2021)
- [On the R-superlinear convergence of the KKT residues generated by the augmented Lagrangian method for convex composite conic programming](https://mlsanity.com/paper/1706.08800/) (2017)
- [Superquantile-based learning: a direct approach using gradient-based optimization](https://mlsanity.com/paper/2201.00505/) (2022)
- [An O(nlog(n)) Algorithm for Projecting Onto the Ordered Weighted ℓ1 Norm Ball](https://mlsanity.com/paper/1505.00870/) (2015)
- [Variational Analysis of the Ky Fan k-norm](https://mlsanity.com/paper/1601.07430/) (2016)
- [Imbalanced Classification in Medical Imaging via Regrouping](https://mlsanity.com/paper/2210.12234/) (2022)
- [On The Use of Risk Measures in Digital Twins to Identify Weaknesses in Structures](https://mlsanity.com/paper/2311.12206/) (2023)
- [Fast projection onto the ordered weighted ℓ1 norm ball](https://mlsanity.com/paper/2002.05004/) (2020)
- [On O(n) Algorithms for Projection onto the Top-k-sum Sublevel Set](https://mlsanity.com/paper/2310.07224/) (2023)

## Abstract (arXiv)

Superquantiles have recently gained significant interest as a risk-aware metric for addressing fairness and distribution shifts in statistical learning and decision making problems. This paper introduces a fast, scalable and robust second-order computational framework to solve large-scale optimization problems with superquantile-based constraints. Unlike empirical risk minimization, superquantile-based optimization requires ranking random functions evaluated across all scenarios to compute the tail conditional expectation. While this tail-based feature might seem computationally unfriendly, it provides an advantageous setting for a semismooth-Newton-based augmented Lagrangian method. The superquantile operator effectively reduces the dimensions of the Newton systems since the tail expectation involves considerably fewer scenarios. Notably, the extra cost of obtaining relevant second-order information and performing matrix inversions is often comparable to, and sometimes even less than, the effort required for gradient computation. Our developed solver is particularly effective when the number of scenarios substantially exceeds the number of decision variables. In synthetic problems with linear and convex diagonal quadratic objectives, numerical experiments demonstrate that our method outperforms existing approaches by a large margin: It achieves speeds more than 750 times faster for linear and quadratic objectives than the alternating direction method of multipliers as implemented by OSQP for computing low-accuracy solutions. Additionally, it is up to 25 times faster for linear objectives and 70 times faster for quadratic objectives than the commercial solver Gurobi, and 20 times faster for linear objectives and 30 times faster for quadratic objectives than the Portfolio Safeguard optimization suite for high-accuracy solution computations.