Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis
This work addresses communication efficiency in distributed optimization for machine learning and data science, offering incremental improvements over existing methods.
The paper tackles finite-sum distributed optimization under δ-similarity and μ-strong convexity by proposing two algorithms, SVRS and AccSVRS, achieving communication complexities of Õ(n + √nδ/μ) and Õ(n + n^{3/4}√(δ/μ)), respectively, with smoothness-free bounds that are superior in ill-conditioned cases and a nearly matched lower bound for AccSVRS.
We study finite-sum distributed optimization problems involving a master node and $n-1$ local nodes under the popular $δ$-similarity and $μ$-strong convexity conditions. We propose two new algorithms, SVRS and AccSVRS, motivated by previous works. The non-accelerated SVRS method combines the techniques of gradient sliding and variance reduction and achieves a better communication complexity of $\tilde{\mathcal{O}}(n {+} \sqrt{n}δ/μ)$ compared to existing non-accelerated algorithms. Applying the framework proposed in Katyusha X, we also develop a directly accelerated version named AccSVRS with the $\tilde{\mathcal{O}}(n {+} n^{3/4}\sqrt{δ/μ})$ communication complexity. In contrast to existing results, our complexity bounds are entirely smoothness-free and exhibit superiority in ill-conditioned cases. Furthermore, we establish a nearly matched lower bound to verify the tightness of our AccSVRS method.