acceptodds
Under review as a conference paper at ICLR 2027

FedBiC: Federated Bilevel Constrained Optimization

Abstract

Bilevel optimization has emerged as a fundamental framework for hierarchical machine learning problems, such as hyperparameter optimization, meta-learning, adversarial training, and neural architecture search. Extending this framework to federated settings allows collaborative training between distributed clients without sharing raw data. However, existing federated bilevel methods assume unconstrained lower-level problems, excluding applications with fairness constraints, resource budgets, or safety requirements. We propose FedBiC, the first federated bilevel algorithm that is capable of handling a convex lower-level objective together with general client-specific convex inequality constraints, using a gap function reformulation. FedBiC is single-loop and Hessian-free, supports partial client participation, and requires no bound on client heterogeneity. We establish an convergence rate to a stationary point of the penalized objective under a fixed penalty and partial participation, where denotes the number of communication rounds. With an increasing penalty parameter and full participation, FedBiC attains an stationarity rate for the penalized objective, together with an rate on the clientwise lower-level gap violation. Experiments on federated constrained LASSO, fair few-shot meta-learning, and federated steering under label noise are conducted to validate our approach.

Primary area:
optimization
Keywords:
Federated learning, Federated Bilevel Optimization, Constrained bilevel optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_PvpYOpenReview ↗
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
  1. 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.
  2. For algorithm design, it emphasizes the difference between the proposed federated method and the existing single-machine BiC-GAFFA algorithm.
  3. The experiments cover multiple federated bilevel applications.
Critical weaknesses
  1. 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.
  2. 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.
  3. Theorem D.14 requires the participation rate larger than pmin⁡(τ)p_{\min}(\tau). 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.
  4. Minor: the parameter ρ\rho appears in rates presented in the abstact and introduction, but its definition is not provided there. Introducing ρ\rho when these rates are first stated would improve clarity.
Questions for authors

See the Weaknesses above.

6 comments
AuthorsOpenReview ↗

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:

GuaranteeTypeSettingWhere
Penalized gradient-mapping stationarity, O(1/pK)O(1/\sqrt{pK})non-asymptoticfixed cc, partial participationThm 4.5
Expected average lower-level gap O(1/c)O(1/c), uniformly over iterationsnon-asymptoticfixed cc, partial participation, lower-level-solved startCor. D.23
Penalized residual stationarity O(K−(1−2ρ)/2)O(K^{-(1-2\rho)/2}); gap O(K−ρ)O(K^{-\rho}) under boundednessnon-asymptoticgrowing ckc_k, full participationThm 4.7(i)
Penalized gradient-mapping stationarity O(p−1/2K−(1−2ρ)/2)O(p^{-1/2}K^{-(1-2\rho)/2}); gap O(K−ρ)O(K^{-\rho}) under boundednessnon-asymptoticgrowing ckc_k, partial participationThm 4.7(ii)
Stationarity of the original bilevel problemasymptotic, at regular limit pointsgrowing ckc_k, full participationThm E.10

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<∞\sum_k c_k^{-2}R_k^2<\infty, while ∑kck−2=∞\sum_k c_k^{-2}=\infty because 2ρ<12\rho<1, so lim inf⁡kRk=0\liminf_k R_k=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 x0x^0 (one local convex solve), with θi0=yi0\theta_i^0=y_i^0, λi0=zi0\lambda_i^0=z_i^0 and a zero gradient table, as in Algorithm 1. Then for every kk,

E[1N∑i=1NGγ,i(wik)]≤1c⋅1N∑i=1N(Fi(x0,yi0)−Fi‾)+4αp0c2⋅1N∑i=1N∥∇xFi(x0,yi0)∥2.\mathbb{E}\Big[\frac{1}{N}\sum_{i=1}^N G_{\gamma,i}(w_i^k)\Big]\le \frac{1}{c}\cdot\frac{1}{N}\sum_{i=1}^N\big(F_i(x^0,y_i^0)-\underline{F_i}\big)+\frac{4\alpha}{p_0c^2}\cdot\frac{1}{N}\sum_{i=1}^N\big\Vert\nabla_xF_i(x^0,y_i^0)\big\Vert^2 .

