acceptodds
Under review as a conference paper at ICLR 2027

SLBRD: A Single-Loop and Byzantine-Resilient Decentralized Bilevel Algorithm

Abstract

Decentralized bilevel optimization has emerged as a powerful paradigm for large-scale machine learning over distributed data. However, these systems are inherently vulnerable to Byzantine agents that transmit arbitrary or adversarial updates. While extensive progress has been made on Byzantine resilience in single-level optimization, extending these robustness guarantees to the bilevel setting remains an open problem. To bridge this gap, we propose SLBRD, the first Byzantine-resilient decentralized bilevel algorithm. By adopting a fully single-loop and Hessian-inversion-free architecture, SLBRD improves communication efficiency and limits the attack surface available to adversaries. We establish its sample and transient iteration complexities, explicitly characterizing the joint effects of network topology, data heterogeneity, and Byzantine influence. We further develop the Polyak-momentum variant SLBRD-M, which removes stochastic variance from the persistent Byzantine error and improves the topology-dependent transient complexity. Experiments on hyperparameter optimization and hyper-representation tasks validate the effectiveness of the proposed methods.

Primary area:
optimization
Keywords:
Bilevel Optimization, Decentralized Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_3YLVOpenReview ↗
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
  1. 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.

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

Response to Reviewer 3YLV (1/2)

Thank you for your review.

