Timezone: »
Poster
Margin-Independent Online Multiclass Learning via Convex Geometry
Guru Guruganesh · Allen Liu · Jon Schneider · Joshua Wang
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 assigned 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 problem of contextual search. In addition, we develop a novel reduction technique from multiclass classification to binary classification which may be of independent interest.
Author Information
Guru Guruganesh (Google Research)
Allen Liu (MIT)
Jon Schneider (Google Research)
Joshua Wang (Google Research)
More from the Same Authors
-
2022 : Semi-Random Sparse Recovery in Nearly-Linear Time »
Jonathan Kelner · Jerry Li · Allen Liu · Aaron Sidford · Kevin Tian -
2023 Poster: A Constant-Factor Approximation for Individual Preference Stable Clustering »
Anders Aamand · Justin Chen · Allen Liu · Sandeep Silwal · Pattara Sukprasert · Ali Vakilian · Fred Zhang -
2022 : Poster Session 1 »
Andrew Lowy · Thomas Bonnier · Yiling Xie · Guy Kornowski · Simon Schug · Seungyub Han · Nicolas Loizou · xinwei zhang · Laurent Condat · Tabea E. Röber · Si Yi Meng · Marco Mondelli · Runlong Zhou · Eshaan Nichani · Adrian Goldwaser · Rudrajit Das · Kayhan Behdin · Atish Agarwala · Mukul Gagrani · Gary Cheng · Tian Li · Haoran Sun · Hossein Taheri · Allen Liu · Siqi Zhang · Dmitrii Avdiukhin · Bradley Brown · Miaolan Xie · Junhyung Lyle Kim · Sharan Vaswani · Xinmeng Huang · Ganesh Ramachandra Kini · Angela Yuan · Weiqiang Zheng · Jiajin Li -
2022 Poster: A Fourier Approach to Mixture Learning »
Mingda Qiao · Guru Guruganesh · Ankit Rawat · Kumar Avinava Dubey · Manzil Zaheer -
2022 Poster: Robust Model Selection and Nearly-Proper Learning for GMMs »
Allen Liu · Jerry Li · Ankur Moitra -
2021 Poster: Contextual Recommendations and Low-Regret Cutting-Plane Algorithms »
Sreenivas Gollapudi · Guru Guruganesh · Kostas Kollias · Pasin Manurangsi · Renato Leme · Jon Schneider -
2020 Poster: Tensor Completion Made Practical »
Allen Liu · Ankur Moitra -
2020 Poster: Myersonian Regression »
Allen Liu · Renato Leme · Jon Schneider -
2020 Poster: Big Bird: Transformers for Longer Sequences »
Manzil Zaheer · Guru Guruganesh · Kumar Avinava Dubey · Joshua Ainslie · Chris Alberti · Santiago Ontanon · Philip Pham · Anirudh Ravula · Qifan Wang · Li Yang · Amr Ahmed -
2019 Poster: Prior-Free Dynamic Auctions with Low Regret Buyers »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Poster: Efficient Rematerialization for Deep Networks »
Ravi Kumar · Manish Purohit · Zoya Svitkina · Erik Vee · Joshua Wang -
2019 Poster: Contextual Bandits with Cross-Learning »
Santiago Balseiro · Negin Golrezaei · Mohammad Mahdian · Vahab Mirrokni · Jon Schneider -
2019 Poster: Strategizing against No-regret Learners »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Oral: Strategizing against No-regret Learners »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2018 Poster: Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization »
Rad Niazadeh · Tim Roughgarden · Joshua Wang -
2018 Oral: Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization »
Rad Niazadeh · Tim Roughgarden · Joshua Wang -
2017 Poster: Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search »
Benjamin Moseley · Joshua Wang -
2017 Oral: Approximation Bounds for Hierarchical Clustering: Average Linkage, Bisecting K-means, and Local Search »
Benjamin Moseley · Joshua Wang