Convergence of Distributed Adaptive Optimization with Local Updates

• URL: http://arxiv.org/abs/2409.13155v1
• Date: Fri, 20 Sep 2024 01:45:10 GMT
• Title: Convergence of Distributed Adaptive Optimization with Local Updates
• Authors: Ziheng Cheng, Margalit Glasgow,
• Abstract summary: We study distributed adaptive algorithms with local updates (intermittent communication) We prove that em Local SGD em with momentum (em Local em SGDM) and em Local em Adam can outperform their minibatch counterparts in convex and weakly convex settings.
• Score: 3.895864050325129
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study distributed adaptive algorithms with local updates (intermittent communication). Despite the great empirical success of adaptive methods in distributed training of modern machine learning models, the theoretical benefits of local updates within adaptive methods, particularly in terms of reducing communication complexity, have not been fully understood yet. In this paper, we prove that \em Local SGD \em with momentum (\em Local \em SGDM) and \em Local \em Adam can outperform their minibatch counterparts in convex and weakly convex settings, respectively. Our analysis relies on a novel technique to prove contraction during local iterations, which is a crucial but challenging step to show the advantages of local updates, under generalized smoothness assumption and gradient clipping.

Related papers

• Local Methods with Adaptivity via Scaling [38.99428012275441]
  This paper aims to merge the local training technique with the adaptive approach to develop efficient distributed learning methods. We consider the classical Local SGD method and enhance it with a scaling feature. In addition to theoretical analysis, we validate the performance of our methods in practice by training a neural network.
  arXiv  Detail & Related papers  (2024-06-02T19:50:05Z)
• Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedup [90.26270347459915]
  We propose a novel momentum-based algorithm via utilizing the global descent locally adaptive. textitLADA could greatly reduce the communication rounds and achieves higher accuracy than several baselines.
  arXiv  Detail & Related papers  (2023-07-30T14:53:21Z)
• FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy [84.45004766136663]
  Federated learning is an emerging distributed machine learning framework. It suffers from the non-vanishing biases introduced by the local inconsistent optimal and the rugged client-drifts by the local over-fitting. We propose a novel and practical method, FedSpeed, to alleviate the negative impacts posed by these problems.
  arXiv  Detail & Related papers  (2023-02-21T03:55:29Z)
• Change Detection for Local Explainability in Evolving Data Streams [72.4816340552763]
  Local feature attribution methods have become a popular technique for post-hoc and model-agnostic explanations. It is often unclear how local attributions behave in realistic, constantly evolving settings such as streaming and online applications. We present CDLEEDS, a flexible and model-agnostic framework for detecting local change and concept drift.
  arXiv  Detail & Related papers  (2022-09-06T18:38:34Z)
• Federated Minimax Optimization: Improved Convergence Analyses and Algorithms [32.062312674333775]
  We consider non minimax optimization, is gaining prominence many modern machine learning applications such as GANs. We provide a novel and tighter analysis algorithm, improves convergence communication guarantees in the existing literature.
  arXiv  Detail & Related papers  (2022-03-09T16:21:31Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  Local methods are one of the promising approaches to reduce communication time. We show that the communication complexity is better than non-local methods when the local datasets is smaller than the smoothness local loss.
  arXiv  Detail & Related papers  (2022-02-12T15:12:17Z)
• An Entropy-guided Reinforced Partial Convolutional Network for Zero-Shot Learning [77.72330187258498]
  We propose a novel Entropy-guided Reinforced Partial Convolutional Network (ERPCNet) ERPCNet extracts and aggregates localities based on semantic relevance and visual correlations without human-annotated regions. It not only discovers global-cooperative localities dynamically but also converges faster for policy gradient optimization.
  arXiv  Detail & Related papers  (2021-11-03T11:13:13Z)
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax Problems [80.46370778277186]
  Large scale convex-concave minimax problems arise in numerous applications, including game theory, robust training, and training of generative adversarial networks. We develop a communication-efficient distributed extragrad algorithm, LocalAdaSient, with an adaptive learning rate suitable for solving convex-concave minimax problem in the. Server model. We demonstrate its efficacy through several experiments in both the homogeneous and heterogeneous settings.
  arXiv  Detail & Related papers  (2021-06-18T09:42:05Z)
• Local Adaptivity in Federated Learning: Convergence and Consistency [25.293584783673413]
  Federated learning (FL) framework trains a machine learning model using decentralized data stored at edge client devices by periodically aggregating locally trained models. We show in both theory and practice that while local adaptive methods can accelerate convergence, they can cause a non-vanishing solution bias. We propose correction techniques to overcome this inconsistency and complement the local adaptive methods for FL.
  arXiv  Detail & Related papers  (2021-06-04T07:36:59Z)
• Distributionally Robust Federated Averaging [19.875176871167966]
  We present communication efficient distributed algorithms for robust learning periodic averaging with adaptive sampling. We give corroborating experimental evidence for our theoretical results in federated learning settings.
  arXiv  Detail & Related papers  (2021-02-25T03:32:09Z)
• Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization [10.592277756185046]
  Large scale distributed optimization has become the default tool for the training of supervised machine learning models. We propose a novel communication sparsification strategy that can take full advantage of the smoothness matrices associated with local losses.
  arXiv  Detail & Related papers  (2021-02-14T20:55:02Z)
• Learning Invariant Representations and Risks for Semi-supervised Domain Adaptation [109.73983088432364]
  We propose the first method that aims to simultaneously learn invariant representations and risks under the setting of semi-supervised domain adaptation (Semi-DA) We introduce the LIRR algorithm for jointly textbfLearning textbfInvariant textbfRepresentations and textbfRisks.
  arXiv  Detail & Related papers  (2020-10-09T15:42:35Z)
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates [70.9701218475002]
  We introduce a unified convergence analysis of decentralized communication methods. We derive universal convergence rates for several applications. Our proofs rely on weak assumptions.
  arXiv  Detail & Related papers  (2020-03-23T17:49:15Z)

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.