SOREL: A Stochastic Algorithm for Spectral Risks Minimization
This addresses the need for efficient optimization in machine learning for real-world decision-making where performance beyond averages is critical, representing a novel algorithmic contribution.
The paper tackles the problem of spectral risk minimization, which allows models to balance average and worst-case performance by weighting losses differently, and proposes SOREL, a stochastic gradient-based algorithm with proven convergence guarantees, achieving a near-optimal rate of O~(1/√ε) and outperforming existing methods in runtime and sample complexity on real datasets.
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 $\widetilde{O}(1/\sqrtε)$ 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.