A Theory of the Risk for Optimization with Relaxation and its Application to Support Vector Machines

In this paper we consider optimization with relaxation, an ample paradigm to\nmake data-driven designs. This approach was previously considered by the same\nauthors of this work in Garatti and Campi (2019), a study that revealed a\ndeep-seated connection between two concepts: risk (probability of not\nsatisfying a new, out-of-sample, constraint) and complexity (according to a\ndefinition introduced in paper Garatti and Campi (2019)). This connection was\nshown to have profound implications in applications because it implied that the\nrisk can be estimated from the complexity, a quantity that can be measured from\nthe data without any knowledge of the data-generation mechanism. In the present\nwork we establish new results. First, we expand the scope of Garatti and Campi\n(2019) so as to embrace a more general setup that covers various algorithms in\nmachine learning. Then, we study classical support vector methods - including\nSVM (Support Vector Machine), SVR (Support Vector Regression) and SVDD (Support\nVector Data Description) - and derive new results for the ability of these\nmethods to generalize. All results are valid for any finite size of the data\nset. When the sample size tends to infinity, we establish the unprecedented\nresult that the risk approaches the ratio between the complexity and the\ncardinality of the data sample, regardless of the value of the complexity.\n