Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity

• URL: http://arxiv.org/abs/2605.13434v1
• Date: Wed, 13 May 2026 12:27:22 GMT
• Title: Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity
• Abstract summary: Asynchronous Vanilla (ASGD) is a standard way to exploit heterogeneous compute resources in distributed learning.<n>We show that the method is biased toward frequency-weighted steps of local objectives rather than the global objective.<n> Experiments confirm that the method converges to the correct objective and is competitive with state-of-the-art baselines.
• Score: 45.88028371034407
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Impute-EM: Native Mixed-State Diffusion Models for Heterogeneous Data Imputation [71.74203645336385]
  Impute-EM alternates between imputing missing entries with the current model and refitting a diffusion backbone on completed data.<n>We characterize the update and show that the observed mask-indexed marginals match the targets at the limit.
  arXiv  Detail & Related papers  (2026-09-14T09:39:13Z)
• Hierarchical Exponential-Gaussian Mixtures for Watch-Time Distribution Prediction [74.05279072166697]
  Exponential-Gaussian Mixture Network (EGMN) models the full conditional WT distribution.<n>EGMN is vulnerable to variance collapse, component redundancy, and inactive components.<n>We propose a Hierarchical Exponential-Gaussian Mixture (HEGM) model that addresses these failure modes.
  arXiv  Detail & Related papers  (2026-08-24T15:06:18Z)
• Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers [8.286183477962203]
  parallelization of training is an important strategy for increasing scale.<n>With constant step sizes, the convergence of ASGD is affected negatively by slow workers due to large delays in updates.<n>We show convergence in expectation, and the first time in asynchronous optimization, convergence with high probability.
  arXiv  Detail & Related papers  (2026-06-11T12:43:53Z)
• Simple yet Effective: Low-Rank Spatial Attention for Neural Operators [12.794762297826848]
  We introduce Low-Rank Spatial Attention (LRSA) as a clean and direct instantiation of this template.<n>Unlike prior approaches that often rely on non-standard aggregation or normalization modules, LRSA is built purely from standard Transformer primitives.<n>In our experiments, such a simple construction is sufficient to achieve high accuracy, yielding an average error reduction of over 17%.
  arXiv  Detail & Related papers  (2026-04-04T04:15:01Z)
• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  We introduce Ringleader ASGD, the first asynchronous algorithm that attains the theoretical lower bounds for parallel computation.<n>Our analysis further establishes that Ringleader ASGD remains optimal under arbitrary gradient and even time-varying speeds.
  arXiv  Detail & Related papers  (2025-09-26T19:19:15Z)
• BayesTTA: Continual-Temporal Test-Time Adaptation for Vision-Language Models via Gaussian Discriminant Analysis [41.09181390655176]
  Vision-language models (VLMs) such as CLIP achieve strong zero-shot recognition but degrade significantly under textittemporally evolving distribution shifts common in real-world scenarios.<n>We formalize this practical problem as textitContinual-Temporal Test-Time Adaptation (CT-TTA), where test distributions evolve gradually over time.<n>We propose textitBayesTTA, a Bayesian adaptation framework that enforces temporally consistent predictions and dynamically aligns visual representations.
  arXiv  Detail & Related papers  (2025-07-11T14:02:54Z)
• Adaptive Deadline and Batch Layered Synchronized Federated Learning [66.93447103966439]
  Federated learning (FL) enables collaborative model training across distributed edge devices while preserving data privacy, and typically operates in a round-based synchronous manner.<n>We propose ADEL-FL, a novel framework that jointly optimize per-round deadlines and user-specific batch sizes for layer-wise aggregation.
  arXiv  Detail & Related papers  (2025-05-29T19:59:18Z)
• Collaborative Heterogeneous Causal Inference Beyond Meta-analysis [68.4474531911361]
  We propose a collaborative inverse propensity score estimator for causal inference with heterogeneous data. Our method shows significant improvements over the methods based on meta-analysis when heterogeneity increases.
  arXiv  Detail & Related papers  (2024-04-24T09:04:36Z)
• Asynchronous Local-SGD Training for Language Modeling [37.02427878640653]
  Local gradient descent (Local-SGD) is an approach to distributed optimization where each device performs more than one SGD update per communication. This work presents an empirical study of it asynchronous Local-SGD for training language models; that is, each worker updates the global parameters as soon as it has finished its SGD steps.
  arXiv  Detail & Related papers  (2024-01-17T11:17:04Z)
• Linear Speedup of Incremental Aggregated Gradient Methods on Streaming Data [38.54333970135826]
  This paper considers a type of incremental aggregated gradient (IAG) method for large-scale distributed optimization. We show that the streaming IAG method achieves linear speedup when the workers are updating frequently enough.
  arXiv  Detail & Related papers  (2023-09-10T10:08:52Z)
• DRAG: Divergence-based Adaptive Aggregation in Federated learning on Non-IID Data [11.830891255837788]
  Local gradient descent (SGD) is a fundamental approach in achieving communication efficiency in Federated Learning (FL) We introduce a novel metric called degree of divergence," quantifying the angle between the local gradient and the global reference direction. We propose the divergence-based adaptive aggregation (DRAG) algorithm, which dynamically drags" the received local updates toward the reference direction in each round without requiring extra communication overhead.
  arXiv  Detail & Related papers  (2023-09-04T19:40:58Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  We study shuffling-based variants: minibatch and local Random Reshuffling, which draw gradients without replacement. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds which show that these shuffling-based variants converge faster than their with-replacement counterparts. We propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
  arXiv  Detail & Related papers  (2021-10-20T02:25:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.