acceptodds
Desk rejected at ICLR 2027

Decentralized Zeroth-Order Gradient Tracking For Bilevel Optimization

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

In many learning and decision-making problems, the quality of a decision depends on the outcome of an underlying optimization process. For example, selecting a model's regularization strength requires training the model under that choice and assessing its performance on validation data. Model training and hyperparameter selection therefore form two nested optimization problems. When organizations jointly train a shared model while keeping data local and operating without a central coordinator, both problems must be solved through neighbor communication, motivating decentralized bilevel optimization. Such coordination becomes more difficult when participating systems expose only loss values or have insufficient memory for differentiation. These constraints motivate a zeroth-order approach that uses function evaluations at both levels. The challenge extends beyond estimating local gradients: agents must recover how the jointly trained model responds to hyperparameter changes from noisy local evaluations, despite incomplete training and disagreement across the network. To recover this response without derivatives, we propose Decentralized Zeroth-Order Bilevel Optimization (DZBO), which optimizes both levels through stochastic function evaluations and communication between neighbors. For a possibly nonconvex outer objective and uniformly strongly convex local lower-level objectives, DZBO achieves an rate for the average expected squared gradient norm at network-averaged iterates after outer updates. Attaining accuracy requires function-value queries per agent and communication rounds, including all inner and auxiliary work, for fixed problem and network parameters. Experiments illustrate the feasibility of our proposed algorithm under heterogeneous data.

Primary area:
optimization
Keywords:
Zeroth-order optimization, bilevel optimization

Reviews

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

This paper studies decentralized stochastic bilevel optimization with a shared lower-level solution, where agents have access only to function evaluations and communicate through neighboring nodes. The authors propose DZBO, which combines zeroth-order lower-level optimization, sensitivity estimation via stochastic residual tracking, and decentralized outer updates. Three JHIP estimation variants are developed, including matrix, vector, and direct-product formulations. Under strong convexity and smoothness assumptions, the paper establishes an O(K−1/2)O(K^{-1/2}) convergence rate for the average expected squared outer-gradient norm, with O(ϵ−3)O(\epsilon^{-3}) function-query and communication complexity. Experiments on synthetic hyperparameter optimization and data hyper-cleaning using MNIST and CIFAR-100 evaluate the method against the derivative-based MA-DSBO baseline.

Critical strengths

The paper addresses a meaningful decentralized bilevel optimization problem with function-value-only access at both levels and neighbor-only communication, extending existing approaches to a challenging combination of constraints.

The theoretical analysis systematically accounts for zeroth-order estimation errors, lower-level approximation, sensitivity tracking, and network disagreement, providing convergence guarantees with explicit query and communication complexity.

Critical weaknesses

The methodological novelty is limited relative to existing decentralized sensitivity tracking (Chen et al., 2023) and zeroth-order bilevel estimation (Aghasi and Ghadimi, 2025). More importantly, the JHIP estimators exhibit substantial dimension-dependent variance even on well-conditioned quadratic problems, while the claimed complexity bounds do not adequately characterize the resulting accuracy–resource trade-off.

The experimental validation does not directly establish the accuracy or practical efficiency of the proposed sensitivity estimation mechanism. In particular, the CIFAR-100 experiments use a matrix JHIP formulation with (O(pq)) auxiliary storage and communication, without sufficient implementation details or comparisons against the more efficient vector and direct formulations.

Questions for authors

Can the authors quantify the actual JHIP estimation error and compare the full, vector, and direct formulations under matched function-query and communication budgets?

What are the actual problem dimensions, auxiliary iteration counts, and memory/communication costs in the CIFAR-100 experiments? How is the reference outer-gradient estimate in Figure 1 computed?

In Lemma A.4, how is the Frobenius-norm bias bound in Eq. (16) justified under the spectral-norm Lipschitz assumption in Section 3, without an additional dimension-dependent factor?

2 comments

Thank you for the feedback. We address the technical contribution, the accuracy–resource trade-off, and the experimental implementation below.

