Empirical minimization

• 成果类型: Article
• 署名作者: Bartlett, PL; Mendelson, S
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley; Australian National University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-005-0462-3
• 发表日期: 2006
• 页码: 311-334
• 关键词: Concentration Inequalities

摘要

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.