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.
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.
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…
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. …
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.
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.
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. 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 ) . Improved mistake bound for group linear separable cases in online multiclass linear classification.
problem Improving mistake bounds for online multiclass linear classification under group linear separable conditions.
method Refined group weak linear separability condition and rational kernel approach.
result Achieved a mistake bound of K ⋅ 2 i l d e O ( 1 / γ log L ) ) K\cdot 2^{ ilde{O}(\sqrt{1/γ}\log L)}) K ⋅ 2 i l d e O ( 1/ γ l o g L ) ) under group weak linear separable condition. 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.
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. Sharp sample complexity for multiclass PAC learning with bandit feedback.
problem Multiclass PAC learning with bandit feedback.
method Characterization of optimal sample complexity using a new combinatorial dimension (bandit DS dimension) and a learning algorithm (ListCascade).
result Sharp sample complexity characterization for every concept class up to logarithmic factors.
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.
Paper tackles noisy bandit feedback for multiclass classification.
problem Learning multiclass classifier with corrupted feedback.
method Proposes an unbiased estimator technique to estimate noise rates and an end-to-end framework.
result Algorithm achieves mistake bounds of O ( T ) O(\sqrt{T}) O ( T ) in high noise and O ( T i c e f r a c 23 ) O(T^{
icefrac{2}{3}}) O ( T i ce f r a c 2 3 ) in worst case. Improved PAC learning algorithm for multiclass classification with bandit feedback.
problem Efficiently learning multiclass classification with limited feedback.
method Novel algorithm using stochastic optimization and Frank-Wolfe updates.
result Improved sample complexity bounds for multiclass PAC learning.
Proposes online conformal prediction method with adversarial semi-bandit feedback.
problem Online uncertainty quantification with adversarial semi-bandit feedback.
method Formulates online conformal prediction as an adversarial bandit problem and uses regret minimization.
result Achieves long-run coverage guarantee with adversarial semi-bandit feedback.
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…
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 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. 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…
Paper proposes online algorithms for multiclass classification with partial labels.
problem Classifying data with partial labels.
method Avg Perceptron, Max Perceptron, Avg Pegasos, Max Pegasos algorithms.
result Mistake bounds for Avg Perceptron and regret bound for Avg Pegasos.
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…
New algorithms reduce sample complexity for multiclass contextual bandits.
problem Designing efficient algorithms for multiclass contextual bandits with sparse rewards.
method Two complementary approaches: decision-estimation coefficient analysis and low-variance exploration.
result Achieved optimal sample complexity bounds for multiclass contextual bandits.
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 ) . 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.
GLCB uses Gated Linear Networks for online contextual bandits.
problem Online learning in contextual bandits with uncertainty estimation.
method Gated Linear Networks (GLNs) for prediction and uncertainty estimation.
result GLCB outperforms state-of-the-art methods in online contextual bandits.
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.
New algorithms handle online prediction with bandit and delayed feedback, improving regret bounds.
problem Achieving finite bounds on surrogate regret with limited feedback.
method Proposed algorithms for bandit and delayed feedback, including inverse-weighted gradient and pseudo-inverse matrix estimators.
result Achieved improved surrogate regret bounds of O ( K T ) O(\sqrt{KT}) O ( K T ) and O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) . New algorithm reduces regret in noisy context bandits.
problem Online decision-making with noisy context predictions.
method Extends classical statistics measurement error model to online decision-making.
result Achieves sublinear regret guarantees under mild conditions.
We study the multiclass online learning problem where a forecaster makes a sequence of predictions using the advice of n n n experts. Our main contribution is to analyze the regime where the best expert makes at most b b b mistakes and to show that when b = o ( log 4 n ) b = o(\log_4{n}) b = o ( log 4 n ) , the expected number of mistakes made by the optima…
Delaytron learns multi-class classifiers with delayed feedbacks, achieving efficient regret bounds.
problem Learning multi-class classifiers with delayed bandit feedbacks where delays are unknown.
method Online algorithm Delaytron with adaptive learning for unknown delays.
result Achieves efficient regret bounds for various loss scenarios.
BCCP uses bandit feedback to provide reliable predictions with limited labeled data.
problem Limited labeled data and bandit feedback challenge online set-valued classification.
method BCCP uses stochastic gradient descent to train model and make set-valued inferences with unbiased estimation of true label.
result BCCP offers coverage guarantees on a class-specific granularity.
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…
Optimal multiclass U-calibration error found to be Θ(√KT).
problem Online multiclass U-calibration with low regret for all bounded proper losses.
method Follow-the-Perturbed-Leader algorithm and lower bound construction.
result Optimal U-calibration error is Θ(√KT).
Algorithm provides online learning guarantees against general comparators in full and bandit feedback.
problem Adversarial online learning with data-dependent regret guarantees.
method Completely online algorithm with data-dependent regret guarantees for full and bandit feedback.
result Algorithm achieves expected performance against arbitrary comparator sequences in full and bandit feedback settings.
This work improves online regression and contextual bandits using neural networks.
problem Improving online regression and contextual bandits using neural networks.
method Investigates neural networks for online regression, showing O ( log T ) \mathcal{O}(\log T) O ( log T ) regret for almost convex losses and KL loss. result Shows i l d e O ( K L ∗ + K ) ilde{\mathcal{O}}(\sqrt{KL^*} + K) i l d e O ( K L ∗ + K ) regret for NeuCB, outperforming existing algorithms. We study the problem of online path learning with non-additive gains, which is a central problem appearing in several applications, including ensemble structured prediction. We present new online algorithms for path learning with non-additive count-based gains for the three settings of full information, semi-bandit and…
Optimal online learning algorithms for label-efficient prediction and bandits.
problem Efficient prediction in online learning with limited information.
method Optimistic online mirror descent with second order corrections and hybrid regularizers.
result Improved regret bounds for label-efficient prediction and bandits.
Algorithm improves decision-making with partially observed contexts using pretrained models.
problem Improving decision-making with partially observed contexts in online linear contextual bandits.
method PULSE-UCB algorithm that uses pretrained models trained on auxiliary data to impute missing features.
result Achieves near-optimal performance in i.i.d. context case with Hölder-smooth missing features.
Explearn learns to explain predictions using Gaussian Processes.
problem Learning to explain predictions effectively.
method Gaussian Processes-based contextual bandits.
result Guaranteed convergence with high probability.
New algorithm handles bandit problems under translations and scales.
problem Adversarial multi-armed bandit problems with arbitrary translations and scales.
method Innovative online algorithm invariant to translations and scales, using universal prediction.
result Second-order regret bounds, unaffected by affine transformations of losses.
Proposes a new algorithm for efficient online model selection of LLMs considering the increasing-then-converging trend.
problem Balancing cost and performance in choosing the best LLM among a diverse set of models.
method Introduces a time-increasing bandit algorithm (TI-UCB) that predicts model performance increases and balances exploration and exploitation.
result Achieves a logarithmic regret upper bound, indicating a fast convergence rate in model selection.
We investigate online classification with paid stochastic experts. Here, before making their prediction, each expert must be paid. The amount that we pay each expert directly influences the accuracy of their prediction through some unknown Lipschitz "productivity" function. In each round, the learner must decide how mu…
New methods detect unfairness in multiclass classifiers using DCP.
problem Detecting unfairness in multiclass classifiers.
method Generalizes DCP to multiclass, provides optimization methods.
result Detects classifiers treating a significant fraction of the population unfairly.
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.
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…
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.
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 ) .