Study online multiclass classification under bandit feedback, extending previous results.
problem Online multiclass classification with bandit feedback, focusing on label space unboundedness.
method Extend Daniely and Helbertal's results, show necessity and sufficiency of Bandit Littlestone dimension for learnability.
result Sequential uniform convergence is necessary but not sufficient for bandit online learnability.
Extends boosting to multiclass online agnostic classification.
problem Online multiclass classification with weak learners.
method Reduces multiclass online agnostic boosting to online convex optimization.
result First boosting algorithm for online agnostic multiclass classification.
Gaptron algorithm reduces mistakes in online multiclass classification.
problem Online multiclass classification with limited information.
method Randomized first-order algorithm exploiting the gap between zero-one loss and surrogate losses.
result First linear time algorithm with O ( K T ) O(K\sqrt{T}) O ( K T ) expected regret. Recent work has extended the theoretical analysis of boosting algorithms to multiclass problems and to online settings. However, the multiclass extension is in the batch setting and the online extensions only consider binary classification. We fill this gap in the literature by defining, and justifying, a weak learning…
New algorithm learns multiclass concepts with finite Littlestone dimension.
problem Agnostic online multiclass classification in adversarial settings.
method Multiplicative weights algorithm with experts based on subsequences.
result Proves agnostic learnability if and only if Littlestone dimension is finite.
FOLKLORE algorithm speeds up online multiclass logistic regression.
problem Efficiently solving online multiclass logistic regression without high computational cost.
method Developed FOLKLORE algorithm with improved runtime and regret bound.
result First practical algorithm for online multiclass logistic regression.
Extends quantum learning theory to multiclass and online settings.
problem Quantum learning theory for batch and online learning.
method Adapts classical models to quantum settings, introduces new online learning model.
result Quantum and classical sample complexities have the same form for various learning scenarios.
Study online learning with set-valued feedback, showing differences between deterministic and randomized approaches.
problem Online learning with set-valued feedback, where labels are sets rather than single labels.
method Introduced new combinatorial dimensions (Set Littlestone and Measure Shattering) to characterize learnability.
result Characterized deterministic and randomized online learnability, and established bounds for various learning settings.
Online L2D algorithm for multiclass classification with varying experts.
problem Handling streaming data, changing expert availability, and shifting expert distribution.
method First online L2D algorithm with O ( ( n + n e ) T 2 / 3 ) O((n+n_e)T^{2/3}) O (( n + n e ) T 2/3 ) and O ( ( n + n e ) T ) O((n+n_e)\sqrt{T}) O (( n + n e ) T ) regret guarantees. result Effective extension of standard L2D to settings with varying expert availability and reliability.
In this paper, we propose online algorithms for multiclass classification using partial labels. We propose two variants of Perceptron called Avg Perceptron and Max Perceptron to deal with the partial labeled data. We also propose Avg Pegasos and Max Pegasos, which are extensions of Pegasos algorithm. We also provide mi…
New bounds show agnostic multiclass learning depends on two dimensions: Natarajan and Daniely-Shalev-Shwartz.
problem Understanding sample complexity in multiclass classification with agnostic learning.
method Developed a novel online procedure based on a self-adaptive multiplicative-weights algorithm.
result Agnostic sample complexity bounds are in the form of DS^(1.5)/ε + Nat/ε^2, nearly tight up to a √DS factor.
This work proves DP learnability implies online learnability for general classification tasks.
problem Link between differential privacy and online learning for general classification tasks.
method Establishes Ramsey-type theorems for trees to prove DP learnability implies online learnability.
result DP learnability implies online learnability for general classification tasks.
Study the tradeoffs of bandit feedback in multiclass classification.
problem The price of using bandit feedback in multiclass classification.
method Mistake bound model, analysis of variants, and comparison of learners and adversaries.
result The optimal mistake bound under bandit feedback is at most O ( k ) O(k) O ( k ) times higher than in full information, with a tight bound of O ( k ) O(k) O ( k ) . We consider the problem of online multiclass classification with partial feedback, where an algorithm predicts a class for a new instance in each round and only receives its correctness. Although several methods have been developed for this problem, recent challenging real-world applications require further performance…
Study improves online learning with adaptable agents in various settings.
problem Learning with improving agents in online settings.
method Extensive analysis of combinatorial dimensions, multiclass setup, bandit feedback, and agent cost.
result Characterization and analysis of online learnability in the model.
Improved multiclass logistic regression with lower computational complexity.
problem High computational complexity in existing methods for multiclass logistic regression.
method Developed a new algorithm that achieves a lower computational complexity.
result Achieved a regret of O ( log ( B n ) ) O(\log(Bn)) O ( log ( B n )) with computational complexity O ( n 1.5 ) O(n^{1.5}) O ( n 1.5 ) . We present online boosting algorithms for multiclass classification with bandit feedback, where the learner only receives feedback about the correctness of its prediction. We propose an unbiased estimate of the loss using a randomized prediction, allowing the model to update its weak learners with limited information. …
We present an efficient second-order algorithm with O ~ ( 1 η T ) \tilde{O}(\frac{1}η\sqrt{T}) O ~ ( η 1 T ) regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by η η η , for a range of η η η restricted by the norm of the competitor. The family of loss funct…
Unified binary and multiclass margin-based classification methods.
problem No consensus on multiclass loss functions analogous to binary margin loss.
method Showed multiclass loss functions can be expressed in relative margin form.
result Extended classification-calibration result to multiclass.
Research on predicting with lists of labels, characterizing learnability and providing algorithms.
problem Multiclass online prediction with multiple labels.
method Characterization using b b b -ary Littlestone dimension, adaptation of classical algorithms, combinatorial results. result Achievement of negative regret in some scenarios, complete characterization of learnability.
The paper analyzes how overparameterized models can generalize well in multiclass classification.
problem Generalization in multiclass classification with overparameterized models.
method Survival/contamination analysis framework adapted for multiclass classification.
result Multiclass classification can generalize well even with many classes, unlike regression tasks.
We consider the online multiclass linear classification under the bandit feedback setting. Beygelzimer, Pál, Szörényi, Thiruvenkatachari, Wei, and Zhang [ICML'19] considered two notions of linear separability, weak and strong linear separability. When examples are strongly linearly separable with margin γ γ γ , they prese…
New research determines the optimal sample complexity for multiclass and list learning.
problem Determining the optimal sample complexity for multiclass classification.
method Algebraic characterization of multiclass hypothesis classes in terms of their DS dimension.
result Proves a longstanding conjecture and determines the optimal dependence of sample complexity on DS dimension.
Study shows exponential error reduction in multiclass classification without bias-variance trade-off.
problem Multiclass classification with margin conditions.
method Analysis of classification error under hard-margin conditions.
result Exponential decrease in classification error without bias-variance trade-off.
Establishes a condition for multiclass classification-calibration of Gamma-Phi losses.
problem Ensuring classification-calibration of multiclass Gamma-Phi losses.
method Develops a general sufficient condition for classification-calibration of Gamma-Phi losses.
result Proves the first family of nonconvex multiclass surrogate losses for which classification-calibration has been fully justified.
New reformulations for multiclass classification problems using optimal transport.
problem Adversarial multiclass classification problems.
method Multimarginal optimal transport formulation.
result Reveals geometric structure and extends binary classification results.
Paper studies multiclass classifiers from binary classifiers, proving methods and demonstrating advantages.
problem Constructing efficient multiclass classifiers from binary ones.
method Two methods: one vs. all and hierarchical classification, with a new leverage-hierarchical method introduced.
result Proves upper bounds and exact formulas for multiclass regret in terms of binary regrets.
This work extends implicit bias analysis to multiclass classification using a new loss framework.
problem The implicit bias of gradient descent on multiclass data without explicit regularization.
method Employing the PERM framework to introduce a multiclass extension of the exponential tail property.
result Extended implicit bias result to multiclass classification using a new loss framework.
New method for multiclass classification reduces error bounds.
problem High-dimensional multiclass classification with sparse coefficients.
method Sparse multinomial logistic regression with convex penalties.
result Plug-in classifiers achieve minimax generalization error bounds.
Algorithm minimizes risk for multiclass classification of stochastic diffusion paths.
problem Multiclass classification of stochastic diffusion paths with distinct drift functions.
method Empirical risk minimization using L2 risk.
result Achieves fast rates of convergence under margin assumption.
Pre-trained word embeddings encode general word semantics and lexical regularities of natural language, and have proven useful across many NLP tasks, including word sense disambiguation, machine translation, and sentiment analysis, to name a few. In supervised tasks such as multiclass text classification (the focus of …
We create a new online reduction of multiclass classification to binary classification for which training and prediction time scale logarithmically with the number of classes. Compared to previous approaches, we obtain substantially better statistical performance for two reasons: First, we prove a tighter and more comp…
We study the problem of efficient online multiclass linear classification with bandit feedback, where all examples belong to one of K K K classes and lie in the d d d -dimensional Euclidean space. Previous works have left open the challenge of designing efficient algorithms with finite mistake bounds when the data is linear…
Online texts -- across genres, registers, domains, and styles -- are riddled with human stereotypes, expressed in overt or subtle ways. Word embeddings, trained on these texts, perpetuate and amplify these stereotypes, and propagate biases to machine learning models that use word embeddings as features. In this work, w…
Study extends binary omniprediction to multiclass setting with improved sample complexity.
problem Suboptimality bounds for each loss function against infinite comparator family in multiclass prediction.
method Design of a framework for solving Blackwell approachability problems with coupled actions.
result Sample complexity of ≈ ε − ( k + 1 ) \approx \varepsilon^{-(k+1)} ≈ ε − ( k + 1 ) for ε \varepsilon ε -omniprediction in a k k k -class problem. Study proves existence of robust classifiers in multiclass adversarial training.
problem Proves existence of robust classifiers in multiclass adversarial training.
method Three models of adversarial training in multiclass classification, proving existence of Borel measurable robust classifiers.
result Proves existence of Borel measurable robust classifiers in each model.
We propose a robust adversarial prediction framework for general multiclass classification. Our method seeks predictive distributions that robustly optimize non-convex and non-continuous multiclass loss metrics against the worst-case conditional label distributions (the adversarial distributions) that (approximately) m…
Reduces bounded loss learning to binary classification.
problem Universal consistency of non-i.i.d. processes with bounded loss.
method Constructive reduction to binary classification.
result Any bounded loss output setting can be reduced to binary classification.
New algorithm tackles multiclass transductive online learning with unbounded labels.
problem Characterizing optimal mistake bound for unbounded label spaces.
method Introducing new combinatorial dimensions (Level-constrained Littlestone and Branching dimensions) to characterize online learnability.
result Established trichotomy of possible minimax rates for unbounded label spaces: Θ ( T ) Θ(T) Θ ( T ) , Θ ( log T ) Θ(\log T) Θ ( log T ) , or Θ ( 1 ) Θ(1) Θ ( 1 ) . Paper analyzes multiclass classification with high-dimensional data.
problem Understanding statistical properties and behavior of multiclass classification algorithms.
method Asymptotic analysis of linear multiclass classification.
result Test error varies significantly across different training algorithms and data distributions.
New algorithm improves multiclass classification regret bound.
problem Improving multiclass classification with bandit feedback.
method Developed a new bandit classification algorithm.
result Guaranteed regret of O ~ ( ∣ H ∣ + T ) \smash{\widetilde{O}(|H|+\sqrt{T})} O ( ∣ H ∣ + T ) , improving over classical algorithms. New binary classification techniques help multiclass classification by aggregating proper learners.
problem Multiclass classification faces a properness barrier that prevents optimal learning by proper learners.
method Aggregations of proper binary learners, generalized to multiclass settings, achieve optimal sample complexity.
result Optimal binary learners can achieve sample complexity $O\left(\frac{d_G + \ln(1 / δ)}ε
ight)$ for classes with finite Graph dimension d G d_G d G . Develops a functional mix-of-experts model for multiclass classification.
problem Multiclass classification with univariate functional predictors.
method Functional mix-of-experts model with regularization and sparsity constraints.
result Regularized maximum likelihood estimation yields interpretable coefficient functions.
New research shows SVM and related methods can overfit without harm in multiclass classification.
problem Understanding benign overfitting in multiclass classification.
method Analyzing three training algorithms: ERM with cross-entropy, least-squares, and one-vs-all SVM.
result All three algorithms can lead to classifiers that interpolate training data and have equal accuracy under high overparameterization.
Binary and multiclass epilepsy detection methods using EEG features.
problem Epilepsy diagnosis from EEG data.
method Feature extraction from power spectrum, spectrogram, and bispectrogram; eight machine learning algorithms used.
result Random forest and backpropagation algorithms achieved highest accuracy for binary and multiclass classification.
Develops NPMC method for noisy labels, improving multiclass classification accuracy.
problem Asymmetric misclassification costs and label noise in multiclass classification.
method Empirical likelihood approach using exponential tilting density ratio model.
result Root n consistent and asymptotically normal estimators for clean labels and noise mechanism.
Improved multiclass classification with class-weighted nearest neighbors.
problem Multiclass classification with large or imbalanced classes.
method Class-weighted k-nearest neighbors algorithm, derived bounds on accuracy and risk.
result Optimized classification metrics like F1 score or Matthew's Correlation Coefficient.
Learning linear predictors with the logistic loss---both in stochastic and online settings---is a fundamental task in machine learning and statistics, with direct connections to classification and boosting. Existing "fast rates" for this setting exhibit exponential dependence on the predictor norm, and Hazan et al. (20…