ESTIMATION BOUNDS AND SHARP ORACLE INEQUALITIES OF REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

We obtain estimation error rates and sharp oracle inequalities for regularization procedures of the form (f ) over cap is an element of argmin(f is an element of F) (1/N Sigma(N )(i=1)l(f) (X-i, Y-i) + lambda parallel to f parallel to) when parallel to . parallel to is any norm, F is a convex class of functions and l is a Lipschitz loss function satisfying a Bernstein condition over F. We explore both the bounded and sub-Gaussian stochastic frameworks for the distribution of the f (X-i)'s, with no assumption on the distribution of the Y-i's. The general results rely on two main objects: a complexity function and a sparsity equation, that depend on the specific setting in hand (loss l and norm parallel to . parallel to). As a proof of concept, we obtain minimax rates of convergence in the following problems: (1) matrix completion with any Lipschitz loss function, including the hinge and logistic loss for the so-called 1-bit matrix completion instance of the problem, and quantile losses for the general case, which enables to estimate any quantile on the entries of the matrix; (2) logistic LASSO and variants such as the logistic SLOPE, and also shape constrained logistic regression; (3) kernel methods, where the loss is the hinge loss, and the regularization function is the RKHS norm.