acceptodds
Withdrawn from ICLR 2027

Complexity Guarantees for Heterogeneous Federated Bilevel Optimization with Lower-Level Constraints

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Federated bilevel optimization (FBO) provides a framework for bilevel learning with decentralized data, yet existing methods largely focus on unconstrained lower-level problems and often rely on hypergradient computation. Lower-level constraints often induce nonsmoothness in the solution mapping, posing substantial challenges for standard implicit differentiation and hypergradient approaches. We propose an inexact zeroth-order framework for FBO that accommodates lower-level constraints and nonsmooth, nonconvex implicit upper-level objectives. To the best of our knowledge, this is the first zeroth-order method for constrained FBO that provides convergence and communication-complexity guarantees while accommodating client drift in both levels. Our contributions are threefold. (i) We design a SCAFFOLD-based zeroth-order scheme that uses control variates to correct client drift under heterogeneous data and partial client participation. To reduce repeated lower-level communication, we compute only two inexact lower-level solutions per outer round and reuse them across multiple local upper-level updates, while explicitly characterizing and controlling the resulting delay, bias, and lower-level inexactness. (ii) We propose Adaptive Penalty SCAFFOLD for constrained federated lower-level problems, using an increasing penalty parameter and round dependent local stepsizes, and establish convergence guarantees for the resulting inexact solutions. (iii) We extend the framework to constrained personalized FBO with client-specific lower-level problems and a general bilevel structure, allowing distinct upper- and lower-level objectives and client-specific constraints. Our numerical experiments on hyperparameter optimization and personalized federated learning demonstrate the performance of the proposed methods.

Primary area:
optimization
Keywords:
Federated bilevel optimization, zeroth-order optimization, constrained optimization, personalized federated learning, client drift, data heterogeneity

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_budnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The heterogeneous federated bilevel optimization with constrained LL problems and nonsmooth, nonconvex UL objectives is studied in this manuscript. There are two considered federated settings. One is GFBO where clients share a global LL solution. Another one is PFBO where each client has its own LL solution. The authors propose a unified zeroth-order framework, SCAFFOLD-RZO_bl to solve the problem. An adaptive penalty SCAFFOLD method is also developed for solving constrained LL problems. Theoretical results including convergence guarantees and communication complexity bounds are presented. Simulation results on CIFAR-10 hyperparameter optimization and MNIST personalized federated learning show improvements over selected baselines.

Critical strengths

The authors propose a unified zeroth-order framework for constrained federated bilevel optimization. Detailed theoretical results and simulation results are given. Overall, this paper is well written.

Critical weaknesses
  1. The comparisons with the existing federated bilevel optimization methods, e.g., some existing methods in Table 1, in terms of the complexity of computational, communication costs and convergence rate, are not given. Readers may care about these complexities and convergence performance. In simulation results, the computational costs, communication rounds, and running time compared with the existing methods are not provided either.
  2. Theorems 3.3 and 3.5 present convergence guarantees. However, the stationarity gap is not reported in the experiment section. Furthermore, in the experiments, do the parameters meet the requirements for convergence, and how should this be determined in practical applications? It is better to provide specific numerical calculations and discussions.
Questions for authors
  1. Please provide comparisons with existing federated bilevel optimization methods regarding computational complexity, communication costs, and convergence rate.
  2. Please provide simulation results on the computational costs, communication rounds, and running time compared with the existing methods.
  3. Are the assumptions too strict? Are these assumptions needed in this paper commonly used in federated bilevel optimization and zeroth-order optimization?
  4. Please provide results on the stationarity gap in the experiment section.
  5. Please provide specific numerical results on whether the parameters considered in the experiments meet the requirements for convergence.
  6. I am not sure the experiments of the proposed methods and the baseline are fair. Can the authors clarify this in detail?
  7. Can the proposed methods work in more complex problems? For example, deep neural networks. It would be better to add this experiment.
Reviewer_frccOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies federated bilevel optimization with constrained lower-level problems and heterogeneous client data. The authors propose a zeroth-order framework based on SCAFFOLD to address client drift and avoid hypergradient computation. They also develop an Adaptive Penalty SCAFFOLD method for solving constrained lower-level problems and extend the framework to personalized federated bilevel optimization. Convergence and communication-complexity guarantees are provided, along with experiments on CIFAR-10 and MNIST.

Critical strengths

I think the paper addresses an interesting problem. Handling lower-level constraints and client heterogeneity together is challenging, especially when the implicit upper-level objective can be nonsmooth. The theoretical analysis is quite detailed. I appreciate that the authors explicitly consider the errors introduced by delayed lower-level solutions, inexact computation, and client drift. The extension to personalized federated bilevel optimization is useful, and the experiments show promising results under heterogeneous data.

