2021/03/26 by Artem Agafonov, Pavel Dvurechensky, Agafonov, Artem +11 · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC
paper · pdf · doi:10.48550/arxiv.2103.14392
arxiv created 2021/03/26 · openalex publication_date 2021/03/26 · arxiv updated 2021/03/29 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We consider distributed stochastic optimization problems that are solved with master/workers computation architecture. Statistical arguments allow to exploit statistical similarity and approximate this problem by a finite-sum problem, for which we propose an inexact accelerated cubic-regularized Newton's method that achieves lower communication complexity bound for this setting and improves upon existing upper bound. We further exploit this algorithm to obtain convergence rate bounds for the original stochastic optimization problem and compare our bounds with the existing bounds in several regimes when the goal is to minimize the number of communication rounds and increase the parallelization by increasing the number of workers.