1. Technical contribution and dimension dependence.

The additional proof difficulty arises because zeroth-order smoothing introduces a bias that depends on the auxiliary iterate inside decentralized residual tracking. In the derivative-based HIGP analysis of Chen et al. (2023, Section 3.5.2), conditional expectations recover a deterministic tracking recursion. With zeroth-order residuals, bounding the additional bias requires controlling an iterate whose evolution is itself driven by the biased tracker. Appendix A.5 resolves this dependence through coupled second-moment and disagreement bounds, establishing stability before deriving the averaged-output error.

Our analysis also explicitly characterizes the dimension dependence of the estimators. For deterministic quadratics, the direct products satisfy

\mathbb{E}\lVert\mathcal{H}(v)-Hv\rVert^2&=(q+1)\lVert Hv\rVert^2, \\\\ \mathbb{E}\lVert\mathcal{J}(v)-Jv\rVert^2&=(p+1)\lVert Jv\rVert^2. \end{aligned}$$ For randomized matrix actions with $H=\kappa I_{q}$, the Hessian-action variance is $\frac{1}{2}(q^2+7q+8)\lVert Hv\rVert^2$. Whereas these expressions describe individual single-step estimates, our auxiliary recursion suppresses the variance at rate $O(N^{-1})$ for the averaged auxiliary solution, yielding the $O(\epsilon^{-3})$ complexity with dimensions fixed. **2. JHIP error and resource comparisons.** Analytically, the common target of all three formulations at fixed query states is $s^{\ast}=JH^{-1}b$, and the mean auxiliary residual directly controls the product error through $$\lVert Jv-s^{\ast}\rVert\leq\frac{\lVert J\rVert_{2}}{\lambda_{g}}\lVert Hv-b\rVert.$$ Comparing the resource budgets across formulations highlights their complementary strengths. For the theoretical algorithms, full matrix uses $4K=O(\epsilon^{-2})$ upper queries and $K(2T+8N)=O(\epsilon^{-3})$ lower queries, while vector/direct use $K(2N+2)=O(\epsilon^{-3})$ upper queries and $K(2T+4N)=O(\epsilon^{-3})$ lower queries. Meanwhile, each auxiliary exchange carries $2pq$ scalars for full matrix and is reduced to $2q$ scalars for vector/direct, with the direct path further reducing the single-step directional variance from $O(q^2)$ to $O(q)$. We will include this resource comparison in Section 4. **3. CIFAR-100 settings and costs.** The CIFAR-100 configuration uses 16 agents on a ring, 8,000 training examples, and a linear softmax classifier on frozen 512-dimensional ResNet-18 features. The resulting dimensions are $p=8{,}000$ and $q=512\times100=51{,}200$, with $T=20$ lower-level steps and $N=10$ auxiliary steps per outer update. In our CIFAR-100 implementation (`szo_jhip_ihvp`), the auxiliary state $Z$ is allocated with $q$ entries per node and paired with a randomized cross-Jacobian action. Its auxiliary states are therefore vectors, corresponding to the vector JHIP formulation and explaining its low storage and communication costs. Specifically, the vector and its tracker occupy $2q$ float32 entries, or 409,600 bytes (approximately 0.391 MiB) per node. Including the lower-level and outer exchanges gives a payload per directed edge per outer update of $$qT+2qN+p=2{,}056{,}000$$ scalars, equivalent to 8.224 MB in float32, spread over $T+N+1=31$ logical exchanges when the auxiliary state and tracker are packed together. We will clarify this vector implementation and report these figures in Section 5. **4. The stationarity metric in Figure 1.** Figure 1 is computed from each method's hypergradient estimates. Specifically, the plotting code records \$ \\log\_{10}\\left\\lVert\\frac{1}{n}\\sum\_{i=1}^{n}\\widehat{h}\_{i,k}\\right\\rVert, \$ where the estimates are evaluated at the agents' local iterates, serving as a direct stationarity proxy to monitor outer-loop convergence. We will clarify this definition in the caption of Figure 1. **5. The Frobenius bound in Eq. (16).** We agree that the stated spectral-norm Lipschitz assumptions introduce rank factors when deriving Frobenius bounds. Applying $\lVert A\rVert_{F}^2\leq\operatorname{rank}(A)\lVert A\rVert_{2}^2$ gives: $$\begin{aligned} \lVert H_{\mu}^{\mathrm{sm}}-H\rVert_{F}^2&\leq2L_{H}^2q^2\mu^2, \\\\ \lVert J_{\eta,\mu}^{\mathrm{sm}}-J\rVert_{F}^2 &\leq rL_{J}^2(p\eta^2+q\mu^2), \end{aligned}$$ with $r=\min(p,q)$. The original right-hand sides apply directly to the spectral norms used in the vector and direct analyses. For the matrix path, the additional factors enter the bias and perturbation constants while preserving the convergence exponents in $N$, $K$, and $\epsilon$ for fixed dimensions.

