- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes the Byzantine-resilient algorithms for the bilevel optimization problem. SLBRD is the single-loop and Hessian-inversion free algorithm and robust against Byzantine adversaries. SLBRD-M is the momentum-enhanced variant, and improves the transient complexity than SLBRD and achieves the optimal Byzantine resilience. The experiments confirm the effectiveness of the proposed algorithms in both synthetic and real-world datasets.
Critical strengths
This paper proposed the single loop and Hessian free method SLBRD and its momentum variant with the provable convergence results. This paper is well written and easy to follow.
Critical weaknesses
-
This papers deals with the Byzantine workers by directly using the assumption (\delta,\kappa) robustness that there is an aggretor that can approximately recover the weighted average of honest worker. This simplifies the analysis, since we can directly degrades the problem to the distributed bi-level optimization problem with certain Byzantine resilience error. It would be helpful if authors could clarify the technical novelty of Byzantine-resilience analysis beyond incorporating an existing aggregation framework into decentralized bilevel optimization.
-
The compared baseline methods MA-DSBO, GBDSBO and their corresponding momentum variants do not consider the Byzantine setting. It is unclear that whether the observed performance improvements come from single-loop design, hyper-gradient estimation method or somewhere else.
Questions for authors
Please refer to the weakness.
3 comments
Response to Reviewer 3YLV (2/2)
W2: Are the baselines protected, and what causes the performance gains?
Thank you for your comment. MA-DSBO, GBDSBO, and their momentum variants use the same robust aggregators at every outer and inner-loop exchange. The paired ablation isolates the accuracy benefit of joint protection. Separate comparisons show fewer exchanges per update for the single-loop design and an accuracy gain from momentum. The complete-method results do not isolate the contribution of hypergradient estimation.
The aggregation implementations and communication accounting are clarified in Section 5 and Appendix A.1.5, with the implementation table and accounting paragraph marked in .
In a matched single-loop ablation, joint protection improves worst-attack accuracy under all four aggregators, including 40.41% to 89.72% with Trimmed Mean and 18.73% to 70.34% with Median.
The two variants differ only in which variables receive robust aggregation. They use identical updates, initialization, stepsizes, attacks, and budgets, with momentum on all three variables () and clipping disabled. Both are D-SOBA-SO-type adaptations. The published algorithm applies momentum only to .
Table R1. Worst-attack accuracy (%) in the matched single-loop ablation. MNIST, D-SOBA-SO-type variants, ALIE/SF/IPM/RN.
| Protected variables | Krum | Median | Trimmed Mean | IOS |
|---|---|---|---|---|
| only | 56.73 | 18.73 | 40.41 | 47.33 |
| 93.45 | 70.34 | 89.72 | 89.54 |
Separately, SLBRD requires 3 block exchanges per update, compared with 7 for MA-DSBO and 5 for GBDSBO, including inner loops. These counts measure communication per update and do not establish an end-to-end speedup. Adding momentum to SLBRD improves worst-attack accuracy from 85.75% to 89.72% (+3.97 percentage points) in the comparison below.
Table R2. Accuracy with and without attacks. MNIST, Trimmed Mean.
| Method | Single-loop | Attack-free (%) | Worst-attack (%) | Drop (pp) |
|---|---|---|---|---|
| MA-DSBO / MA-DSBO-M | No | 89.32 / 93.07 | 84.85 / 88.96 | 4.47 / 4.11 |
| GBDSBO / GBDSBO-M | No | 88.93 / 88.68 | 9.74 / 74.02 | 79.19 / 14.66 |
| Single-loop ( only) | Yes | 96.42 | 40.41 | 56.01 |
| SLBRD / SLBRD-M | Yes | 92.92 / 95.31 | 85.75 / 89.72 | 7.17 / 5.59 |
Table R1 isolates the effect of joint protection. Table R2 compares complete methods, so its performance differences cannot be attributed solely to hypergradient estimation.
A Kind Reminder Regarding Our Author Response
Dear Reviewer 3YLV,
Thank you for your thoughtful feedback on our submission. We have posted our responses and revised the manuscript, with particular attention to the following points:
- Clarification of the methodological and theoretical contributions relative to existing federated and decentralized bilevel methods.
- Matched ablations of joint variable protection, with clarified robust baseline implementations and communication costs.
If you have a chance to review our responses, we would be grateful for any further feedback and would be happy to clarify any remaining questions or concerns.
We sincerely appreciate the time and care you have devoted to reviewing our work. Thank you again for considering our responses.
Warm regards,
The Authors
Response to Reviewer 3YLV (1/2)
Thank you for your review.
Thank you for raising this point. SLBRD jointly protects the three bilevel variables in a single loop, and our analysis controls the feedback between Byzantine aggregation, network disagreement, and bilevel tracking. This yields topology-dependent robustness conditions and, with momentum, a variance-free persistent Byzantine error under the stated assumptions.
Methodological contribution. SLBRD jointly protects the upper-level variable x, lower-level variable y, and auxiliary variable z, while avoiding inner-loop solvers and Hessian inversion. This design addresses a specific difficulty: corrupted lower-level or auxiliary estimates can bias the hypergradient even when upper-level messages are robustly aggregated. Existing Byzantine federated bilevel methods rely on a central server, while benign decentralized methods such as D-SOBA-SO assume honest communication. SLBRD addresses Byzantine attacks on the coupled updates over a peer-to-peer network.
Theoretical contribution. The (δ,κ)-robustness condition bounds aggregation error by the dispersion of local honest states, which itself evolves under attack. The error therefore depends on the algorithm's iterates and cannot be treated as a fixed perturbation added to the benign analysis. Lemmas 3 and 10 capture the resulting feedback: disagreement increases aggregation error, which then perturbs consensus and lower-level and auxiliary tracking. We control these errors jointly using the consensus weight $ A_\Delta=A_3\eta_x+\frac{\kappa A_4}{\eta_x}. $ The additional κA4/ηx term uses consensus contraction to control the aggregation perturbation, yielding the topology-dependent condition κ≤c(1−λ)2 in Appendix D. This term vanishes in the benign case and has no counterpart in server-based methods without network consensus.
Under the stated theorem conditions, the momentum analysis further reduces the persistent Byzantine error from O(κ(σ2+ζf2+ζg2)) to O(κ(ζf2+ζg2)) (Theorems 1–2). When κ=O(δ), the latter matches the lower-bound order in the paper. The proof retains the noise-reduction factor (1−βu)/(1+βu) while separately controlling differences between historical conditional means. Thus the analysis establishes a variance-free persistent error for the coupled decentralized bilevel dynamics.
The revised theorem conditions are marked in blue in Section 4.2. The conditional-mean clarification and historical-disagreement bounds are marked in blue in Appendix E.3.1 (Eq. (170) and Lemma 23).