Boosted CVaR Classification

Abstract

Many modern machine learning tasks require models with high tail performance, i.e. high performance over the worst-off samples in the dataset. This problem has been widely studied in fields such as algorithmic fairness, class imbalance, and risk-sensitive decision making. A popular approach to maximize the model's tail performance is to minimize the CVaR (Conditional Value at Risk) loss, which computes the average risk over the tails of the loss. However, for classification tasks where models are evaluated by the zero-one loss, we show that if the classifiers are deterministic, then the minimizer of the average zero-one loss also minimizes the CVaR zero-one loss, suggesting that CVaR loss minimization is not helpful without additional assumptions. We circumvent this negative result by minimizing the CVaR loss over randomized classifiers, for which the minimizers of the average zero-one loss and the CVaR zero-one loss are no longer the same, so minimizing the latter can lead to better tail performance. To learn such randomized classifiers, we propose the Boosted CVaR Classification framework which is motivated by a direct relationship between CVaR and a classical boosting algorithm called LPBoost. Based on this framework, we design an algorithm called $\alpha$-AdaLPBoost. We empirically evaluate our proposed algorithm on four benchmark datasets and show that it achieves higher tail performance than deterministic model training methods.

NeurIPS 2021. 16 pages, 4 figures

References in corpus (8)

• Wide Residual Networks
• Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization
• Fairness Without Demographics in Repeated Loss Minimization
• Does Distributionally Robust Supervised Learning Give Robust Classifiers?
• An Investigation of Why Overparameterization Exacerbates Spurious Correlations
• Class-Weighted Classification: Trade-offs and Robust Approaches
• DORO: Distributional and Outlier Robust Optimization
• Modeling the Second Player in Distributionally Robust Optimization