A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning

Chenlin Wu, Xiaoyu He, Zike Li, Zibin ZhengarXiv 2024 · DOI · arXiv

TL;DR

This paper introduces ZOFedHT, a novel federated learning algorithm designed for "black-box" scenarios where gradients are unavailable. By leveraging historical solution trajectories to build a non-isotropic gradient estimator, the method intelligently explores the most promising regions of the objective landscape, significantly outperforming standard zeroth-order methods in both convergence speed and final accuracy.

What Problem Does This Paper Address?

Federated Learning (FL) typically relies on sharing gradients or model updates. However, in many real-world applications—such as tuning closed-source Large Language Models (LLMs) or working with low-power edge devices—calculating gradients is either impossible or computationally prohibitive. This leads researchers to Zeroth-Order (ZO) optimization, which estimates gradients by probing the objective function with random perturbations (finite differences).

The "standard" way to do this is via isotropic Gaussian smoothing, where you sample random directions uniformly. The problem? In high-dimensional spaces, most random directions are useless. This "blind" sampling ignores the geometric features of the loss landscape, leading to high estimation errors and sluggish convergence. The authors set out to make ZO-FL smarter by asking: Can we use the path we’ve already traveled to guess the best way forward?

Methods

The authors propose ZOFedHT (Zeroth-Order Federated Learning assisted by Historical Trajectories). The core innovation lies in how the gradient is estimated:

  1. Non-Isotropic Sampling: Instead of sampling directions from a standard uniform distribution, ZOFedHT uses a covariance matrix $C$ that is a convex combination of two parts:
  2. The Identity Matrix ($I$): Ensures the model still explores the entire space (global exploration).
  3. The Trajectory Matrix ($QQ^T$): A projection matrix built from the most recent $\tau$ updates of the global model. This encourages the algorithm to "exploit" directions that have proven successful in recent rounds.
  4. QR Factorization: To keep communication efficient, the server performs a QR factorization on the historical trajectories to extract a thin projection matrix $Q$.
  5. Low Overhead: Only the small $Q$ matrix needs to be broadcast to clients every few rounds. The authors show that the additional computation and communication costs are negligible, making it as efficient as the classic FedAvg algorithm.

Datasets

The algorithm was evaluated on three widely used benchmarks for binary classification tasks:

  • MNIST: Handwritten digit recognition.
  • Fashion-MNIST: Images of clothing items.
  • RCV1: A large-scale text categorization dataset.

The experiments covered both IID (Independent and Identically Distributed) and non-IID (data partitioned by labels) settings to simulate real-world federated environments.

Key Insights and Ideas

  • Capturing "Insensitive" Directions: The authors demonstrate that solution trajectories naturally tend to align with "insensitive" directions—areas where the loss function changes slowly. By biasing the gradient estimation toward these directions, the algorithm achieves much higher accuracy than purely random sampling.
  • The Exploration-Exploitation Balance: The hyperparameter $\alpha$ allows users to tune the balance. A high $\alpha$ focuses on the historical subspace (exploitation), while a low $\alpha$ behaves more like standard random search (exploration).
  • Trajectory as a Hessian Proxy: In second-order optimization, one uses the Hessian matrix to understand the landscape. Since the Hessian is unavailable in ZO settings, the historical trajectory acts as a clever, "free" proxy for this curvature information.

Key Results

  • Superior Convergence: In almost all tests on MNIST and Fashion-MNIST, ZOFedHT converged faster and reached a lower training loss than standard ZO-Federated SGD and ZO-Federated GD.
  • Robustness in Non-IID Settings: Even when data was heavily skewed across clients (non-IID), ZOFedHT maintained its performance edge, proving its utility for practical federated systems.
  • The Sparsity Catch: On the RCV1 dataset, ZOFedHT performed well initially but was eventually overtaken by standard isotropic methods. The authors noted that RCV1 is highly sparse, and isotropic sampling is known to be particularly effective for sparse data, whereas ZOFedHT is better suited for dense problems.

Limitations and Future Work

  • Dense vs. Sparse: As noted with the RCV1 results, the current method is less effective for highly sparse datasets. Future iterations might need to adapt the covariance matrix to account for data sparsity.
  • Hyperparameter Sensitivity: The performance depends on choosing the right trajectory length ($\tau$) and combination coefficient ($\alpha$). Automating the selection of these parameters would make the algorithm more user-friendly.
  • Theoretical Gap: While the paper provides a convergence proof that aligns with existing ZO-FL rates ($O(\sqrt{n/RKM})$), the theoretical "tightness" of the non-isotropic bound remains an open question for future mathematical analysis.

Summary updated

BibTeX
@misc{wu2024historical,
  author = {Chenlin Wu and Xiaoyu He and Zike Li and Zibin Zheng},
  title = {{A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning}},
  year = {2024},
  eprint = {2409.15955},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.15955},
}
Figure