Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
Abstract
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 Õ(max{N1/7,m1/4}) communication rounds. Hence, with m=N4/7 workers, it requires Õ(N1/7) rounds, improving the dependence on the total sample size from Õ(N1/6) 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.
Related
- Noise-Robust Distributed Optimization Over Directed Graphs With Row Stochastic Matrices
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits
- Optimal Network Dependence in Distributed Stochastic Optimization via Tree Routing
- Low-Bit Distributed Constrained Optimization with Application to Optimal Scheduling and Allocation
- Sample average approximation of multiobjective stochastic optimization problems with application in insurance
BibTeX
@misc{sokolov2026application,
title = {{Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity}},
author = {Yury A. Sokolov and Maxim K. Mashtaler and Alexander V. Gasnikov and Martin Takáč and Dmitry I. Kamzolov and Artem D. Agafonov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21878},
eprint = {2609.21878},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21878},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
AU - Yury A. Sokolov
AU - Maxim K. Mashtaler
AU - Alexander V. Gasnikov
AU - Martin Takáč
AU - Dmitry I. Kamzolov
AU - Artem D. Agafonov
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21878
UR - https://arxiv.org/abs/2609.21878
AB - 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 Õ(max{N^1/7,m^1/4}) communication rounds. Hence, with m=N^4/7 workers, it requires Õ(N^1/7) rounds, improving the dependence on the total sample size from Õ(N^1/6) 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.
ER -