TL;DR
Federated Zeroth-Order Optimization (ZOO) lets decentralized edge devices collaboratively optimize objective functions when analytical gradients are unavailable, but standard finite-difference methods require exorbitant query budgets and suffer from severe client drift. FZooS overcomes this by turning past optimization query trajectories into Gaussian Process gradient surrogates, using Random Fourier Features (RFF) to share a global surrogate, and dynamically correcting local gradient drift. The result is a federated ZOO method that converges significantly faster in both communication rounds and total function evaluations.
What Problem Does This Paper Address?
In federated learning, clients collaborate to solve $\min_{x} \frac{1}{N} \sum_{i=1}^N f_i(x)$ without centralizing their raw data. In many real-world scenarios—such as black-box adversarial attacks on private models or directly tuning models for non-differentiable metrics like precision and recall—clients cannot evaluate analytical gradients $\nabla f_i(x)$. Instead, they only have access to noisy, black-box zeroth-order function evaluations $y_i(x) = f_i(x) + \zeta$.
Adapting federated algorithms to zeroth-order settings historically faces two bottlenecks:
- Query Inefficiency: Existing baselines estimate gradients via finite difference (FD) approximations, which require $Q$ exploratory evaluations per step ($NTQ$ extra evaluations per round across $N$ clients and $T$ local steps), quickly becoming prohibitive for expensive functions.
- Communication Inefficiency & Client Drift: When local client functions are heterogeneous, local updates pull client models in disparate directions. Standard variance-reduction or control-variate methods (like SCAFFOLD or FedProx) evaluate correction terms at a static historical anchor point ($x_{r-1}$), causing mismatch errors as local updates wander.
Methods
The authors propose FZooS (Federated Zeroth-Order optimization using trajectory-informed Surrogate gradients):
- Trajectory-Informed Local Gradient Surrogates: Instead of spending queries on finite differences, each client models its local objective as a sample from a Gaussian Process (GP). Conditioned on its historical query trajectory $\mathcal{D}^{(i)}_{r,t-1}$, the client analytical posterior mean $\nabla \mu^{(i)}_{r,t-1}(x)$ serves as a gradient estimator without requiring dedicated exploratory queries.
- Transferable Global Gradient Surrogate via RFF: Because non-parametric GP posteriors cannot be sent to a server without disclosing raw query points, clients approximate the shift-invariant kernel using $M$ shared Random Fourier Features (RFF). Each client aggregates its local GP into an $M$-dimensional weight vector $w^{(i)}_{r,T}$. The server simply averages these vectors into $w_r$, which is broadcast back so any client can query the global gradient surrogate $\nabla \widehat{\mu}_r(x)$ at arbitrary coordinates.
-
Adaptive Gradient Correction: During local iteration $t$, client $i$ updates using: $$\widehat{g}_{r,t-1}^{(i)} = \nabla \mu^{(i)}_{r,t-1}(x_{r,t-1}^{(i)}) + \gamma_{r,t-1} \left( \nabla \widehat{\mu}_{r-1}(x_{r,t-1}^{(i)}) - \nabla \widehat{\mu}^{(i)}_{r-1,T}(x_{r,t-1}^{(i)}) \right)$$ Crucially, surrogates are evaluated at the current local state $x_{r,t-1}^{(i)}$ rather than a stale reference point. The correction weight $\gamma_{r,t-1}$ adapts over time ($\approx 1/t$) to dampen reliance on the global correction as local trajectories drift away from the previous round's data.
-
Active Querying: Clients optionally take a handful of active queries (e.g., 5) guided by GP uncertainty in the neighborhood of current iterates to keep the surrogate accurate.
+-------------------------------------------------------------------------------+
| SERVER |
| Aggregates weights: w_r = (1/N) * sum_i w^{(i)}_{r,T} |
| Aggregates models: x_r = (1/N) * sum_i x^{(i)}_{r,T} |
+---------------------------------------+---------------------------------------+
| Broadcasts x_r, w_r
v
+-------------------------------------------------------------------------------+
| CLIENT i |
| 1. Evaluates transferable global surrogate: \nabla \hat{\mu}_r(x) |
| 2. Computes trajectory GP gradient: \nabla \mu^{(i)}_{r,t-1}(x) |
| 3. Dynamic correction at current state: \gamma_{r,t-1} * (\nabla \hat{\mu}|
| - \nabla \hat{\mu}^{(i)}) |
| 4. Takes a few uncertainty-guided active queries |
| 5. Computes RFF vector w^{(i)}_{r,T} & sends to server |
+-------------------------------------------------------------------------------+
Datasets
The authors evaluate FZooS on both synthetic and real-world benchmarks:
- Synthetic Quadratic Benchmark: Parameterized quadratic problems with controlled client heterogeneity $C \in \{0.5, 5, 50\}$, input dimension $d = 300$, across $N = 5$ clients.
- CIFAR-10: Federated black-box adversarial attack targeting ResNet18 models trained on non-IID class partitions across $N = 10$ clients.
- MNIST: Black-box adversarial attack on CNNs across $N = 10$ clients (evaluated in the appendix).
- Covertype (UCI Repository): Fine-tuning a pre-trained 3-layer MLP ($d = 2,189$ parameters) across $N = 7$ clients to optimize non-differentiable metrics (Precision, Recall, F1 score, Jaccard index).
Key Insights and Ideas
- History Beats Perturbation: FD estimates error scales as $\mathcal{O}(1/\sqrt{Q})$ and carries an unavoidable constant bias. In contrast, GP posterior derivative variance contracts exponentially ($\sim \rho^t$, with $\rho < 1$) along the trajectory, yielding higher accuracy with virtually zero extra query overhead.
- Evaluating Corrections at Moving Points: Unlike SCAFFOLD and FedProx, which suffer an error penalty proportional to $\|x_{r,t-1}^{(i)} - x_{r-1}\|^2$, FZooS can evaluate its surrogate anywhere. This eliminates anchor-point drift.
- Decaying Correction Length: Surrogate quality degrades as the local iterate wanders away from historical samples. An adaptive correction factor $\gamma_{r,t-1} \approx 1/t$ naturally trusts the correction early in local updates and backs off as the client explores new territory.
Key Results
- Sample and Communication Efficiency: Across synthetic experiments ($C \in \{0.5, 5.0, 50.0\}$), FZooS reached target loss values in roughly half the rounds and with orders of magnitude fewer function queries compared to FedZO, FedProx, and SCAFFOLD.
- Adversarial Attacks: On CIFAR-10, FZooS achieved near 100% attack success rates within 15–20 rounds (using $< 25 \times 10^3$ queries). Baselines often plateaued at significantly lower success rates or required more than double the rounds.
- High-Dimensional Non-Differentiable Metric Optimization: For $d=2,189$ MLP tuning on Covertype, FZooS consistently achieved superior metric improvements (lower $1 - \text{precision}$, higher recall, F1, and Jaccard) across all local iteration schedules ($T \in \{5, 10, 20\}$) and client heterogeneity splits ($P \in [0.3, 0.9]$).
- Convergence Guarantees: Proves convergence for strongly convex, general convex, and non-convex objectives without the irreducible error floor that plagues FD-based federated zeroth-order methods.
Limitations and Future Work
- Communication Payload Overhead: FZooS transmits $M$-dimensional RFF vectors ($M = 10,000$ in experiments) between clients and the server, trading bandwidth for query and round efficiency.
- Dimensionality Scaling: While effective at $d \approx 2,000$, standard RFF approximations and GP kernel representations face scaling hurdles in ultra-high-dimensional parameter regimes (e.g., large transformer architectures).
- Extra Synchronization Step: Implementing active querying around the global aggregated point $x_r$ prior to surrogate generation requires an additional communication exchange per round.
Summary updated