Asymptotically Optimal Regularization in Smooth Parametric Models

pages

English

Documents

Écrit par
Francis Bach

Publié par
profil-zyak-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-zyak-2012

Nombre de lectures

Langue

English

Niveau: Supérieur, Doctorat, Bac+8
Asymptotically Optimal Regularization in Smooth Parametric Models Percy Liang University of California, Berkeley Francis Bach INRIA - Ecole Normale Superieure, France Guillaume Bouchard Xerox Research Centre Europe, France Michael I. Jordan University of California, Berkeley Abstract Many types of regularization schemes have been employed in statistical learning, each motivated by some assumption about the problem domain. In this paper, we present a unified asymptotic analysis of smooth regularizers, which allows us to see how the validity of these assumptions impacts the success of a particular regularizer. In addition, our analysis motivates an algorithm for optimizing regu- larization parameters, which in turn can be analyzed within our framework. We apply our analysis to several examples, including hybrid generative-discriminative learning and multi-task learning. 1 Introduction Many problems in machine learning and statistics involve the estimation of parameters from finite data. Although empirical risk minimization has favorable limiting properties, it is well known that this procedure can overfit on finite data. Hence, various forms of regularization have been employed to control this overfitting. Regularizers are usually chosen based on assumptions about the problem domain at hand. For example, in classification, we might use L2 regularization if we expect the data to be separable with a large margin.

regularizer bias

worse than

oracle

oracle regularization

relative risk

parameters ? ?

james-stein estimator

better when

Voir

Publié par

profil-zyak-2012

Nombre de lectures

Langue

English

Asymptotically Optimal Regularization in Smooth Parametric Models

Percy Liang University of California, Berkeley pliang@cs.berkeley.edu

Francis Bach  INRIA-EcoleNormaleSuperieure,France francis.bach@ens.fr

Guillaume Bouchard Xerox Research Centre Europe, France Guillaume.Bouchard@xrce.xerox.com

Abstract

Michael I. Jordan University of California, Berkeley jordan@cs.berkeley.edu

Many types of regularization schemes have been employed in statistical learning, each motivated by some assumption about the problem domain. In this paper, we present a uniﬁed asymptotic analysis of smooth regularizers, which allows us to see how the validity of these assumptions impacts the success of a particular regularizer. In addition, our analysis motivates an algorithm for optimizing regu-larization parameters, which in turn can be analyzed within our framework. We apply our analysis to several examples, including hybrid generative-discriminative learning and multi-task learning.

Introduction

Many problems in machine learning and statistics involve the estimation of parameters from ﬁnite data. Although empirical risk minimization has favorable limiting properties, it is well known that this procedure can overﬁt on ﬁnite data. Hence, various forms of regularization have been employed to control this overﬁtting. Regularizers are usually chosen based on assumptions about the problem domain at hand. For example, in classiﬁcation, we might useL2regularization if we expect the data to be separable with a large margin. We might regularize with a generative model if we think it is roughly well-speciﬁed [7, 20, 15, 17]. In multi-task learning, we might penalize deviation between parameters across tasks if we believe the tasks to be similar [3, 12, 2, 13].

In each case, we would like (1) a procedure for choosing the parameters of the regularizer (for exam-ple, its strength) and (2) an analysis that shows the amount by which regularization reduces expected risk, expressed as a function of the compatibility between the regularizer and the problem domain. In this paper, we address these two points by developing an asymptotic analysis of smooth regular-izers for parametric problems. The key idea is to derive a second-order Taylor approximation of the expected risk, yielding a simple and interpretable quadratic form which can be directly minimized with respect to the regularization parameters. We ﬁrst develop the general theory (Section 2) and then apply it to some examples of common regularizers used in practice (Section 3).

General theory

We use uppercase letters (e.g.,L, R, Z) to denote random variables and script letters (e.g.,L,R,I) to denote constant limits of random variables. For aλ-parametrized differentiable functionθ7→ ... ˙ ¨ f(λ;θ), letf,f, andfdenote the ﬁrst, second and third derivatives offwith respect toθ, and −α letrf(λ;θ)denote the derivative with respect toλ. LetXn=Op(n)denote a sequence of

Voir