Problem-Parameter-Free Decentralized Bilevel Optimization

We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.

Reply to Weaknesses:

1. Thank you for the helpful comment. In our work, problem-parameter-free refers to the fact that our algorithm achieves a convergence rate of ${\mathcal{O}}(\log^4 T/T)$ without requiring any constraints or tuning on the stepsizes for the optimization variables $x$, $y$, and $v$. This is made possible through two key algorithmic innovations:

• Hierarchical Adaptive Stepsize Design: We introduce a principled stepsize structure that automatically balances updates across the three optimization levels. Specifically, the stepsize for updating $v$ depends on the gradient magnitudes of both $v$ and $y$, while the update for $x$ is more conservatively adjusted based on the accumulated gradients of $x$, $y$, and $v$. This hierarchical design ensures that $x$ and $v$ progress more slowly than $y$, preserving the stability and fidelity of the bilevel dynamics—without needing problem-specific hyperparameter tuning.

• Stepsize Tracking Mechanism: Decentralized bilevel optimization naturally leads to coupled, agent-specific adaptive stepsizes, which can become inconsistent and degrade convergence in heterogeneous networks. To address this, we incorporate a stepsize tracking mechanism in which agents exchange lightweight scalar gradient accumulators. This ensures that the stepsizes for $x$, $y$, and $v$ remain globally consistent, even in the presence of heterogeneity.

Together, these components enable us to develop the first problem-parameter-free algorithm for decentralized bilevel optimization that achieves optimal convergence without any reliance on problem-specific constants or manual tuning.

2. Thank you for the thoughtful comment. We respectfully clarify that we have already conducted a detailed numerical study to verify the problem-parameter-free nature of our algorithm, as presented in Figure 2 of the paper.

In this experiment, we compare the test accuracy of our proposed AdaSDBO algorithm against several baseline methods across a wide range of stepsize values (from $10^{-3}$ to $10^{2}$). The results clearly show that:

• AdaSDBO maintains stable and competitive performance across the entire range of tested stepsizes.

• In contrast, baseline algorithms exhibit much narrower windows of stability and performance, indicating a strong sensitivity to stepsize selection.

These findings highlight the robustness of AdaSDBO with respect to stepsize choices and directly support its problem-parameter-free design. Unlike existing methods that require careful tuning for each optimization variable, our approach consistently performs well without manual adjustment—further demonstrating its practical effectiveness.

Reply to Questions:

1. Thank you for your question. While our method introduces three adaptive stepsizes—one for each of the variables $x$, $y$, and $v$—we respectfully clarify that no tuning is required for these hyperparameters due to our hierarchical adaptive stepsize design. In simple terms, all three stepsizes can be initialized with the same value, and the algorithm will automatically adjust them throughout training:

• The stepsize for updating $v$ is adaptively adjusted based on the maximum of the gradient accumulators from both $v$ and $y$, ensuring that $v$ does not progress faster than $y$.

• The stepsize for updating $x$ is made even more conservative by incorporating the accumulators of $x$, $y$, and $v$, so that $x$ progresses slower than both $v$ and $y$, preserving the hierarchical update structure.

With this adaptive mechanism, our method is highly insensitive to the choice of the initial stepsize. This stands in contrast to existing decentralized bilevel algorithms that often require precise tuning to prevent instability or poor performance.

2. Thank you for your insightful question. We agree that Step 6 involves synchronization of adaptive stepsizes across agents. However, this synchronization is highly efficient, as it only requires exchanging a few scalar values that track local gradient information for stepsize adjustment. Compared to the communication cost of transmitting full model parameters such as the primal variable $x$, dual variable $y$, and auxiliary variable $v$—which are typically high-dimensional—the added overhead from sharing scalar accumulators is negligible.

Therefore, although our method includes an additional coordination step, it remains communication-efficient in practice. Moreover, this lightweight tracking mechanism ensures global consistency of stepsizes across agents, which is essential for achieving stable and problem-parameter-free convergence in decentralized bilevel optimization.

3. Thank you for your valuable question. We respectfully clarify that while the final convergence rate of any optimization algorithm inherently depends on problem-specific properties (e.g., smoothness, convexity, curvature), our key contribution lies in the fact that our stepsize strategy does not rely on these parameters.

In our two-stage convergence analysis, we impose no constraints on the choice of stepsizes. The stepsize scheme employed in our method is inherently adaptive and optimal, allowing us to achieve the ${\mathcal{O}}(\log^4 T/T)$ convergence rate without requiring any knowledge of smoothness and strong convexity constants, the spectral gap of the graph adjacency matrix, or other problem-dependent parameters.

