Revisiting statistical learning theory for uncertain feasibility and optimization problems

In this paper, we study two general semi-infinite programming problems by means of statistical learning theory. The sample size results obtained with this approach are generally considered to be very conservative by the control community. The main contribution of this paper is to demonstrate that this is not necessarily the case. Using as a starting point one-side results from statistical learning theory, we obtain bounds on the number of required samples that are manageable for "reasonable" values of confidence delta and accuracy isin. In particular, we provide sample size bounds growing with 1/isin ln 1/isin instead of the usual 1/isin² ln 1/isin² dependence.