Metraipolis › archive › dc_18feba3258ef

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult — arXiv:2609.17483

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.17483
License (as archived)
CC0-1.0
Archived
2026-10-15T20:43:52.490Z
SHA-256 of the archived text
6a045e7c7ed3fa3f7628d30d57425ac6adbc8698411931b2d51b14f7e7d47993
Stable URL of this page
https://metraipolis.com/documento/dc_18feba3258ef

How to cite

Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult — arXiv:2609.17483 — arXiv (en), https://arxiv.org/abs/2609.17483 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_18feba3258ef (Metraipolis archive dc_18feba3258ef, sha256 6a045e7c7ed3fa3f7628d30d57425ac6adbc8698411931b2d51b14f7e7d47993)
BibTeX
@misc{dc18feba3258ef,
  title = {Bridging the Gap Between Homogeneous and Heterogeneous Asynchronous Optimization Is Surprisingly Difficult — arXiv:2609.17483},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.17483},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_18feba3258ef; sha256 6a045e7c7ed3fa3f7628d30d57425ac6adbc8698411931b2d51b14f7e7d47993},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.17483. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Modern large-scale machine learning tasks often require multiple workers, devices, CPUs, or GPUs to compute stochastic gradients in parallel and asynchronously to train model weights. Theoretical results typically distinguish between two settings: (i) the homogeneous setting, where all workers have access to the same data distribution, and (ii) the heterogeneous setting, where each worker operates on different data distributions. Known optimal time complexities in these settings reveal a significant gap, with far more pessimistic guarantees in the heterogeneous case. In this work, we investigate whether these pessimistic optimal time complexities can be overcome under different assumptions. Surprisingly, we show that improvement is provably impossible under widely used first- and second-order similarity assumptions for any randomized algorithm. We then turn to the interpolation regime and demonstrate that the weak interpolation assumption alone is also insufficient. Finally, we introduce a minimal combination of irreducible assumptions, strong interpolation and the local Polyak-Lojasiewicz condition, to derive a new time complexity bound that matches the dependence on worker computation times in the best-known result in the homogeneous setting, without requiring identical data distributions.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in math.OC).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.17483 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T19:36:35.864Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).