TY - JOUR
T1 - Empirical minimization
AU - Bartlett, Peter L.
AU - Mendelson, Shahar
PY - 2006/7
Y1 - 2006/7
N2 - We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either in an additive sense, via the uniform law of large numbers, or in a multiplicative sense, using isomorphic coordinate projections. We then show that a direct analysis of the empirical minimization algorithm yields a significantly better bound, and that the estimates we obtain are essentially sharp. The method of proof we use is based on Talagrand's concentration inequality for empirical processes.
AB - We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either in an additive sense, via the uniform law of large numbers, or in a multiplicative sense, using isomorphic coordinate projections. We then show that a direct analysis of the empirical minimization algorithm yields a significantly better bound, and that the estimates we obtain are essentially sharp. The method of proof we use is based on Talagrand's concentration inequality for empirical processes.
KW - Empirical minimization
KW - Empirical processes
KW - Error bounds
KW - Isomorphic coordinate projections
UR - http://www.scopus.com/inward/record.url?scp=33645979357&partnerID=8YFLogxK
U2 - 10.1007/s00440-005-0462-3
DO - 10.1007/s00440-005-0462-3
M3 - Article
SN - 0178-8051
VL - 135
SP - 311
EP - 334
JO - Probability Theory and Related Fields
JF - Probability Theory and Related Fields
IS - 3
ER -