Towards Problem-dependent Optimal Learning Rates

           Yunbei Xu                   Assaf Zeevi
         Columbia University              Columbia University
         New York, NY 10027               New York, NY 10025
      yunbei.xu@gsb.columbia.edu            assaf@gsb.columbia.edu

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