# Stochastic Approximation with Block Coordinate Optimal Stepsizes

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 55 references that are in the map.
- First posted on arXiv 11 Jul 2025.

## Builds on (most cited first, 24 of 24)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [A Simple Convergence Proof of Adam and Adagrad](https://mlsanity.com/paper/2003.02395/) (2020)
- [Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients](https://mlsanity.com/paper/1705.07774/) (2017)
- [Adam-mini: Use Fewer Learning Rates To Gain More](https://mlsanity.com/paper/2406.16793/) (2024)
- [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018)
- [Adam Can Converge Without Any Modification On Update Rules](https://mlsanity.com/paper/2208.09632/) (2022)
- [Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models](https://mlsanity.com/paper/2402.19449/) (2024)
- [Stochastic Sign Descent Methods: New Algorithms and Better Theory](https://mlsanity.com/paper/1905.12938/) (2019)
- [Optimal Linear Decay Learning Rate Schedules and Further Refinements](https://mlsanity.com/paper/2310.07831/) (2023)
- [Can We Remove the Square-Root in Adaptive Gradient Methods? A Second-Order Perspective](https://mlsanity.com/paper/2402.03496/) (2024)
- [Effective Theory of Transformers at Initialization](https://mlsanity.com/paper/2304.02034/) (2023)
- [An improvement of the convergence proof of the ADAM-Optimizer](https://mlsanity.com/paper/1804.10587/) (2018)
- [FAdam: Adam is a natural gradient optimizer using diagonal empirical Fisher information](https://mlsanity.com/paper/2405.12807/) (2024)
- [AdaFisher: Adaptive Second Order Optimization via Fisher Information](https://mlsanity.com/paper/2405.16397/) (2024)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [AdamS: Momentum Itself Can Be A Normalizer for LLM Pretraining and Post-training](https://mlsanity.com/paper/2505.16363/) (2025)

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

- [Clarifying Shampoo: Adapting Spectral Descent to Stochasticity and the Parameter Trajectory](https://mlsanity.com/paper/2602.09314/) (2026)
- [Schattor: Schatten-family methods for deep learning optimization](https://mlsanity.com/paper/2606.15702/) (2026)
- [Second-Moment Stochastic Approximation Methods](https://mlsanity.com/paper/2609.36600/) (2026)

## Abstract (arXiv)

We consider stochastic approximation with block-coordinate stepsizes and propose adaptive stepsize rules that aim to minimize the expected distance from the next iterate to an (unknown) target point. These stepsize rules employ online estimates of the second moment of the search direction along each block coordinate. The popular Adam algorithm can be interpreted as a variant with a specific estimator. By leveraging a simple conditional estimator, we derive a new method that obtains competitive performance against Adam but requires less memory and fewer hyper-parameters. We prove that this family of methods converges almost surely to a small neighborhood of the target point, and the radius of the neighborhood depends on the bias and variance of the second-moment estimator. Our analysis relies on a simple aiming condition that assumes neither convexity nor smoothness, thus has broad applicability.