The Internal Growth Function: A More General PAC Framework for Scenario Decision Making

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 \emph{and only if} it satisfies our criterion. Finally, we demonstrate the usefulness of our framework, and compare with existing approaches, on practical problems.