Multiclass Online Learning and Uniform Convergence
- URL: http://arxiv.org/abs/2303.17716v2
- Date: Fri, 7 Jul 2023 14:45:35 GMT
- Title: Multiclass Online Learning and Uniform Convergence
- Authors: Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, Ambuj Tewari
- Abstract summary: We study multiclass classification in the adversarial online learning setting.
We prove that any multiclass concept class is agnostically learnable if and only if its Littlestone dimension is finite.
- Score: 34.21248304961989
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study multiclass classification in the agnostic adversarial online
learning setting. As our main result, we prove that any multiclass concept
class is agnostically learnable if and only if its Littlestone dimension is
finite. This solves an open problem studied by Daniely, Sabato, Ben-David, and
Shalev-Shwartz (2011,2015) who handled the case when the number of classes (or
labels) is bounded. We also prove a separation between online learnability and
online uniform convergence by exhibiting an easy-to-learn class whose
sequential Rademacher complexity is unbounded.
Our learning algorithm uses the multiplicative weights algorithm, with a set
of experts defined by executions of the Standard Optimal Algorithm on
subsequences of size Littlestone dimension. We argue that the best expert has
regret at most Littlestone dimension relative to the best concept in the class.
This differs from the well-known covering technique of Ben-David, P\'{a}l, and
Shalev-Shwartz (2009) for binary classification, where the best expert has
regret zero.
Related papers
- Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem [26.292576184028924]
This work continues to investigate the link between differentially private (DP) and online learning.
We show that for general classification tasks, DP learnability implies online learnability.
arXiv Detail & Related papers (2024-07-10T15:43:30Z) - Simple online learning with consistent oracle [55.43220407902113]
We consider online learning in the model where a learning algorithm can access the class only via the emphconsistent oracle -- an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far.
arXiv Detail & Related papers (2023-08-15T21:50:40Z) - A Combinatorial Characterization of Supervised Online Learnability [20.291598040396302]
We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions.
We give a new scale-sensitive dimension, named the sequential minimax dimension, and show that it gives a tight quantitative characterization of online learnability.
arXiv Detail & Related papers (2023-07-07T20:11:07Z) - Adversarially Robust Learning: A Generic Minimax Optimal Learner and
Characterization [39.51923275855131]
We present a minimax optimal learner for the problem of learning predictors robust to adversarial examples at test-time.
In particular, we show, in a strong negative sense, the suboptimality of the robust learner proposed by Montasser, Hanneke, and Srebro.
arXiv Detail & Related papers (2022-09-15T15:32:42Z) - Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm [14.834625066344582]
We study the sequential general online regression, known also as the sequential probability assignments, under logarithmic loss.
We focus on obtaining tight, often matching, lower and upper bounds for the sequential minimax regret that are defined as the excess loss it incurs over a class of experts.
arXiv Detail & Related papers (2022-05-07T22:03:00Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
We provide the first oracle-efficient, no-regret algorithms in this setting.
We show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits.
arXiv Detail & Related papers (2022-02-09T19:22:34Z) - Fast Rates for Nonparametric Online Learning: From Realizability to
Learning in Games [36.969021834291745]
We propose a proper learning algorithm which gets a near-optimal mistake bound in terms of the sequential fat-shattering dimension of the hypothesis class.
This result answers a question as to whether proper learners could achieve near-optimal mistake bounds.
For the real-valued (regression) setting, the optimal mistake bound was not even known for improper learners.
arXiv Detail & Related papers (2021-11-17T05:24:21Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
We prove that the sample complexity of properly learning a class of Littlestone dimension $d$ with approximate differential privacy is $tilde O(d6)$, ignoring privacy and accuracy parameters.
This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of $2O(d)$ on the sample complexity.
arXiv Detail & Related papers (2020-12-07T18:17:46Z) - Theoretical Insights Into Multiclass Classification: A High-dimensional
Asymptotic View [82.80085730891126]
We provide the first modernally precise analysis of linear multiclass classification.
Our analysis reveals that the classification accuracy is highly distribution-dependent.
The insights gained may pave the way for a precise understanding of other classification algorithms.
arXiv Detail & Related papers (2020-11-16T05:17:29Z) - Active Online Learning with Hidden Shifting Domains [64.75186088512034]
We propose a surprisingly simple algorithm that adaptively balances its regret and its number of label queries.
Our algorithm can adaptively deal with interleaving spans of inputs from different domains.
arXiv Detail & Related papers (2020-06-25T15:23:59Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.