Rademacher penalties and structural risk minimization

We suggest a penalty function to be used in various problems of structural risk minimization. This penalty is data dependent and is based on the sup-n orm of the so-called Rademacher process indexed by the underlying class of functions (sets), The standard complexity penalties, used in learning probl ems and based on the VC-dimensions of the classes, are conservative upper b ounds tin a probabilistic sense, uniformly over the set of all underlying d istributions) for the penalty we suggest. Thus, For a particular distributi on of training examples, one can expect better performance of learning algo rithms with the data-driven Rademacher penalties. We obtain oracle inequali ties for the theoretical risk of estimators, obtained by structural minimiz ation of the empirical risk with Rademacher penalties. The inequalities imp ly some form of optimality of the empirical risk minimizers. We also sugges t an iterative approach to structural risk minimization with Rademacher pen alties, in which the hierarchy of classes is not given in advance, but is d etermined in the data-driven iterative process of risk minimization, We pro ve probabilistic oracle inequalities for the theoretical risk of the estima tors based on this approach as well.