Research map / Bandits and online learning / Multi-armed bandits
Adaptive Data Collection for Robust Learning Across Multiple Distributions
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 UCB-OGD, an adaptive data collection method that uses UCB source selection with online gradient descent to minimize worst-case expected loss across multiple data distributions under a fixed annotation budget, with a regret bound of O(T^{1/2}(K ln T)^{1/2}).
Problem
Robust learning across multiple data distributions under a fixed data collection/annotation budget, where the goal is to minimize the maximum expected loss across sources without an initial annotated pool.
Approach
Treat source selection as a multi-armed bandit: at each round choose the data source with the highest UCB on its empirical loss, collect and annotate a batch from it, and update the model with online gradient descent on that source's gradient, yielding minimax regret guarantees.
Key results
- UCB-OGD achieves a minimum CIFAR10 accuracy of 52.3 vs 36.3 for Rand-OGD at a 10K budget, and matches the best active learning minimum (DBAL 52.7).
- On the COSMOS testbed, UCB-OGD improves minimum AP@50 by 4.7 points over Rand-OGD (61.7 vs 57.0) and reaches 57.0 AP@50 with 2,160 samples instead of 2,500.
- Theory: UCB-OGD achieves O(T^{1/2}(K ln T)^{1/2}) minimax regret, with a lower bound of Omega(T^{1/2}), so it is optimal up to a ln T factor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UCB sampling instead of random sampling | OGD data collection · CIFAR10 | minimum class-wise accuracy: 36.3 -> 52.3 | Helped |
| Use UCB sampling instead of random sampling | OGD data collection · CIFAR10 | mean class-wise accuracy: 63.3 -> 66.5 | Helped |
| Use UCB sampling instead of random sampling | OGD data collection · VOC2012 | minimum mAP@50: 40.6 -> 44.7 | Helped |
| Use UCB sampling instead of random sampling | OGD data collection · VOC2012 | mean mAP@50: 51.3 -> 53.0 | Helped |
| Use UCB sampling instead of random sampling | OGD data collection · VQAv2 | minimum per-token accuracy: 20.9 -> 22.6 | Helped |
| Use UCB sampling instead of random sampling | OGD data collection · VQAv2 | mean per-token accuracy: 20.9 -> 22.9 | Helped |
| Use UCB sampling instead of random sampling | OGD data collection · COSMOS testbed | minimum AP@50: +4.7 AP@50 | Helped |
| Use UCB sampling instead of random sampling | OGD data collection · COSMOS testbed | mean AP@50: 66.7 -> 69.2 | Helped |
| Use UCB sampling instead of MDN active learning | VOC2012 object detection · VOC2012 | minimum mAP@50: 42.2 -> 44.7 | Helped |
| Use UCB sampling instead of MDN active learning | VOC2012 object detection · VOC2012 | mean mAP@50: 47.2 -> 53.0 | Helped |
| Increase MDN's initial labeled pool size (ablation) | MDN on VOC2012 · VOC2012 | minimum and mean mAP@50: 1,200 initially labeled samples (40% of budget) | Helped |
| Use Adam with cosine-annealing learning-rate scheduling and L2 regularization (ablation) | UCB-OGD on MNIST · MNIST | validation accuracy trajectory | Helped |
Surprising findings
- The MDN active learning baseline needs about 1,200 initial labeled samples (40% of budget) on VOC2012 to surpass UCB-OGD, suggesting pool-based AL is sensitive to the initial pool size.
Limitations
- Regret bounds are proven for convex losses; non-convex case only yields convergence to Pareto-stationary points under time-smoothing.
- Experiments are small-scale (e.g., VQA with 1K QA pairs, and the authors note larger experiments are needed).
- Theoretical guarantees rely on assumptions such as iid sampling and bounded Lipschitz losses, and generalization regret is left out of scope.
Experimental setup
Datasets: CIFAR10 MNIST PASCAL VOC2012 VQAv2 COSMOS testbed
Benchmarks: CIFAR10 PASCAL VOC2012 VQAv2 COSMOS testbed
Metrics: minimum accuracy mean accuracy mAP@50 AP@50
Baselines: Rand-OGD Eps-OGD Uncertainty sampling Entropy sampling BALD DBAL BADGE MDN
Builds on: Auer et al. 2002 UCB / epsilon-greedy bandits online gradient descent group distributionally robust optimization Haghtalab et al. 2022 on-demand sampling
Closest papers by meaning
- On the Convergence of Loss and Uncertainty-based Active Learning Algorithms (NeurIPS 2024 · similarity 0.84)
- Sparse Optimistic Information Directed Sampling (NeurIPS 2025 · similarity 0.84)
- Robust Sampling for Active Statistical Inference (NeurIPS 2025 · similarity 0.84)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.83)
- Sample-Adaptivity Tradeoff in On-Demand Sampling (NeurIPS 2025 · similarity 0.83)
- Leveraging (Biased) Information: Multi-armed Bandits with Offline Data (ICML 2024 · similarity 0.83)
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.