Research map / Label-efficient and robust learning / Noisy labels

Information-theoretic Limits of Online Classification with Noisy Labels

NeurIPS 2024 · Label-efficient and robust learning › Noisy labels · approach: Noise-aware loss and pairwise methods · 1 citations (OpenAlex)

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.

Characterizes minimax risk of online classification from adversarially chosen features and stochastic noisy labels, showing it is tightly governed (up to a log factor) by the Hellinger gap of the induced noisy label distributions.

Problem

Online classification where predictions must be evaluated against true labels while only noisy labels (from an unknown, adversarially chosen distribution in a kernel set) are observed; prior work covered only bounded Bernoulli noise.

Approach

Models noise via a general noisy kernel mapping each (x,y) to a set of label distributions; reduces the problem to pairwise hypothesis testing and proves a conditional version of Le Cam-Birgé testing, yielding bounds in terms of the Hellinger gap, plus an L2-gap bound for binary labels via exp-concave EWA regression.

Key results

• Upper bound O(log^2 K / γH) on expected minimax risk and high-probability bound (8 log(4K/δ) log K/γH + log(2/δ)) for finite classes of size K under Hellinger gap γH.
• Matching lower bound Ω(min{L, log K}/γH) for some kernels, so the characterization is tight up to a log K factor.
• For binary labels, an L2-gap based bound of 16 log|H|/γL, with 4γL ≤ γH ≤ √M γL, improves the log-dependence to linear in log|H|.

Limitations

• Upper and lower bounds differ by a log|H| (or log K) factor for general kernels; closing this gap is open.
• Computational efficiency of the predictors is not addressed; results are information-theoretic.
• Results stated for finite hypothesis classes; infinite classes handled only via covering arguments deferred to future work.

Experimental setup

Metrics: expected minimax risk high-probability minimax risk

Baselines: Ben-David et al. (2009) noisy online classification

Builds on: Ben-David et al. online learning with bounded Bernoulli noise Le Cam-Birgé testing exponential weighted average

Closest papers by meaning

• Learning Functional Distributions with Private Labels (ICML 2023 · similarity 0.89)
• Peer Loss Functions: Learning from Noisy Labels without Knowing Noise Rates (ICML 2020 · similarity 0.88)
• Label Noise: Ignorance Is Bliss (NeurIPS 2024 · similarity 0.88)
• Online Linear Classification with Massart Noise (ICML 2025 · similarity 0.87)
• Understanding Domain Generalization: A Noise Robustness Perspective (ICLR 2024 · similarity 0.86)
• Online Classification with Predictions (NeurIPS 2024 · similarity 0.85)