Search Machine Learning Repository: @inproceedings{icml2014c2_kontorovichb14,
    Publisher = {JMLR Workshop and Conference Proceedings},
    Title = {Maximum Margin Multiclass Nearest Neighbors},
    Url = {http://jmlr.org/proceedings/papers/v32/kontorovichb14.pdf},
    Abstract = {We develop a general framework for margin-based multicategory classification in metric spaces. The basic work-horse is a margin-regularized version of the nearest-neighbor classifier. We prove generalization bounds that match the state of the art in sample size $n$ and significantly improve the dependence on the number of classes $k$. Our point of departure is a nearly Bayes-optimal finite-sample risk bound independent of $k$. Although $k$-free, this bound is unregularized and non-adaptive, which motivates our main result: Rademacher and scale-sensitive margin bounds with a logarithmic dependence on $k$. As the best previous risk estimates in this setting were of order $\sqrt k$, our bound is exponentially sharper. From the algorithmic standpoint, in doubling metric spaces our classifier may be trained on $n$ examples in $O(n^2\log n)$ time and evaluated on new points in $O(\log n)$ time.},
    Author = {Aryeh Kontorovich and Roi Weiss},
    Editor = {Tony Jebara and Eric P. Xing},
    Year = {2014},
    Booktitle = {Proceedings of the 31st International Conference on Machine Learning (ICML-14)},
    Pages = {892-900}
   }