A Semismooth Newton Augmented Lagrangian Method for Sparse Spectral Risk Optimization

Empirical risk minimization is a standard and effective paradigm for learning predictive models by minimizing average loss.

In high-stakes decision-making, however, an average-loss criterion may underrepresent rare but severe losses.

Spectral risk measures (SRMs) provide a principled framework by incorporating weighted order statistics of losses, but the induced nonsmoothness and nonseparability from sorting make the resulting optimization problems challenging.

We propose a relative inexact proximal augmented Lagrangian method with a semismooth Newton subproblem solver for solving SRM-based optimization problems.

Exploiting a dual reformulation and properties of the Moreau envelope, we reduce the subproblems to structured dual-variable formulations, significantly simplifying computation.

We provide explicit generalized Jacobian characterizations and tailor the pool adjacent violators algorithm for their efficient evaluation.

Numerical results on synthetic and real-data instances show that the proposed method attains lower running times than the tested ADMM baseline while producing comparable stationarity residuals and sparse solutions.