Abstract
In developing efficient optimization algorithms, it is crucial to account forcommunication constraints -- a significant challenge in modern federatedlearning settings. The best-known communication complexity amongnon-accelerated algorithms is achieved by DANE, a distributed proximal-pointalgorithm that solves local subproblems in each iteration and that can exploitsecond-order similarity among individual functions. However, to achieve suchcommunication efficiency, the accuracy requirement for solving the localsubproblems is slightly sub-optimal. Inspired by the hybrid projection-proximalpoint method, in this work, we i) propose a novel distributed algorithm S-DANE.This method adopts a more stabilized prox-center in the proximal step comparedwith DANE, and matches its deterministic communication complexity. Moreover,the accuracy condition of the subproblem is milder, leading to enhanced localcomputation efficiency. Furthermore, it supports partial client participationand arbitrary stochastic local solvers, making it more attractive in practice.We further ii) accelerate S-DANE, and show that the resulting algorithmachieves the best-known communication complexity among all existing methods fordistributed convex optimization, with the same improved local computationefficiency as S-DANE.