Spectral risk-based learning using unbounded losses

Matthew J. Holland, El Mehdi Haress

Abstract

In this work, we consider the setting of learning problems under a wide class of spectral risk (or "L-risk") functions, where a Lipschitz-continuous spectral density is used to flexibly assign weight to extreme loss values. We obtain excess risk guarantees for a derivative-free learning procedure under unbounded heavy-tailed loss distributions, and propose a computationally efficient implementation which empirically outperforms traditional risk minimizers in terms of balancing spectral risk and misclassification error.

Introduction

Standard Empirical Risk Minimization (ERM) is the bedrock of modern machine learning, yet it possesses a significant blind spot: it optimizes for average performance. By focusing solely on the mean, ERM can leave models vulnerable to rare but catastrophic errors, particularly in safety-critical applications. While practitioners have historically turned to Conditional Value-at-Risk (CVaR) to mitigate these risks by averaging the worst $\beta$% of losses, CVaR is often too rigid, assigning uniform weight to all losses above a specific threshold.

Spectral risks (or L-risks) offer a more sophisticated alternative. They allow for a user-specified, non-constant spectral density function to weight losses, providing a highly customizable framework for risk preference. However, spectral risks are notoriously difficult to optimize. They are typically non-smooth, computationally expensive to estimate, and highly sensitive to heavy-tailed, unbounded loss distributions. This research introduces a robust algorithm for optimizing spectral risks with formal theoretical guarantees and a practical, high-performance implementation.

Methodology

The proposed approach addresses the challenges of spectral risk optimization through three distinct mechanisms:

1. Derivative-Free Stochastic Mirror Descent

Because spectral risk functions are non-smooth, their exact gradients are often unavailable or difficult to compute. The authors utilize a stochastic smoothing technique, evaluating the loss at randomly perturbed parameter values (using noise drawn from a unit sphere). This allows for the construction of an unbiased gradient estimate for a "smoothed" version of the spectral risk, bypassing the non-differentiability of the original objective.

2. Robust Confidence Boosting

To handle the volatility of heavy-tailed data (assuming only finite variance), the authors implement a robust model selection strategy. The derivative-free algorithm is run $k$ independent times to generate a pool of candidate models. A robust M-estimator is then applied to a hold-out validation set to select the optimal candidate. This "median-of-means" style approach provides high-probability excess risk guarantees even when the underlying data is prone to extreme outliers.

3. Fast Gradient-Based Approximation

Recognizing that derivative-free methods can be computationally slow, the authors developed a "fast" implementation for real-world use. This method approximates the unknown Cumulative Distribution Function (CDF) of the losses using a parametric folded Normal distribution. By assuming this structure, the authors can apply the chain rule to compute approximate first-order gradients directly, significantly accelerating the training process.

Empirical Evaluation and Key Insights

The authors evaluated their methods against traditional ERM across eight standard multi-class classification benchmarks, including cifar10, mnist, fashion_mnist, and protein.

Key Results

  • Theoretical Sample Complexity: The authors proved that their derivative-free algorithm achieves a sample complexity of $\mathcal{O}(\epsilon^{-8})$ to reach an $\epsilon$ excess spectral risk. When paired with robust boosting, these guarantees hold even under bounded variance conditions.
  • Superior Generalization: Surprisingly, the "fast" spectral risk method consistently outperformed traditional ERM in terms of misclassification error across all eight datasets. This suggests that risk-averse optimization acts as a powerful regularizer; by forcing the model to address the most difficult examples, it improves overall generalization.
  • Computational Efficiency: The parametric CDF approximation allowed the "fast" method to achieve these results within the same number of epochs (50) as standard ERM, demonstrating that robust risk management does not require prohibitive computational overhead.

Discussion and Future Work

While this work provides a robust framework for spectral risk learning, several avenues for improvement remain. The theoretical sample complexity of $\mathcal{O}(\epsilon^{-8})$ is relatively slow compared to standard convex optimization rates, suggesting that multi-point gradient estimators could be used to improve convergence. Additionally, the "fast" method currently relies on a simple folded Normal assumption for the loss distribution; integrating more sophisticated statistical modeling could further enhance its utility.

Finally, the current theoretical proofs are restricted to finite-dimensional spaces ($\mathbb{R}^d$). Extending these guarantees to general Hilbert spaces—potentially through the use of Malliavin calculus—would allow these spectral risk techniques to be applied to kernel methods and other infinite-dimensional function spaces.

Summary updated

Abstract

In this work, we consider the setting of learning problems under a wide class of spectral risk (or "L-risk") functions, where a Lipschitz-continuous spectral density is used to flexibly assign weight to extreme loss values. We obtain excess risk guarantees for a derivative-free learning procedure under unbounded heavy-tailed loss distributions, and propose a computationally efficient implementation which empirically outperforms traditional risk minimizers in terms of balancing spectral risk and misclassification error.
BibTeX
@inproceedings{holland2022spectral,
  author = {Matthew J. Holland and El Mehdi Haress},
  title = {{Spectral risk-based learning using unbounded losses}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=yS5TSHLW0g},
}
Figure