PAC-Bayesian Bound for the Conditional Value at Risk

Conditional Value at Risk (CVaR) is a family of "coherent risk measures" which generalize the traditional mathematical expectation. Widely used in mathematical finance, it is garnering increasing interest in machine learning, e.g., as an alternate approach to regularization, and as a means for ensuring fairness. This paper presents a generalization bound for learning algorithms that minimize the CVaR of the empirical loss. The bound is of PAC-Bayesian type and is guaranteed to be small when the empirical CVaR is small. We achieve this by reducing the problem of estimating CVaR to that of merely estimating an expectation. This then enables us, as a by-product, to obtain concentration inequalities for CVaR even when the random variable in question is unbounded.

• Publication year

  2020

• Venue

  Neural Information Processing Systems

• Publication date

  2020-06-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2006.14763
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• High‐dimensional Statistics: A Non‐asymptotic Viewpoint, Martin J.Wainwright, Cambridge University Press, 2019, xvii 552 pages, £57.99, hardback ISBN: 978‐1‐1084‐9802‐9

  2020influential reference
• An Exponential Tail Bound for Lq Stable Learning Rules. Application to k-Folds Cross-Validation

  2019cited by this paper
• PAC-Bayes Un-Expected Bernstein Inequality

  2019cited by this paper
• Adaptive Sampling for Stochastic Risk-Averse Learning

  2019cited by this paper
• Sharper bounds for uniformly stable algorithms

  2019influential reference
• Concentration of risk measures: A Wasserstein distance approach

  2019influential reference
• Concentration Inequalities for Conditional Value at Risk

  2019cited by this paper
• A Primer on PAC-Bayesian Learning

  2019cited by this paper
• Fairness risk measures

  2019cited by this paper
• Concentration bounds for empirical conditional value-at-risk: The unbounded case

  2018influential reference
• Learning Models with Uniform Performance via Distributionally Robust Optimization

  2018cited by this paper
• Risk-aware multi-armed bandit problem with application to portfolio selection

  2017cited by this paper
• Robust Adversarial Reinforcement Learning

  2017cited by this paper
• Stability revisited: new generalisation bounds for the Leave-one-Out

  2016cited by this paper
• Variance-based Regularization with Convex Objectives

  2016cited by this paper
• Optimizing the CVaR via Sampling

  2014cited by this paper
• Algorithms for CVaR Optimization in MDPs

  2014cited by this paper
• Concentration Inequalities: A Nonasymptotic Theory of Independence

  2013cited by this paper
• PAC-Bayes-Empirical-Bernstein Inequality

  2013cited by this paper
• Actor-Critic Algorithms for Risk-Sensitive MDPs

  2013cited by this paper
• The fundamental risk quadrangle in risk management, optimization and statistical estimation

  2013influential reference
• Entropic Value-at-Risk: A New Coherent Risk Measure

  2012cited by this paper
• $ \nu$ -Support Vector Machine as Conditional Value-at-Risk Minimization

  2011cited by this paper
• Nonparametric Return Distribution Approximation for Reinforcement Learning

  2010cited by this paper
• Deviation inequalities for an estimator of the conditional value-at-risk

  2010influential reference
• A robust approach based on conditional value-at-risk measure to statistical learning problems

  2009cited by this paper
• Empirical Bernstein Bounds and Sample-Variance Penalization

  2009cited by this paper
• Technical Note - A Risk-Averse Newsvendor Model Under the CVaR Criterion

  2009cited by this paper
• Concentration Inequalities

  2008cited by this paper
• Large deviations bounds for estimating conditional value-at-risk

  2007influential reference
• PAC-BAYESIAN SUPERVISED CLASSIFICATION: The Thermodynamics of Statistical Learning

  2007cited by this paper
• Prediction, learning, and games

  2006cited by this paper
• A Note on the PAC Bayesian Theorem

  2004cited by this paper
• PAC-Bayesian Stochastic Model Selection

  2003influential reference
• PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification

  2003cited by this paper
• Mirror descent and nonlinear projected subgradient methods for convex optimization

  2003cited by this paper
• PAC-Bayes & Margins

  2002cited by this paper
• Stability and Generalization

  2002cited by this paper
• Optimization of conditional value-at risk

  2000cited by this paper
• Some Remarks on the Value-at-Risk and the Conditional Value-at-Risk

  2000cited by this paper
• Coherent Measures of Risk

  1999influential reference
• Probabilistic methods for algorithmic discrete mathematics

  1998cited by this paper
• Decision, probability, and utility: Risk, ambiguity, and the Savage axioms

  1988cited by this paper
• $I$-Divergence Geometry of Probability Distributions and Minimization Problems

  1975influential reference
• Asymptotic evaluation of certain Markov process expectations for large time

  1975influential reference
• Le comportement de l'homme rationnel devant le risque : critique des postulats et axiomes de l'ecole americaine

  1953cited by this paper
• Concentration

  1894cited by this paper

• Generalizing the Fano inequality further

  2026cites this paper
• Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?

  2025cites this paper
• MFRLMO: Model-free reinforcement learning for multi-objective optimization of apache spark

  2024cites this paper
• Integration of Conditional Value-at-Risk (CVaR) in Multi-Objective Optimization

  2024cites this paper
• Group Distributionally Robust Dataset Distillation with Risk Minimization

  2024influential citation
• Concentration Bounds for Optimized Certainty Equivalent Risk Estimation

  2024cites this paper
• Improved Concentration Bound for CVaR

  2024cites this paper
• Comparing Comparators in Generalization Bounds

  2023cites this paper
• Learning via Wasserstein-Based High Probability Generalisation Bounds

  2023cites this paper
• Safe Collaborative Filtering

  2023cites this paper
• Fast and Stable Convergence of Online SGD for CV@R-Based Risk-Aware Learning

  2022cites this paper
• On change of measure inequalities for f-divergences

  2022cites this paper
• Sample-Based Bounds for Coherent Risk Measures: Applications to Policy Synthesis and Verification

  2022cites this paper
• Risk of Stochastic Systems for Temporal Logic Specifications

  2022cites this paper
• Software reliability prediction: A survey

  2022cites this paper
• STL Robustness Risk over Discrete-Time Stochastic Processes

  2021cites this paper
• Online Estimation and Optimization of Utility-Based Shortfall Risk

  2021cites this paper
• Superquantiles at Work: Machine Learning Applications and Efficient Subgradient Computation

  2021cites this paper
• On Empirical Risk Minimization with Dependent and Heavy-Tailed Data

  2021cites this paper
• A PAC-Bayesian Perspective on Structured Prediction with Implicit Loss Embeddings

  2020cites this paper
• Upper and Lower Bounds on the Performance of Kernel PCA

  2020cites this paper
• Noisy Linear Convergence of Stochastic Gradient Descent for CV@R Statistical Learning under Polyak-Łojasiewicz Conditions

  2020cites this paper
• Adaptive Sampling for Stochastic Risk-Averse Learning

  2019cites this paper