Thank you for the detailed response. I acknowledge that the analysis of iterate-dependent smoothing bias clarifies the technical contribution beyond existing decentralized residual-tracking methods. The clarification of the vector JHIP implementation in CIFAR-100 also resolves my previous concern regarding auxiliary storage, and the proposed correction to Lemma A.4 appears reasonable.

However, my main concern regarding the empirical validation remains. Although the authors provide analytical variance bounds and resource comparisons, the response does not sufficiently clarify the actual accuracy of the JHIP estimates under the experimental budgets. More importantly, Figure 1 uses each method's own stochastic hypergradient estimates rather than an independent evaluation of the true outer gradient. Since these estimates contain method-dependent variance, their norms do not directly reflect the true stationarity of the outer objective, particularly when comparing different problem dimensions.

While I appreciate the authors' clarifications, the evidence supporting the practical effectiveness of the proposed sensitivity-estimation mechanism remains insufficient. Therefore, I maintain my original rating.

Reviewer_zxwQOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper introduces DZBO for decentralized bilevel optimization using only function values and communication between neighbors. It combines zeroth-order estimates with sensitivity tracking and gives an O(K−1/2)O(K^{-1/2}) convergence bound on the average expected squared gradient norm. Tests on synthetic problems and data hyper-cleaning show that the method can make progress under these access constraints.

Critical strengths
  1. Decentralized bilevel optimization with only function-value access is a practical problem worth studying. The paper proposes a fully zeroth-order method for this setting.

  2. The related-work discussion clearly explains where the method fits, including how its derivative access and communication requirements differ from those of existing approaches.

Critical weaknesses
  1. The paper is hard to follow. It introduces many symbols without clearly explaining how the three algorithmic variants relate, and several statements are repetitive. The proof of Eq. (16) also seems to be missing a rank-dependent factor when moving from spectral-norm Lipschitz bounds to Frobenius-norm bounds.

  2. The experiments show that the method works, but no clear convergence advantage over MA-DSBO. The performance gap grows with dimension in Figure 1 and needs more explanation. The computational and memory benefits used to motivate the method are not directly measured.

Questions for authors
  1. What makes combining these existing techniques technically challenging? Which parts of the method or proof need new ideas?

  2. Why does the gap between DZBO and MA-DSBO grow with dimension in Figure 1? Could you add experiments measuring computation time and memory use to assess the method's practical benefits?

2 comments

Thank you for your comments. We address the relationship among the variants, the rank factor in Eq. (16), and the experimental results below.

1. Relationship among the variants and the additional technical difficulty.

The three variants approximate the same implicit-gradient quantity JH−1bJH^{-1}b through different auxiliary computations. Full matrix solves HZ=J⊤HZ=J^\top and forms Z⊤bZ^\top b, while vector and direct solve Hv=bHv=b and estimate JvJv. The latter two differ in whether they use randomized matrix actions or direct product estimators.

