Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients

• URL: http://arxiv.org/abs/2308.04077v1
• Date: Tue, 8 Aug 2023 06:26:54 GMT
• Title: Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients
• Authors: Yao Shu, Xiaoqiang Lin, Zhongxiang Dai, Bryan Kian Hsiang Low
• Abstract summary: We introduce trajectory-informed surrogate gradients (FZooS) algorithm for query- and communication-efficient federated ZOO. Our FZooS achieves theoretical improvements over the existing approaches, which is supported by our real-world experiments such as federated black-box adversarial attack and federated non-differentiable metric optimization.
• Score: 31.674600866528788
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Federated optimization, an emerging paradigm which finds wide real-world applications such as federated learning, enables multiple clients (e.g., edge devices) to collaboratively optimize a global function. The clients do not share their local datasets and typically only share their local gradients. However, the gradient information is not available in many applications of federated optimization, which hence gives rise to the paradigm of federated zeroth-order optimization (ZOO). Existing federated ZOO algorithms suffer from the limitations of query and communication inefficiency, which can be attributed to (a) their reliance on a substantial number of function queries for gradient estimation and (b) the significant disparity between their realized local updates and the intended global updates. To this end, we (a) introduce trajectory-informed gradient surrogates which is able to use the history of function queries during optimization for accurate and query-efficient gradient estimation, and (b) develop the technique of adaptive gradient correction using these gradient surrogates to mitigate the aforementioned disparity. Based on these, we propose the federated zeroth-order optimization using trajectory-informed surrogate gradients (FZooS) algorithm for query- and communication-efficient federated ZOO. Our FZooS achieves theoretical improvements over the existing approaches, which is supported by our real-world experiments such as federated black-box adversarial attack and federated non-differentiable metric optimization.

Related papers

• Aiding Global Convergence in Federated Learning via Local Perturbation and Mutual Similarity Information [6.767885381740953]
  Federated learning has emerged as a distributed optimization paradigm. We propose a novel modified framework wherein each client locally performs a perturbed gradient step. We show that our algorithm speeds convergence up to a margin of 30 global rounds compared with FedAvg.
  arXiv  Detail & Related papers  (2024-10-07T23:14:05Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• 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)
• Accelerated Federated Learning with Decoupled Adaptive Optimization [53.230515878096426]
  federated learning (FL) framework enables clients to collaboratively learn a shared model while keeping privacy of training data on clients. Recently, many iterations efforts have been made to generalize centralized adaptive optimization methods, such as SGDM, Adam, AdaGrad, etc., to federated settings. This work aims to develop novel adaptive optimization methods for FL from the perspective of dynamics of ordinary differential equations (ODEs)
  arXiv  Detail & Related papers  (2022-07-14T22:46:43Z)
• Disentangled Federated Learning for Tackling Attributes Skew via Invariant Aggregation and Diversity Transferring [104.19414150171472]
  Attributes skews the current federated learning (FL) frameworks from consistent optimization directions among the clients. We propose disentangled federated learning (DFL) to disentangle the domain-specific and cross-invariant attributes into two complementary branches. Experiments verify that DFL facilitates FL with higher performance, better interpretability, and faster convergence rate, compared with SOTA FL methods.
  arXiv  Detail & Related papers  (2022-06-14T13:12:12Z)
• Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning [28.65635956111857]
  Federated learning (FL) enables edge devices to collaboratively train a global model without sharing their private data. To enhance the training efficiency of FL, various algorithms have been proposed, ranging from first-order computation to first-order methods.
  arXiv  Detail & Related papers  (2022-01-24T08:56:06Z)
• 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)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Domain Adaptive Person Re-Identification via Coupling Optimization [58.567492812339566]
  Domain adaptive person Re-Identification (ReID) is challenging owing to the domain gap and shortage of annotations on target scenarios. This paper proposes a coupling optimization method including the Domain-Invariant Mapping (DIM) method and the Global-Local distance Optimization ( GLO) GLO is designed to train the ReID model with unsupervised setting on the target domain.
  arXiv  Detail & Related papers  (2020-11-06T14:01:03Z)
• An adaptive stochastic gradient-free approach for high-dimensional blackbox optimization [0.0]
  We propose an adaptive gradient-free (ASGF) approach for high-dimensional non-smoothing problems. We illustrate the performance of this method on benchmark global problems and learning tasks.
  arXiv  Detail & Related papers  (2020-06-18T22:47:58Z)

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.