# Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning

arXiv: https://arxiv.org/abs/2201.09531 · HTML: https://mlsanity.com/paper/2201.09531/

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 53 references that are in the map.
- First posted on arXiv 24 Jan 2022.

## Builds on (most cited first, 30 of 38)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [A Joint Learning and Communications Framework for Federated Learning over Wireless Networks](https://mlsanity.com/paper/1909.07972/) (2019)
- [Federated Learning via Over-the-Air Computation](https://mlsanity.com/paper/1812.11750/) (2018)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Broadband Analog Aggregation for Low-Latency Federated Edge Learning (Extended Version)](https://mlsanity.com/paper/1812.11494/) (2018)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data](https://mlsanity.com/paper/2005.11418/) (2020)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020)
- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization](https://mlsanity.com/paper/1708.01012/) (2017)
- [Federated Bayesian Optimization via Thompson Sampling](https://mlsanity.com/paper/2010.10154/) (2020)
- [FedDANE: A Federated Newton-Type Method](https://mlsanity.com/paper/2001.01920/) (2020)
- [Over-the-Air Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2009.12787/) (2020)
- [Scheduling for Cellular Federated Edge Learning with Importance and Channel Awareness](https://mlsanity.com/paper/2004.00490/) (2020)
- [Optimized Power Control Design for Over-the-Air Federated Edge Learning](https://mlsanity.com/paper/2106.09316/) (2021)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [Federated Learning via Intelligent Reflecting Surface](https://mlsanity.com/paper/2011.05051/) (2020)
- [Reconfigurable Intelligent Surface Enabled Federated Learning: A Unified Communication-Learning Design Approach](https://mlsanity.com/paper/2011.10282/) (2020)
- [Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applications](https://mlsanity.com/paper/1710.07804/) (2017)
- [Federated Machine Learning for Intelligent IoT via Reconfigurable Intelligent Surface](https://mlsanity.com/paper/2004.05843/) (2020)

## Built on by (most cited first, 30 of 59)

- [Decentralized Federated Learning: A Survey and Perspective](https://mlsanity.com/paper/2306.01603/) (2023)
- [Federated Full-Parameter Tuning of Billion-Sized Language Models with Communication Cost under 18 Kilobytes](https://mlsanity.com/paper/2312.06353/) (2023)
- [Federated Learning for Connected and Automated Vehicles: A Survey of Existing Approaches and Challenges](https://mlsanity.com/paper/2308.10407/) (2023)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [A Survey on Over-the-Air Computation](https://mlsanity.com/paper/2210.11350/) (2022)
- [FIARSE: Model-Heterogeneous Federated Learning via Importance-Aware Submodel Extraction](https://mlsanity.com/paper/2407.19389/) (2024)
- [On the Convergence of Zeroth-Order Federated Tuning for Large Language Models](https://mlsanity.com/paper/2402.05926/) (2024)
- [Interference Management for Over-the-Air Federated Learning in Multi-Cell Wireless Networks](https://mlsanity.com/paper/2206.02398/) (2022)
- [Can Textual Gradient Work in Federated Learning?](https://mlsanity.com/paper/2502.19980/) (2025)
- [Synergizing Foundation Models and Federated Learning: A Survey](https://mlsanity.com/paper/2406.12844/) (2024)
- [Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimization](https://mlsanity.com/paper/2405.15861/) (2024)
- [BAFFLE: A Baseline of Backpropagation-Free Federated Learning](https://mlsanity.com/paper/2301.12195/) (2023)
- [Communication-Efficient Multimodal Federated Learning: Joint Modality and Client Selection](https://mlsanity.com/paper/2401.16685/) (2024)
- [Over-the-Air Federated Learning and Optimization](https://mlsanity.com/paper/2310.10089/) (2023)
- [ZooPFL: Exploring Black-box Foundation Models for Personalized Federated Learning](https://mlsanity.com/paper/2310.05143/) (2023)
- [Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients](https://mlsanity.com/paper/2308.04077/) (2023)
- [Hierarchical Federated Learning with Multi-Timescale Gradient Correction](https://mlsanity.com/paper/2409.18448/) (2024)
- [Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing](https://mlsanity.com/paper/2404.00158/) (2024)
- [Ferret: Federated Full-Parameter Tuning at Scale for Large Language Models](https://mlsanity.com/paper/2409.06277/) (2024)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [FedZeN: Towards superlinear zeroth-order federated learning via incremental Hessian estimation](https://mlsanity.com/paper/2309.17174/) (2023)
- [FedMFS: Federated Multimodal Fusion Learning with Selective Modality Communication](https://mlsanity.com/paper/2310.07048/) (2023)
- [Rendering Wireless Environments Useful for Gradient Estimators: A Zero-Order Stochastic Federated Learning Method](https://mlsanity.com/paper/2401.17460/) (2024)
- [Communication-Efficient Byzantine-Resilient Federated Zero-Order Optimization](https://mlsanity.com/paper/2406.14362/) (2024)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [Age-Based Device Selection and Transmit Power Optimization in Over-the-Air Federated Learning](https://mlsanity.com/paper/2501.01828/) (2025)
- [Cooperative Decentralized Backdoor Attacks on Vertical Federated Learning](https://mlsanity.com/paper/2501.09320/) (2025)
- [Converge Faster, Talk Less: Hessian-Informed Federated Zeroth-Order Optimization](https://mlsanity.com/paper/2506.02370/) (2025)
- [HOSL: Hybrid-Order Split Learning for Memory-Constrained Edge Training](https://mlsanity.com/paper/2601.10940/) (2026)
- [Lazy Queries Can Reduce Variance in Zeroth-order Optimization](https://mlsanity.com/paper/2206.07126/) (2022)

## Abstract (arXiv)

Federated learning (FL), as an emerging edge artificial intelligence paradigm, enables many 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 to second-order methods. However, these algorithms cannot be applied in scenarios where the gradient information is not available, e.g., federated black-box attack and federated hyperparameter tuning. To address this issue, in this paper we propose a derivative-free federated zeroth-order optimization (FedZO) algorithm featured by performing multiple local updates based on stochastic gradient estimators in each communication round and enabling partial device participation. Under non-convex settings, we derive the convergence performance of the FedZO algorithm on non-independent and identically distributed data and characterize the impact of the numbers of local iterates and participating edge devices on the convergence. To enable communication-efficient FedZO over wireless networks, we further propose an over-the-air computation (AirComp) assisted FedZO algorithm. With an appropriate transceiver design, we show that the convergence of AirComp-assisted FedZO can still be preserved under certain signal-to-noise ratio conditions. Simulation results demonstrate the effectiveness of the FedZO algorithm and validate the theoretical observations.