acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 – 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.

Primary area:
optimization
Keywords:
Federated Learning, Communication Efficiency, Zero order

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_VSzGOpenReview ↗
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
  1. The method provides a way to trade local computation for reduced communication without backpropagation.
  2. The reported results show improvements over the other zeroth-order baselines in terms of communication overhead across several benchmarks.
  3. The paper includes multi-seed results and ablations, and explicitly acknowledges the additional computational cost.
Critical weaknesses
  1. 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 10×10\times more forward evaluations (32.4M vs. 3.0M).

  2. 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.

  3. 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
  1. 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?
  2. Can the authors provide code,specific configurations like batch size, and a breakdown of function evaluations and samples processed by stage?
  3. 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

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.

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.

Reviewer_sECxOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

BlackBoxFL for communication-efficient federated zeroth-order optimization. Combines parameter-block search, Lipschitz pruning, transmission gating, weighted aggregation and client voting. Includes convergence analysis and experiments on several tasks.

Critical strengths
  1. Communication-efficient federated optimization is a meaningful problem, especially when clients cannot use backpropagation or communication is expensive.
  2. The paper provides a relatively complete optimization protocol with both theoretical analysis and experiments.
Critical weaknesses
  1. The motivation is unclear. For example, the second and third paragraphs of the Introduction discuss existing work, but then directly move to BlackBoxFL without explaining the key limitations of existing methods or why the proposed approach is needed (neither point is clearly addressed from the Abstract to the Conclusion).
  2. BlackBoxFL combines several existing techniques, but unclear what new and non-trivial algorithmic contribution this combination brings. If mainly a combination of existing, the novelty is limited.
  3. Problems with the theoretical analysis. Sec. 4 claims Lemma K.1 guarantees alignment between client votes and the global objective, but the condition is insufficient. For example, with (g1,g2,g3)=(−0.1,1.55,1.55)(g_1,g_2,g_3)=(-0.1,1.55,1.55), Γ=1\Gamma=1 and (ζ=0.55<∣Γ∣)(\zeta=0.55<|\Gamma|), yet client 1 votes against the update. Also, Sec. 4 proves convergence for an idealized algorithm using the exact global objective, not the actual BlackBoxFL.
  4. Communication costs are calculated assuming INT8 quantization, but full-precision values are used in practice. BlackBoxFL also requires more local computation, but the trade-off between computation and communication is not sufficiently analyzed. The models are relatively small, so the scalability claim remains unsupported.
  5. The Abstract and Conclusion are too long, with too many details and not enough focus on the key points.

Shortcomings in motivation, methodology, theoretical/experimental validation, and presentation.

Questions for authors
  1. What is the core novelty of BlackBoxFL over existing federated zeroth-order optimization and parameter-block search methods? What new capabilities or theoretical advantages does this combination bring?
  2. Can the inequality in Lemma K.1 be justified, and can the voting-alignment result be corrected? Can the convergence guarantees for the idealized algorithm be extended to the actual BlackBoxFL protocol?
  3. Does BlackBoxFL still maintain its performance and communication advantages with actual INT8 quantization and the same computational budget as the baselines?
1 comment

