Research map / Optimization / Optimizers
ADAM Optimization with Adaptive Batch 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.
Proposes AdamCB, which replaces single-arm bandit batch selection in Adam with a combinatorial semi-bandit (without-replacement DepRound sampling) and proves a regret bound that improves on uniform-sampling AdamX and corrected AdamBS.
Problem
Adam with uniform sampling treats samples equally, and the prior bandit-based sampler AdamBS has convergence/regret analysis errors, allows duplicate samples within a batch, and shows inconsistent empirical results.
Approach
Formulate mini-batch selection as a combinatorial semi-bandit over samples, sampling K distinct samples without replacement via DepRound with capped probabilities summing to K, using importance-weighted gradients and exponential weight updates driven by gradient norms, and combining this with Adam's update rule.
Key results
- AdamCB achieves regret bound O(d sqrt(T) + sqrt(d)/n^{3/4} (T/K ln(n/K))^{1/4}), improving on AdamBS's corrected bound by a factor of K inside the second term.
- Across MNIST, Fashion MNIST and CIFAR10 with MLP and CNN, AdamCB consistently shows faster reduction in training and test loss than Adam, AdamX and AdamBS (averaged over five seeds).
- Reproduction of AdamBS yields inconsistent results with significant loss fluctuations and possible divergence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use combinatorial bandit sampling for adaptive batch selection instead of uniform sampling | Adam · Cumulative regret | regret bound: \Ocal \big(d\sqrt{T} + \frac{\sqrt{d}}{n^{1/2}}\sqrt{T}\big) -> \Ocal\big(d\sqrt{T} + \frac{\sqrt{d}}{n^{3/4}} \left(\fr | Helped |
| Use combinatorial batch sampling instead of single-action bandit sampling | Adam · Cumulative regret | regret bound: \Ocal\big(d\sqrt{T} + \frac{\sqrt{d}}{n^{3/4}}\left(T\ln{n}\right)\!^{\frac{1}{4}}\big) -> \Ocal\big(d\sqrt{T} + \frac{\ | Helped |
| Use combinatorial bandit sampling for adaptive batch selection | Adam · MNIST, Fashion MNIST, and CIFAR10 | training and test loss | Helped |
| Use combinatorial bandit sampling instead of AdamBS bandit sampling | Adam · MNIST, Fashion MNIST, and CIFAR10 | training and test loss | Helped |
Surprising findings
- The original AdamBS regret proof contains an error (Jensen's inequality applied to a non-convex expression), and AdamBS's reported results could not be reliably reproduced.
Limitations
- Regret analysis relies on bounded gradient and bounded parameter assumptions, with bounded gradient variance needed only for fair comparison.
- Experiments are limited to small MLP and CNN models on MNIST, Fashion MNIST and CIFAR10.
Experimental setup
Datasets: MNIST Fashion MNIST CIFAR10
Benchmarks: MNIST Fashion MNIST CIFAR10
Metrics: training loss test loss regret bound
Baselines: Adam AdamX AdamBS
Builds on: Adam AdamBS AdamX EXP3 DepRound
Closest papers by meaning
- A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD (ICML 2025 · similarity 0.87)
- Prodigy: An Expeditiously Adaptive Parameter-Free Learner (ICML 2024 · similarity 0.86)
- Understanding the Generalization of Stochastic Gradient Adam in Learning Neural Networks (NeurIPS 2025 · similarity 0.86)
- Adam-mini: Use Fewer Learning Rates To Gain More (ICLR 2025 · similarity 0.86)
- Surge Phenomenon in Optimal Learning Rate and Batch Size Scaling (NeurIPS 2024 · similarity 0.85)
- ADOPT: Modified Adam Can Converge with Any $\beta_2$ with the Optimal Rate (NeurIPS 2024 · 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.