Complexity is an effective observable to tune early stopping in scenario optimization

Scenario optimization is a broad scheme for data-driven decision-making in which experimental observations act as constraints on the feasible domain for the optimization variables. The probability with which the solution is not feasible for a new, out-of-sample, observation is called the "risk". Recent studies have unveiled the profound link that exists between the risk and a properly defined notion of "complexity" of the scenario solution. In the present work, we leverage these results to introduce a new scheme where the size of the sample of scenarios is iteratively tuned to the current complexity of the solution so as to eventually hit a desired level of risk. This new scheme implies a substantial saving of data as compared to previous approaches. The paper presents the new method, offers a full theoretical study and illustrates it on a control problem.