  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{\epsilon})$ in terms of
$\epsilon$. Experiments on real datasets show that our algorithm outperforms
existing algorithms in most cases, both in terms of runtime and sample
complexity.