So Theorem 4.5 also comes with an O(1/c)O(1/c) bound on the expected average lower-level gap, uniformly over iterations, and hence an O(c−1/2)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/2p^{-1/2} (proof in Theorem D.24, in blue).

AuthorsOpenReview ↗

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 μpenmax⁡(0,∣ci⊤yi∣−ε0)2\mu_{\mathrm{pen}}\max(0,|c_i^\top y_i|-\varepsilon_0)^2 is added to each client's training objective. For each baseline, we tuned μpen\mu_{\mathrm{pen}} 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):

MethodTest Acc ↑\uparrowTest DP gap ↓\downarrow
FedBiC0.7155±0.0130\mathbf{0.7155\pm0.0130}0.1134±0.02390.1134\pm0.0239
SCAFFOLD + penalty0.6717±0.01530.6717\pm0.01530.1036±0.05040.1036\pm0.0504
FedAvg + penalty0.6663±0.02330.6663\pm0.02330.0872±0.03080.0872\pm0.0308
FedProx + penalty0.6843±0.01490.6843\pm0.01490.1460±0.03660.1460\pm0.0366
FedNest + penalty0.6539±0.02070.6539\pm0.02070.1050±0.02730.1050\pm0.0273

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.

AuthorsOpenReview ↗

Weakness 3 & 4 Response to Reviewer Pvpy

Weakness 3

The participation condition of Lemma D.9 is

pmin⁡(τ)=max⁡j∈{1,2}4γjτ4γjτ+η.p_{\min}(\tau)=\max_{j\in\lbrace 1,2\rbrace}\frac{4\gamma_j\tau}{4\gamma_j\tau+\eta}.

For any prescribed participation rate p∈(0,1)p\in(0,1), the condition p>pmin⁡(τ)p>p_{\min}(\tau) holds whenever

0<τ<min⁡j∈{1,2}ηp4γj(1−p),τ≤1.0<\tau<\min_{j\in\lbrace 1,2\rbrace}\frac{\eta p}{4\gamma_j(1-p)},\qquad \tau\le 1.

Thus Theorems 4.5 and 4.7(ii) accommodate arbitrarily small fixed positive participation rates. One chooses τ\tau appropriately and then selects the step size and the number of inner iterations according to the stated sufficient conditions. The case p=1p=1 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 Φ\Phi in Table 9 range from 0.5632 to 0.5650 as participation varies from p=0.2p=0.2 to p=1p=1, suggesting limited sensitivity to participation in this experiment. Remark D.15 now explicitly explains (in blue) how τ\tau, the step size, and the number of inner iterations are chosen for a prescribed participation rate.

Weakness 4 Thank you. ρ∈(0,1/2)\rho\in(0,1/2) is the exponent of the penalty schedule ck=c0(k+1)ρc_k=c_0(k+1)^\rho, so it sets how fast the penalty grows. It controls a trade-off: a larger ρ\rho gives a faster gap rate O(K−ρ)O(K^{-\rho}) but a slower stationarity rate O(K−(1−2ρ)/2)O(K^{-(1-2\rho)/2}), and ρ=1/4\rho=1/4 balances the two at O(K−1/4)O(K^{-1/4}). 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.

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

The paper proposes the first federated bilevel optimization algorithm with general lower-level inequality constraints, FedBiC, which is single-loop and Hessian-free. The algorithm is analyzed under partial client participation. The authors provide theoretical analysis on the problem with convex local lower-level objectives and constraints. The method shows empirical practicality through numerical experiments on federated constrained LASSO, fair few-shot meta-learning, and federated steering.

Critical strengths

As the authors claim, this is the first federated bilevel optimization algorithm with general client-specific lower-level inequality constraints. The paper provides convergence guarantees of the algorithm to a stationary point for the penalized formulation.

Critical weaknesses

