LOCAL VS. GLOBAL PARAMETERS-BREAKING THE GAUSSIAN COMPLEXITY BARRIER

• 成果类型: Article
• 署名作者: Mendelson, Shahar
• 署名单位: Technion Israel Institute of Technology
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/16-AOS1510
• 发表日期: 2017
• 页码: 1835-1862
• 关键词: rates

摘要

We show that if F is a convex class of functions that is L-sub-Gaussian, the error rate of learning problems generated by independent noise is equivalent to a fixed point determined by local covering estimates of the class (i.e., the covering number at a specific level), rather than by the Gaussian average, which takes into account the structure of F at an arbitrarily small scale. To that end, we establish new sharp upper and lower estimates on the error rate in such learning problems.