The internal growth function: a more general PAC framework for scenario decision making
(2026) Transactions on Machine Learning Research — (2026)
Files
TMLR_Internal_Growth.pdf
Open Access - Adobe PDF
- 625.42 KB
Details
- Authors
- Abstract
- This paper introduces a new PAC framework for scenario decision-making problems. Scenario decision making consists in making a decision that satisfies a probabilistic constraint (also called a chance constraint) from finitely many sampled realizations (called scenarios) of the constraint. PAC bounds are sufficient conditions on the number of samples to guarantee with high confidence that the sample-based decision satisfies the true constraint with a prescribed probability. Existing PAC bounds rely on intrinsic properties of the problem, such as convexity (Calafiore and Campi, 2005), finite VC dimension (Alamo et al., 2009) or existence of a compression scheme (Margellos et al., 2014). While powerful in some applications, these PAC bounds can be vacuous (or infinite) when the properties are not satisfied. In this paper, we propose a new PAC framework, leading to PAC bounds that are not vacuous for a strictly larger class of scenario decision-making problems. This bound is based on the novel notion of “internal growth”, which adapts the notion of “growth function” from classical machine learning (Vapnik and Chervonenkis, 1968) to scenario decision making. We also relate this notion to other novel properties of the system, such as the k-VC dimension. Furthermore, we show a partial converse result: namely, that for the family of stable monotone scenario decision algorithms, the algorithm is PAC if and only if it satisfies our criterion. Finally, we demonstrate the usefulness of our framework, and compare with existing approaches, on practical problems.
- Affiliations
Citations
Berger, G., & Jungers, R. (2026). The internal growth function: a more general PAC framework for scenario decision making. Transactions on Machine Learning Research. Accepted/in-press. https://hdl.handle.net/2078.5/267709 (Original work published 2026)