Metraipolis › archive › dc_a720c19b29f5

Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity — arXiv:2609.21878

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.21878
License (as archived): CC0-1.0
Archived: 2026-10-10T02:04:47.611Z
SHA-256 of the archived text: 800e56a96f0a37712756e65b5c06ca5a6455e1fede1dd7e0bbab4e6cb3e7e89b
Stable URL of this page: https://metraipolis.com/documento/dc_a720c19b29f5

How to cite

Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity — arXiv:2609.21878 — arXiv (en), https://arxiv.org/abs/2609.21878 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a720c19b29f5 (Metraipolis archive dc_a720c19b29f5, sha256 800e56a96f0a37712756e65b5c06ca5a6455e1fede1dd7e0bbab4e6cb3e7e89b)

BibTeX

@misc{dca720c19b29f5,
  title = {Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity — arXiv:2609.21878},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21878},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a720c19b29f5; sha256 800e56a96f0a37712756e65b5c06ca5a6455e1fede1dd7e0bbab4e6cb3e7e89b},
  year = {2026}
}

Archived text

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

We consider distributed stochastic convex optimization with a fixed budget of $N$ independent samples split among $m$ workers. Sample average approximation reduces the problem to a regularized finite-sum problem whose local Hessians are statistically similar. This allows the Hessian of the local objective at the server to be used as an inexact Hessian of the global objective, while the workers communicate only gradients. We apply the optimal accelerated inexact Newton extragradient method of (Chen et al., 2026) and propose its distributed restarted variant for the strongly convex empirical problem. The method reaches the statistical accuracy of order $N^{-1/2}$ in $\widetilde O\left(\max\{N^{1/7},m^{1/4}\}\right)$ communication rounds. Hence, with $m=N^{4/7}$ workers, it requires $\widetilde O\left(N^{1/7}\right)$ rounds, improving the dependence on the total sample size from $\widetilde O\left(N^{1/6}\right)$ for the previous accelerated cubic Newton construction of (Agafonov et al., 2021). Each iteration uses two gradient aggregation rounds and does not require Hessian communication.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.21878 — 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-10T01:45:31.247Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).