This stands in sharp contrast to problem-parameter-dependent methods, whose optimal convergence guarantees rely on carefully setting stepsizes based on such parameters. If these conditions are violated, those methods can no longer ensure optimal convergence.

In summary, while the convergence rate ultimately reflects the nature of the problem, our algorithm ensures that no hyperparameter tuning is needed based on problem parameters to attain this optimal performance.

4. Thank you for your thoughtful question. Due to limited computational resources, we have done our best to evaluate the scalability of our algorithm on larger decentralized networks within a feasible range. Specifically, we conducted experiments on the decentralized meta-learning task with CIFAR-10 dataset using wider network sizes. The results are summarized below:

Table 1: Convergence Performance under Different Number of Agents with Decentralized Meta-Learning Task

These results demonstrate that AdaSDBO maintains consistently superior performance over baselines even as the number of agents increases. While this setup may not fully represent large-scale real-world systems with hundreds or thousands of nodes, such experimental scales are commonly adopted in the decentralized optimization literature [1]–[3] due to similar resource constraints. Moreover, AdaSDBO is inherently scalable due to its:

• Problem-parameter-free design, which eliminates the need for manual hyperparameter adjustment across agents.

• Single-loop architecture, avoiding costly nested optimization common in bilevel methods.

These properties suggest that AdaSDBO is well-suited for scaling to larger networks.

Reply to Limitations:

Thank you for your constructive comment. We discuss the limitations of our method as follows:

• Communication Overhead: Our framework requires the exchange of scalar gradient norms as accumulators, which incurs minimal overhead compared to transmitting high-dimensional variables. While more aggressive communication-saving techniques (e.g., quantized or partially shared accumulators) could further reduce cost, they risk losing the global coordination necessary for stable convergence. We consider this an interesting direction for future exploration.

• Memory Cost: Adaptive methods like ours introduce a small additional cost for maintaining gradient accumulators. However, this cost is negligible compared to full gradient evaluations. Nonetheless, reducing memory usage remains a valuable direction for improving overall efficiency.

• Applicability to Real-World Tasks: While our method is theoretically grounded in the nonconvex–strongly-convex setting, many real-world tasks involve fully nonconvex landscapes. Extending the framework to such general settings poses additional challenges (e.g., non-uniqueness, non-differentiability [6]) and represents an important open problem in decentralized bilevel optimization.

We have incorporated this discussion into our paper and are enthusiastic about exploring these directions in future work.

References:

[1] A Single-Loop Algorithm for Decentralized Bilevel Optimization.

[2] Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic Update and Transient Iteration Complexity.

[3] Decentralized Bilevel Optimization.

[4] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.

[5] Fully First-Order Methods for Decentralized Bilevel Optimization.

[6] On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis.

Thank you once again for your thoughtful review and constructive feedback.

Dear Reviewer Y6eW,

Thank you very much for your reply and for recognizing our contributions. We are delighted that your concerns have been resolved. We sincerely appreciate your thoughtful review and constructive feedback.

Sincerely,

Authors of the paper

We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.

Reply to Weaknesses:

1. Thank you for your helpful suggestion. To further validate the effectiveness of our proposed method on more complex datasets, we have added new experiments on the CIFAR-100 dataset using ResNet-18 model with varying numbers of agents. The results are summarized below:

Table 1: Convergence Performance on the CIFAR-100 Dataset with Varying Numbers of Agents

Moreover, we have made every effort to further validate the robustness of our method by adding experiments on the MNIST, FashionMNIST, and CIFAR-10 datasets, as shown below:

• Added more experiments on MNIST and FashionMNIST by varying the network topology, with the corresponding structural specifications described in the Appendix of [1], as shown in the following table.

Table 2: Convergence Performance under Different Topologies ($n=8$)

• Added new experiments on CIFAR-10 by varying the number of agents in the decentralized meta-learning setup, as presented in the table below.

Table 3: Convergence Performance under Different Number of Agents with Decentralized Meta-Learning Task

These additional results further confirm the robustness and superior performance of our proposed AdaSDBO method across diverse settings.

2. Thank you for your insightful comment. Through a consolidation of our theoretical analysis, we can get that the communication complexity of AdaSDBO is $\mathcal{O}\left(\frac{1}{\epsilon(1 - \rho_W)^2} \log^4\left(\frac{1}{\epsilon}\right)\right)$, which matches the results of existing methods such as [2]–[4], up to logarithmic factors. Since logarithmic terms grow significantly slower than polynomial ones, they are typically considered negligible in the context of optimization theory (e.g., [1], [5]–[6]).