Combining zeroth-order estimation with decentralized tracking introduces an additional analytical difficulty: the smoothing bias depends on the auxiliary iterate generated by the tracker. In Chen et al. (2023, Section 3.5.2), taking conditional expectations recovers a deterministic tracking recursion for the original linear system. With zeroth-order residuals, this recursion contains an additional bias satisfying $ \lVert\mathfrak{b}_{N}(U)\rVert^2\leq s_{N}^2(K_{0}+K_{1}\lVert U\rVert^2). $ Controlling this bias therefore requires controlling the auxiliary iterate, whose evolution is itself affected by the bias. Appendix A.5 resolves this dependence by jointly bounding the auxiliary-state error and the disagreement in the states and trackers. This establishes bounded second moments before time-averaging and leads to the O(N−1)O(N^{-1}) auxiliary error. We will highlight this proof structure in Section 3 to make the relationship among the variants and the analysis easier to follow.

2. The rank factor in Eq. (16).

We agree that converting the spectral bounds to Frobenius bounds introduces rank factors through ∥A∥F2≤rank⁡(A)∥A∥22\lVert A\rVert_{F}^2\leq\operatorname{rank}(A)\lVert A\rVert_{2}^2. With r=min⁡(p,q)r=\min(p,q), the resulting bounds are

\lVert H_{\mu}^{\mathrm{sm}}-H\rVert_{F}^2&\leq2L_{H}^2q^2\mu^2, \\\\ \lVert J_{\eta,\mu}^{\mathrm{sm}}-J\rVert_{F}^2 &\leq rL_{J}^2(p\eta^2+q\mu^2). \end{aligned}$$ The original right-hand sides apply directly to the spectral norms used in the vector and direct analyses. For Frobenius norms in the matrix path, the additional factors propagate into the bias and perturbation constants. With $p,q$ fixed, this changes the dimension-dependent constants and horizon conditions while preserving the convergence exponents in $N$, $K$, and $\epsilon$. **3. The dimension-dependent gap in Figure 1.** The widening gap across dimensions in Figure 1 is explained by the growth of directional sampling noise with dimension. Even for a deterministic quadratic with $H=\kappa I_{q}$, Appendix B.2 gives $$\mathbb{E}\lVert\widehat{H}v-Hv\rVert^2 =\frac{q^2+7q+8}{2}\lVert Hv\rVert^2,$$ whereas the direct estimator has variance $(q+1)\lVert Hv\rVert^2$. Thus, with fixed auxiliary iterations and direction counts, the estimation noise grows with dimension even when the condition number is one, whereas the derivative-based MA-DSBO baseline has access to exact first- and second-order derivatives and avoids this directional sampling noise. This theoretical scaling is consistent with the observed trend in Figure 1, which records the norm of each method's averaged update estimate as a stationarity proxy to demonstrate consistent optimization progress under function-value-only access. **4. Runtime and memory.** We conducted additional experiments to evaluate computation time and memory usage to assess DZBO's practical efficiency. For runtime, DZBO requires approximately 1.824\$\times\$ the computation time of MA-DSBO for the same number of iterations, while maintaining consistent optimization progress using only function values. For memory, the additional CIFAR-100 experiments show that DZBO reduces workspace memory for local Hessian-vector and cross-Jacobian-vector products by $11.173\\%$ relative to MA-DSBO (Chen et al., 2023). DZBO computes these products from function values with gradient recording disabled, avoiding the backward graphs and intermediate tensors retained for backpropagation by the derivative-based implementation. We will include these additional results in the manuscript to improve our paper.

Thank you for the theoretical correction, clarifications, and additional experiments. I maintain my original rating.

Reviewer_CWyQOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper develops zeroth-order bilevel optimization methods for learning over decentralized networks. Specifically, the paper develops Decentralized Zeroth-Order Bilevel Optimization (DZBO) utilizing function evaluations at both the upper and lower levels and neighbourhood communication over a graph to achieve O(ϵ−3)\mathcal{O}(\epsilon^{-3}) communication and computation complexity to reach a stationary point of the bilevel objective. Experiments have been conducted to show the feasibility of the proposed algorithm.