Despite the new analysis of inactive-client drift and gradient-table staleness, there remains a concern about the significance of the advancement beyond previous works like BiC-GAFFA and FedVARP. To strengthen the contribution, the authors may explore an increasing-penalty result under partial participation, as well as broader federated settings, such as bidirectional compression and stochastic gradient estimation, non-convex lower-level objectives and constraints, and shared lower-level variables, as valuable directions for future work.

Questions for authors
  • What existing analysis adds beyond BiC-GAFFA and server-side table methods?
  • The increasing-penalty guarantee requires full participation. Is it intrinsic to the method or a limitation of the current analysis?
7 comments
AuthorsOpenReview ↗

Question 1 Response to Reviewer wdqc

We thank the reviewer for the positive assessment and the precise questions. All changes in the revised PDF are marked in blue.

Q1. What existing analysis adds beyond BiC-GAFFA and server-side table methods?

BiC-GAFFA provides the gap-function reformulation and its centralized analysis. Server-side table methods such as FedVARP handle stale gradients of fixed local objectives. Neither covers what happens to a client's lower-level problem while that client is not sampled, which is the central difficulty of constrained federated bilevel optimization. Our analysis adds four things.

  1. Drift of an unsampled client's lower-level problem (Lemma D.9). In single-level table methods, a stale entry is the gradient of a fixed function at an old xx, and its error is controlled by smoothness and the motion of xx. In FedBiC, an inactive client also holds lower-level variables (yi,zi,θi,λi)(y_i,z_i,\theta_i,\lambda_i) that stay frozen while xx moves. Their targets θi⋆\theta_i^{\star} and λi⋆\lambda_i^{\star} depend on xx, so the client's tracking error grows while it waits. Single-level methods have no tracking variables, so this has no analogue there.
  2. An explicit participation threshold (Theorem D.14). Sampled clients contract their tracking errors, while unsampled clients drift. The merit function decreases when contraction dominates, that is, when peff=p−(1−p)⋅4γτ/η>0p_{\mathrm{eff}}=p-(1-p)\cdot 4\gamma\tau/\eta>0. This gives the threshold pmin⁡(τ)p_{\min}(\tau). The analysis parameter τ\tau trades it against the step size, so any p>0p>0 is admissible.
  3. Cancellation across clients without a heterogeneity constant (Lemma D.9, Step 1; Theorem D.14). Bounding each client's term ⟨∇xϕc,i,xk+1−xk⟩\langle\nabla_x\phi_{c,i}, x^{k+1}-x^k\rangle separately by Young's inequality leaves a term that is not proportional to the step size, and the analysis does not close. We keep these inner products and average them over all NN clients, active or not, so they combine into one term that cancels against the server step. This is why neither rate depends on a heterogeneity bound. The table staleness (Lemma D.17) is then coupled to the tracking errors through the augmented Lyapunov function Vk+(4α/p0)SkV_k+(4\alpha/p_0)S^k (Theorem D.21).
  4. Relation to the original problem (Appendix E). BiC-GAFFA's algorithmic guarantees are for the residual of the penalized objective, and it relates its reformulation to the original problem only at global minimizers. Theorem E.10 shows that, under its stated smoothness, interiority and regularity assumptions, the penalized stationarity conditions rescaled by ckc_k become the adjoint system of the original problem at the limit point selected in Lemma E.4. That point is therefore stationary for the original problem.

The revision adds two further results:

  • Theorem 4.7(ii) (in blue). See Q2.
  • Corollary D.23 (Appendix D, in blue). Under a fixed penalty and partial participation, the expected average lower-level gap stays O(1/c)O(1/c) at every iterate when each client starts from a lower-level solution.
AuthorsOpenReview ↗

Question 2 Response to Reviewer wdqc

Q2. The increasing-penalty guarantee requires full participation. Is it intrinsic to the method or a limitation of the current analysis?

No, it is not intrinsic to the method. The submission stated the increasing-penalty result in the setting where it gives the residual RkR_k at the actual iterate, which requires every client to take a projected step and on which the correspondence analysis of Appendix E builds. The rate itself does not need full participation. The partial-participation analysis of Theorem D.21 extends to the growing penalty with three local changes, and the revised Theorem 4.7 now covers partial participation in part (ii) (in blue; proof in Theorem D.24, in blue). For ck=c0(k+1)ρc_k=c_0(k+1)^\rho with ρ∈(0,1/2)\rho\in(0,1/2) and any participation rate p≥p0>pmin⁡(τ)p\ge p_0>p_{\min}(\tau),