Critical weaknesses
  1. My main concern is the novelty of the proposed method. It seems to mainly combine existing techniques, including SCAFFOLD, zeroth-order optimization, and penalty methods. I would like to see a clearer explanation of what is fundamentally new compared with FedRZObl (Qiu et al., 2023).

  2. I find the experimental comparisons somewhat unfair. In Table 2, the proposed method directly optimizes the ramp loss and enforces hard constraints, while Ditto and pFedMe use different objectives and soft penalties. This makes it difficult to attribute the improvements to the proposed algorithm itself.

  3. I am not fully convinced by the communication-efficiency results. Figure 1 mainly reports outer communication rounds, but the additional communication required by the lower-level solver is not clearly reflected in the comparison.

  4. I think the ablation studies are insufficient. It would be helpful to see how much each component, such as SCAFFOLD correction, delayed reuse, and adaptive penalty, contributes to the overall performance.

Questions for authors
  1. Could the authors clarify the main novelty compared with FedRZObl (Qiu et al., 2023)? What are the key contributions beyond combining existing techniques?

  2. Could the authors explain how the comparison with Ditto and pFedMe in Table 2 is fair, given that the methods optimize different objectives and handle constraints differently?

  3. Could the authors provide a comparison based on total communication cost, including the lower-level solver, rather than only outer communication rounds?

  4. Could the authors include ablation studies to show the individual contributions of SCAFFOLD correction, delayed reuse, and adaptive penalty?

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

The paper combines randomized zeroth-order upper updates with SCAFFOLD control variates for global and personalized federated bilevel problems with lower-level constraints. It proposes an adaptive-penalty lower solver, analyzes reuse and approximation errors, and reports communication bounds and classification experiments.

Critical strengths
  1. The problem setting addresses an important limitation of smooth unconstrained hypergradient methods. The paper distinguishes a shared federated lower response from client-specific responses and gives concrete parameter-dependent constraint examples.
  2. The upper analysis does not simply assume that reused information stays unbiased. It separates bias from reusing a random direction, delay from reusing lower solutions, and lower-solver error, then tracks their interaction with local drift. This is a useful part of the proposed framework.
  3. The paper distinguishes upper communication from total communication, including the two lower solves per global outer round. The experiments report uncertainty and explicit feasibility measures, and openly state that the personalized baselines optimize different objectives (Figure 1 and Table 2).
Critical weaknesses
  1. The lower-solver guarantee is not established as stated (major correctness issue, potentially fixable). The proof retains the initial distance in Equation 104, but the stated bound in Theorem A.30 drops it and depends only on G-star and noise. My counterexample is one noiseless client with h(x,y)=(y−1)2/2h(x,y) = (y-1)^2/2 and no constraint: G-star is zero at the solution, but the algorithm starts at zero and does not solve the problem exactly after one small step, whereas the displayed bound is zero. Also, Algorithms 2-3 return the last iterate, while the proof bounds a weighted average. Restore initialization dependence and prove the bound for the actual returned point, or change the algorithm and downstream bounds.
  2. A stronger uniform client-gradient assumption enters the communication proof without appearing in the main theorem (major but fixable). Assumption 2.2 bounds the gradient of the averaged lower objective at its constrained solution, while Lemma A.32 additionally bounds the average squared client gradients uniformly over x; Theorem 3.3 invokes that lemma without this extra condition. These are not equivalent: my example h1(x,y)=y2/2+xyh_1(x,y) = y^2/2 + xy and h2(x,y)=y2/2−xyh_2(x,y) = y^2/2 - xy has zero average gradient at y(x) = 0 but client gradients of magnitude |x|. State the needed condition explicitly or derive a bound along the iterates, and qualify the claimed absence of heterogeneity dependence.
  3. The hyperparameter experiment is not covered by the uniform curvature assumptions as written (major but fixable theory-to-experiment gap). Equation 1 allows unrestricted regularization parameters and uses softplus coefficients, which can approach zero or grow without bound. Thus, pointwise strong convexity does not supply the uniform positive curvature and smoothness constants required in Assumption 2.1. Lemma A.13 verifies a different gradient bound, not these constants. Specify bounded parameter domains or another parameterization, then verify the assumptions for that implemented problem.
  4. The experiments do not isolate the claimed communication and optimization benefits (fixable). Figure 1 labels communication rounds without giving a clear upper-plus-lower cost breakdown or full CIFAR-10 binary-task settings. Table 2 compares direct ramp-loss optimization with methods using different objectives and soft rather than hard constraints, so its loss and feasibility gains do not isolate the optimizer's contribution. Add same-objective, same-constraint controls, drift/reuse ablations, total communication and time, and a clear separation of training, validation, and held-out test data.
Questions for authors

Please refer to the weaknesses.

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

Related papers

Discussion (0)

Sign in to comment.