On the Connection Between Compression Learning and Scenario Based Single-Stage and Cascading Optimization Problems

We investigate the connections between compression learning and scenario based optimization. We first show how to strengthen, or relax the consistency assumption at the basis of compression learning and provide novel learnability conditions for the underlying algorithms. We then consider different constrained optimization problems affected by uncertainty represented by means of scenarios. We show that the compression learning perspective provides a unifying framework for scenario based optimization, since the issue of providing guarantees on the probability of constraint violation reduces to a learning problem for an appropriately chosen algorithm that satisfies some consistency assumption. To illustrate this, we revisit the scenario approach within the developed context. Moreover, using the compression learning machinery we provide novel results on the probability of constraint violation for the class of cascading optimization problems.