EUROPT 2025
Abstract Submission

275. Stabilized Proximal-Point Methods for Federated Optimization

Invited abstract in session MC-5: Optimization and machine learning II, stream Optimization for machine learning.

Monday, 14:00-16:00
Room: B100/4013

Authors (first author is the speaker)

1. Xiaowen Jiang
CISPA Helmholtz Center for Information Security
2. Anton Rodomanov
CISPA Helmholtz Center for Information Security
3. Sebastian Stich
CISPA Helmholtz Center for Information Security

Abstract

In developing efficient optimization algorithms, it is crucial to account for communication constraints---a significant challenge in modern Federated Learning. The best-known communication complexity among non-accelerated algorithms is achieved by DANE, a distributed proximal-point algorithm that solves local subproblems at each iteration and that can exploit second-order similarity among individual functions. However, to achieve such communication efficiency, the algorithm requires solving local subproblems sufficiently accurately, resulting in slightly sub-optimal local complexity. Inspired by the hybrid-projection proximal-point method, in this work, we propose a novel distributed algorithm S-DANE. Compared to DANE, this method uses an auxiliary sequence of prox-centers while maintaining the same deterministic communication complexity. Moreover, the accuracy condition for solving the subproblem is milder, leading to enhanced local computation efficiency. Furthermore, S-DANE supports partial client participation and arbitrary stochastic local solvers, making it attractive in practice. We further accelerate S-DANE and show that the resulting algorithm achieves the best-known communication complexity among all existing methods for distributed convex optimization while still enjoying good local computation efficiency as S-DANE. Finally, we propose adaptive variants of both methods using line search, obtaining the first provably efficient adaptive algorithm.

Keywords

Status: accepted

Back to the list of papers