Research map / Bandits and online learning / Multi-armed bandits
Bandit Guided Submodular Curriculum for Adaptive Subset Selection
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.
Frames adaptive subset selection for curriculum learning as a multi-armed bandit over submodular functions, proposing OnlineSubmod, a greedy validation-reward-driven arm selection policy with claimed no-regret guarantees, evaluated on LLM finetuning (LLaMA-2-7B, Mistral-7B on MMLU/TydiQA) and image classification.
Problem
Adaptive subset selection for curriculum learning requires a difficulty notion that is reliable and evolves with training, but existing methods (bilevel optimization, gradient matching, importance sampling) are computationally expensive.
Approach
Treat each monotone submodular function as a bandit arm that selects a training subset per batch; the arm is chosen greedily by a validation-loss-reduction reward (one-step influence-style utility), with an annealed exploration threshold, yielding a cheap online curriculum with a regret bound.
Key results
- On LLaMA-2-7B MMLU/TydiQA fine-tuning, OnlineSubmod reaches 49.6% average versus 47.8% for the best baseline (GREATS).
- On TinyImageNet at 10% budget, OnlineSubmod (batchwise) reports 0.553 accuracy versus 0.544 for Rho-Loss and 0.532 for MILO.
- Reports submodular selection takes about 0.8 ms versus 630 ms of gradient computation per step for LLaMA-2-7B with LoRA rank 128.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OnlineSubmod instead of GREATS | LLM fine-tuning · MMLU | average accuracy | Helped |
| Use OnlineSubmod instead of the strongest listed baseline | ResNet18 subset training · TinyImageNet, CIFAR-100, and CIFAR-10 at 10%, 30%, and 50% budgets | test accuracy | Mixed |
| Use gradient-based features instead of DINO embeddings for submodular selection (ablation) | Submodular acquisition · Fashion-MNIST across subset sizes | test accuracy | Helped |
| Set exploration sharpness to π = 1.5 rather than π = 1.0 or π = 0.5 (ablation) | OnlineSubmod · Image classification experiments | model performance | Helped |
| Use a few epochs of full-data warm-up before subset selection (ablation) | Image subset-selection algorithms · Image classification | downstream accuracy | Helped |
Surprising findings
- Authors report RHO-Loss converges within a few epochs but does not improve further and falls short of other SOTA baselines.
Limitations
- Regret bound relies on strong assumptions (constant exploration dampening, bounded sharpness, known optimality gap).
- Gradient approximations (last layer, LoRA) and identity Hessian approximation may not hold in general.
- Broader impact section not discussed.
Experimental setup
Datasets: MMLU TydiQA LESS OpenWebText subset CIFAR-10 CIFAR-100 TinyImageNet SVHN MNIST
Benchmarks: MMLU TydiQA CIFAR-10 CIFAR-100 TinyImageNet
Metrics: accuracy test perplexity speedup
Baselines: GradNorm MaxLoss RhoLoss SBERT GREATS GradMatch CRAIG GLISTER BOSS MILO
Builds on: GREATS GradMatch CRAIG GLISTER RHO-Loss
Closest papers by meaning
- LASeR: Learning to Adaptively Select Reward Models with Multi-Arm Bandits (NeurIPS 2025 · similarity 0.85)
- From Imitation to Discrimination: Toward a Generalized Curriculum Advantage Mechanism Enhancing Cross-Domain Reasoning Tasks (AAAI 2026 · similarity 0.85)
- Multiple Trade-offs: An Improved Approach for Lexicographic Linear Bandits (AAAI 2025 · similarity 0.84)
- AdaCuRL: Adaptive Curriculum Reinforcement Learning with Invalid Sample Mitigation and Historical Revisiting (AAAI 2026 · similarity 0.84)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.84)
- Dual-Level Curriculum Meta-Learning for Noisy Few-Shot Learning Tasks (AAAI 2024 · similarity 0.84)
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.