# Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2020.

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

- [Enhancing Efficiency of Safe Reinforcement Learning via Sample Manipulation](https://mlsanity.com/paper/2405.20860/) (2024)
- [Learning Stochastic Graph Neural Networks with Constrained Variance](https://mlsanity.com/paper/2201.12611/) (2022)
- [Graph Neural Networks over the Air for Decentralized Tasks in Wireless Networks](https://mlsanity.com/paper/2302.08447/) (2023)
- [Increasing Batch Size Improves Convergence of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2501.08883/) (2025)
- [Digital Over-the-Air Federated Learning in Multi-Antenna Systems](https://mlsanity.com/paper/2302.14648/) (2023)
- [Dynamic Batch Adaptation](https://mlsanity.com/paper/2208.00815/) (2022)

## Abstract (arXiv)

Stochastic gradient descent is a canonical tool for addressing stochastic optimization problems, and forms the bedrock of modern machine learning and statistics. In this work, we seek to balance the fact that attenuating step-size is required for exact asymptotic convergence with the fact that constant step-size learns faster in finite time up to an error. To do so, rather than fixing the mini-batch and the step-size at the outset, we propose a strategy to allow parameters to evolve adaptively. Specifically, the batch-size is set to be a piecewise-constant increasing sequence where the increase occurs when a suitable error criterion is satisfied. Moreover, the step-size is selected as that which yields the fastest convergence. The overall algorithm, two scale adaptive (TSA) scheme, is developed for both convex and non-convex stochastic optimization problems. It inherits the exact asymptotic convergence of stochastic gradient method. More importantly, the optimal error decreasing rate is achieved theoretically, as well as an overall reduction in computational cost. Experimentally, we observe that TSA attains a favorable tradeoff relative to standard SGD that fixes the mini-batch and the step-size, or simply allowing one to increase or decrease respectively.