In sharp contrast to [2]–[4], AdaSDBO is entirely problem-parameter-free, requiring no knowledge of problem-specific constants or manual hyperparameter tuning. This makes it significantly easier to deploy and more robust in heterogeneous, real-world decentralized systems. Combined with its competitive communication complexity, this problem-parameter-free design underscores the practical advantages of AdaSDBO over existing decentralized bilevel methods. We have included comparisons of communication cost with existing works in our paper.

3. Thank you for your thoughtful comment. We acknowledge that the strong convexity assumption on the lower-level problem may not always hold in real-world applications. However, this assumption remains a standard and widely adopted condition in the bilevel optimization literature [2]-[4].

We agree that extending the theory to handle nonconvex lower-level problems is an important and nontrivial direction. In such cases, the solution set may be non-unique and the overall objective may become non-differentiable [7], requiring fundamentally different algorithmic frameworks. This remains a challenging open problem in decentralized bilevel optimization. We regard this as an important direction for future research and appreciate the reviewer for highlighting this point.

Reply to Questions:

1. Thank you for your thoughtful question. In Figure 2 of our paper, for baseline methods, we first tune the stepsizes for each optimization variable to their optimal values, and then test sensitivity by scaling these stepsizes up or down by factors of 10. This is necessary because baseline algorithms require precise tuning of individual stepsizes to properly control the progress of different variables.

In contrast, our proposed problem-parameter-free method uses the same initial stepsize for all three variables $x$, $y$, and $v$. This simple choice is supported by our hierarchical adaptive stepsize mechanism:

• The update for $v$ uses a stepsize inversely proportional to $\max(m^v_{i,t+1}, m^y_{i,t+1})$,
• The update for $x$ uses a stepsize inversely proportional to $m^x_{i,t+1} \max(m^v_{i,t+1}, m^y_{i,t+1})$, making it more conservative,

where $m^x_{i,t+1}$, $m^y_{i,t+1}$, and $m^v_{i,t+1}$ denote the gradient accumulators for the primal variable $x$, dual variable $y$, and auxiliary variable $v$, respectively. This structure ensures:

• $v$ progresses no faster than $y$,
• $x$ progresses no faster than both $y$ and $v$,

thus maintaining a well-coordinated dynamic across levels and preserving the fidelity of the hypergradient approximation. As a result, our method is robust to the initial stepsize setting, and automatically adapts to reach optimal convergence performance without manual tuning.

2. Thank you for your insightful question. Through our two-stage theoretical analysis, we have rigorously shown that our problem-parameter-free algorithm guarantees convergence to a stationary point without requiring any specific tuning of stepsize values. However, in practice, the initial stepsize value can still influence the speed of convergence. This behavior is typical of AdaGrad-norm-based adaptive methods. Specifically:

• When the initial stepsize is excessively large, early gradient updates may cause the accumulated gradient norms to grow quickly, which in turn causes the adaptive stepsize to shrink prematurely. This leads to slower progress in subsequent iterations.

• Conversely, when the initial stepsize is too small, the early updates are overly conservative, and the method takes longer to begin meaningful descent—even though the stepsize will eventually adapt.

Despite this, convergence is still ensured in both cases due to the adaptivity of our design. The observed sensitivity only affects the rate of convergence, not the final outcome. With sufficient communication rounds, our method can still achieve optimal performance. Importantly, our method is robust across a much wider range of stepsize values compared to existing baselines, many of which fail to converge if the stepsizes are not properly set. This highlights the practical value of our design, which eliminates the need for manual tuning while maintaining convergence guarantees.

References:

[1] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.

[2] On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network.

[3] A Single-Loop Algorithm for Decentralized Bilevel Optimization.

[4] Decentralized Bilevel Optimization.

[5] How Free is Parameter-Free Stochastic Optimization?

[6] Tuning-Free Stochastic Optimization.

[7] On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis.

Thank you once again for your thoughtful review and constructive feedback.

We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.

Reply to Weaknesses:

