# Adaptivity via a Parallel Architecture for Stochastic Gradient Methods

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 31 Jul 2026.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks](https://mlsanity.com/paper/1806.06763/) (2018)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [Variants of RMSProp and Adagrad with Logarithmic Regret Bounds](https://mlsanity.com/paper/1706.05507/) (2017)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Scale-Free Algorithms for Online Linear Optimization](https://mlsanity.com/paper/1502.05744/) (2015)
- [Linear Convergence of Adaptive Stochastic Gradient Descent](https://mlsanity.com/paper/1908.10525/) (2019)
- [Distributed Stochastic Optimization via Adaptive SGD](https://mlsanity.com/paper/1802.05811/) (2018)
- [AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods](https://mlsanity.com/paper/1711.01761/) (2017)
- [MT-DAO: Multi-Timescale Distributed Adaptive Optimizers with Local Updates](https://mlsanity.com/paper/2510.05361/) (2025)

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

- [Arithmetic Simplicity in Stochastic Gradient Methods](https://mlsanity.com/paper/2609.32240/) (2026)

## Abstract (arXiv)

Let A(x0,y) be an algorithm with two inputs: an initial point x0 and an integer parameter y, which specifies that A(.,.) executes at most y iterations or steps. Given an integer p≥ 1, p parallel processors search an appropriate value of T for for A(.). Each processor executes an infinite sequence of stages indexed by i=0,1,2,ldots. At stage i, processor j is assigned Tj,i=h(j,i), where h:mathbbN×mathbbNrightarrowℝ+ is a prescribed function. Processor j (j=0,1,ldots,p-1) then executes A(x0,Tj,i). The efficiency of the parallel framework is characterized by its (p,αp)-approximation guarantee. Specifically, for every integer T≥ T0, there exist a processor j and a stage i such that T≤ Tj,i≤ Tj,i^*<αp T, where Tj,i^*=sumt=0iTj,t denotes the cumulative number of iterations executed by processor j from the beginning to stage i. We prove that this framework achieves a (p,αp)-approximation, and a tight lower bound for αp for all large p. We develop arithmetically simple stochastic gradient methods in which every division is of the form x/2t for some integer t, and integrate them into the proposed parallel framework.