A New Bound on the Generalization Rate of Sampled Convex Programs

This paper deals with the sampled scenarios approach to robust convex programming. It has been shown in previous works that by randomly sampling a sufficient number of constraints among the (possibly) infinite constraints of a robust convex program, one obtains a standard convex optimization problem whose solution is 'approximately feasible', in a probabilistic sense, for the original robust convex program. This is a generalization property in the learning theoretic sense, since the satisfaction of a certain number of 'training' constraints entails the satisfaction of other 'unseen' constraints. In this paper we provide a new efficient bound on the generalization rate of sampled convex programs, and show an example of application to a robust control design problem