Federated Composite Saddle Point Optimization

Site Bai, Brian BullinsarXiv 2023 · OpenReview

Abstract

Federated learning (FL) 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. Addressing these issues, we propose Federated Dual Extrapolation (FeDualEx), an extra-step primal-dual algorithm, which is the first of its kind that encompasses both saddle point optimization and composite objectives under the FL paradigm. Both the convergence analysis and the empirical evaluation demonstrate the effectiveness of FeDualEx in these challenging settings. In addition, even for the sequential version of FeDualEx, we provide rates for the stochastic composite saddle point setting which, to our knowledge, are not found in prior literature.

Introduction

Saddle Point Problems (SPP), mathematically expressed as $\min_x \max_y \phi(x, y)$, are the backbone of modern machine learning, powering applications from Generative Adversarial Networks (GANs) to robust optimization. When these problems are transitioned to a Federated Learning (FL) environment, where data is distributed across many clients and communication is expensive, significant challenges arise.

Most existing federated SPP solvers assume objective smoothness. However, real-world ML often requires Composite Optimization (CO), incorporating non-smooth regularization terms like the $\ell_1$ norm for sparsity or the nuclear norm for low-rank models. Standard FL techniques often suffer from the "curse of primal averaging": averaging sparse models from different clients typically results in a global model that loses its intended structural properties. This work introduces Federated Dual Extrapolation (FeDualEx) to bridge this gap.

Methods: Federated Dual Extrapolation

FeDualEx is designed to handle non-smooth, min-max problems across distributed networks using three primary pillars:

  1. Dual Extrapolation: Unlike standard gradient descent-ascent, which can oscillate or diverge in saddle point problems, dual extrapolation utilizes an "extra-step" approach. It computes a gradient, takes a mid-step, and then uses the gradient at that mid-step to update the model.
  2. Generalized Bregman Divergence: To handle non-smooth terms, the algorithm incorporates regularization directly into the distance-generating function. This allows the algorithm to treat non-smooth constraints as part of the space's geometry, maintaining efficient convergence rates.
  3. Dual Aggregation: Instead of averaging primal model weights, FeDualEx aggregates updates in the dual space. This ensures that the global model inherits structural properties (like sparsity or low-rankness) intended by the regularization.
Comparison of FeDualEx with existing federated optimization methods.

Key Insights and Theoretical Results

FeDualEx provides the first-ever convergence rates for composite saddle point optimization under the federated paradigm. Theoretical analysis shows that FeDualEx achieves an $O(1/R^{2/3})$ convergence rate, matching state-of-the-art federated composite convex algorithms. This proves that the transition from simple minimization to complex saddle point problems does not necessarily degrade the convergence rate.

Furthermore, the analysis provides new convergence rates for sequential (non-federated) stochastic composite SPPs—a result previously missing from the literature.

Convergence rates for composite and smooth saddle point problems (SPP).

Empirical Evaluation

The algorithm was evaluated using high-dimensional synthetic benchmarks designed to test specific structural constraints, such as Bilinear Sparsity Problems and Low-Rank Matrix Problems.

In experiments, FeDualEx successfully converged to a duality gap of $10^{-1}$, while standard methods like FedDualAvg plateaued. Crucially, FeDualEx maintained significantly better adherence to regularization; in sparsity tests, it reached a sparsity ratio of ~0.7, whereas primal-averaging counterparts failed to maintain the structure, resulting in ratios near 0.95.

Limitations and Future Work

Current convergence analysis assumes homogeneous (IID) data across clients. Extending this to the heterogeneous (non-IID) setting remains a significant challenge due to the non-symmetric nature of the Jacobian in saddle point problems. Additionally, future research will explore communication efficiency through gradient compression and the application of FeDualEx to large-scale non-convex SPPs, such as transformer-based GANs.

Summary updated

Abstract

Federated learning (FL) 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. Addressing these issues, we propose Federated Dual Extrapolation (FeDualEx), an extra-step primal-dual algorithm, which is the first of its kind that encompasses both saddle point optimization and composite objectives under the FL paradigm. Both the convergence analysis and the empirical evaluation demonstrate the effectiveness of FeDualEx in these challenging settings. In addition, even for the sequential version of FeDualEx, we provide rates for the stochastic composite saddle point setting which, to our knowledge, are not found in prior literature.
BibTeX
@misc{bai2023federated,
  author = {Site Bai and Brian Bullins},
  title = {{Federated Composite Saddle Point Optimization}},
  year = {2023},
  eprint = {2305.15643},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.15643},
}
Figure