Workshop on Structure Adapting Methods - Abstract
Within the penalized model selection (PMS) approach the selected model is defined by minimization of penalized empirical risk. Such procedures enjoy nice algorithmic properties especially if both the empirical risk and the penalty function are convex functions of the parameter. A number of “oracle” risk bounds for such methods are available. However, the choice of penalty is critical and there is no unified approach for fixing this penalty. This paper presents another method of model selection based on a saddle point optimization (SP model selection). The basic observation behind the SP method is that the empirical risk minimizer is a saddle point of the bivariate function built as the difference between empirical risks of two models. An extension of this idea is to define the model selector via a saddle point of a penalized difference. The penalty is also a bivariate function and it has to be selected by the condition that the “oracle” model can be rejected against a larger model only with a very small probability.