Tight generalization guarantees for the sampling and discarding approach to scenario optimization

We consider the scenario approach theory to deal with convex optimization programs affected by uncertainty, which is in turn represented by means of scenarios. An approach to deal with such programs while trading feasibility to performance is known as sampling and discarding in the scenario approach literature. Existing bounds on the probability of constraint satisfaction for such programs are not tight. In this paper we use learning theoretic concepts based on the notion of compression to show that for a particular class of convex scenario programs, namely, the so called fully-supported ones, and under a particular scenario discarding scheme, a tight bound can be obtained. We illustrate our developments by means of an example that admits an analytic solution