Boosted CVaR Classification
This work addresses the need for better tail performance in machine learning, which is crucial for applications like algorithmic fairness and risk-sensitive decision-making, though it is incremental as it builds on existing boosting techniques.
The paper tackles the problem of improving tail performance in classification tasks by showing that minimizing CVaR loss with deterministic classifiers is ineffective, and instead proposes using randomized classifiers to achieve better results. The proposed Boosted CVaR Classification framework, implemented as α-AdaLPBoost, empirically demonstrates higher tail performance on four benchmark datasets compared to deterministic methods.
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 $α$-AdaLPBoost. We empirically evaluate our proposed algorithm on four benchmark datasets and show that it achieves higher tail performance than deterministic model training methods.