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

• 成果类型: Article
• 署名作者: Alquier, Pierre; Cottet, Vincent; Lecue, Guillaume
• 署名单位: Universite Paris Saclay; Institut Polytechnique de Paris; ENSAE Paris; Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; ENSAE Paris
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/18-AOS1742
• 发表日期: 2019
• 页码: 2117-2144
• 关键词: matrix completion; Lasso; slope; geometry; rates

摘要

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.