  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.
