Research map / Bandits and online learning / Online convex optimization and games
Label Shift Meets Online Learning: Ensuring Consistent Adaptation with Universal Dynamic Regret
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.
Proposes LASU, an online label shift method that estimates label distributions via a likelihood-based soft confusion matrix (OSCM-L), builds a convex risk estimator, and combines optimistic online mirror descent learners with an optimistic Hedge ensemble to get universal dynamic regret.
Problem
Online label shift adaptation in streaming data, where BBSE-based label distribution estimates are inconsistent and yield non-convex risk estimators, and prior static/dynamic regret guarantees are either too optimistic or too pessimistic.
Approach
Replace BBSE inversion with a maximum-likelihood estimate of the online label distribution (OSCM-L) that is guaranteed non-negative, yielding a convex risk estimator; then ensemble optimistic online mirror descent learners with different step sizes via optimistic Hedge to attain universal dynamic regret that is minimax optimal.
Key results
- LASU achieves the lowest average error among online methods in most dataset/shift combinations, e.g., CIFAR-10 Bernoulli shift 9.68% vs. 10.20% for UOGD and 15.11% for the fixed model.
- Theory: universal dynamic regret O(sqrt((T+V_T)(1+P_T))), claimed minimax optimal since it matches the Omega(sqrt(T(1+P_T))) lower bound.
- On the SHL human motion task LASU outperforms ROGD, UOGD, FTFWH, FLH-FTL and ATLAS over 7000 rounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LASU instead of the strongest listed baseline | Online label-shift adaptation · MNIST, four shift types | average error (%): Bernoulli: 2.41±0.09 -> 2.33±0.05; Linear: 2.95±0.08 -> 2.92±0.10; Sine: 2.32±0.13 -> 2.34±0.19; Square: 3.08±0.20 -> 2. | Mixed |
| Use LASU instead of the strongest listed baseline | Online label-shift adaptation · CIFAR-10, four shift types | average error (%): Bernoulli: 10.20±0.41 -> 9.68±0.36; Linear: 10.34±0.29 -> 10.58±0.31; Sine: 9.16±0.15 -> 9.02±0.15; Square: 10.97±0.11 - | Mixed |
| Use LASU instead of the strongest listed baseline | Online label-shift adaptation · EuroSAT, four shift types | average error (%): Bernoulli: 6.08±0.26 -> 4.42±0.14; Linear: 5.80±0.16 -> 5.00±0.10; Sine: 5.69±0.16 -> 4.81±0.03; Square: 6.31±0.15 -> 4. | Helped |
| Use LASU instead of the strongest listed baseline | Online label-shift adaptation · Fashion-MNIST, four shift types | average error (%): Bernoulli: 8.72±0.16 -> 7.86±0.15; Linear: 9.53±0.25 -> 9.04±0.12; Sine: 8.48±0.09 -> 7.76±0.12; Square: 9.47±0.23 -> 8. | Helped |
| Use LASU instead of the strongest listed baseline | Online label-shift adaptation · CINIC-10, four shift types | average error (%): Bernoulli: 24.70±0.30 -> 23.71±0.33; Linear: 21.56±0.50 -> 21.95±0.54; Sine: 18.75±0.27 -> 18.43±0.09; Square: 22.61±0.2 | Mixed |
| Vary the base Opt-OMD step size and combine learners with the LASU ensemble (ablation) | LASU · CIFAR-10 and EuroSAT | average error (%) | Mixed |
| Increase the online sample size (ablation) | Online label-shift algorithms, including LASU · CIFAR-10 and EuroSAT, Bernoulli Shift | average error | Helped |
Limitations
- Assumes bounded loss, bounded decision domain and Lipschitz gradients; theory does not cover feature shift.
- Gap to the best fixed-step Opt-OMD remains due to unknown path variation and label-shift estimation error.
- Regret bound still depends on T, which the authors note as a point to improve.
Experimental setup
Datasets: MNIST CIFAR-10 Fashion-MNIST EuroSAT CINIC-10 SHL
Benchmarks: MNIST CIFAR-10 Fashion-MNIST EuroSAT CINIC-10 SHL
Metrics: average error (%)
Baselines: Fixed FTH FTFWH FLH-FTL ROGD UOGD ATLAS Oracle
Builds on: BBSE ATLAS Opt-OMD Optimistic Hedge universal dynamic regret
Closest papers by meaning
- Efficient Non-stationary Online Learning by Wavelets with Applications to Online Distribution Shift Adaptation (ICML 2024 · similarity 0.89)
- Online Feature Updates Improve Online (Generalized) Label Shift Adaptation (NeurIPS 2024 · similarity 0.88)
- Learning from Noisy Labels via Conditional Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.86)
- Addressing Label Shift in Distributed Learning via Entropy Regularization (ICLR 2025 · similarity 0.86)
- Improving self-training under distribution shifts via anchored confidence with theoretical guarantees (NeurIPS 2024 · similarity 0.86)
- Uncertainty Herding: One Active Learning Method for All Label Budgets (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.