Guillaume O. Berger

Guillaume O. Berger, Raphaël M. Jungers

We consider the problem of repetitive scenario design where one has to solve repeatedly a scenario design problem and can adjust the sample size (number of scenarios) to obtain a desired level of risk (constraint violation probability). We propose an approach to learn on the fly the optimal sample size based on observed data consisting in previous scenario solutions and their risk level. Our approach consists in learning a function that represents the pdf (probability density function) of the risk as a function of the sample size. Once this function is known, retrieving the optimal sample size is straightforward. We prove the soundness and convergence of our approach to obtain the optimal sample size for the class of fixed-complexity scenario problems, which generalizes fully-supported convex scenario programs that have been studied extensively in the scenario optimization literature. We also demonstrate the practical efficiency of our approach on a series of challenging repetitive scenario design problems, including non-fixed-complexity problems, nonconvex constraints and time-varying distributions.

Guillaume O. Berger, Raphaël M. Jungers

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.

Guillaume O. Berger

Scenario decision making offers a flexible way of making decision in an uncertain environment while obtaining probabilistic guarantees on the risk of failure of the decision. The idea of this approach is to draw samples of the uncertainty and make a decision based on the samples, called "scenarios". The probabilistic guarantees take the form of a bound on the probability of sampling a set of scenarios that will lead to a decision whose risk of failure is above a given maximum tolerance. This bound can be expressed as a function of the number of sampled scenarios, the maximum tolerated risk, and some intrinsic property of the problem called the "compression size". Several such bounds have been proposed in the literature under various assumptions on the problem. We propose new bounds that improve upon the existing ones without requiring stronger assumptions on the problem.