Local Composite Saddle Point Optimization

Distributed optimization (DO) approaches for saddle point problems (SPP) have recently gained in popularity due to the critical role they play in machine learning (ML). Existing works mostly target smooth unconstrained objectives in Euclidean space, whereas ML problems often involve constraints or non-smooth regularization, which results in a need for composite optimization. Moreover, although non-smooth regularization often serves to induce structure (e.g., sparsity), standard aggregation schemes in distributed optimization break this structure. Addressing these issues, we propose Federated Dual Extrapolation (FeDualEx), an extra-step primal-dual algorithm with local updates, which is the first of its kind to encompass both saddle point optimization and composite objectives under the distributed paradigm. Using a generalized notion of Bregman divergence, we analyze its convergence and communication complexity in the homogeneous setting. Furthermore, the empirical evaluation demonstrates the effectiveness of FeDualEx for inducing structure in these challenging settings. INTRODUCTION A notable fraction of machine learning (ML) problems belong to saddle point problems (SPP), including adversarial robustness (Madry et al., 2018; Chen & Hsieh, 2023) , generative adversarial networks (GAN) (Goodfellow et al., 2014), matrix games (Abernethy et al., 2018) , multi-agent reinforcement learning (Wai et al., 2018) , among others. These applications call for effective distributed saddle point optimization as their scale evolves beyond centralized learning. In typical distributed optimization (DO) approaches, a central server coordinates collaborative learning among clients through rounds of communication. In each round, clients learn a synchronized global model locally without sharing their private data, then send the model to the server for aggregation, usually through averaging (McMahan et al., 2017; Stich, 2019) , to produce a new global model. The cost of communication is known to dominate the optimization process (Konečnỳ et al., 2016) . Although preliminary progress has been made in distributed saddle point optimization (Beznosikov et al., 2020; Hou et al., 2021) , we would note that machine learning problems are commonly associated with task-specific constraints or non-smooth regularization, which results in a need for composite optimization (CO). Moreover, a common purpose for non-smooth regularization is to induce structure. Typical ones include ℓ 1 norm for sparsity and nuclear norm for low-rankness, which show up in examples spanning from classical LASSO (Tibshirani, 1996), sparse regression (Hastie et al., 2015) to deep learning such as adversarial example generation (Moosavi-Dezfooli et al., 2016) , sparse GAN (Zhou et al., 2020), convexified learning (Sahiner et al., 2022; Bai et al., 2024) and others. Meanwhile, Yuan et al. (2021) identified the "curse of primal averaging" in standard aggregation schemes of DO, where the specific regularization-imposed structure on the client models may no longer hold after direct averaging on the server. For instance, each client may be able to obtain a sparse solution, yet averaging the solutions across clients yields a dense solution. To address this issue for convex optimization, they adopted the dual averaging technique (Nesterov, 2009) , but this approach is not specifically designed for SPP. Even in the sequential deterministic setting, dual averaging or mirror descent (Nemirovskij & Yudin, 1983 ) achieve only a O(1/ √ T ) rate for SPP (Bubeck et al., 2015) , whereas extra-step methods achieve a O(1/T ) rate (Nemirovski, 2004; Nesterov, 2007) . At the same time, existing distributed methods for SPP fail to cover these composite scenarios and address associated challenges, as summarized in Table 1 .