- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper proposes BlackBoxFL, a federated zeroth-order optimization method. Clients search over a small number of parameter blocks using function evaluations and upload candidates only when their local losses improv. The server combines these candidates, and clients vote to accept or reject the updates. Experiments show reduced communication and better final performance than the evaluated zeroth-order baselines, at the cost of substantially more function evaluations.
Critical strengths
- The method provides a way to trade local computation for reduced communication without backpropagation.
- The reported results show improvements over the other zeroth-order baselines in terms of communication overhead across several benchmarks.
- The paper includes multi-seed results and ablations, and explicitly acknowledges the additional computational cost.
Critical weaknesses
-
The baseline (DeComFL) already has a very small communication footprint (around 600 bytes per client per round). BlackBoxFL reduces this further, but requires much higher compute. On MNIST/TinyCNN, BlackBoxFL achieves higher accuracy (96.4% vs. 92.4%), but uses over more forward evaluations (32.4M vs. 3.0M).
-
The theoretical guarantees do not directly support the evaluated protocol. Corollary 4.5 relies on exact objective evaluations and certified Lipschitz pruning of a maintained joint-space partition. In contrast, Algorithm 2 uses finite local searches followed by loss-weighted aggregation and client voting.
-
Reproducibility is limited. Code is unavailable, and important details including batch sizes and baseline configurations are insufficiently specified. Table 2 notes that batch sizes and query setups differ across baselines, but the actual batch sizes are omitted. It is difficult to verify how much total data each method processes.
Questions for authors
- In which practical settings would this method be beneficial? Existing zeroth-order methods already communicate very little. Substantially more computation may increase energy consumption and latency. Can the authors identify and demonstrate conditions where this trade-off is worthwhile?
- Can the authors provide code,specific configurations like batch size, and a breakdown of function evaluations and samples processed by stage?
- How do the authors explain the gap between the theroy and actual implementation, and what guarantees or insights do these results provide for the practical method?
2 comments
Thanks for your rebuttal. A basic counting error changed the reported forward-pass count from 32.4M to about 6M, which makes me question how carefully the experiments were checked. The authors also confirm that the theory does not cover the actual algorithm. Besides, the paper and rebuttal are both hard to follow. I do not think the paper is ready for acceptance, so I would keep my rejection.
W1 (compute versus communication). DeComFL is indeed communication-efficient, making it a strong comparator. BlackBoxFL addresses a different trade-off: extensive local block search does not increase the number of transmitted values. The submitted 32.4M figure contained a counter not reset between successive runs; the corrected MNIST/TinyCNN count is about 6M, versus 3M for DeComFL’s reference run. This is a comparison of batch-level calls, not equal sample counts, since the reference batch sizes differ (Appendix L.2). Communication counts were unaffected. At matched forward-pass budgets (Section 6.2), BlackBoxFL reaches comparable quality while DeComFL transmits 14–33× more; at a common target, 13–40× more, with BlackBoxFL using 0.8–1.9× its forward passes. On Shakespeare, all methods use 64 sequences per forward pass, making their computational costs directly comparable. BlackBoxFL requires fewer forward passes than DeComFL (2.69M versus 3.24M) while communicating 40× fewer bits (Table 3). W2 (theory versus implementation). Theoretical and empirical results address complementary questions. The implemented protocol has the dimension-independent per-cycle communication bound of Section 5. For a closely related certified variant, Corollary 4.5 proves almost-sure convergence of the best objective value to the global optimum, under exact averaged losses and safe blockwise refinement. These assumptions are not imposed on the implemented local-search and voting heuristic. The revision separates these claims explicitly; Q3 explains the voting guarantees. W3 (reproducibility). The concern is code availability, not an unspecified protocol. Algorithms 1–2 specify the update and communication schedule, and Appendices L.2 and M list architectures, hyperparameters, batch sizes, baseline configurations, quantization and evaluation counts. These make the experimental setup and bit accounting independently auditable. Code release is planned upon publication. Q1 (practical operating regime). BlackBoxFL targets networks in which transmitted bits are much costlier than local computation, for example remote sensing or interference-limited, duty-cycled wireless links. Its per-client uplink is roughly 35–85 B (Table 4) per cycle, versus about 600 B for a DeComFL reference round, despite three communication phases. For illustration, EU868 LoRaWAN at SF12 permits at most 51 B of application payload per packet: a 600 B message requires at least 12 packets, whereas BlackBoxFL’s smaller stage messages can require substantially fewer. This is a fragmentation illustration, not a measured end-to-end latency comparison; downlink scheduling, duty cycles and local compute also matter. On high-rate links or when latency dominates, BlackBoxFL need not be preferable. Its advantage is the measured reduction in bits at comparable quality, not universally shorter training time. Q2 (code, configurations and evaluation breakdown). Algorithms 1–2 give the procedure; Appendices L.2 and M give baseline settings, architectures and full hyperparameters. BlackBoxFL uses batches of 512 images or 64 Shakespeare sequences. At reference settings, FedZO, BAFFLE and DeComFL use 32 images or 64 sequences, 30 directions, five local steps, learning rate 0.1 and normalized steps. The additional controlled comparison uses batch 512 for all methods, with about 6M batch-level forward calls and 3.2 billion sample evaluations each. A CIFAR-10/LeNet5 BlackBoxFL cycle uses about 6,200 forward calls (3.2M sample evaluations): 19% for screening, 71% for local search and 10% for voting. Other benchmarks use 6,000–6,300 calls, with similar fractions. Communication and compute are counted separately; code release is planned upon publication. Q3 (what the guarantees establish). Three results should be distinguished. First, Proposition 4.3 establishes convergence of certified search to the global minimum on a fixed coordinate slice, explaining why nonlocal search can improve beyond a local gradient step. Second, Proposition 4.4 and Corollary 4.5 give almost-sure global convergence for a full-domain partition refined blockwise, not for repeated slice minimization. Third, Lemma K.3 and Proposition K.5 provide deterministic and probabilistic conditions under which client voting agrees with the averaged objective. These do not prove convergence of the implemented heuristic, but explain its design and when the voting decision is reliable. The practical protocol’s efficiency is established separately by its communication bound and the new matched-computation experiments.