W1 (motivation). BlackBoxFL targets bandwidth-limited federated training by enabling extensive nonlocal client optimization without increasing the per-block communication payload. Each client reports only the selected point and loss, independently of its local query budget. The revised abstract and introduction make this motivation explicit. W2 (novelty). BlackBoxFL introduces a federated zero-order optimization protocol that combines nonlocal blockwise search with communication independent of the local optimization effort. Each client explores a low-dimensional parameter block using dyadic search and local refinement, transmitting only the resulting point and loss, regardless of the number of function evaluations performed. The server combines these results using WLS, and clients vote on accepting the update, without requiring server-side data. This enables substantial communication savings while benefiting from more extensive local optimization. The ablation in Q1 demonstrates the importance of nonlocal search. W3 (theory). The counterexample does not satisfy Lemma K.1’s hypothesis (Q2). We added majority and probabilistic voting guarantees (Lemma K.3, Proposition K.5). Corollary 4.5 separately proves global convergence in objective value for the idealised exact-loss block-refinement method, not the implementation; the revision distinguishes them. W4 (INT8, compute, scale). Actual INT8 messages now replace estimated 8-bit payloads (Q3). Local cost is measured (about 6,200 batch-level forward passes per CIFAR-10/LeNet5 cycle; Appendix L.2), and matched-compute tests retain substantial bit savings (Section 6.2). We target low-rate links, not universally faster training. Fixed per-cycle payload does not imply dimension-free coverage; more cycles are needed as d grows. We do not extrapolate beyond tested models. W5 (presentation). The shortened abstract, introduction and conclusion now foreground the motivation, mechanism and results. Q1 (core novelty). Unlike local finite-difference or random-direction ZO updates, each client first explores a low-dimensional block box by dyadic search, potentially finding an improving point beyond the neighbourhood reached by a local step. No intermediate search evaluations are transmitted: the report is at most a point and its loss, followed by an accept/reject vote on the combined candidate. Hence clients can spend additional computation on nonlocal search without increasing the per-block payload. The new CIFAR-10/LeNet5 ablation (Appendix N.7, 300 cycles, 10 runs) isolates this distinction. Finite-difference descent alone stays at chance (10.0%), even with the transmit gate effectively disabled; only 0.1% of weights change. The full protocol achieves 39.4% with that gate setting. Dyadic-only search reaches 40.1% versus 38.7% for the default two-stage protocol. Thus the data identify nonlocal search, not the subsequent descent, as the essential component in this setting; we do not claim that finite-difference refinement improves every run. Q2 (vote lemma and guarantees). The counterexample does not contradict Lemma K.1. For g = (−0.1, 1.55, 1.55) and Γ = 1, the lemma uses ζ = maxk |gk − Γ| = 1.10, not 0.55, so its hypothesis ζ < |Γ| fails. Nevertheless, two clients vote correctly, motivating the stronger Lemma K.3. If A = {k : |gk − Γ| < |Γ|}, the decision is guaranteed correct when |A| ≥ ⌈K/2⌉ for a genuinely improving candidate (Γ > 0), or |A| ≥ ⌊K/2⌋ + 1 for a harmful candidate (Γ < 0), under the protocol’s “at least half accept” rule. Remark K.4 gives an exact one-sided criterion; Proposition K.5 gives a conditional probabilistic guarantee under explicit heterogeneity and independent-minibatch assumptions. These results certify a voting decision under stated conditions, not convergence of the implemented protocol. Q3 (INT8 and matched computation). All reported experiments now quantise transmitted points and losses to 8 bits in both directions, so measured accuracy and communication reflect actual INT8 messages. Matched-seed full-precision checks differ by at most 0.2 accuracy points (Appendix L.4, Table 8). At equal forward-pass budgets (Table 2), BlackBoxFL, DeComFL and BAFFLE achieve comparable quality (within 0.8 accuracy points on image tasks), but DeComFL sends 14–33× and BAFFLE 176–4,841× as many bits. At equal target performance (Table 3), BlackBoxFL uses at most 2.9× the forward-pass calls of any baseline and 13–40× less communication than DeComFL. The advantage is communication at comparable quality, not uniformly higher accuracy or lower runtime.

Reviewer_fwPDOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposed a federated zero-order protocol aimed at reducing communication, namely BlackBoxFL. Model parameters are split into two-coordinate blocks, and each cycle a shared random seed selects 30 blocks. Clients first screen each block with a one-bit finite-difference activity test. They then search it locally using only forward-pass losses: narrowing of a box around the current value, followed by central-difference gradient descent, committing moves only when local loss improves. Experiments on 5 models, trained on MNIST, CIFAR-10 and tiny-Shakespeare, show 7–25× less communication than DeComFL and the best accuracy among zero-order baselines, at 2–22× more forward passes.

Critical strengths

• The protocol is fully specified (Algorithm 2, all hyperparameters), with 100 seeds and 5–95% intervals; communication and forward-pass counts are hardware-independent. • The authors are candid about the theory–implementation gap (Section 4, Appendix K) and about compute cost (2–22× more forward passes than ZO baselines, up to ~490× more than first-order). • Ablations and the update-dynamics analysis (Figure 13) are informative. • Headline ratios (7–25×, 3.6–19.0 points, 93–1,230× versus signSGD) and the 8,100/540-bit per-cycle bounds check out against the tables.

