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."