Apprentissage statistique, parcimonie et Langevin Monte Carlo

Alexandre Tsybakov

Description

IntroductionSparsity oracle inequalities(SOI)BIC and LASSODantzig selector and LASSO for linear regressionSparse exponential weighting (SEW)Apprentissage statistique, parcimonie et LangevinMonte CarloAlexandre TsybakovLaboratoire de Statistique, CREST ,Laboratoire de Probabilit´es et Mod`eles Al´eatoires,Universit´e Paris 6etCMAP, Ecole PolytechniqueDijon, le 26 novembre 2009Alexandre TsybakovIntroductionSparsity oracle inequalities(SOI)Model, dictionary, approximationBIC and LASSOSparsityDantzig selector and LASSO for linear regressionSparse exponential weighting (SEW)Nonparametric regression model (fixed design)dAssume that we observe the pairs (X ,Y ),...,(X ,Y )∈R ×R1 1 n nwhereY = f(X )+ξ , i = 1,...,n.i i idRegression function f :R →R is unknown2Errors ξ are independent GaussianN(0,σ ) random variables.idX ∈R are arbitrary fixed (non-random) points.iWe want to estimate f based on the data (X ,Y ),...,(X ,Y ).1 1 n nAlexandre TsybakovIntroductionSparsity oracle inequalities(SOI)Model, dictionary, approximationBIC and LASSOSparsityDantzig selector and LASSO for linear regressionSparse exponential weighting (SEW)Approximating function, dictionaryWe assume that there exists a function f (x) (known as a functionθof θ and x) such thatf ≈ fθfor some θ = (θ ,...,θ ).1 MPossibly M nAlexandre TsybakovIntroductionSparsity oracle inequalities(SOI)Model, dictionary, approximationBIC and LASSOSparsityDantzig selector and LASSO ...

Informations

• Publié par: Thion
• Nombre de lectures: 72
• Langue: English

Extrait

Introduction Sparsity oracle inequalities(SOI) BIC and LASSO Dantzig selector and LASSO for linear regression Sparse exponential weighting (SEW)

Apprentissage statistique, parcimonie et Langevin Monte Carlo

Alexandre Tsybakov

Laboratoire de Statistique, CREST , LaboratoiredeProbabilit´esetMod`elesAle´atoires, Universit´eParis6 et CMAP, Ecole Polytechnique

Dijon, le 26 novembre 2009

AlexandreTsybakov

Introduction Sparsity oracle inequalities(SOI) Model, dictionary, approximation DantzigselectorandLASSOforl B i I n C ea a r n r d eg L re A s S si S o O n Sparsity Sparse exponential weighting (SEW)

Nonparametric regression model (fixed design)

Assume that we observe the pairs (X 1 ,Y 1 ), . . . ,(X n ,Y n )∈R d ×R where

Y i =f(X i ) +ξ i ,i= 1, . . . ,n.

Regression functionf:R d →Ris unknown Errorsξ i are independent GaussianN(0, σ 2 ) random variables. X i ∈R d are arbitrary fixed (non-random) points.

We want to estimatefbased on the data (X 1 ,Y 1 ), . . . ,(X n ,Y n ).

AlexandresTbykavo

Introduction Sparsity oracle inequalities(SOI) Model, dictionary, approximation DantzigselectorandLASSOforl B i I n C ea a r n r d eg L re A s S si S o O n Sparsity Sparse exponential weighting (SEW)

Approximating function, dictionary

We assume that there exists a function f θ (x) (known as a function ofθandx) such that f≈f θ

for someθ= (θ 1 , . . . , θ M ).

lAxenard

PossiblyMn

esTbykavo

Introduction Sparsity oracle inequalities(SOI) Model, dictionary, approximation DantzigselectorandLASSOforl B i I n C ea a r n r d eg L re A s S si S o O n Sparsity Sparse exponential weighting (SEW)

Example: linear approximation, dictionary

Letf 1 , . . . ,f M be a finitedictionary of functions,f j :R d →R. We approximate the regression functionfby linear combination

M f θ (x) = X θ j f j (x) with weightsθ= (θ 1 , . . . , θ M ). j=1

We believe that

M f(x)≈ X θ j f j (x) j=1

for someθ= (θ 1 , . . . , θ M ).

AlexandresTbykavo