Critical strengths

The paper considers an important problem of zeroth-order bilevel optimization over decentralized communication networks. The paper presents multiple ways to approximate the hypergradient of the outer objective and presents unified convergence guarantees for the proposed DZBO method. Finally, experiments show that feasibility of the proposed approach.

Critical weaknesses

I believe the paper has some fundamental flaws that the authors need to address. Here are the major issues.

  • The paper presents both a matrix-based and a vector-based estimator to estimate the Hessian (inverse) Jacobian and Hessian-vector products. In my understanding, both of these analyses cannot be conducted under the same set of assumptions. For example, the matrix path approach requires strong convexity among other assumptions for the stochastic objectives (see [R1]), while the analysis for the vector path estimate does not require these assumptions for the stochastic objectives. While the assumption of strong convexity (and other assumptions) on stochastic objectives can be removed, it comes at the cost of adding dimension dependence on the stochastic variance of the hypergradient estimator (see [R2]).

    • [R1] Approximation Methods for Bilevel Programming (see discussion after Assumption 3)
    • [R2] A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic

    The paper completely misses this point and attempts to present a unified analysis, which I believe is flawed.

  • Another major issue with the paper is that, first, it requires strong convexity of the local lower-level objectives (3.2); on the other hand, it requires the gradient of the stochastic objectives (in the mean-squared sense) to be bounded (3.4). Both assumptions are contradictory; one can easily check that for even quadratic objectives, Assumption 3.4 cannot hold.

  • The detailed discussion on dimension dependence from the analysis is missing. The analysis should capture the effect of both LL and UL dimensions on the convergence behavior of the algorithm.

  • The comparison presented in Table 1 is uninformative since the computational/communication complexity and the number of iterations are different for the presented algorithms. One naturally cares about the computational/communication complexity rather than the number of iterations.

  • The paper should discuss the upper and lower complexities separately, similar to ZDSBA (Aghasi & Ghadimi, 2025). Stating the complexity as O(ϵ−3)\mathcal{O}(\epsilon^{-3}) hides many important details that should be presented in the main result.

  • The writing of the paper can be improved. The paper uses terms that are not standard in bilevel optimization without defining them. For example, the paper uses the terms global sensitivity of bilevel optimization and sensitivity tracking, which are not defined in the paper.

  • The paper motivates the zeroth-order methods using LLM applications but then presents the results on typical hyperparameter optimization/cleaning problems, which is a bit underwhelming.

Questions for authors

I believe that to significantly improve the paper, the authors need to address all the weaknesses above except the last one since it may be time consuming.

1 comment

Thank you for your review. We address your concerns about the assumptions, dimension dependence, and resource costs below.

1. Matrix/vector analysis and [R1]–[R2].

The distinction you raise between sample-wise and expected curvature is relevant. [R1] imposes sample-wise lower-level curvature conditions, whereas [R2] retains strong convexity of the expected lower objective and controls random matrix products through mean contraction and second moments, with a dimension factor appearing in Lemma 12. Thus, [R2] still guarantees a unique minimizer of the expected lower-level problem without requiring sample-wise strong convexity.

Our analysis similarly separates the contraction properties of the mean operator from the variance bounds on its stochastic estimators. At fixed local query states, the matrix and vector recursions solve HZ=J⊤HZ=J^\top and Hv=bHv=b, respectively, where H,J,bH,J,b are the network-averaged derivative blocks. Assumption 3.2 gives H⪰λgIH\succeq\lambda_{g} I, which also implies $\langle Z,HZ\rangle_{F}\geq\lambda_{g}\lVert Z\rVert_{F}^2. $ This mean-operator positivity provides the contraction used in Appendix A.5, while the stochastic perturbations are controlled through

