# PAC Learnability of Scenario Decision-Making Algorithms: Necessary Conditions and Sufficient Conditions

arXiv: https://arxiv.org/abs/2501.08887 · HTML: https://mlsanity.com/paper/2501.08887/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 15 Jan 2025.

## Builds on (most cited first, 7 of 7)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Compression, Generalization and Learning](https://mlsanity.com/paper/2301.12767/) (2023)
- [On the exact feasibility of convex scenario programs with discarded constraints](https://mlsanity.com/paper/2003.13433/) (2020)
- [Performance Bounds for the Scenario Approach and an Extension to a Class of Non-convex Programs](https://mlsanity.com/paper/1307.0345/) (2013)
- [A scenario approach for non-convex control design](https://mlsanity.com/paper/1401.2200/) (2014)
- [On the VC-dimension of half-spaces with respect to convex sets](https://mlsanity.com/paper/1907.01241/) (2019)

## Abstract (arXiv)

We investigate the Probably Approximately Correct (PAC) property of scenario decision algorithms, which refers to their ability to produce decisions with an arbitrarily low risk of violating unknown safety constraints, provided a sufficient number of realizations of these constraints are sampled. While several PAC sufficient conditions for such algorithms exist in the literature -- such as the finiteness of the VC dimension of their associated classifiers, or the existence of a compression scheme -- it remains unclear whether these conditions are also necessary. In this work, we demonstrate through counterexamples that these conditions are not necessary in general. These findings stand in contrast to binary classification learning, where analogous conditions are both sufficient and necessary for a family of classifiers to be PAC. Furthermore, we extend our analysis to stable scenario decision algorithms, a broad class that includes practical methods like scenario optimization. Even under this additional assumption, we show that the aforementioned conditions remain unnecessary. Furthermore, we introduce a novel quantity, called the dVC dimension, which serves as an analogue to the VC dimension for scenario decision algorithms. We prove that the finiteness of this dimension is a PAC necessary condition for scenario decision algorithms. This allows to (i) guide algorithm users and designers to recognize algorithms that are not PAC, and (ii) contribute to a comprehensive characterization of PAC scenario decision algorithms.