- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes FOBFBL, a fully first-order, single-loop method for Byzantine-robust federated bilevel optimization, and its momentum variant. By using finite multiplication numerical functions to rephrase and blockwise robust aggregation of three first-order directions, high-order calculations and repetitive inner loop communication are avoided. The paper establishes convergence guarantees for the nonconvex setting and under an additional upper-level PL condition, and proves that appropriately configured momentum eliminates the stochastic-variance term from the asymptotic Byzantine-induced error. Experiments on MNIST and CIFAR-10 evaluate robustness and computational, memory, and communication costs.
Critical strengths
(1) Finite-multiplier reformulation and blockwise robust aggregation enable fully first-order, single-loop updates in one communication round, reducing computation and communication costs.
(2) The paper provides guarantees for nonconvex stationary points under strong convex conditions in the lower layer and for the final iteration under PL conditions in the upper layer. It distinguishes between optimization error, Byzantine error, and multiplier bias, and proves that appropriate momentum can eliminate the random variance term in asymptotic Byzantine error.
(3) The experiment covers hyperparameter optimization and hyper representation learning, comparing various attacks, aggregators, and baselines, balancing predictive performance and resource cost, and comprehensively evaluating robustness and single update efficiency.
Critical weaknesses
(1) The main components have direct precedents, but there is a lack of robust aggregation versions such as MemFBO and BR FedBiM for direct comparison, making it difficult to clarify the independent benefits and importance of the design in this article.
(2) The correspondence between theoretical assumptions and experimental implementation is unclear. The description of the HPO model is inconsistent, and the local update protocol is not clear, which raises doubts about whether the strong convexity and conditional unbiasedness of the lower layer hold, and whether the existing convergence guarantees cover the actual implementation.
(3) The experiment has not yet systematically examined the trade-off between approximate bias, noise, and heterogeneity of finite multipliers, nor has it directly verified the influence of momentum on asymptotic residual error under theoretical parameter settings.
(4) The current efficiency evaluation focuses on the cost of a single update, and in some configurations, the accuracy is lower than the main baseline. Therefore, it is still necessary to compare the total time, communication volume, and Oracle call times under the same accuracy or stagnation error tolerance.
Overall Assessment after Rebuttal Thank you for the detailed revisions and clarifications. The authors have provided detailed responses to my remaining technical concerns, and the additional explanations have improved the clarity and rigor of the manuscript. I appreciate their efforts and acknowledge the value of the theoretical contributions. However, my overall assessment of the manuscript remains unchanged, as the revisions do not substantially alter my evaluation of its novelty and significance. I therefore maintain my original rating.
Questions for authors
(1) What HPO models and configurations are used for Table 2, Appendix B.1 and B.3 respectively? What satisfies the assumption of strong convexity in the lower layer?
(2) What are the advantages of our method compared to MemFBO and BR FedBiM using block robust aggregation under the same experimental setup and comparable parameter tuning budget?
(3) Do local steps repeat sampling at fixed shared parameters or continuously update parameters? If it is the latter, how to define the uploaded message, and does it still satisfy the condition of unbiasedness required by equation (10)?
(4) Can you provide an experiment that satisfies theoretical assumptions and allows for direct calculation of real hypergradients to verify convergence analysis?
(5) Does the total running time, number of communication bytes, and number of calls still demonstrate significant efficiency advantages when achieving the same accuracy or stationary error tolerance?
(6) How is the attack of ALIE/IPM on three message blocks constructed, before or after momentum processing and gradient pruning? If the attacker can observe the current round of honest messages, does the conditional independence required for non-momentum proof still hold?
7 comments
Response to Reviewer CwpN (2/4)
W2 & Q3: Local updates, uploaded messages, and conditional unbiasedness.
Our theoretical analysis considers one local step per communication round. The neural-network experiments use five sequential local updates per round.
-
Extending the analysis to multiple local steps. Under the stated oracle assumptions, the directions in Eq. (10) are conditionally unbiased at the broadcast point when one local step is used. With multiple steps, directions remain conditionally unbiased at their local query points, but their average can be biased at the broadcast point. Extending the proof requires controlling local drift [1] alongside lower-level tracking, robust aggregation, and momentum errors.
-
The neural-network experiments use sequential local updates. Clients start from and update all three variables five times, using fresh minibatches at each step, with some derivative components sharing a minibatch. For directions evaluated at the local parameters, FOBFBL uploads the average
Response to Reviewer CwpN (3/4)
W3: The trade-off between finite-multiplier bias, stochastic noise, and client heterogeneity.
Thank you for your comment. The experiments support task-dependent multiplier selection and identify noise suppression as momentum's clearest benefit in these tests. We measure test accuracy on MNIST HPO and the exact squared hypergradient on a synthetic problem with a strongly convex lower level. All tests below use seed 42.
- 1. Select to balance bias and perturbations on the target task.
On MNIST HPO, both methods peak at , with similar accuracy at smaller multipliers and lower accuracy at larger values under the stated stepsize scaling (Table R2).
Table R2. MNIST HPO accuracy (%) across . ALIE + CWMed, 1,000 updates. , other nominal stepsizes fixed, and for FOBFBL-M.
| Method | |||||||
|---|---|---|---|---|---|---|---|
| FOBFBL | 77.73 | 77.63 | 78.01 | 77.34 | 74.84 | 68.87 | 61.28 |
| FOBFBL-M | 77.50 | 77.61 | 77.66 | 77.45 | 74.87 | 67.87 | 60.16 |
On the synthetic problem, the lowest residual occurs at for FOBFBL and for FOBFBL-M (Table R3). Larger values worsen the residual, consistent with Remark 2's bias–perturbation trade-off.
Table R3. Synthetic squared-hypergradient residual across . Strongly convex lower level, ALIE + CWMed, . Final-10% average over 100,000 updates, with fixed stepsizes and for FOBFBL-M.
| Method | ||||||
|---|---|---|---|---|---|---|
| FOBFBL | 0.00616 | 0.00294 | 0.00177 | 0.000788 | 0.00136 | 0.00477 |
| FOBFBL-M | 0.00612 | 0.00288 | 0.00169 | 0.000561 | 0.000544 | 0.00163 |
- 2. Moderate momentum preserves HPO accuracy and is especially effective under high noise.
MNIST HPO accuracy is stable across moderate and falls at the largest tested value (Table R4).
Table R4. MNIST HPO accuracy (%) across . ALIE + CWMed, , 1,000 updates. Here recovers FOBFBL.
| 0 | 0.25 | 0.5 | 0.75 | 0.9 | 0.95 | |
|---|---|---|---|---|---|---|
| Final test accuracy (%) | 77.34 | 77.43 | 77.45 | 77.40 | 77.18 | 76.77 |
Momentum lowers the synthetic residual in all three settings, with a 65.1% reduction under high noise, versus 17.8% under high heterogeneity (Table R5). Varying changes the honest objectives, so the heterogeneity comparison measures sensitivity to that change.
Table R5. Synthetic residuals under separate noise and heterogeneity changes. ALIE + CWMed, , fixed stepsizes, for FOBFBL-M. Final-10% averages over 100,000 updates. Reductions are relative to FOBFBL.
| Setting | Noise | Heterogeneity | FOBFBL | FOBFBL-M | Relative reduction (%) |
|---|---|---|---|---|---|
| Reference | 0.003 | 0.003 | 0.000788 | 0.000561 | 28.8 |
| Higher noise | 0.03 | 0.003 | 0.0306 | 0.0107 | 65.1 |
| Higher heterogeneity | 0.003 | 0.3 | 0.00174 | 0.00143 | 17.8 |
- 3. Coupled momentum reduces the stationarity residual's sensitivity to noise.
Using Theorem 3's coupling form, with , we compare noisy and noiseless synthetic runs at zero heterogeneity. All methods use matched stepsizes at each budget, with pilot-selected scaling constants. Coupled momentum gives the lowest average squared true hypergradient at every tested budget (Table R6). Its residual increase over the paired noiseless run falls from 0.00393 to 0.00166 as the budget grows. At the largest budget, this increase is 0.03212 without momentum and 0.01585 with fixed momentum.
Table R6. Synthetic problem: full-run average squared true hypergradient. ALIE + CWMed, , , . Separate runs for each budget.
| Updates | No momentum (FOBFBL) | Fixed momentum () | Coupled momentum () |
|---|---|---|---|
| 4,000 | 1.200650 | 1.193249 | 1.188419 |
| 16,000 | 0.891875 | 0.880144 | 0.870067 |
| 64,000 | 0.559041 | 0.544373 | 0.530746 |
| 256,000 | 0.313041 | 0.296772 | 0.282857 |
Response to Reviewer CwpN (1/4)
Thank you for your comment. Relative to blockwise robust MemFBO, our contribution is a convergence analysis that controls coupled Byzantine and finite-multiplier errors, together with a momentum extension that removes stochastic variance from the persistent Byzantine error. Relative to BR-FedBiM, we establish this variance-removal property using only ordinary gradients. The BR-FedBiM comparisons have been added to Tables 2–3 in Section 5.1, highlighted in red.
Relation to MemFBO. Replacing MemFBO's [1] server averaging with blockwise robust aggregation gives the FOBFBL update structure under matched parameters and protocols. Our Lyapunov analysis controls biased aggregation and the coupled evolution of x and its two lower-level estimates, establishing Theorem 1 with separate Byzantine and finite-multiplier error terms.
Difference from BR-FedBiM. BR-FedBiM [2] removes stochastic variance from the asymptotic Byzantine error using Hessian- and Jacobian-vector products. Theorem 3 achieves this using ordinary gradients, by jointly controlling momentum lag and both lower-level tracking errors under its parameter choices. Heterogeneity and finite-multiplier terms remain.
Comparison with BR-FedBiM. Both methods outperform BR-FedBiM in all 16 HPO settings. For hyper-representation learning, FOBFBL and FOBFBL-M lead in worst-attack accuracy with Trimmed Mean and CWMed, respectively. BR-FedBiM leads with Krum and Median (Table R1). Methods use the same five local steps and 1,000-round communication budget, with fixed paper configurations and no additional tuning (Appendix B.1).
Table R1. Worst-attack accuracy (%) in the two MNIST tasks. Minimum across four attacks of the three-seed mean accuracy in Tables 2–3.
References
[1] Yang et al. First-Order Federated Bilevel Learning. AAAI 2025.
[2] Li et al. Single-Loop Byzantine-Resilient Federated Bilevel Optimization. ICLR 2026.
Thank you for pointing this out. We apologize for the confusion in the model description. The MNIST HPO experiments in Table 2 use an MLP. We have corrected Section 5.1 and clarified the upper- and lower-level HPO objectives, with Appendix B.1 referring to the same setting. These changes are highlighted in red. Strong convexity is used in the theoretical analysis, and our experiments cover both strongly convex and nonconvex lower levels.
Our algorithms can apply to both strongly convex and nonconvex lower-level objectives. FOBFBL and FOBFBL-M use only first-order gradients and run the same updates in both settings. In the convergence proof, strong convexity makes the lower-level solution y⋆(x) unique and Lipschitz in x, which bounds the lower-level tracking and finite-multiplier approximation errors.
Our experiments cover both settings. Hyper-representation learning (Tables 3–4) has a strongly convex lower level: a regularized linear classifier with fixed features. HPO uses a 784–200–100–10 MNIST MLP (Table 2, Appendices B.1/B.3) and a CIFAR-10 CNN with 16/32 convolutional channels and a 2048–100–10 classifier (Appendix B.3). Its upper level tunes 20 classwise VS-loss parameters using class-balanced validation cross-entropy. The nonconvex lower level trains all network weights with VS loss plus 0.01∣y∣2/2.