Timezone: »

 
Spotlight
Towards Problem-dependent Optimal Learning Rates
Yunbei Xu · Assaf Zeevi

Thu Dec 10 08:10 AM -- 08:20 AM (PST) @ Orals & Spotlights: Optimization/Theory
in Orals & Spotlights Track 30: Optimization/Theory »

We study problem-dependent rates, i.e., generalization errors that scale tightly with the variance or the effective loss at the "best hypothesis." Existing uniform convergence and localization frameworks, the most widely used tools to study this problem, often fail to simultaneously provide parameter localization and optimal dependence on the sample size. As a result, existing problem-dependent rates are often rather weak when the hypothesis class is "rich" and the worst-case bound of the loss is large. In this paper we propose a new framework based on a "uniform localized convergence" principle. We provide the first (moment-penalized) estimator that achieves the optimal variance-dependent rate for general "rich" classes; we also establish improved loss-dependent rate for standard empirical risk minimization.

Author Information

Yunbei Xu (Columbia University)
Assaf Zeevi (Columbia University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors