Towards Problem-dependent Optimal Learning Rates

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.