Performance of empirical risk minimization in linear aggregation

Guillaume Lecué; Shahar Mendelson

doi:10.3150/15-BEJ701

Performance of empirical risk minimization in linear aggregation

Guillaume Lecué, Shahar Mendelson

Research output: Contribution to journal › Article › peer-review

24 Citations (Scopus)

Abstract

We study conditions under which, given a dictionary F = {f₁, . . . , f_M} and an i.i.d. sample (X_i,Y_i )N i=1, the empirical minimizer in span(F ) relative to the squared loss, satisfies that with high probability R(∼f ERM) ≤ inf f span(F )R(f )+ rN(M),where R() is the squared risk and rN(M) is of the order of M/N. Among other results, we prove that a uniform small-ball estimate for functions in span(F) is enough to achieve that goal when the noise is independent of the design.

Original language	English
Pages (from-to)	1520-1534
Number of pages	15
Journal	Bernoulli
Volume	22
Issue number	3
DOIs	https://doi.org/10.3150/15-BEJ701
Publication status	Published - Aug 2016
Externally published	Yes

Access to Document

10.3150/15-BEJ701

Cite this

@article{ded243e8e05d47c9b84c4941edb9f0ac,

title = "Performance of empirical risk minimization in linear aggregation",

abstract = "We study conditions under which, given a dictionary F = \{f1, . . . , fM\} and an i.i.d. sample (Xi,Yi )N i=1, the empirical minimizer in span(F ) relative to the squared loss, satisfies that with high probability R(∼f ERM) ≤ inf f span(F )R(f )+ rN(M),where R() is the squared risk and rN(M) is of the order of M/N. Among other results, we prove that a uniform small-ball estimate for functions in span(F) is enough to achieve that goal when the noise is independent of the design.",

keywords = "Aggregation theory, Empirical processes, Empirical risk minimization, Learning theory",

author = "Guillaume Lecu{\'e} and Shahar Mendelson",

note = "Publisher Copyright: {\textcopyright} 2016 ISI/BS.",

year = "2016",

month = aug,

doi = "10.3150/15-BEJ701",

language = "English",

volume = "22",

pages = "1520--1534",

journal = "Bernoulli",

issn = "1350-7265",

publisher = "Bernoulli Society for Mathematical Statistics and Probability",

number = "3",

}

TY - JOUR

T1 - Performance of empirical risk minimization in linear aggregation

AU - Lecué, Guillaume

AU - Mendelson, Shahar

PY - 2016/8

Y1 - 2016/8

N2 - We study conditions under which, given a dictionary F = {f1, . . . , fM} and an i.i.d. sample (Xi,Yi )N i=1, the empirical minimizer in span(F ) relative to the squared loss, satisfies that with high probability R(∼f ERM) ≤ inf f span(F )R(f )+ rN(M),where R() is the squared risk and rN(M) is of the order of M/N. Among other results, we prove that a uniform small-ball estimate for functions in span(F) is enough to achieve that goal when the noise is independent of the design.

AB - We study conditions under which, given a dictionary F = {f1, . . . , fM} and an i.i.d. sample (Xi,Yi )N i=1, the empirical minimizer in span(F ) relative to the squared loss, satisfies that with high probability R(∼f ERM) ≤ inf f span(F )R(f )+ rN(M),where R() is the squared risk and rN(M) is of the order of M/N. Among other results, we prove that a uniform small-ball estimate for functions in span(F) is enough to achieve that goal when the noise is independent of the design.

KW - Aggregation theory

KW - Empirical processes

KW - Empirical risk minimization

KW - Learning theory

UR - https://www.scopus.com/pages/publications/84964534021

U2 - 10.3150/15-BEJ701

DO - 10.3150/15-BEJ701

M3 - Article

SN - 1350-7265

VL - 22

SP - 1520

EP - 1534

JO - Bernoulli

JF - Bernoulli

IS - 3

ER -

Performance of empirical risk minimization in linear aggregation

Abstract

Access to Document

Other files and links

Fingerprint

Cite this