min⁡0≤k≤K−1E[ck∥Gα(wk)∥]=O(p−1/2K−(1−2ρ)/2),\min_{0\le k\le K-1}\mathbb{E}\big[c_k\Vert G_\alpha(w^k)\Vert\big]=O\big(p^{-1/2}K^{-(1-2\rho)/2}\big),

the same exponent as under full participation, together with the O(K−ρ)O(K^{-\rho}) gap rate under the same boundedness hypothesis. The three changes are:

  1. Splitting an inactive client's merit increment at the new point, the penalty-variation part (1/ck+1−1/ck)(Fi−Fi‾)(1/c_{k+1}-1/c_k)(F_i-\underline{F_i}) is nonpositive and drops, and the rest gives the inner product at ckc_k, the same index as for active clients. The tracking targets θi⋆\theta_i^{\star} and λi⋆\lambda_i^{\star} do not depend on cc, so the drift bounds are unchanged.
  2. The server table stores normalized gradients dxi/ckd_{x_i}/c_k (Algorithm 1, line 12). At a given state, the penalty change alters a stored entry's reference gradient only by (1/ck′−1/ck)∇xFi(1/c_{k'}-1/c_k)\nabla_xF_i, on top of the drift and inexactness errors already controlled in the fixed-penalty analysis. In the staleness recursion this adds a summable term of order (1/ck−1/ck+1)2=O(k−2−2ρ)(1/c_k-1/c_{k+1})^2=O(k^{-2-2\rho}).
  3. As in Theorem 4.5, an inactive client's blocks are not produced by a projected step, so we report the gradient mapping ckGα(wk)c_kG_\alpha(w^k) of ψck\psi_{c_k} instead of the residual at wk+1w^{k+1}. Under full participation it controls the residual that part (i) reports.

The admissible step size may be smaller than with a fixed penalty, and the constants depend on p0p_0 and τ\tau.

Broader settings. We agree that stochastic gradients, compressed communication, nonconvex lower-level problems, and shared lower-level variables are valuable directions; the revised conclusion lists them as future work (in blue).

We hope this clarifies the contribution and we are happy to clarify anything further.

AuthorsOpenReview ↗

Follow-up on our response

Dear Reviewer ,

Thank you again for your review. As the discussion period closes on November 18, we wanted to check whether our response and the revised PDF address your questions. In brief, our response explains what the analysis adds beyond BiC-GAFFA and server-side gradient-table methods. The revised Theorem 4.7(ii) shows that the increasing-penalty result does not require full participation, and the revised conclusion lists the broader settings you raised as future work.

All changes are marked in blue. We would be glad to clarify anything further, and we would be grateful if you would consider updating your score in light of the revision.

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

FedBiC addresses personalized federated bilevel optimization in which clients share upper-level parameters but solve separate convex lower-level problems with client-specific inequality constraints. It builds on BiC-GAFFA’s regularized gap-function reformulation, penalizes departures from lower-level optimality, and combines local primal-dual tracking with a server-side gradient table that reuses updates from inactive clients. The resulting first-order algorithm supports partial client participation while retaining lower-level states locally.

The analysis establishes convergence to stationarity of the fixed-penalty objective under partial participation. With full participation and an increasing penalty, it provides a lower-level gap bound under an additional boundedness assumption and connects selected accumulation points to original bilevel stationarity under further regularity conditions. Experiments evaluate synthetic constrained sparse regression, fair personalized meta-learning on EMNIST, and binary CIFAR-10 learning under label noise.

9:55

Critical strengths

FedBiC handles client-specific inequality constraints under partial participation. The lower-level objectives need not be strongly convex. Its analysis accounts for outdated client states and stored gradients. This addresses a central challenge in federated constrained bilevel optimization.

