Extreme Multiclass
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Shows that multiclass prediction can run in O(log K) time while remaining statistically sound by reducing multiclass to binary partitions, using a ramp-loss relaxation and an online algorithm to build top‑down trees. Proves regret bounds that multiply average binary regret by depth but then replaces depth with a constant using error-correcting tournaments (factor ≈5.5). Implements the method in Vowpal Wabbit, tests on synthetic 100‑class grids, MNIST and RCV1, and finds much lower computation with somewhat higher test error (root partition error ~0.1253 on MNIST).
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:34The Problem
- 3:30Counters
- 6:20Is logarithmic time possible?
- 7:30Filter Trees (BLR09)
- 10:20Can you make it robust?
- 14:28How do you learn structure?
- 17:55The Partitioning Problem CAL13
- 20:40Bottom Up doesn't work
- 21:59Does partitioning recurse well?
- 23:59Online Partitioning
- 26:33Does it work? An Acid Test
- 27:19Does it work? Partition Quality
- 28:43What Follow
related talks
42mBypassing the Impossibility of Online Learning Thresholds: Unbounded Losses and Transductive Priors
28mClassification Through Regression:Unlock the True Potential of Your Labels
38mMulti-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere!
01h 12mRecent Progress in High-Dimensional Learning
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration
46mDynamic Regret Minimization for Bandits without Prior Knowledge
01h 11mA Theory of Multi-objective Machine Learning
01h 18mGeneralization III