Boosted CVaR Classification

• URL: http://arxiv.org/abs/2110.13948v1
• Date: Tue, 26 Oct 2021 18:27:25 GMT
• Title: Boosted CVaR Classification
• Authors: Runtian Zhai, Chen Dan, Arun Sai Suggala, Zico Kolter, Pradeep Ravikumar
• Abstract summary: A popular approach to maximize the model's tail performance is to minimize the CVaR loss. We show that for classification tasks where models are evaluated by the zero-one loss, the minimizer of the average zero-one loss also minimizes the CVaR zero-one loss. We propose the Boosted CVaR Classification framework which is motivated by a direct relationship between CVaR and a classical boosting algorithm called LPBoost.
• Score: 44.731468512484824
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Provably Efficient CVaR RL in Low-rank MDPs [58.58570425202862]
  We study risk-sensitive Reinforcement Learning (RL) We propose a novel Upper Confidence Bound (UCB) bonus-driven algorithm to balance interplay between exploration, exploitation, and representation learning in CVaR RL. We prove that our algorithm achieves a sample complexity of $epsilon$-optimal CVaR, where $H$ is the length of each episode, $A$ is the capacity of action space, and $d$ is the dimension of representations.
  arXiv  Detail & Related papers  (2023-11-20T17:44:40Z)
• Robust Long-Tailed Learning via Label-Aware Bounded CVaR [36.26100472960534]
  We propose two novel approaches to improve the performance of long-tailed learning with a solid theoretical ground. Specifically, we introduce a Label-Aware Bounded CVaR loss to overcome the pessimistic result of the original CVaR. We additionally propose a LAB-CVaR with logit adjustment to stabilize the optimization process.
  arXiv  Detail & Related papers  (2023-08-29T16:07:18Z)
• A Model-Based Method for Minimizing CVaR and Beyond [7.751691910877239]
  We develop a variant of the prox-linear method for minimizing the Conditional Value-at-Risk (CVaR) objective. CVaR is a risk measure focused on minimizing worst-case performance, defined as the average of the top quantile of the losses. In machine learning, such a risk measure is useful to train more robust models.
  arXiv  Detail & Related papers  (2023-05-27T15:38:53Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)
• Learning by Minimizing the Sum of Ranked Range [58.24935359348289]
  We introduce the sum of ranked range (SoRR) as a general approach to form learning objectives. A ranked range is a consecutive sequence of sorted values of a set of real numbers. We explore two applications in machine learning of the minimization of the SoRR framework, namely the AoRR aggregate loss for binary classification and the TKML individual loss for multi-label/multi-class classification.
  arXiv  Detail & Related papers  (2020-10-05T01:58:32Z)
• Learning with CVaR-based feedback under potentially heavy tails [8.572654816871873]
  We study learning algorithms that seek to minimize the conditional value-at-risk (CVaR) We first study a general-purpose estimator of CVaR for potentially heavy-tailed random variables. We then derive a new learning algorithm which robustly chooses among candidates produced by gradient-driven sub-processes.
  arXiv  Detail & Related papers  (2020-06-03T01:08:29Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
  arXiv  Detail & Related papers  (2020-02-19T08:35:15Z)
• Statistical Learning with Conditional Value at Risk [35.4968603057034]
  We propose a risk-averse statistical learning framework wherein the performance of a learning algorithm is evaluated by the conditional value-at-risk (CVaR) of losses rather than the expected loss.
  arXiv  Detail & Related papers  (2020-02-14T00:58:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.