\lVert\mathfrak{b}_{N}(U)\rVert^2&\leq s_{N}^2(K_{0}+K_{1}\lVert U\rVert^2), \\\\ \mathbb{E}[\lVert\zeta_{t}\rVert^2\mid\mathcal{F}_{t}]&\leq K_{2}+K_{3}\lVert U_{t}\rVert^2. \end{aligned}$$ Together with $s_{N}^2=O(N^{-1})$ and $\gamma_{N}=c_{\gamma}/\sqrt{N}$, these bounds establish iterate stability and an $O(N^{-1})$ error for the averaged output without requiring sample-wise positive definiteness. The unified analysis therefore refers to this shared stability argument for the auxiliary recursion, while the matrix and vector oracle bounds are established separately and retain their respective dimension factors. **2. Strong convexity and Assumption 3.4.** We agree that globally bounded lower-gradient second moments conflict with strong convexity on unbounded domains. Assumption 3.4 instead bounds upper-gradient moments globally and lower-gradient moments only at the aggregate lower solution: $$\max_{i}~\mathbb{E}\left[ \left\lVert \nabla_{y} G_{i}(x_{i}, y_{\mathbf{X}}^{\ast}; \xi_{i}) \right\rVert^{2} \right] \leq M_{g,\ast}^{2}.$$ The lower gradient can therefore grow away from the solution without violating this condition. For example, $G(y;\xi)=\lambda\lVert y-a\rVert^2/2+\xi^\top y$, with $\lambda > 0$ and centered finite-variance $\xi$, has a strongly convex mean and a finite gradient second moment at $y^{\ast}=a$. The solution-point moment bound is a compatible regularity condition at the optimum, and we will highlight this distinction after Assumption 3.4. **3. Dependence on the upper and lower dimensions.** Both dimensions enter the estimator bounds explicitly. Writing $p=\dim(x)$ and $q=\dim(y)$, Appendix A.2 gives $$\begin{aligned} V_{H}&=M_{H}^2[q(q+2)]^2, \\\\ V_{J}&=M_{J}^2p(p+2)q(q+2). \end{aligned}$$ The randomized Hessian and cross-Jacobian actions have second-moment bounds larger than direct products by factors of $(q+2)$, affecting convergence constants and admissible auxiliary horizons. Converting the spectral bias bounds in Eq. (16) to squared Frobenius bounds further introduces rank factors $q$ and $\min(p,q)$, respectively. These dimension-dependent factors affect constants and horizon conditions but preserve the convergence exponents in $N$, $K$, and $\epsilon$. We will clarify them in the main text. **4. Separate query and communication complexities.** To compare resource costs beyond iteration counts, the per-node query counts and communication payloads are summarized below: | Variant | Upper queries $Q_{F}$ | Lower queries $Q_{G}$ | Scalar payload per directed edge | |---|---:|---:|---:| | Full matrix | $4K$ | $K(2T+8N)$ | $K(qT+2pqN+p)$ | | Vector/direct | $K(2N+2)$ | $K(2T+4N)$ | $K(qT+2qN+p)$ | Both use $K(T+N+1)$ communication rounds. Substituting $K=O(\epsilon^{-2})$ and $T,N=O(\epsilon^{-1})$ for the criterion $\mathbb{E}\lVert\nabla\Phi\rVert^2\leq\epsilon$ gives $Q_{F}=O(\epsilon^{-2})$ and $Q_{G}=O(\epsilon^{-3})$ for full matrix, while both query counts are $O(\epsilon^{-3})$ for vector/direct, with dimensions fixed. The auxiliary storage and local residual arithmetic scale as $O(pq)$ for full matrix and are reduced to $O(q)$ for vector/direct. We will include this detailed breakdown in Table 1 and Section 4. **5. Terminology and motivation.** Thank you for the valuable feedback. We will improve clarity and provide explicit definitions of non-standard terms. Regarding the application motivation, the LLM discussion illustrates practical scenarios where only function-value evaluations are accessible, while our experiments demonstrate the effectiveness of the proposed framework on decentralized hyperparameter optimization and data hyper-cleaning tasks.

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

Related papers

Discussion (0)

Sign in to comment.