Efficient Algorithms for Federated Saddle Point Optimization

• URL: http://arxiv.org/abs/2102.06333v1
• Date: Fri, 12 Feb 2021 02:55:36 GMT
• Title: Efficient Algorithms for Federated Saddle Point Optimization
• Authors: Charlie Hou, Kiran K. Thekumparampil, Giulia Fanti, Sewoong Oh
• Abstract summary: We consider strongly convex-concave minimax problems in the federated setting, where the communication constraint is the main bottleneck. Our goal is to design an algorithm that can harness the benefit of similarity in the clients while recovering the Minibatch Mirror-prox performance under arbitrary heterogeneity.
• Score: 32.060759921090856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider strongly convex-concave minimax problems in the federated setting, where the communication constraint is the main bottleneck. When clients are arbitrarily heterogeneous, a simple Minibatch Mirror-prox achieves the best performance. As the clients become more homogeneous, using multiple local gradient updates at the clients significantly improves upon Minibatch Mirror-prox by communicating less frequently. Our goal is to design an algorithm that can harness the benefit of similarity in the clients while recovering the Minibatch Mirror-prox performance under arbitrary heterogeneity (up to log factors). We give the first federated minimax optimization algorithm that achieves this goal. The main idea is to combine (i) SCAFFOLD (an algorithm that performs variance reduction across clients for convex optimization) to erase the worst-case dependency on heterogeneity and (ii) Catalyst (a framework for acceleration based on modifying the objective) to accelerate convergence without amplifying client drift. We prove that this algorithm achieves our goal, and include experiments to validate the theory.

Related papers

• Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delays [0.0]
  Federated learning (FL) was recently proposed to securely train models with data held over multiple locations ("clients") Two major challenges hindering the performance of FL algorithms are long training times caused by straggling clients, and a decline in model accuracy under non-iid local data distributions ("client drift") We propose and analyze Asynchronous Exact Averaging (AREA), a new (sub)gradient algorithm that utilizes communication to speed up convergence and enhance scalability, and employs client memory to correct the client drift caused by variations in client update frequencies.
  arXiv  Detail & Related papers  (2024-05-16T14:22:49Z)
• Dynamic Regularized Sharpness Aware Minimization in Federated Learning: Approaching Global Consistency and Smooth Landscape [59.841889495864386]
  In federated learning (FL), a cluster of local clients are chaired under the coordination of a global server. Clients are prone to overfit into their own optima, which extremely deviates from the global objective. ttfamily FedSMOO adopts a dynamic regularizer to guarantee the local optima towards the global objective. Our theoretical analysis indicates that ttfamily FedSMOO achieves fast $mathcalO (1/T)$ convergence rate with low bound generalization.
  arXiv  Detail & Related papers  (2023-05-19T10:47:44Z)
• Federated Minimax Optimization with Client Heterogeneity [11.558008138030845]
  Minimax computation has seen a surge in interest with the advent modern applications such as GANs. We propose a general federated minimax framework that subsumes settings and existing methods like Local SGDA.
  arXiv  Detail & Related papers  (2023-02-08T18:33:55Z)
• Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy [6.170898159041277]
  We present an algorithm for minimizing an objective with hard-to-compute gradients by using a related, easier-to-access function as a proxy. Our algorithm guarantees convergence at a rate matching the gradient descent on a $delta$-smooth objective. Our algorithm has many potential applications in machine learning, and provides a principled means of leveraging synthetic data, physics simulators, mixed public and private data, and more.
  arXiv  Detail & Related papers  (2023-02-07T15:50:49Z)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  We propose an efficient adaptive minimax optimization algorithm (i.e., AdaFGDA) to solve these minimax problems. It builds our momentum-based reduced and localSGD techniques, and it flexibly incorporate various adaptive learning rates.
  arXiv  Detail & Related papers  (2022-11-14T12:32:18Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Ascent. We show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings. We extend our algorithm to extend the setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings.
  arXiv  Detail & Related papers  (2022-10-31T17:59:29Z)
• Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization [6.935471115003109]
  We present a theoretical study of federated learning of client updates. In particular, we prove that whenever localizes are small, one can take an update over all clients. We also prove that the noise of client sampling can be controlled by using a small server-side stepsize.
  arXiv  Detail & Related papers  (2022-01-26T17:26:25Z)
• Faster Non-Convex Federated Learning via Global and Local Momentum [57.52663209739171]
  textttFedGLOMO is the first (first-order) FLtexttFedGLOMO algorithm. Our algorithm is provably optimal even with communication between the clients and the server.
  arXiv  Detail & Related papers  (2020-12-07T21:05:31Z)
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning [102.26119328920547]
  Federated learning (FL) is a challenging setting for optimization due to the heterogeneity of the data across different clients. We propose a general algorithmic framework, Mime, which mitigates client drift and adapts arbitrary centralized optimization algorithms.
  arXiv  Detail & Related papers  (2020-08-08T21:55:07Z)
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization [93.78811018928583]
  This paper provides a framework to analyze the convergence of federated heterogeneous optimization algorithms. We propose FedNova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.
  arXiv  Detail & Related papers  (2020-07-15T05:01:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.