W1: Novelty and contributions beyond (δ,κ)(\delta,\kappa)-robust aggregation.

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 xx, lower-level variable yy, and auxiliary variable zz, 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 (δ,κ)(\delta,\kappa)-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\kappa A_4/\eta_x term uses consensus contraction to control the aggregation perturbation, yielding the topology-dependent condition κ≤c(1−λ)2\kappa\leq c(1-\lambda)^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))\mathcal O(\kappa(\sigma^2+\zeta_f^2+\zeta_g^2)) to O(κ(ζf2+ζg2))\mathcal O(\kappa(\zeta_f^2+\zeta_g^2)) (Theorems 1–2). When κ=O(δ)\kappa=\mathcal O(\delta), the latter matches the lower-bound order in the paper. The proof retains the noise-reduction factor (1−βu)/(1+βu)(1-\beta_u)/(1+\beta_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‾\underline{\text{blue}} in Section 4.2. The conditional-mean clarification and historical-disagreement bounds are marked in blue‾\underline{\text{blue}} in Appendix E.3.1 (Eq. (170) and Lemma 23).

AuthorsOpenReview ↗

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 blue‾\underline{\text{blue}}.

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 (β=0.9\beta=0.9) and clipping disabled. Both are D-SOBA-SO-type adaptations. The published algorithm applies momentum only to xx.

Table R1. Worst-attack accuracy (%) in the matched single-loop ablation. MNIST, D-SOBA-SO-type variants, ALIE/SF/IPM/RN.

Protected variablesKrumMedianTrimmed MeanIOS
xx only56.7318.7340.4147.33
(x,y,z)(x,y,z)93.4570.3489.7289.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.

MethodSingle-loopAttack-free (%)Worst-attack (%)Drop (pp)
MA-DSBO / MA-DSBO-MNo89.32 / 93.0784.85 / 88.964.47 / 4.11
GBDSBO / GBDSBO-MNo88.93 / 88.689.74 / 74.0279.19 / 14.66
Single-loop (xx only)Yes96.4240.4156.01
SLBRD / SLBRD-MYes92.92 / 95.3185.75 / 89.727.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.

AuthorsOpenReview ↗

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

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

The paper studies decentralized stochastic bilevel optimization with Byzantine agents, targeting the objective defined by the honest population. SLBRD jointly updates the upper-level variable, a lower-level solution estimate, and an auxiliary variable for hypergradient estimation. It uses a single loop, robust neighborhood aggregation, and auxiliary-variable clipping, avoiding explicit Hessian inversion. SLBRD-M adds momentum. The main theoretical claims concern convergence, network-dependent transient complexity, and the removal of stochastic variance from the persistent Byzantine error through momentum. The experiments evaluate hyperparameter optimization and hyper-representation learning under several attacks and aggregation rules.

Critical strengths
  1. Joint robust tracking addresses a meaningful problem The honest-population objective in Section 2 gives a precise target under Byzantine participation. Corruption of either the lower-level estimate or the auxiliary estimate can distort the upper-level direction, so there is a clear reason to protect all three updates. The decentralized extension is worth studying because neighborhood communication adds consensus errors to these coupled tracking updates.
  2. Experiments cover several attacks and aggregation rules Tables 2 and 3 compare SLBRD and SLBRD-M with MA-DSBO, GBDSBO, and their momentum variants across four attacks and four aggregation rules. The results support their empirical robustness in the tested settings. Section 5.3 also examines the effects of the Byzantine fraction, network size, and data heterogeneity, with detailed results in the appendix.
Critical weaknesses
  1. The central convergence guarantees are not established as stated Algorithm 1 and Section 3.2 require only a positive clipping radius, but a radius that excludes the target auxiliary solution can prevent convergence. This affects the main-text theorem itself. Consider two identical, deterministic honest agents with exact averaging and no momentum. For each agent, let the upper-level objective be half the square of the upper-level variable, plus the lower-level variable and one. Let the lower-level objective be half the squared difference between the lower-level and upper-level variables. These objectives satisfy Assumptions 1-5 with zero noise and heterogeneity. The exact lower-level solution equals the upper-level variable, and the target auxiliary solution is minus one. Set the clipping radius to 0.5 and initialize all three variables at -0.5. Equation (11) then gives zero upper-level and lower-level update directions and an auxiliary direction of 0.5. Every positive auxiliary step is clipped back to -0.5. The iterates therefore remain fixed while the true hypergradient has magnitude 0.5, contradicting the vanishing bound in Theorem 1. The theorem needs an explicit radius condition that ensures containment of the target auxiliary solution, with a sufficient choice derived from Assumptions 2 and 3. The momentum guarantee has a separate gap in Lemma 23, Equation (171), on page 60: common-point heterogeneity is used to bound disagreement between gradients evaluated at different local states. Consider two equally weighted honest agents with identical deterministic scalar objectives. For each agent, take the upper-level objective to be half the square of the upper-level variable and the lower-level objective to be half the square of the lower-level variable. Initialize the lower-level states at 1 and -1, set the initial momenta to zero, and use a momentum coefficient of 0.5. At the first iteration, the lower-level momenta are 0.5 and -0.5. The left-hand side of Equation (171) is 0.25, whereas its right-hand side is zero because there is neither stochastic noise nor objective heterogeneity. Theorem 2 may still be repairable. Before accepting its persistent-error and transient-complexity claims, I would need to see a bound that includes and controls the missing iterate-disagreement terms.
  2. The novelty and communication advantage need clearer support Table 1 and Sections 1.1-3 should make clear what is new relative to the cited Byzantine federated bilevel methods and D-SOBA-SO. Studying the combined setting is useful, but single-loop tracking and momentum already appear in earlier work. I would like the authors to identify the consensus and robustness terms that require new analysis under their assumptions. Tables 2 and 3 report accuracy under the stated budgets, but I could not tell how those budgets count communication within the inner loops of MA-DSBO and GBDSBO. Without that information, I cannot judge the claimed communication advantage. The momentum baselines are useful comparisons. Reporting total message exchanges and local oracle work would help explain where the gains come from. Section 5.2 should also explain how the lower-level classifier is made strongly convex. If it is not, the authors should state that these experiments fall outside the theorem's assumptions.
Questions for authors
  1. What clipping-radius restriction is intended in Algorithm 1 and Theorems 1 and 2? Please address the fixed-point example above, state a sufficient radius using the constants in Assumptions 2 and 3, and confirm whether the reported guarantees hold under that restriction.
  2. How should Lemma 23 be corrected to include disagreement between local and historical iterates? Please show whether the corrected recursion preserves the variance-free persistent error in Theorem 2 and the transient bound in Corollary 2.
  3. Which result or proof step in the paper specifically addresses the additional coupling introduced by decentralized robust aggregation, beyond the cited Byzantine federated bilevel methods and D-SOBA-SO? Please explain the coupling it introduces and which guarantee addresses it.
  4. In Tables 2 and 3, does one reported communication round count every inner-loop exchange in the baselines? Please summarize the message and local-oracle budgets. For the hyper-representation experiment, is the lower-level classifier made strongly convex, or is this an empirical evaluation outside the theorem's scope? Please clarify these points using the existing experimental setup.
4 comments
AuthorsOpenReview ↗

Response to Reviewer jFb6 (1/3)

Thank you for your careful review. We have made the radius condition explicit and included historical iterate disagreement in the analysis. Changes are marked in blue‾\underline{\text{blue}}.

W1 & Q1: What radius condition removes the spurious fixed point, and how is projection handled?

Thank you for pointing this out. Choosing ρ≥Lf/μg\rho\geq L_f/\mu_g ensures that the projection ball contains the target auxiliary solution. In your example, ρ≥1\rho\geq1 includes z⋆=−1z^\star=-1 and rules out the spurious fixed point at −0.5-0.5. The revised proof also controls projection through consensus error, preserving the convergence order and variance-free persistent error under the stated conditions.

Under Assumptions 2–3, the target auxiliary solution satisfies

\qquad \\|z^\star(x)\\|\leq L_f/\mu_g.$$ We now state this radius condition in Algorithm 1, Section 3.2, and Theorems 1–2 (Section 4.2), with the additions marked in $\underline{\text{blue}}$. **We also account explicitly for projection in the proof.** Let $u_i^k$ be the iterate before projection, $z_i^{k+1}=\Pi_\rho(u_i^k)$ the projected iterate, and $\bar u^k$ the average over honest agents. Projection is nonexpansive and therefore does not increase consensus error. Its effect on tracking error is bounded using firm nonexpansiveness: $$\\|\bar z^{k+1}-\bar z_\star^k\\|^2 \leq\\|\bar u^k-\bar z_\star^k\\|^2 +\frac1{n_h}\sum_{i\in\mathcal H}\mathbf1_{\\{\\|u_i^k\\|>\rho\\}}\\|u_i^k-\bar u^k\\|^2.$$ The extra term is bounded by consensus error. Appendices D.3.4 and E.3.4 control its cumulative contribution under $\eta_x=\mathcal O((1-\lambda)^2)$, preserving the $K^{-1/2}$ convergence order and SLBRD-M's variance-free persistent error. If every iterate lies inside the ball before projection, this term vanishes and adds nothing to the transient bound. Containing the target alone does not ensure that every iterate remains inside the ball. The added projection argument in Appendix D.3.4 is marked in $\underline{\text{blue}}$. **The paired tests show that clipping improves stability.** With $\rho=1$, the auxiliary iterates remain bounded and accuracy is 94.5–95.2% (Table R1). The main HPO experiments use $\rho=5$ on synthetic data and $\rho=50$ on MNIST. The main hyper-representation experiments run without clipping. **Table R1. Paired clipping test.** MNIST, SLBRD-M. | Attack + aggregator | ACC, no clipping | ACC, $\rho=1$ | Max. $\Vert z\Vert$, no clipping | Max. $\Vert z\Vert$, $\rho=1$ | | --- | ---: | ---: | ---: | ---: | | SF + Krum | 48.3 | **94.9** | $3.3\times10^5$ | 1.00 | | ALIE + Median | 77.3 | **94.5** | $5.0\times10^5$ | 1.00 | | ALIE + Krum | 88.8 | **95.2** | $1.1\times10^5$ | 1.00 | | IPM + Median | 94.6 | **94.9** | 8.63 | 1.00 | These tests show improved stability with clipping, but do not verify that the chosen radius satisfies the theoretical condition.
AuthorsOpenReview ↗

Response to Reviewer jFb6 (2/3)

W1 & Q2: How does Lemma 23 account for local and historical iterate disagreement?

Thank you for the counterexample. The corrected Lemma 23 retains local iterate disagreement throughout the momentum history. Its cumulative contribution is controlled by consensus error, preserving the convergence order and SLBRD-M's variance-free persistent error under the revised conditions.

Let vjt=(xjt,yjt)v_j^t=(x_j^t,y_j^t) and Cvt=nh−1∑jE∣vjt−vˉt∣2C_v^t=n_h^{-1}\sum_j\mathbb E\\|v_j^t-\bar v^t\\|^2. For the weighted neighborhood momentum mˉi,yk=∑jwijmj,yk\bar m_{i,y}^k=\sum_jw_{ij}m_{j,y}^k, define $ \mathcal E_y^k=\frac1{n_h}\sum_i\sum_jw_{ij}\mathbb E\|m_{j,y}^k-\bar m_{i,y}^k\|^2. $

We separate the sampling noise from the conditional means and evaluate heterogeneity at the common reference point vˉt\bar v^t. Smoothness bounds the differences between local iterates and this reference, giving $ \mathcal E_y^k\leq 6\frac{1-\beta_y}{1+\beta_y}\sigma^2+9\zeta_g^2 +18L_g^2(1-\beta_y)\sum_{t=0}^k\beta_y^{k-t}C_v^t. $

In your counterexample, Cv0=1C_v^0=1, βy=1/2\beta_y=1/2, and Lg=1L_g=1 make the corrected right-hand side 9, which bounds the observed value 0.25. We include the corresponding history terms in the xx- and zz-bounds.

To bound their cumulative contribution, define HΔk,u=(1−βu)∑t=0kβuk−tΔtH_\Delta^{k,u}=(1-\beta_u)\sum_{t=0}^k\beta_u^{k-t}\Delta^t. Reversing the order of summation gives $ \sum_{k=0}^{K-1}H_\Delta^{k,u} =\sum_{t=0}^{K-1}(1-\beta_u^{K-t})\Delta^t \leq\sum_{t=0}^{K-1}\Delta^t. $

This bound holds without assuming that Δt\Delta^t decreases monotonically. In the consensus recursion, the history terms have coefficient O(ηx2/(1−λ))\mathcal O(\eta_x^2/(1-\lambda)), so consensus contraction dominates them for sufficiently small stepsizes. In the aggregation-error bound, their coefficient is κηu2\kappa\eta_u^2. After summation, their contribution is controlled by the decrease in the consensus component of the Lyapunov function. These changes appear in Lemmas 12, 18, and 23 and the final proof in Appendix E. The conditional-mean clarification and revised historical-disagreement bounds are marked in blue‾\underline{\text{blue}} in Appendix E.3.1 (Eq. (170) and Lemma 23).

The sampling-noise term retains the factor (1−βu)/(1+βu)=O(ηu)(1-\beta_u)/(1+\beta_u)=\mathcal O(\eta_u), so its contribution to the persistent error still vanishes. The projection condition for the transient bounds is discussed separately in Q1.


W2 & Q3: What analysis is new beyond federated robust methods and D-SOBA-SO?

We appreciate your comment. Local Byzantine aggregation creates feedback between network disagreement and bilevel tracking. Our joint Lyapunov analysis controls this feedback, yielding a topology-dependent robustness condition and a variance-free persistent error for SLBRD-M.

The additional difficulty. Federated robust methods [1] aggregate at a server and have no network-consensus recursion. Benign D-SOBA-SO [2] uses linear mixing that preserves the honest average. In our setting, each node robustly aggregates its own neighborhood. Lemma 3 bounds aggregation error by local honest-state dispersion, so this error depends on the evolving iterates. It then feeds back into consensus and the coupled bilevel updates: lower-level error perturbs both the auxiliary and upper-level directions, while auxiliary error enters the hypergradient through ∇xy2gizi\nabla^2_{xy}g_i z_i.

The new analysis and resulting guarantees. Lemma 10 quantifies this feedback by replacing the benign consensus factor λ\lambda with $ \lambda+\frac{8\kappa(1+L_g^2)}{1-\sqrt\lambda}. $ We control the coupled errors through a joint Lyapunov function whose consensus weight is $ A_\Delta=A_3\eta_x+\frac{\kappa A_4}{\eta_x}. $ The additional κA4/ηx\kappa A_4/\eta_x term allows consensus contraction to offset the O(κΔk/ηx)\mathcal O(\kappa\Delta^k/\eta_x) aggregation perturbation (Appendix D.2, Eqs. (35) and (43)–(44)). This step yields the topology-dependent condition κ≤c(1−λ)2\kappa\leq c(1-\lambda)^2. The extra weight vanishes in benign D-SOBA-SO and has no counterpart in server-based methods without network consensus.

Under the stated theorem conditions, SLBRD-M further reduces the persistent error from O(κ(σ2+ζf2+ζg2))\mathcal O(\kappa(\sigma^2+\zeta_f^2+\zeta_g^2)) to O(κ(ζf2+ζg2))\mathcal O(\kappa(\zeta_f^2+\zeta_g^2)) (Theorems 1–2). Lemmas 12 and 23 establish this improvement by controlling historical disagreement separately from sampling noise, as explained in Q2. For κ=O(δ)\kappa=\mathcal O(\delta), the resulting error matches the lower-bound order cited in the paper.

The revised conditions in Theorems 1–2 (Section 4.2) and the conditional-mean and historical-disagreement bounds in Appendix E.3.1 are marked in blue‾\underline{\text{blue}}.

[1] Li et al. Single-Loop Byzantine-Resilient Federated Bilevel Optimization. ICLR, 2026.

[2] Kong et al. Decentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity. JMLR, 2025.

AuthorsOpenReview ↗

Response to Reviewer jFb6 (3/3)

W2 & Q4: Do the budgets count inner-loop exchanges, and is the neural lower level strongly convex?

Thank you for the question. The per-update counts include all inner-loop exchanges, while the plotted hyper-representation budget is epoch-weighted rather than a cumulative exchange count. The original neural lower level is unregularized. The added strongly convex comparison preserves SLBRD-M's advantage with at most a 0.46-point accuracy change.

Communication and oracle work. The plotted hyper-representation budget is B=e×cB=e\times c, where ee is the number of completed epochs and cc is the number of variable-block exchanges per update. One block exchange communicates one variable across the network. A complete hyper-representation update has the following costs, unchanged by adding momentum:

Table R2. Cost per update. Oracle counts are per node.

MethodBlock exchangesGradientsHVPsJVPs
SLBRD3311
MA-DSBO7621
GBDSBO5331

SLBRD exchanges x,y,zx,y,z once each. MA-DSBO uses T+2N+1=7T+2N+1=7 exchanges with T=N=2T=N=2, including its inner loops. GBDSBO uses five exchanges and three HVPs. The corresponding synthetic- and MNIST-HPO exchange coefficients are (6,11,8)(6,11,8) and (6,6,8)(6,6,8) in the same method order.

For HPO, the logger advances after each outer iteration. For hyper-representation, the logger adds cc once per epoch: c=3c=3 for SLBRD, 77 for MA-DSBO, and 55 for GBDSBO. For example, three SLBRD epochs give B=3×3=9B=3\times3=9. Since an epoch can contain multiple updates, BB is an epoch-weighted budget rather than the actual cumulative exchange count. This distinction is now stated in Section 5.2 and the "Network and communication accounting" paragraph of Appendix A.1.5, with the additions marked in blue‾\underline{\text{blue}}. The supported communication comparison is 3 versus 7 block exchanges per update, not a total-message ratio inferred from the plotted axis.

For example, under IPM + IOS on MNIST, SLBRD-M first reaches 85% accuracy at median logged B=9B=9 (3 epochs), versus B=28B=28 (4 epochs) for MA-DSBO-M. These are epoch-based progress measurements, not measured end-to-end communication totals.


Is the neural lower level strongly convex? Our algorithms can be applied to both settings. HPO uses positively regularized logistic regression. In the original hyper-representation runs, the lower variable is an unregularized linear classifier, so those runs evaluate performance outside the strong-convexity assumption. Adding μ∣θ∣2/2\mu\\|\theta\\|^2/2 to all classifier weights and biases enforces μ\mu-strong convexity for fixed features.

Table R3. Worst-attack accuracy (%). MNIST, Trimmed Mean.

Methodμ=0\mu=010−410^{-4}10−310^{-3}10−210^{-2}
SLBRD-M89.7289.6589.2689.46
MA-DSBO-M88.9688.9688.9688.72

Enforcing strong convexity changes SLBRD-M's accuracy by at most 0.46 percentage points, while its advantage over MA-DSBO-M persists.

AuthorsOpenReview ↗

A Kind Reminder Regarding Our Author Response

Dear Reviewer jFb6,

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:

  • An explicit projection-radius condition and a revised treatment of projection in the convergence proof.
  • A correction to Lemma 23 that accounts for historical iterate disagreement in the momentum analysis.

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

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

The paper studies decentralized stochastic bilevel optimization with Byzantine agents. It proposes SLBRD, which jointly updates the upper-level variable, lower-level variable, and an auxiliary Hessian-inverse-vector estimate in a single loop, with robust aggregation after each update.

The authors derive convergence and transient-complexity bounds. A momentum variant, SLBRD-M, is claimed to remove stochastic variance from the persistent Byzantine error and improve part of the topology-dependent transient complexity.

Experiments cover synthetic data, MNIST, and CIFAR-10, using hyperparameter optimization and hyper-representation tasks under four attacks and four aggregation rules.

Critical strengths

The paper addresses a meaningful gap between decentralized bilevel optimization and Byzantine-resilient learning. Corruption can affect both the lower-level response and the resulting hypergradient, so extending robustness to this setting is not merely a matter of protecting the upper-level update.

The algorithm is compact and implementable. Tracking the auxiliary vector avoids explicit Hessian inversion, and the single-loop structure makes the communication pattern straightforward. The attempt to separate topology, heterogeneity, stochastic noise, and Byzantine effects in the bounds is useful.

The empirical study covers several attacks and aggregators, and includes momentum versions of the baselines. That is a stronger comparison than testing only unprotected or non-momentum alternatives.

Critical weaknesses

Important theorem conditions are omitted. The proofs require a small aggregation constant (\kappa), depending on topology and smoothness. These restrictions should appear in the theorems and be reconciled with the experiments at 30% Byzantine agents.

The network assumptions are insufficiently specified. A global Byzantine fraction does not ensure suitable local neighborhoods. The graph, mixing weights, and conditions needed by the robust aggregators should be explicit.

Aggregator definitions are unclear. The stated trimmed mean differs from coordinate-wise trimming, and the median description is inconsistent across sections. The exact implementations need clarification.

Questions for authors

What is the complete admissible range of (\kappa), (\delta), and the spectral gap after combining all proof conditions? Does any reported experiment satisfy it?

How is Equation (170) derived when the mean stochastic direction changes with the iterates?

What local Byzantine-neighbor condition is required, and how does it relate to the stated global corruption fraction?

Which exact Krum, median, and trimmed-mean implementations produced the tables?

What graphs, mixing weights, and communication accounting are used?

How do the methods compare with a robustly aggregated single-loop bilevel baseline, and how is lower-level strong convexity enforced in the neural experiments?

5 comments
AuthorsOpenReview ↗

Response to Reviewer HgEW (1/4)

Thank you for your review. Manuscript revisions are marked in blue‾\underline{\text{blue}}.

W1 & Q1: What conditions are required, and do the 30% Byzantine experiments satisfy them?

Thank you for your comment. The κ\kappa condition is sufficient for the convergence guarantee, not a limit on the algorithm's empirical tolerance. The reported 30% Byzantine runs fall outside this certified range. The topology experiments demonstrate empirical robustness beyond it, rather than validate the theoretical bound.

For the theoretical analysis, κ≤κˉ(λ)=Θ((1−λ)2)\kappa\leq\bar\kappa(\lambda)=\Theta((1-\lambda)^2) is a sufficient condition used to establish the convergence guarantee. The bound specifies the scope of the convergence guarantee, rather than the algorithm's maximum Byzantine tolerance. Here 1−λ1-\lambda is the honest-reference spectral gap. A smaller gap means slower consensus and a stricter bound in the proof, which also requires the stated assumptions, stepsize restrictions, and clipping-radius condition. We have made the additional conditions explicit in Theorems 1–2 (Section 4.2), with the changes marked in blue‾\underline{\text{blue}}.

In practice, SLBRD-M can tolerate corruption levels beyond those certified by this bound, as demonstrated in the tested settings. At δ=0.30\delta=0.30, the robustness lowerbound κ≥δ/(1−2δ)=0.75\kappa\geq\delta/(1-2\delta)=0.75 already exceeds κˉ(λ)<1/32\bar\kappa(\lambda)<1/32, so the 30% Byzantine runs are outside the sufficient theoretical range. SLBRD-M nevertheless achieves 87.69–90.40% accuracy across the four graphs in Table R1.

The topology experiment further tests this tolerance on sparser networks. At each global corruption level, we vary the graph while keeping the task, number of agents, attack, and logged budget fixed. Even on the degree-4 graph, where the maximal local Byzantine fraction reaches 40% at 30% global corruption, SLBRD-M achieves 87.69% accuracy.

Table R1. Test accuracy (%) across network topologies. MNIST, SLBRD-M, IPM + Trimmed Mean.

Graphgallg_{\mathrm{all}}10% Byz.20% Byz.30% Byz.δmax⁡\delta_{\max} at 30%
Circulant, degree 40.08095.2793.0187.690.40
Circulant, degree 80.26995.4591.8789.930.33
Circulant, degree 120.52295.1192.6490.400.31
Complete0.95294.6991.9489.950.30

Here gallg_{\mathrm{all}} describes the full graph, whereas the theorem uses the honest-reference gap. The local Byzantine fraction also changes with topology. Thus the table supports empirical robustness across the tested networks, without isolating or validating the theoretical squared-gap dependence.

AuthorsOpenReview ↗

Response to Reviewer HgEW (2/4)

Q2: Why does Eq. (170) hold when the mean direction changes with the iterates?

Thank you for raising this point. Eq. (170) bounds sampling noise around the evolving conditional means. Conditional centering eliminates cross-step noise terms even as the iterates change, while Lemma 23 separately controls differences between the accumulated mean directions.

Let Ft\mathcal F^t contain the history before sampling at step tt, including the current iterates. Define

\epsilon_{u,j}^t=D_{u,j}^t-d_{u,j}^t,\qquad M_{u,j}^k=(1-\beta_u)\sum_{t=0}^k\beta_u^{k-t}d_{u,j}^t.$$ Here $M_{u,j}^k$ accumulates the conditional means along the realized iterates. It is the reference denoted by $\mathbb E(m_{u,j}^k)$ in the original shorthand, rather than the unconditional expectation of the momentum. The clarification of this reference and the cross-step noise argument is marked in $\underline{\text{blue}}$ in Appendix E.3.1, around Eq. (170). With zero initial momentum, $m_{u,j}^k-M_{u,j}^k=(1-\beta_u)\sum_{t=0}^k\beta_u^{k-t}\epsilon_{u,j}^t$. At every step, $\mathbb E[\epsilon_{u,j}^t\mid\mathcal F^t]=0$, even though the iterates and conditional means change. For $s<t$, the earlier noise is $\mathcal F^t$-measurable, so conditional expectation gives $\mathbb E\langle\epsilon_{u,j}^s,\epsilon_{u,j}^t\rangle=0$. With the bounded-variance assumption, this yields $$\mathbb E\\|m_{u,j}^k-M_{u,j}^k\\|^2 =(1-\beta_u)^2\sum_{t=0}^k\beta_u^{2(k-t)}\mathbb E\\|\epsilon_{u,j}^t\\|^2 \leq\frac{1-\beta_u}{1+\beta_u}\sigma_u^2.$$ To account for differences in the mean directions, Lemma 23 uses $$\mathbb E\\|m_j-\bar m_i\\|^2 \leq3\mathbb E\\|m_j-M_j\\|^2 +3\mathbb E\\|\bar m_i-\bar M_i\\|^2 +3\mathbb E\\|M_j-\bar M_i\\|^2,$$ where bars denote weighted neighborhood averages and block and iteration indices are omitted. The first two terms contribute at most $6(1-\beta_u)\sigma_u^2/(1+\beta_u)$. The third retains the differences between agents' accumulated conditional means and is bounded using heterogeneity at a common point and historical iterate disagreement. This separates the sampling-noise bound from the mean-direction differences without requiring the two to be orthogonal. --- > **W2 & Q3: Is a global Byzantine fraction sufficient on a sparse graph?** Thank you for the question. **The Byzantine-fraction requirement is local: every honest node must have a strict majority of honest inputs, counting its own message.** A small global fraction does not ensure this. The full guarantee also requires honest-network connectivity, the aggregator's validity conditions, and the small-$\kappa$ bound. Each node aggregates only its own message and those from its neighbors. The clarification marked in $\underline{\text{blue}}$ after Definition 2 in Section 2 states the corresponding local requirement: \$ \\delta_i=\\frac{|\\mathcal N_i\\cap\\mathcal B|}{|\\mathcal N_i|+1}, \\delta_{\\max}=\\max_{i\\in\\mathcal H}\\delta_i<\\frac12. \$ Here $\mathcal N_i$ excludes node $i$, and $\delta_i$ counts Byzantine inputs among all inputs to its aggregator. This is an input-count fraction, consistent with the uniform input weights used in our robust aggregation implementations. On the default complete graph, every honest node aggregates all $n=10$ inputs, including $f=3$ Byzantine inputs, so $\delta_i=f/n=0.30$. On a sparse graph, Byzantine nodes can be concentrated in particular neighborhoods. In the topology experiment in Table R1, the degree-4 graph has $\delta_{\max}=0.40$ at the same 30% global corruption. The convergence guarantee additionally requires a connected honest network, the chosen aggregator's own validity conditions, and the small-$\kappa$ bound in Q1. The local majority condition alone is therefore insufficient for the full guarantee.
AuthorsOpenReview ↗

Response to Reviewer HgEW (3/4)

W3 & Q4: Aggregation implementations and robustness guarantees.

Thank you for your comment. The HPO and MNIST results use Multi-Krum, coordinatewise median, coordinatewise trimmed mean, and IOS. We specify the CIFAR-10 variants separately and apply the stated robustness constants only to the matching coordinatewise rules.

Section 5 and Appendix A.1.5 now distinguish the exact implementations behind each aggregation label. The implementation table (Table 6) and its introductory explanation are marked in blue‾\underline{\text{blue}}. Each rule is applied separately to each parameter tensor. On the default complete graph, it receives 10 inputs, including the node's own message, with f=3f=3.

For Multi-Krum, kk is the number of nearest other inputs used in each squared-distance score, and mm is the number of lowest-scoring inputs averaged.

LabelHPO and MNIST hyper-representation
KrumMulti-Krum: (k,m)=(5,7)(k,m)=(5,7) for HPO and (6,5)(6,5) for MNIST
MedianCoordinatewise median
Trimmed MeanDiscard the 3 largest and 3 smallest values in each coordinate, then average the remaining 4
IOSRemove the vector farthest from the current mean, recomputing the mean after each removal. Repeat 3 times, then average the remaining 7

The CIFAR-10 variants are specified separately in Appendix A.1.5. Its Median variant uses at most 20 Weiszfeld iterations with tolerance 10−610^{-6} to approximate the geometric median.

Table 7 gives the robustness constants from [1] for coordinatewise rules under uniform honest-reference weights. We apply these constants only to the corresponding rules. The other implemented variants provide additional empirical comparisons.

[1] Allouah et al. Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity. AISTATS, 2023.


W2 & Q5: Network topology, mixing weights, and communication costs.

Thank you for this question. All main experiments use complete graphs, and the per-update exchange counts include the baselines' inner loops. The hyper-representation axis is an epoch-weighted budget, so the 3-versus-7 comparison establishes a per-update communication advantage, not a measured total-message saving.

The additions marked in blue‾\underline{\text{blue}} in Section 5 and the "Network and communication accounting" paragraph of Appendix A.1.5 specify the network settings and budget convention.

The default graph has 10 agents, including 3 Byzantine agents. The full-graph mixing matrices are Wall=11⊤/nW_{\mathrm{all}}=\mathbf1\mathbf1^\top/n for HPO and Wall=(I+11⊤)/(n+1)W_{\mathrm{all}}=(I+\mathbf1\mathbf1^\top)/(n+1) for hyper-representation. Robust aggregation treats neighborhood inputs uniformly, including the node's own message.

One block exchange communicates one variable across the network. The following counts include all such exchanges within an outer update:

TaskSLBRD / SLBRD-MMA-DSBO / MA-DSBO-MGBDSBO / GBDSBO-M
Synthetic HPO6118
MNIST HPO668
Hyper-representation375

For hyper-representation, SLBRD exchanges x,y,zx,y,z once each. MA-DSBO uses T+2N+1=7T+2N+1=7 exchanges with T=N=2T=N=2, including its inner loops. For HPO, SLBRD exchanges three direction blocks and three iterate blocks.

HPO records the budget after each outer iteration. Hyper-representation records B=e×cB=e\times c, where ee is the number of completed epochs and cc is the number of block exchanges per update listed above. For example, three SLBRD epochs give B=3×3=9B=3\times3=9. Since an epoch can contain multiple updates, this axis is an epoch-weighted budget. The 3-versus-7 comparison measures communication per update. Ratios of plotted BB values do not directly measure cumulative message savings.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Author Responses and Manuscript Revisions

Dear reviewers and AC,

Thank you for your thoughtful comments, questions, and suggestions. We have addressed the individual reviewer feedback in our detailed responses. In this global response, we highlight the main experiments and manuscript updates. As the discussion draws to a close, we would be happy to address any remaining questions or concerns.

New experiments

We have added the following experiments in response to the reviewers’ comments. Changes in the revised manuscript are highlighted in blue‾\underline{\text{blue}}.

  • New study of four network topologies, including 30% Byzantine corruption beyond the theorem’s sufficient range (Reviewer HgEW).
  • Ablation comparing protection of all three variables with protection of the upper variable alone (Reviewer 3YLV).
  • Comparison of SLBRD with and without momentum under attacked and attack-free conditions (Reviewer 3YLV).
  • Paired MNIST experiments with and without clipping the auxiliary variable (Reviewer jFb6).
  • New comparison with MA-DSBO-M using a strongly convex lower-level classifier (Reviewer HgEW).

Other updates on the manuscript

  • Clarified the local honest-majority requirement and the spectral-gap condition for convergence (Sections 2 and 4.2).
  • Specified the projection radius and revised the proof for auxiliary-variable tracking (Section 3.2, Appendices D.3.4 and E.3.4).
  • Clarified the conditional mean in Eq. (170) and corrected the bound on past disagreement in Lemma 23 (Appendix E.3.1).
  • Explained how the momentum analysis controls network and tracking errors and removes stochastic variance from the persistent Byzantine error (Reviewer 3YLV).
  • Documented aggregation rules, robustness bounds and network mixing weights (Section 5, Appendix A.1.5).
  • Clarified per-update communication counts and the epoch-based budget in hyper-representation experiments (Section 5.2, Appendix A.1.5).
  • Reported derivative calls per node and clarified baseline protection at inner- and outer-loop exchanges (Reviewers jFb6 and 3YLV).

Thank you again for the time invested in reviewing our work.

Best regards,
The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.