  This paper deals with the scenario approach to robust optimization. This
relies on a random sampling of the possibly infinite number of constraints
induced by uncertainties in the parameters of an optimization problem. Solving
the resulting random program yields a solution for which the quality is
measured in terms of the probability of violating the constraints for a random
value of the uncertainties, typically unseen before. Another central issue is
the determination of the sample complexity, i.e., the number of random
constraints (or scenarios) that one must consider in order to guarantee a
certain level of reliability. In this paper, we introduce the notion of margin
to improve upon standard results in this field. In particular, using tools from
statistical learning theory, we show that the sample complexity of a class of
random programs does not explicitly depend on the number of variables. In
addition, within the considered class, that includes polynomial constraints
among others, this result holds for both convex and nonconvex instances with
the same level of guarantees. We also derive a posteriori bounds on the
probability of violation and sketch a regularization approach that could be
used to improve the reliability of computed solutions on the basis of these
bounds.