Introduction Sparsityoraclein B e I q C u a al n it d ie L s( A S S O S I O ) Model, dictionary, approximation Dantzig selector and LASSO for linear regression Sparsity Sparse exponential weighting (SEW) Scenarios for linear approximation (LinReg) exists thereExact equality:θ ∗ ∈R M such that f= f θ ∗ = P j M =1 θ j ∗ f j (linear regression, with possiblyMnparameters); (NPReg)f 1 , . . . ,f M are the firstMfunctions of a basis (usually orthonormal) andM≤n, there existsθ ∗ such thatf−f θ ∗ is small:nonparametric estimation of regression; (Agg)aggregation of arbitrary estimators: in this casef 1 , . . . ,f M are preliminary estimators offbased on a training sample independent of the observations (X 1 ,Y 1 ), . . . ,(X n ,Y n ); Weak learning, additive models etc. Alexandre Tsybakov

Introduction Sparsity oracle inequalities(SOI) BIC and LASSO S M p o a d rs e i l t , y dictionary, approximation Dantzig selector and LASSO for linear regression Sparse exponential weighting (SEW)

Example: nonlinear approximation

We consider the generalized linear (or single-index) model

f θ (x) =G(θ T x)

whereG:R→Ris a known (or unknown) function.

Thus, we believe that

f(x)≈G(θ T x)

for someθ= (θ 1 , . . . , θ M ), possibly withMn.

AlexandreTsybakov

Introduction Sparsity oracle inequalities(SOI) BIC and LASSO Dantzig selector and LASSO for linear regression Sparse exponential weighting (SEW)

Sparsity of a vector

Model, dictionary, approximation Sparsity

The number of non-zero coordinates ofθ:

M M(θ) = X I {θ j 6=0} j=1

The valueM(θ) characterizes thesparsityof vectorθ∈R M : the smallerM(θ), the “sparser”θ.

AlexandresTbykavo

Introduction Sparsity oracle inequalities(SOI) BIC and LASSO Dantzig selector and LASSO for linear regression Sparse exponential weighting (SEW)

Sparsity of the model

Model, dictionary, approximation Sparsity

Intuitive formulation of sparsity assumption:

f(x)≈f θ (“fis well approximated by f θ ”)

where the vectorθ= (θ 1 , . . . , θ M ) is sparse:

lAxenardeT

M(θ)M.

ysabokv

Introduction Sparsity oracle inequalities(SOI) Model, dictionary, approximation DantzigselectorandLASSOforl B i I n C ea a r n r d eg L re A s S si S o O n Sparsity Sparse exponential weighting (SEW)

Sparsity and dimension reduction

b Letθ OLS  Letbe the ordinary least squares (OLS) estimator. f θ be linear result:approximation. Elementary

2 σ 2 min(M,n) Ekf θ b OLS −fk n 2 ≤ kf−f θ k n + n

for anyθ∈R M wherek ∙ k n is the empirical norm: v = u 1 X n f 2 (X i ). kfk n t n i=1

AlexandresTbyakov

Introduction Sparsity oracle inequalities(SOI) BIC and LASSO S M p o ar d s e i l t , y dictionary, approximation Dantzig selector and LASSO for linear regression Sparse exponential weighting (SEW)

Sparsity and dimension reduction

For anyθ∈R M the “oracular” OLS that acts only on the relevant M(θ)<ncoordinates satisfies

Ekf θ o b r O a L c S le −fk n 2 ≤ kf−f θ k n 2 + σ 2 n M(θ) .

This is only an OLS oracle, not an estimator. The set of relevant coordinates should be known.

AlexandreTsybakov

Introduction Sparsity oracle inequalities(SOI) BIC and LASSOImplications of SOI Dantzig selector and LASSO for linear regression Sparse exponential weighting (SEW)

Sparsity oracle inequalities

Do there exist true estimators with similar behavior? Basic idea: b b b Choose some suitable data-driven weightsθ= (θ 1 , . . . , θ M ) and estimatefby

M f b (x) = f θ b (x) = X θ b j f j (x). j=1

What to do when the approximation is non-linea b r (ex. G(θ T x))? Should we also plug in an estimatorθ? b ˜ ˜ Can we findθsuch thatf= f θ b orfdefined in differently satisfies

Ekf ˜ −fk 2 n .kf−f θ k n 2 + σ 2 M(θ) ,∀θ? n

AlexandreTsybakov