The paper connects limits of its iterates to stationary points of the original bilevel problem. This result requires full participation and additional assumptions. It strengthens the theory beyond stationarity of the penalty objective alone.

Critical weaknesses

The guarantees under partial participation cover only stationarity of a fixed-penalty objective. The stronger results require full participation and a boundedness assumption that the analysis does not establish. The theory therefore leaves lower-level optimality unresolved under partial participation.

The experimental comparisons change several factors at once. Regression baselines use different constraints or personalization. Fairness baselines have no fairness mechanism. Steering baselines use clean validation data only for model selection, while FedBiC uses them for training. These differences prevent a clear assessment of the proposed optimizer’s advantage.

Questions for authors

What conditions ensure the bounded penalty objective required for the lower-level optimality guarantee? Is there evidence that this assumption holds in the experiments?

Which guarantees cover partial participation with an increasing penalty? Does the claimed participation speedup hold after accounting for the step size’s dependence on participation?

Could you provide comparisons with the same client-specific models and constraints, including a fairness-aware baseline? This would help separate the optimizer’s contribution from the formulation.

Do the steering gains remain when baselines can train on the same clean examples as FedBiC? Model selection should use a separate split.

3 comments
AuthorsOpenReview ↗

Weakness 1 , Q 1-2 Respone to Reviewer wkva

We thank the reviewer for the careful assessment and the precise questions. All changes in the revised PDF are marked in blue.

W1 and Q2. Partial participation with an increasing penalty, and the participation speedup.

The revised Theorem 4.7 covers partial participation in part (ii) (in blue, proof in Theorem D.24, in blue). For ck=c0(k+1)ρc_k=c_0(k+1)^{\rho} with ρ∈(0,1/2)\rho\in(0,1/2) and any participation rate p≥p0>pmin⁡(τ)p\ge p_0>p_{\min}(\tau),

min⁡0≤k≤K−1E[ck∥Gα(wk)∥]=O(p−1/2K−(1−2ρ)/2),\min_{0\le k\le K-1}\mathbb{E}\big[c_k\Vert G_\alpha(w^k)\Vert\big]=O\big(p^{-1/2}K^{-(1-2\rho)/2}\big),