Critical weaknesses
  • The theory does not describe the algorithm • Proposition 4.2 and Corollary 4.5 amount to consistency of dense grid search with optimum-preserving pruning: classical, and exponential in d. • Proposition 4.4's blockwise method still keeps a full-dimensional partition (δ² ≤ Σ4^(−Nᵢ)), so it is not Proposition 4.3's per-slice search; the abstract's global-optimality claim conflates them. • Pruning needs the exact averaged f at every cell, which in FL means exponential communication. • The implementation re-centers a radius-0.5 box each visit, so the fixed compact domain C of Eq. (3) is never realized. • Asymptotic guarantees need infinitely many visits per coordinate; experiments visit most coordinates zero or one times.

  • Experimental scope. Federated ZO is mainly used to fine-tune large pretrained models; there is no fine-tuning experiment, where the coverage problem would be most severe. Baselines get 1,000 rounds and BlackBoxFL 1,000 cycles, each three synchronous round trips; report latency and round trips. Some baselines look under-tuned (~75% on MNIST/LeNet5), and several curves still improve at termination. Per-benchmark thresholds εact and εtx: state the data they were tuned on. Add a matched forward-pass-budget comparison. Why not compare this paper with more communication-cost efficient method such as quantization?

  • Missing renference and comparison [a,b,c]. [a] FL basics: FedAvg (McMahan et al., 2017), Kairouz et al. (2021), Hsu et al. (2019) for Dirichlet partitions, SCAFFOLD (Karimireddy et al., 2020). [b] Compression: QSGD, TernGrad, Deep Gradient Compression, rand-k sparsification (Wangni et al., 2018), FedPAQ. Konečný et al. (2016) is cited, but its seed-generated random-mask updates, the closest classical analog of block selection, are not discussed. [c] Partial/sub-model training: Federated Dropout, HeteroFL, FjORD, independent subnetwork training, FedBCD.

Questions for authors

Why not compare this paper with more communication-cost efficient method such as quantization?

What fraction of parameters is never modified by the end of each run?

1 comment

W1 (theory versus implementation). Section 5 proves that the implemented protocol’s per-cycle communication is independent of model dimension and local evaluations; experiments test this protocol. The idealized variant motivates blockwise global search; Sections 3–4 and Appendix K distinguish it from the practical heuristic. W2 (classical theory and exponential complexity). We do not claim polynomial-time global optimization. Beyond classical partitioning, we derive smoothness-matched pruning (Lemma 4.1) and a bounded survivor count under quadratic growth (Theorem B.6). The exponential full-domain cost motivates small blocks (d′ = 2); the main novelty is the federated search/communication protocol. W3 (different block mechanisms). Proposition 4.3 certifies slice-global, not joint, optimality. Proposition 4.4 instead refines a full-domain partition by blocks using exact averaged losses and safe pruning. Corollary 4.5 proves almost-sure convergence of the best objective value to the joint optimum for this conceptual variant, not the implemented heuristic. W4 (requiring exact f ). Evaluating f at every trial point requires repeated aggregation, defeating our communication goal. Instead, clients search locally and report one point/loss per block; the server uses WLS and clients vote. Appendix K proves voting alignment under stated conditions. W5 (re-centred boxes). The re-centred radius-0.5 box tracks the model without storing a full-domain partition. This makes search practical but forfeits certified refinement, as now stated. W6 (infinite visits). Asymptotic consistency is not presented as a finite-time guarantee. Random reshuffling repeatedly selects coordinates (Section 3); Table 14 (Appendix N.9) quantifies finite-run coverage. Per-cycle payload is dimension-independent, but the cycles required for coverage grow with model size (Section 7). W7 (experimental scope). Section 6.2 adds two compute-matched comparisons: with equal forward-pass budgets, BlackBoxFL reaches comparable quality using 14–33× less communication than DeComFL; at equal target quality, 13–40× less. We extended runs, swept baselines (Appendix L.3), added quantization baselines (Q1), used actual INT8, and documented threshold sensitivity (Appendices M.1 and N.6). Fine-tuning remains future work. Three synchronous exchanges entail latency; the design targets bandwidth-limited links, not universal latency reduction. W8 (references). We now discuss the missing references. Konečný et al. use shared-seed masks with local SGD; we instead communicate the outcome of nonlocal, forward-only block search—a different optimization protocol.

