# Margin-Independent Online Multiclass Learning via Convex Geometry

arXiv: https://arxiv.org/abs/2111.08057 · HTML: https://mlsanity.com/paper/2111.08057/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 36 references that are in the map.
- First posted on arXiv 15 Nov 2021.

## Builds on (most cited first, 7 of 7)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Multidimensional Binary Search for Contextual Decision-Making](https://mlsanity.com/paper/1611.00829/) (2016)
- [Contextual Search via Intrinsic Volumes](https://mlsanity.com/paper/1804.03195/) (2018)
- [An Algorithm for Online K-Means Clustering](https://mlsanity.com/paper/1412.5721/) (2014)
- [Perceptron Mistake Bounds](https://mlsanity.com/paper/1305.0208/) (2013)

## Abstract (arXiv)

We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which seek to minimize the misclassification rate, we minimize the total distance from each query to the region corresponding to its correct label. When the true labels are determined via a nearest neighbor partition -- i.e. the label of a point is given by which of k centers it is closest to in Euclidean distance -- we show that one can achieve a loss that is independent of the total number of queries. We complement this result by showing that learning general convex sets requires an almost linear loss per query. Our results build off of regret guarantees for the geometric problem of contextual search. In addition, we develop a novel reduction technique from multiclass classification to binary classification which may be of independent interest.