1. Thank you for your thoughtful comment. The stepsize tracking scheme is a key component of our problem-parameter-free framework. Due to the hierarchical nature of decentralized bilevel optimization, multiple coupled adaptive stepsizes naturally arise and may evolve inconsistently across agents. Without proper coordination, this variability may impair convergence. Importantly, our method employs a lightweight tracking mechanism that synchronizes scalar stepsizes across agents. The resulting communication overhead is minimal—only scalar values are exchanged—especially when compared to the cost of transmitting primal variables ($x$), dual variables ($y$), and auxiliary variables ($v$), which are commonly involved in decentralized bilevel methods. In summary, our approach does not incur significant communication overhead relative to existing methods, while simultaneously offering a robust and problem-parameter-free solution to decentralized bilevel optimization.

2. Thank you for your insightful comment. Extending the proposed methods to stochastic bilevel optimization remains a challenging direction with several open theoretical issues:

• The variance in both first- and second-order gradient estimates can affect the reliability of stepsize bounds and compromise algorithmic stability.

• The two-stage convergence analysis and the coupled stepsize structure adopted in our framework may require additional conditions or variance-reduction techniques to ensure convergence in the stochastic setting.

In this work, our primary aim is to establish the first problem-parameter-free method for decentralized bilevel optimization, which lays a solid foundation in the current literature. We are enthusiastic about extending our framework to stochastic settings in future work.

3. Thank you for your thoughtful comment. We acknowledge that the $\log^4(T)$ term introduces a slight theoretical gap compared to the $\mathcal{O}(1/T)$ rate. However, in optimization research, such logarithmic factors are generally considered marginal due to their much slower growth compared to polynomial terms [1]–[4]. In our work, the presence of this logarithmic term stems from the accumulated gradient norms used for adaptive stepsize adjustment. Accordingly, it is an inherent consequence of achieving a problem-parameter-free implementation and is a common feature in similar problem-parameter-free algorithms (e.g., [1]–[5]). Given the significant practical advantages of removing the need for problem-specific tuning, this slight theoretical gap is widely regarded as acceptable and well-justified in the current literature.

4. Thank you for your thoughtful comment. We agree that computing the full Hessian matrix can be expensive, especially for large-scale problems. However, we respectfully clarify that our method only requires computing an approximate Hessian–vector product, rather than the full Hessian matrix, which is significantly more efficient.

Specifically, we compute the Hessian–vector product $\nabla^{2} \ell(x, y) v$ indirectly using the identity $\nabla^{2} \ell(x, y) v = \nabla \left( \nabla \ell(x, y)^{\top} v \right).$

This computation involves the following two steps:

• Compute the inner product $s := \nabla \ell(x, y)^{\top} v,$ which is a scalar and only requires first-order gradient evaluations.

• Compute the gradient of $s$ with respect to $y$: $\nabla s = \nabla \left( \nabla \ell(x, y)^{\top} v \right) = \nabla^{2} \ell(x, y) v.$

This two-step process avoids forming the full Hessian explicitly and relies only on gradient-like operations. As a result, the computational overhead is much lower than directly computing or storing the full Hessian.

5. Thank you for your constructive comment. To address this concern, we have conducted additional experiments on a more challenging decentralized meta-learning task using the CIFAR-10 dataset with a CNN model. In particular, we extended the number of agents to 10, 20, and 30—the widest setting we could support given our limited computational resources. We summarize the results in the table below:

Table 1: Convergence Performance under Different Number of Agents with Decentralized Meta-Learning Task

These results demonstrate that AdaSDBO remains consistently stable and competitive as the number of agents increases, outperforming the baselines even under more complex settings. We have also made every effort to add new experiments on the CIFAR-100 dataset using a ResNet-18 model with varying numbers of agents. The results, presented in the following table, confirm the sustained superior performance of our proposed method.

Table 2: Convergence Performance on the CIFAR-100 Dataset with Varying Numbers of Agents

6. Thank you for your helpful comment. To assess the practical efficiency of our algorithm, we report the total wall-clock runtime required to complete training over 500 communication rounds under different network topologies, using the MNIST and FMNIST datasets. The structural details of these topologies can be found in the Appendix of [1]. The results are summarized below:

Table 3: Total Runtime Performance under Different Topologies ($n=8$)

From the results, we observe that AdaSDBO incurs slightly higher total runtime than the single-loop method SLDBO. However, in terms of convergence results, we respectfully refer you to Table 1 in our response to Reviewer 3RRn due to space limitations here, which demonstrates that AdaSDBO consistently achieves superior accuracy and convergence performance compared to SLDBO. This implies that AdaSDBO requires less time to reach the same level of accuracy, highlighting its improved overall training efficiency. Moreover, compared to double-loop methods, AdaSDBO remains significantly more efficient in terms of both runtime and convergence performance.

