Timezone: »
Poster
From Stochastic Mixability to Fast Rates
Nishant Mehta · Robert Williamson
Empirical risk minimization (ERM) is a fundamental learning rule for statistical learning problems where the data is generated according to some unknown distribution $\mathsf{P}$ and returns a hypothesis $f$ chosen from a fixed class $\mathcal{F}$ with small loss $\ell$. In the parametric setting, depending upon $(\ell, \mathcal{F},\mathsf{P})$ ERM can have slow $(1/\sqrt{n})$ or fast $(1/n)$ rates of convergence of the excess risk as a function of the sample size $n$. There exist several results that give sufficient conditions for fast rates in terms of joint properties of $\ell$, $\mathcal{F}$, and $\mathsf{P}$, such as the margin condition and the Bernstein condition. In the non-statistical prediction with expert advice setting, there is an analogous slow and fast rate phenomenon, and it is entirely characterized in terms of the mixability of the loss $\ell$ (there being no role there for $\mathcal{F}$ or $\mathsf{P}$). The notion of stochastic mixability builds a bridge between these two models of learning, reducing to classical mixability in a special case. The present paper presents a direct proof of fast rates for ERM in terms of stochastic mixability of $(\ell,\mathcal{F}, \mathsf{P})$, and in so doing provides new insight into the fast-rates phenomenon. The proof exploits an old result of Kemperman on the solution to the general moment problem. We also show a partial converse that suggests a characterization of fast rates for ERM in terms of stochastic mixability is possible.
Author Information
Nishant Mehta (University of Victoria)
Robert Williamson (Australian National University & Data61)
Related Events (a corresponding poster, oral, or spotlight)
-
2014 Oral: From Stochastic Mixability to Fast Rates »
Wed Dec 10th 04:20 -- 04:40 PM Room Level 2, room 210
More from the Same Authors
-
2019 Poster: A Primal-Dual link between GANs and Autoencoders »
Hisham Husain · Richard Nock · Robert Williamson -
2018 Poster: A loss framework for calibrated anomaly detection »
Aditya Menon · Robert Williamson -
2018 Poster: Constant Regret, Generalized Mixability, and Mirror Descent »
Zakaria Mhammedi · Robert Williamson -
2018 Spotlight: Constant Regret, Generalized Mixability, and Mirror Descent »
Zakaria Mhammedi · Robert Williamson -
2018 Spotlight: A loss framework for calibrated anomaly detection »
Aditya Menon · Robert Williamson -
2017 Poster: f-GANs in an Information Geometric Nutshell »
Richard Nock · Zac Cranko · Aditya K Menon · Lizhen Qu · Robert Williamson -
2017 Spotlight: f-GANs in an Information Geometric Nutshell »
Richard Nock · Zac Cranko · Aditya K Menon · Lizhen Qu · Robert Williamson -
2015 Poster: Learning with Symmetric Label Noise: The Importance of Being Unhinged »
Brendan van Rooyen · Aditya Menon · Robert Williamson -
2015 Spotlight: Learning with Symmetric Label Noise: The Importance of Being Unhinged »
Brendan van Rooyen · Aditya Menon · Robert Williamson -
2012 Poster: Mixability in Statistical Learning »
Tim van Erven · Peter Grünwald · Mark Reid · Robert Williamson -
2011 Workshop: Relations between machine learning problems - an approach to unify the field »
Robert Williamson · John Langford · Ulrike von Luxburg · Mark Reid · Jennifer Wortman Vaughan -
2011 Poster: Composite Multiclass Losses »
Elodie Vernet · Robert Williamson · Mark Reid -
2009 Workshop: Clustering: Science or art? Towards principled approaches »
Margareta Ackerman · Shai Ben-David · Avrim Blum · Isabelle Guyon · Ulrike von Luxburg · Robert Williamson · Reza Zadeh