Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Online Linear Classification with Massart Noise

ICML 2025 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Ranking bandits

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first computationally efficient online learner for γ-margin linear classification under Massart noise, achieving ηT + o(T) mistakes via reweighted Leaky-ReLU online gradient descent, and extends the approach to k-arm contextual bandits with monotone rewards.

Problem

Efficient online learning of linear classifiers when the adversary picks contexts and labels are flipped with probability at most η (Massart noise); prior online methods were inefficient or gave no nontrivial mistake bound.

Approach

Run online gradient descent on a sequence of Leaky-ReLU losses reweighted by the inverse of the current hypothesis's margin on each example, so that regret guarantees translate into mistake bounds under Massart noise; extend this to k-arm bandits with linearly sorted expected rewards via unbiased fake-reward estimates and uniform exploration.

Key results

• Online Massart learner achieves M(T) = ηT + O(T^{3/4}/γ) mistakes in poly(d) time per round for γ-margin linear classifiers.
• k-arm monotone contextual bandit algorithm gets expected reward at least (k-1)/k·∆T − O(T^{5/6}(k∆M^2)^{1/3}/γ) above uniform random play.
• For 2 arms the bandit reduction matches the ηT bound, which is argued to be tight for efficient SQ algorithms.

Measured effects reported in the paper

Surprising findings

• Plain online gradient descent on Leaky-ReLU loss fails in the online setting because the adversary can place points near the current decision boundary; margin reweighting is needed.

Limitations

• Mistake bound ηT + o(T) requires a γ-margin assumption; without margin, even noiseless learning needs T mistakes.
• Bandit result for k>2 arms may not be tight; the gap to best-arm play is unclear.
• Bounds are o(T) with polynomial dependence on 1/γ, not optimal rates.

Experimental setup

Metrics: mistake bound regret expected reward

Baselines: Standard Optimal Algorithm (Ben-David et al. 2009) random guessing

Builds on: Leaky-ReLU loss (Bylander 1998; Diakonikolas et al. 2019) Massart online learning model (Ben-David et al. 2009) online gradient descent (Hazan 2016)

Closest papers by meaning

• Information-theoretic Limits of Online Classification with Noisy Labels (NeurIPS 2024 · similarity 0.87)
• Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs (NeurIPS 2024 · similarity 0.87)
• Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.86)
• From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards (NeurIPS 2025 · similarity 0.86)
• Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.86)
• Direction-Aware Offline-to-Online Learning in Linear Contextual Bandits (NeurIPS 2026 · similarity 0.86)