which has the same exponent as under full participation, together with the lower-level gap rate Gγ,i(wiK)=O(K−ρ)G_{\gamma,i}(w_i^K)=O(K^{-\rho}) under the same boundedness hypothesis (see Q1). As in Theorem 4.5, we report the gradient mapping because an inactive client's blocks are not produced by a projected step. Under full participation it controls the residual RkR_k reported in part (i). The analysis extends to a growing penalty because the server table stores normalized gradients dxi/ckd_{x_i}/c_k. A change of penalty alters a stored entry's reference gradient only by (1/ck′−1/ck)∇xFi(1/c_{k'}-1/c_k)\nabla_xF_i, which adds a summable term to the staleness recursion. For a fixed penalty, Corollary D.23 (in blue) bounds the expected average lower-level gap by O(1/c)O(1/c) at every iterate under partial participation (see Q1). Lower-level optimality under partial participation is therefore covered for both penalty schedules, under the conditions discussed in Q1. Of the submission's results, only the correspondence with the original bilevel problem (Appendix E) is stated under full participation.

On the speedup: the step-size bounds of Theorems D.21 and D.24 depend on the problem constants, on τ\tau and on the participation floor p0p_0, but not on the realized rate p∈[p0,1]p\in[p_0,1]. For a fixed p0p_0, the same step size is therefore admissible for every pp in [p0,1][p_0,1], and the bound improves as 1/p1/\sqrt{p} across this range. This is the sense of the speedup, and Remark 4.6 now states it explicitly (in blue). The speedup does not extend to vanishing participation. Keeping p0>pmin⁡(τ)=max⁡j∈{1,2}4γjτ/(4γjτ+η)p_0>p_{\min}(\tau)=\max_{j\in\lbrace 1,2\rbrace}4\gamma_j\tau/(4\gamma_j\tau+\eta) as p0→0p_0\to0 requires τ→0\tau\to0, and the admissible step scales as O(τ)O(\tau).

Q1. Conditions for the bounded penalty objective, and evidence.

Since ψc(w)=1N∑i=1N[Fi(x,yi)+cGγ,i(wi)]\psi_c(w)=\frac{1}{N}\sum_{i=1}^N\big[F_i(x,y_i)+cG_{\gamma,i}(w_i)\big] and each FiF_i is continuous on the compact feasible set, the hypothesis ψck(wk)≤M\psi_{c_k}(w^k)\le M is equivalent to ckc_k times the average lower-level gap staying bounded, that is, to the gap decreasing at least as fast as 1/ck1/c_k.

Fixed penalty. Corollary D.23 (in blue) shows that if each client starts from a lower-level primal–dual solution at x0x^0 (one local convex solve), then for every kk,

E[1N∑i=1NGγ,i(wik)]≤1c⋅1N∑i=1N(Fi(x0,yi0)−Fi‾)+4αp0c2⋅1N∑i=1N∥∇xFi(x0,yi0)∥2.\mathbb{E}\Big[\frac{1}{N}\sum_{i=1}^N G_{\gamma,i}(w_i^k)\Big]\le \frac{1}{c}\cdot\frac{1}{N}\sum_{i=1}^N\big(F_i(x^0,y_i^0)-\underline{F_i}\big)+\frac{4\alpha}{p_0c^2}\cdot\frac{1}{N}\sum_{i=1}^N\big\Vert\nabla_xF_i(x^0,y_i^0)\big\Vert^2 .

Hence E[ψc(wk)]\mathbb{E}[\psi_c(w^k)] is bounded uniformly in kk under partial participation, with no further hypothesis.

Increasing penalty. Theorem D.24 also gives the gap rate in expectation under the weaker condition E[ψck(wk)]≤M\mathbb{E}[\psi_{c_k}(w^k)]\le M. For a growing penalty, the bound remains a condition on the trajectory, as stated in Theorem 4.7, and we verify it empirically.

Evidence. We monitored the condition in the LASSO experiment, which runs the increasing-penalty schedule of Theorem 4.7 (c0=1c_0=1, ρ=1/4\rho=1/4) and in which the auxiliary problems can be solved to convergence, so ψck(wk)\psi_{c_k}(w^k) is evaluated accurately (Appendix B.1, in blue). Over all five evaluation runs, logged every 100 rounds, ψck(wk)\psi_{c_k}(w^k) never exceeds its value after the first round (at most 0.830.83) and decreases to about 0.220.22 at K=2000K=2000, while ckc_k times the average gap decreases from 0.230.23 to below 0.010.01. The gap therefore decays faster than the 1/ck1/c_k rate the condition requires.

AuthorsOpenReview ↗

Weakness 2 and Question 3-4 Response to reviewer wkva

W2 and Q3. Comparisons with the same client-specific models and constraints.

LASSO. We reran the three federated baselines with per-client lower-level variables yiy_i ("pc": no averaging of yy, each client evaluated with its own yiy_i), with and without projecting every lower-level step onto the box ∣yi,j∣≤xj\vert y_{i,j}\vert\le x_j ("proj"), which imposes FedBiC's constraint. They use the same problem, the same nine-point grids, and the same tuning and evaluation seeds (Appendix B.1, in blue).

MethodΦ\Phi ↓Val MSE∥x∥1\Vert x\Vert_1
FedBiC (rerun)0.3156 ± 0.00810.2095 ± 0.00732.121
SimFBO-pc0.3507 ± 0.00920.2528 ± 0.00961.959
SimFBO-pc+proj0.3523 ± 0.00990.2541 ± 0.01131.964
FedBiOAcc-pc0.3745 ± 0.01200.2577 ± 0.01242.336
FedBiOAcc-pc+proj0.3745 ± 0.01200.2577 ± 0.01242.336
FedNest-pc0.4298 ± 0.00810.1005 ± 0.00886.585
FedNest-pc+proj0.4298 ± 0.00810.1005 ± 0.00886.585

FedBiC attains the lowest Φ\Phi on every evaluation seed against every matched baseline. The smallest paired gap, to SimFBO-pc+proj, is 0.037±0.0030.037\pm0.003. Projection changes the baselines' results only marginally, so imposing the constraint on their lower-level steps does not close the gap. As in Table 2, FedNest reaches a lower validation MSE by growing ∥x∥1\Vert x\Vert_1 to about three times FedBiC's.

Fairness. We added the penalty μpenmax⁡(0,∣ci⊤yi∣−ϵ0)2\mu_{\mathrm{pen}}\max(0,\vert c_i^\top y_i\vert-\epsilon_0)^2 to each baseline's client objective, so every baseline receives the same fairness information as FedBiC. For each baseline, μpen\mu_{\mathrm{pen}} is 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. Results are reported on the same five held-out seeds (Appendix B.2, Table 12, in blue).

MethodTest Acc ↑Test DP gap ↓
FedBiC0.7155 ± 0.01300.1134 ± 0.0239
SCAFFOLD + penalty0.6717 ± 0.01530.1036 ± 0.0504
FedAvg + penalty0.6663 ± 0.02330.0872 ± 0.0308
FedProx + penalty0.6843 ± 0.01490.1460 ± 0.0366
FedNest + penalty0.6539 ± 0.02070.1050 ± 0.0273

FedBiC is 3.1–6.2 points more accurate than every penalty-augmented baseline. 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. Across every penalty weight we evaluated (Table 13, in blue), no penalized configuration matches FedBiC on both accuracy and parity gap. Table 3 was also updated (in blue) with each client's fairness direction cic_i computed from its support and query data only (Appendix B.2, in blue).

Q4. Steering with the same clean examples.

The separation of the optimizer's contribution from the formulation that the reviewer asks for in W2 is provided by the matched LASSO comparison above. There the baselines use the same per-client models and, with projection, the same constraint and data, and FedBiC attains the lowest Φ\Phi on every evaluation seed. The steering experiment serves a different purpose: it shows what the constrained bilevel formulation makes possible in a learning task.

In FedBiC, the clean validation split is the upper-level objective. The shared tolerance cc is learned by minimizing validation loss, which is the role validation data play in bilevel hyperparameter optimization. The single-level baselines have no upper level, so the validation split serves as their model-selection set. The steering examples, the clean data available to them during training, enter their local loss through a tuned weight λ\lambda. As stated in Section 5.3, FedBiC's accuracy reflects its use of the clean validation data through its upper level, together with the steering constraint.

What the experiment demonstrates is constraint handling. FedBiC enforces a different clean-loss constraint on each client and learns the shared tolerance from data, whereas each baseline relies on a hand-tuned mixing weight λ\lambda. The learned tolerance settles at c⋆≈0.46c^{\star}\approx0.46 (IID) and c⋆≈0.43c^{\star}\approx0.43 (non-IID), with a mean residual violation of about 0.050.05 on the local steering sets (Appendix B.3). None of the baselines can enforce such per-client constraints. To make the role of each experiment explicit, Section 5.3 now states that the steering experiment demonstrates the constrained formulation, while Appendix B.1 isolates the optimizer under matched models and constraints (in blue).

We hope these additions address the reviewer's concerns. We are happy to clarify anything further.

AuthorsOpenReview ↗

Follow-up on our response

Dear Reviewer ,

Thank you again for your careful review. As the discussion period closes on November 18, we wanted to check whether our response and the revised PDF address your concerns. In brief, the revision:

  1. Extends Theorem 4.7 to partial participation with an increasing penalty and adds Corollary D.23 for the fixed penalty, so lower-level optimality is now covered under partial participation, and Remark 4.6 states the range over which the speedup holds,
  2. Reports, in Appendix B.1, that the boundedness condition holds along every LASSO run,
  3. Adds matched LASSO baselines with the same per-client models and constraint, where FedBiC attains the lowest objective on every seed, together with fairness-aware baselines,
  4. Clarifies in Section 5.3 the role of the steering experiment.

All changes are marked in blue. We would be glad to clarify anything further, and we would be grateful if you would consider updating your score in light of the revision.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.