- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies federated bilevel optimization with constrained lower-level problems. The author propose FedBiC, a single-loop and Hessian-free algorithm based on a gap function reformulation. They provide theoretical analysis under partial participation, and evaluate the proposed method on several federated bilevel tasks.
Critical strengths
- Existing federated bilevel optimization methods primarily consider unconstrained lower-level problems. This paper extends the single-machine method to client-specific lower-level inquality constraints, addresing an relatively unexplored problem.
- For algorithm design, it emphasizes the difference between the proposed federated method and the existing single-machine BiC-GAFFA algorithm.
- The experiments cover multiple federated bilevel applications.
Critical weaknesses
- Theorem 4.5 establishes convergence to a stationary point of the penalized formulation, rather than the original constrained bilevel optimization. Although Appendix E further discusses the connection to stationarity of the original bilevel problem under additional regularity conditions, this result relies on a convergent subsequence with vanishing stationarity residual and lower-level gap. It remains unclear to what extent the proposed algorithm guarantees stationarity of the original constrained bilevel problem. The authors should clarify the scope of their stationarity results and revise the corresponding claim in Table 1.
- The federated bilevel baselines considered in the experiments solve unconstraint lower-level problems, whereas FedBIC explicitly incorporates lower-level constraints. Therefore, it remains unclear whether the empirical gains primarily arise the constraint formulation, or the proposed algorithm design. Additional ablation studies would help distinguish these contributions.
- Theorem D.14 requires the participation rate larger than . Although the authors discuss this condition in the appendix, it remains unclear whether the theoretical requirements can be satisfied with practical step sizes for the participation rates evaluated in the experiments. Further clarification would help establish the practical relevance of this convergence guarantee.
- Minor: the parameter appears in rates presented in the abstact and introduction, but its definition is not provided there. Introducing when these rates are first stated would improve clarity.
Questions for authors
See the Weaknesses above.
6 comments
Weakness 2 Response to Reviewer Pvpy
Weakness 2
We agree that comparisons against unconstrained baselines alone do not separate the effect of the formulation from that of the algorithm. To our knowledge, no existing federated bilevel method handles lower-level inequality constraints, so these baselines solve the relaxed problem. Our contribution is an algorithm that handles client-specific lower-level inequality constraints in the federated setting, with convergence guarantees, while keeping a single loop, Hessian-free updates, partial participation, and no heterogeneity bound.
The fairness experiment (Table 3) shows the resulting trade-off. FedBiC has the lowest parity gap, 54–60% below every unconstrained baseline, with accuracy within one standard deviation of SCAFFOLD, FedProx and FedNest; FedAvg is 1.6 points more accurate but has about 2.5 times the parity gap.
To assess whether access to the same fairness information explains the gains, we evaluated penalty-augmented baselines. The penalty is added to each client's training objective. For each baseline, we tuned on the tuning seeds, choosing the most accurate weight whose parity gap is no larger than FedBiC's, or the lowest-gap weight if none reaches it, and evaluated on the same five held-out seeds (Appendix B.2, Table 12, in blue):
| Method | Test Acc | Test DP gap |
|---|---|---|
| FedBiC | ||
| SCAFFOLD + penalty | ||
| FedAvg + penalty | ||
| FedProx + penalty | ||
| FedNest + penalty |
FedBiC is 3.1–6.2 points more accurate than each penalty-augmented baseline. On the held-out test results, FedAvg, SCAFFOLD and FedNest with the penalty reach a slightly smaller parity gap, at 4.4–6.2 points lower accuracy, and FedProx with the penalty is worse on both. Table 13 (in blue) reports every penalty weight we evaluated. Every penalized configuration at least as accurate as FedBiC has a parity gap of at least 0.22, about twice FedBiC's, and every configuration with a parity gap no larger than FedBiC's is at least 3.4 points less accurate. In these experiments, no penalized configuration matched FedBiC on both accuracy and parity gap.
Weakness 3 & 4 Response to Reviewer Pvpy
Weakness 3
The participation condition of Lemma D.9 is
For any prescribed participation rate , the condition holds whenever
Thus Theorems 4.5 and 4.7(ii) accommodate arbitrarily small fixed positive participation rates. One chooses appropriately and then selects the step size and the number of inner iterations according to the stated sufficient conditions. The case satisfies the condition automatically. The Table 9 runs use an increasing penalty, so the revised Theorem 4.7(ii) addresses the increasing-penalty, partial-participation setting used in these experiments; the text under Table 9 now notes this (in blue).
The role of this condition is to ensure that the contraction of the local tracking errors outweighs the drift caused by updates of the shared variable while clients are inactive. Lower participation therefore requires a more conservative balance between outer movement and inner tracking. It does not create an intrinsic participation cutoff for FedBiC.
The step-size bounds in the analysis are sufficient conditions, obtained by simultaneously controlling smoothness, tracking, and gradient-table errors. They establish a nonempty convergence regime. They are not meant to characterize the largest stable step sizes in practice. Empirically, the mean values of in Table 9 range from 0.5632 to 0.5650 as participation varies from to , suggesting limited sensitivity to participation in this experiment. Remark D.15 now explicitly explains (in blue) how , the step size, and the number of inner iterations are chosen for a prescribed participation rate.
Weakness 4 Thank you. is the exponent of the penalty schedule , so it sets how fast the penalty grows. It controls a trade-off: a larger gives a faster gap rate but a slower stationarity rate , and balances the two at . It is now defined, with this meaning, in Section 1.1 (in blue).
We hope the revision addresses the reviewer's concerns. If so, we would be grateful if the reviewer would consider updating the score. We are happy to clarify anything further.
Weakness 1 Response to Reviewer PvpY
We thank the reviewer for the careful reading and the concrete suggestions. All changes in the revised PDF are marked in blue.
Weakness 1
We agree that the scope should be stated precisely. Our guarantees are:
We do not claim a non-asymptotic rate for stationarity of the original constrained bilevel problem. We have clarified in the Related Work section (in blue) that, for BiC-GAFFA and FedBiC, the complexity in Table 1 refers to stationarity of the penalized objective.
On the subsequence: Appendix E does not assume it. Lemma E.4 proves that it exists. The proof of Theorem 4.7(i) gives ∑kck−2Rk2<∞, while ∑kck−2=∞ because 2ρ<1, so liminfkRk=0. Under the boundedness hypothesis of Theorem 4.7, the gap vanishes along the whole sequence, and compactness gives a convergent subsequence. Theorem E.10 then establishes stationarity of the original problem at the selected limit point under its stated smoothness, interiority, and lower-level regularity assumptions, including LICQ, strict complementarity, and SSOSC. These assumptions justify the local differentiable solution map used in the argument. Without them, this conclusion does not follow from our analysis. For comparison, BiC-GAFFA states its algorithmic guarantees for the same penalized residual, and relates its reformulation to the original problem only at global minimizers.
The revision adds two results.
Corollary D.23 (Appendix D, in blue). Under a fixed penalty and partial participation, suppose each client initializes at a lower-level primal–dual solution at x0 (one local convex solve), with θi0=yi0, λi0=zi0 and a zero gradient table, as in Algorithm 1. Then for every k,
E[N1∑i=1NGγ,i(wik)]≤c1⋅N1∑i=1N(Fi(x0,yi0)−Fi)+p0c24α⋅N1∑i=1N∇xFi(x0,yi0)2.
So Theorem 4.5 also comes with an O(1/c) bound on the expected average lower-level gap, uniformly over iterations, and hence an O(c−1/2) bound on the expected constraint violation, without the boundedness hypothesis of Theorem 4.7.
Theorem 4.7(ii) (in blue). An increasing-penalty gradient-mapping rate now also holds under partial participation, with the same exponent and an extra factor p−1/2 (proof in Theorem D.24, in blue).