Communication Efficient Federated Learning via Distributed Black-Box Zero Order Optimization

Federated learning (FL) enables collaborative model training while keeping raw client data local, but the repeated exchange of high-dimensional gradients or model updates can make communication the dominant systems cost. Existing communication-efficient FL methods reduce this burden mainly through gradient or model compression, sparsification, or zero-order updates built from random perturbation directions. We propose BlackBoxFL, a communication-efficient federated zero-order protocol that takes a different approach: clients perform local black-box optimization over a small number of low-dimensional parameter blocks and communicate only the resulting block candidates, scalar losses, and one-bit control decisions. In each cycle, a small set of blocks is selected at random. Each client then searches the corresponding low-dimensional region using forward-pass loss evaluations alone, combining dyadic narrowing with finite-difference descent, and transmits a candidate only when it improves sufficiently over its local baseline. The server performs only a loss-weighted least-squares combination of the reported candidates, after which clients vote on fresh local data to accept or roll back the aggregate update. Unlike gradient-compression methods, BlackBoxFL therefore communicates no gradients, and unlike seed-based zero-order methods, it communicates no directional estimates derived from random perturbations. For a fixed block size, number of selected blocks, and number of clients, both the uplink and the downlink communication per cycle are independent of the ambient model dimension. We complement the implemented protocol with a certified exact-loss analysis based on Lipschitz global optimization. Under mild continuity and smoothness assumptions, the idealized search over a selected block converges to the global optimum of the corresponding block-restricted objective, and, with repeated block coverage and Lipschitz pruning, the associated fully blockwise method converges to the global optimum of the full objective. Experiments on MNIST and CIFAR-10 image classification, and on character-level language modeling with tiny-Shakespeare, demonstrate substantial savings: on five benchmarks, BlackBoxFL uses $7$–$25\times$ less communication than the most communication-efficient of the from-scratch zero-order baselines in our main comparison and roughly two to four orders of magnitude less than the others, while attaining the highest accuracy among zero-order methods across all evaluated tasks. These gains come at the cost of substantially more local forward-pass evaluations.