# Adaptive Sampling Strategies for Stochastic Optimization

arXiv: https://arxiv.org/abs/1710.11258 · HTML: https://mlsanity.com/paper/1710.11258/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2017.

## Built on by (most cited first, 30 of 30)

- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Cramming: Training a Language Model on a Single GPU in One Day](https://mlsanity.com/paper/2212.14034/) (2022)
- [A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scale](https://mlsanity.com/paper/2309.06497/) (2023)
- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021)
- [Globally Convergent Multilevel Training of Deep Residual Networks](https://mlsanity.com/paper/2107.07572/) (2021)
- [Enhancing Efficiency of Safe Reinforcement Learning via Sample Manipulation](https://mlsanity.com/paper/2405.20860/) (2024)
- [AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methods](https://mlsanity.com/paper/2402.11215/) (2024)
- [Cockpit: A Practical Debugging Tool for the Training of Deep Neural Networks](https://mlsanity.com/paper/2102.06604/) (2021)
- [Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits](https://mlsanity.com/paper/2111.07952/) (2021)
- [IMPACT: A Generic Semantic Loss for Multimodal Medical Image Registration](https://mlsanity.com/paper/2503.24121/) (2025)
- [Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization](https://mlsanity.com/paper/2109.12213/) (2021)
- [Communication-Efficient Adaptive Batch Size Strategies for Distributed Local Gradient Methods](https://mlsanity.com/paper/2406.13936/) (2024)
- [Adaptive Batch Size Schedules for Distributed Training of Language Models with Data and Model Parallelism](https://mlsanity.com/paper/2412.21124/) (2024)
- [AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Size](https://mlsanity.com/paper/2402.05264/) (2024)
- [Communication-Efficient Federated Optimization over Semi-Decentralized Networks](https://mlsanity.com/paper/2311.18787/) (2023)
- [Adaptive Batch Sizes Using Non-Euclidean Gradient Noise Scales for Stochastic Sign and Spectral Descent](https://mlsanity.com/paper/2602.03001/) (2026)
- [A Retrospective Approximation Approach for Smooth Stochastic Optimization](https://mlsanity.com/paper/2103.04392/) (2021)
- [Adaptive First- and Second-Order Algorithms for Large-Scale Machine Learning](https://mlsanity.com/paper/2111.14761/) (2021)
- [Efficient Personalization of Quantized Diffusion Model without Backpropagation](https://mlsanity.com/paper/2503.14868/) (2025)
- [Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions](https://mlsanity.com/paper/2104.12949/) (2021)
- [GOALS: Gradient-Only Approximations for Line Searches Towards Robust and Consistent Training of Deep Neural Networks](https://mlsanity.com/paper/2105.10915/) (2021)
- [On the equivalence of different adaptive batch size selection strategies for stochastic gradient descent methods](https://mlsanity.com/paper/2109.10933/) (2021)
- [Bolstering Stochastic Gradient Descent with Model Building](https://mlsanity.com/paper/2111.07058/) (2021)
- [A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization](https://mlsanity.com/paper/2206.06531/) (2022)
- [Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothness](https://mlsanity.com/paper/2212.01848/) (2022)
- [AdLoCo: adaptive batching significantly improves communications efficiency and convergence for Large Language Models](https://mlsanity.com/paper/2508.18182/) (2025)
- [Guiding the Recommender: Information-Aware Auto-Bidding for Content Promotion](https://mlsanity.com/paper/2601.20422/) (2026)
- [Why Does Adaptive Batching Help LLM Pretraining? A Perspective from Unbounded Variance](https://mlsanity.com/paper/2610.02355/) (2026)

## Abstract (arXiv)

In this paper, we propose a stochastic optimization method that adaptively controls the sample size used in the computation of gradient approximations. Unlike other variance reduction techniques that either require additional storage or the regular computation of full gradients, the proposed method reduces variance by increasing the sample size as needed. The decision to increase the sample size is governed by an inner product test that ensures that search directions are descent directions with high probability. We show that the inner product test improves upon the well known norm test, and can be used as a basis for an algorithm that is globally convergent on nonconvex functions and enjoys a global linear rate of convergence on strongly convex functions. Numerical experiments on logistic regression problems illustrate the performance of the algorithm.