- 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 convergence rate for the average expected squared outer-gradient norm, with 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 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.
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.