Q1 (comparison with quantization-based methods). Quantization and BlackBoxFL address communication efficiency through complementary mechanisms. QSGD and FedPAQ compress gradient-based updates, whereas BlackBoxFL uses only forward evaluations and communicates the outcome of a local block search, in-dependently of the number of evaluations performed. Moreover, BlackBoxFL already quantizes all transmitted parameters and losses to 8 bits. To address this question, we added QSGD and FedPAQ (Appendix L.1, Table 5), sweeping quantization levels s ∈ {1, 4} and learning rates {0.02, 0.05, 0.1}. As expected, these first-order methods achieve higher accuracy on CIFAR-10, but at substantially greater communication cost. For example, on CIFAR-10/LeNet5, FedPAQ achieves 61.6% accuracy using 3,225 Mb, whereas BlackBoxFL achieves 47.5% using only 7.3 Mb, a 442× commu-nication reduction. Indeed, a single FedPAQ round communicates approximately as many bits as 440 BlackBoxFL cycles. These results demonstrate that conventional gradient quantization does not eliminate the communication advan-tage of our approach. While the first-order methods can attain higher accuracy, BlackBoxFL provides a different operating point for severely communication- constrained systems without requiring backpropagation. Q2 (parameters never modified). The untouched fractions (Table 14, Appendix N.9) are 80% on CIFAR-10/LeNet5 after 300 cycles (39% after 1,000), 70% on NanoLM, 32% on MNIST/LeNet5, and 16% on CIFAR-10/TinyCIFARWide after 1,000 cycles. They fall below 1% on TinyCIFARWide after 3,000 cycles and on MNIST/TinyCNN. An untouched parameter need not be unselected: activity screening, the transmit gate and the vote suppress updates that

Comments on the paper

1 comment

We thank the reviewers for their constructive comments. The central novelty of BlackBoxFL is the use of blockwise global search at each client to reduce communication in federated zero-order optimization. Unlike existing methods that rely primarily on local gradient estimates or random perturbations, BlackBoxFL explores low-dimensional parameter blocks using dyadic search followed by local refinement. Each client performs inde-pendent optimization, transmitting only the resulting parameters and loss. Hence, communication per cycle is independent of the number of local function evaluations and ambient model dimension, for a fixed block budget. The server combines the results without accessing client data, and clients vote on accepting the update. The theoretical contribution has three complementary parts. Proposition 4.3 proves convergence of certified black-box search to the global minimum on a coordinate slice, explaining how nonlocal search can overcome limitations of local gradient-based optimization. Proposition 4.4 and Corollary 4.5 establish almost-sure convergence to the global optimum of the full objective for a conceptual method that maintains a full-domain partition and refines it blockwise using certified Lipschitz pruning. Importantly, this is global convergence, not merely convergence to a blockwise optimum. Lemma K.3 and Proposition K.5 establish deterministic and probabilistic conditions under which client voting agrees with the global objective. These results provide theoretical foundations for the proposed approach, while the practical implementation replaces certified global search with a computationally efficient heuristic. For the implemented protocol, Section 5 establishes a dimension-independent per-cycle communication bound, and the new matched-computation experiments demonstrate its substantial communication advantage. We uploaded a revised manuscript clarifying the contributions and address the reviewers’ concerns. The main changes are: (i) abstract and introduction emphasizing the motivation, novelty, and distinction from prior work, together with a more concise conclusion; (ii) distinction between the theoretically analysed global optimization method and practical heuristic implementation are clarified (Sections 3–4); (iii) additional related work; (iv) majority-vote and probabilistic extensions of the voting analysis (Appendix K); and (v) new experiments, in-cluding matched-computation comparisons and ablations (Section 6.2 and Appendices L and N), detailed below. To address the reviewers’ concerns, we have substantially expanded and strengthened the experimental evaluation. Most importantly, we conducted two complementary matched-computation comparisons (Section 6.2): under equal forward-pass budgets, BlackBoxFL achieves accuracy comparable to the strongest zero-order baselines while reducing communication by 14–33× relative to DeComFL, 176–4,841× relative to BAFFLE, and 1,537–26,731× relative to FedZO. When comparing the computational and communication costs required to reach the same target accuracy, BlackBoxFL requires at most 2.9× the forward passes of the competing methods, while communicating 13–40× less than DeComFL. We also added comparisons with the quantization-based methods QSGD and FedPAQ (Appendix L.1), implemented actual 8-bit quantization of all transmitted numerical values, and extended the training runs to demonstrate continued convergence and improved final accuracy. New ablation experiments (Appendix N.7) demonstrate the importance of the proposed nonlocal dyadic search: finite-difference descent alone fails to learn in the tested CIFAR-10 setting. Finally, we corrected an error in forward-pass accounting that had overestimated BlackBoxFL’s computational requirements by a factor of 5–6, without affecting the reported communication costs. Together, these additional experiments provide substantially stronger evidence that BlackBoxFL’s communication gains arise from its algorithmic design rather than merely from allocating more computation to the clients. The following table summarizes the matched-computation comparison with DeComFL, the most communication-efficient competing zero-order method (Section 6.2, Table 2). Both methods use the same forward-pass budget on each benchmark.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.