Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity
Ammar Mahran, Artavazd Maranjyan, Peter Richtárik · 2026
Read Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity by Ammar Mahran, Artavazd Maranjyan, Peter Richtárik (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13434.txt.
Introduction
Ammar Mahran, Artavazd Maranjyan and Peter Richtarik propose Rescaled Asynchronous SGD to fix bias in distributed learning under heterogeneity. In asynchronous gradient descent, the server updates whenever a gradient arrives, so fast workers contribute more. With mixed data, vanilla ASGD leans toward a frequency-weighted average of goals, not the global goal. Existing fixes add gathering or buffering. The authors instead rescale stepsizes by compute time, so every worker contributes the same learning rate. They prove convergence to the correct goal, with time cost at the lower bound.
Catalog record
| CREATOR | Ammar Mahran, Artavazd Maranjyan, Peter Richtárik |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98938 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13434
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity Ammar Mahran, Artavazd Maranjyan, Peter Richtárik Abstract Asynchronous stochastic gradient descent (ASGD) is a standard way to exploit heterogeneous compute resources in distributed learning: instead of forcing fast workers to wait for slow ones, the server updates the model whenever a gradient arrives. Vanilla ASGD applies each arriving gradient with the same weight. When local data distributions are heterogeneous, this becomes problematic: faster workers contribute more updates, and we show theoretically that the method is biased toward a frequency-weighted average of the local objectives rather than the desired global objective. Existing remedies typically move away from the simple ASGD template by introducing gathering phases, buffering, or extra memory. We show that this is unnecessary. Keeping the standard ASGD mechanism, we recover the correct objective by rescaling worker-specific stepsizes in proportion to their computation times, so that each worker contributes the same aggregate learning rate over a cycle. In the non-convex setting, under smoothness and bounded heterogeneity assumptions, we prove that the resulting method, Rescaled ASGD , converges to stationary points of the correct global objective in the fixed-computation model. Its time complexity matches the known lower bound in the leading term, while the effects of staleness and data heterogeneity appear only in lower-order terms. Experiments confirm that the method converges to the correct objective and is competitive with state-of-the-art baselines. theorem]Theorem theorem]Lemma theorem]Definition theorem]Assumption 1 Introduction We consider the non-convex distributed optimization problem \min_{\mathbf{x}\in\mathbb{R}^{d}}\left\{F(\mathbf{x})\coloneqq\frac{1}{n}\sum_{i=1}^{n}F_{i}(\mathbf{x})\right\}, (1) where F_{i}:\mathbb{R}^{d}\to\mathbb{R},\mathbf{x}\mapsto{\mathbb{E}}_{\xi\sim\mathcal{D}_{i}}\left[f_{i}(\mathbf{x};\xi)\right] denotes the local objective function of worker i=1,\dots,n , which is the expected value of the sample loss f_{i}(\mathbf{x};\xi) over data points \xi drawn from their local distribution \mathcal{D}_{i} . In parallel stochastic gradient descent methods, workers collaboratively solve this problem by computing stochastic gradients of their local objectives, which are then processed by a central server to find an \varepsilon -stationary point, that is, a random vector \bar{\mathbf{x}}\in\mathbb{R}^{d} such that \mathbb{E}\left\|\nabla F(\bar{\mathbf{x}})\right\|^{2}\leq\varepsilon . In this model, workers differ across two dimensions. First, each worker has their own local objective function F_{i} which may differ from one another and the global objective function F . These objective functions vary across workers, typically due to highly heterogeneous local data distributions \mathcal{D}_{i} , as is common in federated learning ( 36 ; 8 ; 20 ; 47 ) , for example. While early asynchronous literature primarily focused on the homogeneous data setting ( 45 ; 34 , e.g.,) , recent extensions to the heterogeneous setting ( 37 ; 22 ; 40 ) often require restrictive similarity assumptions or algorithmic modifications. In the present work, our focus is on the general case allowing for data heterogeneity ( F_{i}\neq F_{j} ) under a relaxed similarity assumption ( 2.5 ). Second, workers may also differ in the time it takes them to compute stochastic gradients, due to, for example, hardware differences ( 12 ; 26 ; 30 ; 32 ; 33 ) . We denote the time needed for worker i to compute a stochastic gradient by \tau_{i} throughout the text and explicitly allow for these to differ across workers. Table 1 : Comparison of worst-case wall-clock time complexities for parallel stochastic first-order methods in the fixed-computation time model with data and system heterogeneity to achieve \varepsilon -stationarity in ( 1 ). We denote the arithmetic mean and maximum, respectively, of the workers’ computation times by \tau_{A},\tau_{\max} . Problem parameters include the initial optimality gap \Delta\coloneqq F(\mathbf{x}^{0})-F^{*} and global smoothness constant L ( 2.3 ), the target stationarity \varepsilon>0 , and a bound on the stochastic gradient variance \sigma^{2} ( 2.2 ). Asymptotic Optimality: time complexity matches the lower bound established by 45 in the leading term and achieves \varepsilon -stationarity for arbitrarily small \varepsilon . No Idle Workers: all workers remain busy and computational resources are fully utilized. No Memory Overhead: no gradients or model iterates need to be stored for later use. Method (Reference) Time Complexity (Leading Term) Asymptotic Optimality No Idle Workers No Memory Overhead Naive Minibatch SGD ( 10 ; 11 ) \frac{\Delta L\sigma^{2}}{n\varepsilon^{2}}\tau_{\max} ✘ ✘ ✔ Malenia SGD ( 45 ) \frac{\Delta L\sigma^{2}}{n\varepsilon^{2}}\tau_{A} ✔ ✔ ✘ Ringleader ASGD ( 31 ) \frac{\Delta L^{\prime}\sigma^{2}}{n\varepsilon^{2}}\tau_{A} (†) ✘ ✔ ✘ Concurrent ASGD ( 22 ) \frac{\Delta L(\sigma^{2}+\zeta^{2})}{n\varepsilon^{2}}\tau_{\max} (‡) ✘ ✘ ✘ Delay-Adaptive ASGD ( 37 ) \frac{\Delta L\sigma^{2}}{n\varepsilon^{2}}\tau_{A} ✘ (‡) ✔ ✔ Rescaled ASGD Theorem 4.1 , Corollary 4.2 \frac{\Delta L\sigma^{2}}{n\varepsilon^{2}}\tau_{A} ✔ ✔ ✔ (†) 31 rely on a constant L^{\prime}\geq L to bound data heterogeneity. In certain settings, L^{\prime}=\mathcal{O}(L) , and Ringleader ASGD achieves optimal time complexity. (‡) 22 ; 37 rely on a stricter assumption on the data heterogeneity, \left\|\nabla F_{i}(\mathbf{x})-\nabla F(\mathbf{x})\right\|^{2}\leq\zeta^{2} . In Concurrent ASGD , the constant \zeta^{2} affects the leading term of the time complexity. In Delay-Adaptive ASGD , the gradient norm can be bounded only up to this constant, therefore not achieving arbitrary \varepsilon -stationarity, and thus no asymptotic optimality. If the computation times are equal across workers, Delay-Adaptive ASGD achieves arbitrary \varepsilon -stationarity with the leading term of the time complexity scaling with \tau_{A} . See Appendix D for details. Naive Distributed Optimization In Naive Minibatch SGD ( 10 ; 11 ) , each worker i computes a stochastic gradient in \tau_{i} units of time and sends it to the central server. Once the server has received gradients from all workers, gradients are averaged, and the model is updated and sent back to the workers for computation of another round of gradients. Each round thus takes \tau_{\max}\coloneqq\max_{i}\tau_{i} units of time, leaving faster workers idle after delivering their gradients while they wait for the global model update. While this fully synchronized procedure simplifies the theoretical analysis to that of standard SGD, it severely underutilizes fast workers whose idle time could be spent more productively. Leveraging Faster Workers 45 introduce an improved variant, Malenia SGD , that addresses worker idleness. In this algorithm, workers compute a number of stochastic gradients at the current model until the server receives at least one stochastic gradient from each. Thus, faster workers do not idly wait after computation of a single stochastic gradient, but continue computing stochastic gradients at the same model iterate. These gradients are then averaged per worker, so that each worker effectively delivers one stochastic gradient with reduced variance. Once the server has obtained at least one gradient from each worker, the model is updated and sent back to all workers for the next round. While the gradient gathering phase is asynchronous, the model update happens synchronously ensuring all workers compute gradients at the same model iterate in each round. Building on this, 31 introduce an asynchronous algorithm, Ringleader ASGD , in which the number of model updates is greater, allowing for greater exploration of the search space. Here, the gradient gathering phase is followed by n asynchronous updates, one from each worker. Notably, Ringleader ASGD utilizes a gradient table in which gradients from all workers are stored to ensure that once an asynchronous update is taken, the step direction approximates the gradient of the global objective function rather than that of the workers’ local objective functions. As in Naive Minibatch SGD and Malenia SGD , the gathering phase causes the slowest worker to dictate when updates from all workers can