Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients

Yao Shu, Xiaoqiang Lin, Zhongxiang Dai, Bryan Kian Hsiang Low

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.

Introduction

In standard Federated Learning (FL), clients collaboratively train a model by sharing local gradients. However, in many real-world scenarios—such as attacking black-box adversarial models or optimizing non-differentiable metrics like precision and recall—gradient information is unavailable. This necessitates Federated Zeroth-Order Optimization (ZOO), where optimization relies solely on function outputs ($y = f(x)$).

Existing Federated ZOO algorithms face two major hurdles. First, they are query inefficient, typically relying on Finite Difference (FD) methods that require a massive number of new function queries at every step to estimate a gradient. Second, they are communication inefficient; in heterogeneous settings where data across devices varies significantly, local updates tend to drift away from the global objective, requiring frequent and expensive communication rounds to correct.

The FZooS Algorithm

To address these challenges, we propose FZooS (Federated Zeroth-Order optimization using trajectory-informed Surrogate gradients). The algorithm introduces two key innovations to the standard federated framework.

Algorithmic comparison between the general Federated ZOO framework (Algorithm 1) and the proposed FZooS algorithm (Algorithm 2).

Trajectory-Informed Surrogate Gradients

Instead of performing new queries for every gradient estimate, FZooS uses a Gaussian Process (GP) to model the local function. It treats the entire history of previous queries (the "trajectory") as data points to predict the current gradient. This allows for accurate estimation with minimal additional queries per iteration. While traditional ZOO methods are "memoryless," FZooS recognizes that every query provides information about the function's shape.

Transferable Global Surrogates and Adaptive Correction

Since GPs are non-parametric and difficult to share, FZooS utilizes Random Fourier Features (RFF) to approximate the GP mean. This converts the complex GP into a transferable $M$-dimensional vector that clients can send to a central server. The server averages these to create a "global gradient surrogate." FZooS then employs an adaptive correction length ($\gamma$) that intelligently balances local and global information based on the degree of client heterogeneity.

Experimental Evaluation

We evaluated FZooS across three distinct environments:

  1. Synthetic Quadratic Functions: Used to precisely control and test the impact of client heterogeneity.
  2. Federated Black-Box Adversarial Attacks: Conducted on CIFAR-10 (ResNet18) and MNIST (CNN) to find universal perturbations that cause misclassification across private models.
  3. Federated Non-Differentiable Metric Optimization: Maximizing non-smooth metrics like F1-score and Jaccard index on the Covertype dataset using a multi-layer perceptron (MLP).

Key Results and Insights

FZooS demonstrates significant improvements in both query and communication efficiency compared to baselines like FedZO, FedProx, and SCAFFOLD.

Convergence comparison of FZooS against baselines across different levels of client heterogeneity (C) in terms of rounds and queries.
  • Efficiency Gains: In synthetic tests, FZooS reached optimal values using orders of magnitude fewer queries. As shown in the convergence plots, FZooS (orange squares) maintains a steady descent even as heterogeneity ($C$) increases, while baselines often stagnate.
  • Exponential Error Reduction: A major theoretical finding is that FZooS can achieve an exponential rate of reduction in gradient estimation error, whereas finite-difference methods are limited to a slower polynomial rate ($O(1/Q)$).
  • Adversarial Attack Success: On CIFAR-10, FZooS achieved a near 100% attack success rate significantly faster than other methods, maintaining its performance even under high client heterogeneity.
  • High-Dimensional Performance: FZooS successfully optimized high-dimensional (d=2189) non-smooth metrics on the Covertype dataset, outperforming competitors in both final metric value and convergence speed.

Discussion and Future Work

While FZooS drastically reduces communication rounds, each round involves sending an $M$-dimensional RFF vector, which adds a fixed bandwidth overhead. Additionally, while GPs are powerful, they can struggle with extremely high-dimensional spaces (millions of parameters). Future research may explore replacing the GP with Neural Networks acting as surrogates to handle massive-scale federated models and investigating more sophisticated kernels for non-stationary landscapes.

Summary updated

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.
BibTeX
@misc{shu2023federated,
  author = {Yao Shu and Xiaoqiang Lin and Zhongxiang Dai and Bryan Kian Hsiang Low},
  title = {{Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients}},
  year = {2023},
  eprint = {2308.04077},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2308.04077},
}
Figure