7. Thank you for your valuable comment. We will release our complete codebase upon acceptance via GitHub, including thorough documentation, running scripts, and configuration files.

Reply to Questions:

1. Thank you for your thoughtful question. The accumulators in our framework serve to adaptively adjust stepsizes by accumulating the squared gradients of each variable over time. The accumulator allows the algorithm to assign smaller stepsizes to variables with consistently large gradients, and larger stepsizes to those with smaller or infrequent gradients. This is particularly important in decentralized bilevel settings, where gradient magnitudes can vary significantly across agents or levels. This mechanism enhances stability and robustness without requiring manual tuning of stepsize schedules.

We agree that communication efficiency is important in decentralized settings. However, in our framework, only scalar gradient norms are transmitted as accumulators, which incurs minimal overhead compared to exchanging high-dimensional variables. While alternative designs (e.g., compressed accumulators) could reduce communication, they risk losing global coordination, which is essential in our problem-parameter-free setting to avoid divergence from inconsistent learning dynamics. However, exploring more communication-efficient schemes—such as quantized norms or partial sharing—is an interesting direction for future work.

2. Thank you for your question. The update in Line 196 concerns the upper-level variable $x$, which must be carefully coordinated with the lower-level variables $y$ and the auxiliary variable $v$ to maintain a faithful hypergradient approximation in single-loop decentralized bilevel optimization.

In our design, the stepsize for $x$ is conservatively adapted based on the accumulated gradient norms of $x$, $y$, and $v$. This ensures the upper-level update does not progress too aggressively relative to the lower level, which is crucial for maintaining stability in a single-loop, problem-parameter-free setting. This hierarchical coordination plays a central role in balancing progress across levels and avoiding divergence in decentralized bilevel optimization.

References:

[1] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.

[2] Two Sides of One Coin: The Limits of Untuned SGD and the Power of Adaptive Methods.

[3] How Free is Parameter-Free Stochastic Optimization?

[4] Tuning-Free Stochastic Optimization.

[5] Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds.

Thank you once again for your thoughtful review and constructive feedback.

We sincerely appreciate the reviewer for recognizing our contributions and for the constructive comments. Our point-to-point responses to concerns on Weaknesses and Questions are given below.

Reply to Weaknesses:

1. Thank you for your insightful comment. Following your suggestion, we have conducted additional experiments with two additional graph topologies beyond the ring: ladder and complete, using 8 agents on both the MNIST and FashionMNIST datasets. The structural details of these topologies can be found in the Appendix of [1]. A summary of the experimental results across the different topologies is provided below:

Table 1: Convergence Performance under Different Topologies ($n=8$)

As shown in the table above, better network connectivity leads to faster convergence and improved final performance. The complete topology, having the highest connectivity, achieves the best convergence rate and stability, while the ring topology lags behind due to its minimal connectivity.

2. Thank you for your valuable comment. We agree that many deep learning problems do not satisfy smoothness or strong convexity assumptions, particularly in realistic scenarios where both levels of the bilevel problem may be nonconvex. However, due to the inherent complexity of analyzing fully nonconvex bilevel problems, most existing theoretical works on bilevel optimization—such as [2]-[4]—primarily focus on the nonconvex-strongly-convex setting.

We acknowledge that extending the theory to fully nonconvex–nonconvex settings is a highly significant direction, but it remains a challenging open problem in decentralized bilevel optimization. In such cases, the lower-level solution may not be unique, and the upper-level objective can become non-differentiable [5]. Addressing these challenges would require the development of fundamentally different techniques, which are beyond the scope of this work. We plan to investigate this in future work, thank you once again for your insightful comment.

Reply to Questions:

1. Thank you for your helpful suggestion. Following your advice, we have removed this equation in the revised version to enhance clarity.

2. Thank you for your question. The set $\mathcal{V}$ refers to the domain of the auxiliary variable $v$, we have clarified this definition explicitly to improve readability.

3. Thank you for pointing this out. We have adjusted the formatting in the legend of Figure 2 (c & d) to ensure that the formula is now properly horizontally centered.

References:

[1] Problem-Parameter-Free Decentralized Nonconvex Stochastic Optimization.

[2] Decentralized Bilevel Optimization over Graphs: Loopless Algorithmic Update and Transient Iteration Complexity.

[3] A Single-Loop Algorithm for Decentralized Bilevel Optimization.

[4] SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization.

[5] On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis.

Thank you once again for your thoughtful review and constructive feedback.