DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity

Comment 3: (Unclear Table 1) Most of the algorithms in Table 1 use the eps-stationary convergence metric while this paper uses LLSC-less. However, this is not directly visible in this table. Meanwhile, the centralized settings may be moved to the appendix, as this paper mainly focuses on the distributed setting.

Our Response: Thanks for your comments. We would like to clarify a misunderstanding regarding the stationary measures and the purpose of the table:

1. Stationarity Measures in the Convex Setting: For convex settings, it is not true that most algorithms in Table 1 use the same $\epsilon$-stationary convergence metric. In fact, these algorithms have different stationarity measures, since each is tailored to the specific method for solveing the problems. Our work introduces a new stationary measure to address the unique challenges of decentralized bilevel optimization in the non-LLSC setting.

2. Purpose of Table 1: The primary goal of Table 1 is not to compare stationary measures but to highlight the differences in problem settings of the listed algorithms. This includes the distinction between centralized and decentralized settings, the presence or absence of LLSC, and the types of objectives considered (e.g., convex, strongly convex, or non-convex). The table serves to provide readers with a comprehensive understanding of how our work fits within the broader literature.

3. Placement of Centralized Settings: While our paper focuses on the decentralized setting, centralized settings are included in Table 1 to provide additional context and to better highlight our contributions. Moving these to the appendix may obscure the broader comparison and reduce the table’s function to showcase differences in problem settings.

Comment 4: (Misleading name) The name of the extended version of DUET, DSGT, might be a little misleading -- as it refers to distributed stochastic optimization with gradient tracking in the distributed optimization literature. It would be better if the authors could use another name for the extended version of their algorithm.

Our Response: Thanks for your comments. We clarify that DSGT is not an extension of our algorithm DUET. Rahter, it is an extension of the centralized SL-BAMM method, which is also done by us and used as a baseline for performance comparison. Regarding the DSGT naming, we understand that the name DSGT might cause confusion, as it is associated with distributed stochastic optimization with gradient tracking. To avoid such misunderstanding, we will rename DSGT in our paper to a less used term (e.g., SL-BAMM+) in the revised manuscript.

Comment 5: Can the authors provide some insights on the lower bound of this problem? For example the current O(eps^{-2.5}) seems not to be optimal, and it would be interesting to study the lower bound of DBO under the LLSC-less metric.

Our Response: Thanks for your question. To our knowledge, there is no existing research on the lower bounds for decentralized bilevel optimization in the non-LLSC setting, which is a fundamental and challenging problem itself and deserves a dedicated paper. In fact, even our convergence rate upper bound $O(\epsilon^{-2.5})$ is the first for DBO problems without LLSC, let alone the corresponding lower bound. This gap highlights a lack of fundamental understanding regarding the complexity of DBO problems in the non-LLSC setting. We appreciate the reviewer for pointing out this important research direction, which we will further investigate in our future studies.

Comment 6: Is it correct to claim the complexity results are O(eps^{-3.5}) and O(eps^{-2.5}) in Corollary 2 and 4? Technically speaking \tau cannot be 0 and thus the logic "\tau --> 0 leads to -3.5 and -2.5" complexity seems a little bit problematic.

Our Respinse: Thanks for your comments. You are correct that $\tau$ cannot exactly be 0, and the complexities $O(\epsilon^{-3.5})$ and $O(\epsilon^{-2.5})$ represent asymptotic behavior as $\tau \to 0$. These results should be interpreted as sample complexity bounds that our method approaches in the limit. However, since $\tau$ can be made arbitrarily close to 0, one can always achieve a sample complexity bound that is ever so slightly larger than $O(\epsilon^{-3.5})$ and $O(\epsilon^{-2.5})$.

Comment 2: (Simple experiments with incomplete context) The experimental settings are relatively simple -- A Pedagogical Example and MNIST dataset are so simple that they may not well represent the non-convex nature of lower-level non-convexity in many bilevel optimization problems. Some important details about the experiments setup are missing -- for example it would be better if the architecture of the neural network in the meta learning experiments is reported, otherwise the readers need to go through the code to figure it out.

Our Response: Thanks for your comments. The details about the experiment setup are as follows:

1. Choice of Problems: Since our work addresses the case in DBO where the LL problem is convex but not strongly convex, and the UL problem is non-convex, the problems we chose (the pedagogical example and the decentralized meta-learning) align with this focus and reflect the theoretical assumptions of our proposed algorithm.

2. Choice of Datasets: The use of simpler datasets such as MNIST and the Pedagogical Example is to clearly illustrate the core concepts and validate the effectiveness of our proposed algorithm. These datasets provide a controlled environment to demonstrate the scalability and performance of the method.

3. Expanded Experiments: We are currently working on additional experiment results. We will provide the additional experiment results in both the revised manuscript as well as the response in here as soon as we finish the additional experiments.

Comment 1: (Novelty of the theory) Although the proposed metric and algorithm are novel, the analysis used to obtain the final convergence is quite standard in distributed optimization and bilevel optimization literature.

Our Response: Thanks for your comments. We note that our theoretical analysis is actually quite non-standard due to the absence of LLSC in decentralized bilevel optimization. These challenges necessitate novel metrics, proof techniques, and significant modifications to the existing proof fameworks. In what follows, we will elaborate the novelty of our theoretical analysis:

1. General Challenges Without LLSC: Without LLSC, the LL solution $\mathbf{y}^*$ may not be unique, and the hyper-gradient is ill-defined. Therefore, we have to redefine the stationarity convergence metric using the KKT stationarity through a logically equivalent reformulated problem. These signficant changes necessitate new algorithmic designs on how to track and bound the variations in both the LL solution and dual variables in the KKT system across iterations. Note that the existing methods based on the LLSC setting do not need to handle these complications, since strong convexity guarantees a unique LL solution and simplifies convergence analysis. Hence, the theoretical analyses of the existing methods are much simpler compared to ours.

2. New Proof Techniques: Due to the new challenges in the non-LLSC setting stated above, we have to propose several new proof techniques as follows:

• In Lemma 4, we establish new bounds on the deviations of the current LL solution $\mathbf{y} _ {i,t+1}$ and dual multiplier $\mathbf{v} _ {i,t+1}$, i.e., \left\\|\mathbf{y} _ {i,t+1}-\mathbf{y} _ {\mu_t}^*\left(\mathbf{x} _ {i,t}\right)\right\\|^2 and \left\\|\mathbf{v} _ {i,t+1}-\mathbf{v} _ {\mu_t}^*\left(x_{i,t}\right)\right\\|^2.

• In Lemma 5, we further analyze and bound the variations of both the primal LL solution and the dual multiplier as the regularization parameter $\mu_t$ diminishes. Specifically, we handle terms such as: \left\\|\mathbf{y} _ {\mu_t}^*\left(x _ {i,t}\right) - \mathbf{y} _ {\mu_{t+1}}^*\left(\mathbf{x} _ {i,t+1}\right)\right\\|^2 and \left\\|\mathbf{v} _ {\mu_t}^*\left(\mathbf{x} _ {i,t}\right) - \mathbf{v} _ {\mu_{t+1}}^*\left(\mathbf{x} _ {i,t+1}\right)\right\\|^2. These terms capture the evolution of the optimal LL solution and its associated dual multipliers, which are influenced by the diminishing regularization parameter $\mu_t$ and decentralized updates. Unlike in settings with LLSC, where strong convexity simplifies the analysis, we cannot directly bound terms like \left\\|\mathbf{y} _ {i,t+1}-\mathbf{y} _ {t+1}^*\left(\mathbf{x} _ {i,t+1}\right)\right\\|^2-\left\\|\mathbf{y} _ {i,t}-\mathbf{y} _ {t+1}^*\left(\mathbf{x} _ {i,t}\right)\right\\|^2 and turn out to be quite challenging to analyze. In our theortical analysis, based on Lemma 4 and Lemma 5, our proof must carefully account for the interplay between diminishing regularization \left\\|\mathbf{y} _ {i,t+1}-\mathbf{y} _ {\mu_{t+1}}^*\left(\mathbf{x} _ {i,t+1}\right)\right\\|^2-\left\\|\mathbf{y} _ {i,t}-\mathbf{y} _ {\mu_t}^*\left(\mathbf{x} _ {i,t}\right)\right\\|^2 and \left\\|\mathbf{v} _ {i,t+1}-\mathbf{v} _ {\mu_{t+1}}^*\left(\mathbf{x} _ {i,t+1}\right)\right\\|^2-\left\\|\mathbf{v} _ {i,t}-\mathbf{v} _ {\mu_t}^*\left(\mathbf{x} _ {i,t}\right)\right\\|^2. This is very different from the counterpart in the LLSC setting, where one can easily obtain \left\\|\mathbf{y} _ {i,t+1}-\mathbf{y} _ {t+1}^*\left(\mathbf{x} _ {i,t+1}\right)\right\\|^2-\left\\|\mathbf{y} _ {i,t}-\mathbf{y} _ {t+1}^*\left(\mathbf{x} _ {i,t}\right)\right\\|^2, which are fundamentally different from the complicated terms appearing in proofs in the non-LLSC setting.

3. Impacts on Aggregation Function: The use of the diminishing regularization parameter $\mu_t$ also implies that care must be taken in the aggregation function design. Unlike standard decentralized methods, our aggregation function incorporates a time-varying of $\mu_t$, which requires that both the primal and dual variables remain synchronized as $\mu_t$ evolves. This adjustment is essential to maintain convergence in the non-LLSC setting and our theoretical analysis in this aspect is new.

Comment 3: The rationale behind the utilization of the projection parameters $r_v^t$ and $r_y^t$ remains ambiguous (line 301).

Our Response: Thanks for comments. We would like to clarify that the roles of radii $r_y^t$ and $r_v^t$ in the projection steps for $\mathbf{y} _ {i,t}$ and $\mathbf{v} _ {i,t}$ are to ensure that the sequences $\mathbf{y} _ {i,t}$ and $\mathbf{v} _ {i,t}$ remain bounded with radii $r_y^t$ and $r_v^t$, respectively. These boundedness results are important for establishing convergence due to the following reasons:

1. Inducing Boundedness of $\mathbf{x} _ {i,t}$: In Lemma 8, we show that the boundedness of $\mathbf{y} _ {i,t}$ and $\mathbf{v} _ {i,t}$, ensured by the above projection steps, directly results in the boundedness of the UL variables $\mathbf{x} _ {i,t}$. This interplay is important for maintaining feasible updates across iterations.

2. Convergence via Bounded $\mathbf{x} _ {i,t}$: In Lemma 3, the boundedness of $\mathbf{x} _ {i,t}$ is a key condition for establishing the overall convergence of the algorithm. By controlling the growth of $r_y^t$ and $r_v^t$, the projection steps ensure that $\mathbf{x} _ {i,t}$ remains bounded, thereby establishing convergence guarantee.

We will revise the manuscript to clarify the role of these projection parameters $r_v^t$ and $r_y^t$, and their connection to Lemma 8 and Lemma 3.

Comment 4: The definitions of $\otimes$ and $\bar\beta$, $\bar \mu$ are not clearly articulated (lines 347 and 362).

Our Response: Thanks for your comments. The $\otimes$ symbol represents the Kronecker product in linear algebra. $\bar\beta$ and $\bar\mu$ are the initial LL learning rate and averaging control parameter, respectively. Both $\bar{\beta}$ and $\bar{\mu}$ are constants. We have defined and clarified these terms in the revised manuscript.

Comment 5: To enhance the understanding of Theorem 5, a comparative analysis with other algorithms is recommended.

Our Response: Thanks for your suggestion. However, since our work is the first in the areas of decentralized bilevel optimization (DBO) without LLSC, there is a lack of existing algorithms as comparison baselines in the current literature. Due to this reason, in our numeical studies, we have to develop another DBO method called DSGT, which can handle the non-LLSC setting by adapting a related centralized bilevel optimization algorithm to the decentralized setting. Unfortunately, adapting centralized methods to the decentralized setting is highly non-trivial and may not be always possible due to the unique challenges in the decentralized setting, such as communication constraints, consensus errors, and heterogeneous data distributions. As a first step toward a theoretical and algorithmic foundation for solivng DBO problems without LLSC, the significance of Theorem 5 is that it shows it is possible to design algorithms that solve non-LLSC DBO problems without provable convergence rate guarantees.

Comment 2: The update mode of Algorithm 1 is similar to the algorithm of [5], so I want to know the distinctions between these two algorithms.

Our Response: Thanks for your comments. We would like to further clarify the differences between our algorithm and the approach in [5]:

1. Different Assumptions on the UL Objective Functions: Ref. [5] assumes the UL objective $F(x,y)$ is strongly convex (cf. Assumption 3.1 in Ref. [5]), so that they can aggregate the UL and LL objective functions to recover LLSC in the LL variable $\mathbf{y}$. This strongly convex assumption of the UL objective function significantly limits the applicability of their proposed approach, since many real-world bilevel optimization problems involve non-convex UL objectives. In stark contrast, our work does not assume the UL objective $F(x,y)$ to be strongly convex. Instead, we address the non-LLSC challenge through the proposed diminishing quadratic regularization approach, which temporarily enforces a LLSC property in each iteration that is gradually diminishing. As the regularization paremter $\mu_t$ shrinks over the iterations, our DUET algorithm guarantees the convergence to a KKT-stationary solution of the original DBO problem.

2. Decentralized Problem Setting: Our DUET algorithm is designed for decentralized bilevel optimization (DBO), where agents operate in a peer-to-peer network and share information through local communication. This requires a consensus-based aggregation mechanism to synchronize the UL updates across the agents, while accounting for communication constraints, consensus errors, and heterogeneity among agents simultaneously. All these algorithm designs are absent in Ref. [5], which is focused on centralized bilevel optimization.

Comment 1: My primary concern is the presentation of this paper. For instance: 1-1. It is imperative to delineate the feasible region for $p$ and $\tau$ in line 81;

Our Response: Thanks for your suggesiton. We have added the feasible region for $p$ and $\tau$ in the revised manuscript.

1-2. The definitions of communication costs and communication complexity must be elucidated in lines 105 and 117;

Our Response: Thanks for your suggestion. Here, both "communication costs" and "communication complexity" refer to the total rounds of communications required by an algorithm to achieve an $\epsilon$-stationary point. We have explicitly defined the terms "communication costs" and "communication complexity" to avoid ambiguity and ensure consistent usage throughout the paper.

1-3. In line 138, it is noted that several methods exist which offer enhanced complexity solutions for simple bilevel problems, as evidenced by references [1, 2, 3, 4];

Our Response: Thanks for providng pointers to the related works.

[1] addressed convex bilevel optimization problems with nonsmooth outer objectives, introducing a generalized sub-gradient method to the bilevel setting and achieves sub-linear convergence rates for outer and inner objectives under mild assumptions. They additionally improves to a linear rate for strongly convex outer objectives while allowing for nonsmoothness. However, our work specifically deals with smooth UL objectives.

[2] proposed a penalty-based algorithm that leverages Hölderian error bounds to achieve convergence rates of $O(1/\epsilon^2)$, assuming a convex UL objective.

[3] introduced an accelerated gradient method specifically designed for bilevel problems with a convex lower-level problem, achieving convergence rates of $O(1/\sqrt{\epsilon})$ for smooth convex objectives.

[4] achieved optimal complexity guarantees for a class of convex bilevel problems using advanced regularization techniques and strong convexity assumptions.

While their work ([2, 3, 4]) assume UL convexity, our work focuses on non-convex UL objectives, broadening the applicability to more general problem settings.

We will enrich the references in the revised manuscript to include all necessary publication ([1, 2, 3, 4]).

1-4. The formulation of the decentralized bilevel optimization problem should be introduced earlier in the paper, ideally in the Section introduction;

Our Response: Thanks for the suggestion. We will move the problem formulation to the first paragraph of the introduction to provide early context for readers.

1-5. A precise definition of $\nabla \mathcal{L}$ is essential and should be provided in line 231. Furthermore, given that $\nabla \mathcal{L}$ is a matrix (since may be a matrix), it is crucial to specify the type of norm to be used (F-norm or 2-norm); moreover, similarly, the definition (vector or matrix) of $\nabla \Phi$ in line 347 is also important.

Our Response: Thanks for your comment. However, we would like to clarify that $\nabla \mathcal{L}$ is a vector, not a matrix. This is because the Lagrangian function in Line 221 is scalar-valued. Also, the UL variable $\mathbf{x}$ is a vector in $\mathbb{R}^{p_1}$ (cf. the definition of $\mathbf{x}$ in Line 190. Note that, even if a learning model contains multiple layers of matrices, one can always construct such a vector $\mathbf{x}$ by stacking the columns of these matrices without loss of generality). Hence, the gradient of $\mathcal{L}$ with respect to $\mathbf{x}$ is a vector. The norm we use in Line 231 is the $\ell_2$ norm. Hence, we use the $\|\cdot\|$ norm notation following the convention. To make the paper more reader-friendly, we have added a notation table in the revised manuscript.

1-6. The definitions of $x_{i,t}$ and $y_{i,t}$ remain ambiguous in line 242. Here, I assume that these represent the vectors $x_{i}$ and $y_{i}$ at the $t$-th iteration;

Our Response: Thanks for the comment. We would like to further clarify that $\mathbf{x} _ {i,t}$ and $\mathbf{y} _ {i,t}$ represent the values of UL and LL variables at agent $i$ in iteration $t$, respectively. To this ambiguity, we have added the definition of $\mathbf{x} _ {i,t}$ and $\mathbf{y} _ {i,t}$ in the revised manuscript.

Thanks for the author's responses. As the authors demonstrate, if it is true that the algorithm proposed in this paper is the first attempt at DBO, I am willing to increase my score to 6. However, I may decrease my confidence from 3 to 2 if the authors cannot confirm that this paper is the first attempt at DBO. Can the authors confirm this point again?

Comment 4: The experimental results are not sufficiently convincing, as only a limited set of results is provided. Additionally, the experiments are conducted on a small-scale distributed system with only a few clients. I have concerns about the scalability of the proposed method, especially given its deterministic setting. Specifically: 1) Could the authors provide additional experimental results on a larger-scale distributed system? 2) The tasks addressed in the experiments are quite limited. I am curious if the proposed algorithm can be applied to more complex tasks, such as bilevel NAS (e.g., DARTS).

Our Response: Thanks for your comments. We are currently working on additional experiment results. We will provide the additional experiment results in both the revised manuscript as well as the response in here as soon as we finish the additional experiments.

Comment 5: Please refer to the Weaknesses. Additionally, the readability of this work is quite poor, with an excessive number of notations. Could you improve the manuscript’s readability and overall presentation?

Our Response: Thanks for your feedback regarding the readability and presentation of the manuscript. We will attempt to improve. We note that, due to the problem nature of in decentralized bilevel optimization without LLSC, the problem statement and algorithmic design inherently require complex formulations and careful theoretical treatment. Hence, having a large number of mathematical notations is somewhat inevitable. We note that the number of notations used in our paper is not to excessive in the sense that the number of notations is quite comparable with other works on decentralization bilevel optimization in this field. To enhance the readability and clarity as suggested by the reviewer, we have added a notation table in the appendix of the revised manuscript. This table will serve as a quick reference guide, summarizing all key notations and their definitions to make the content more accessible.

Comment 3: In Corollary 2, in addition to discussing the number of communication rounds required for the proposed algorithm to converge, it is also essential to analyze the number of bits needed during this process. Can you provide some comparisons about the communication complexity between the proposed method with the existing distributed bilevel optimization methods in the experiments?

Our Response: Thanks for your comments. Here, we first discuss per-round communication complexity, which will further shed light on overall communication complexity "in terms of the number of bits".

1. Per-Round Communication Volume: In DUET, the per-round communication cost (or volume) of each agent includes transmitting the UL variables ($\mathbf{x}_i$) and the tracked gradients ($\mathbf{h}_i$). Hence, the per-round communication cost in terms of "bits" at each node is $2d$, where $d$ is the model size. We note that this communication structure is identical to several existing decentralized gradient-tracking-based bilevel optimization methods, such as INTERACT [1] and DIAMOND [2] (i.e., having the same need to exchange these variables). As a result, the amount of information exchanged per round in DUET is the same as these existing methods in decentralized bilevel optimization with LLSC.

2. Overall Communication Volume of DUET: Multiplying the $2d$ per-round communication cost above with the communication complexity results in Corollaries 2 and 4 yields the overall communication costs of our DUET method in terms of "bits."

[1] Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. Interact: Achieving low sample and communication complexities in decentralized bilevel learning over networks. In Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pp. 61–70, 2022.

[2] P. Qiu, Y. Li, Z. Liu, P. Khanduri, J. Liu, N.B. Shroff, E.S. Bentley, and K. Turck. Diamond: Taming sample and communication complexities in decentralized bilevel optimization. In IEEE INFOCOM 2023 - IEEE Conference on Computer Communications, pp. 1–10, 2023.

Comment 2: The relaxed stationarity (KKT-stationarity) is employed in this work without adequate justification. It is essential to provide a clear rationale for this relaxation, as it may result in significantly different solutions compared to the original problem. The stationarity measures are somewhat different from the traditional bilevel optimization works.

Our Response: Thanks for your comments. We would like to further clarify and explain the rationale behind the use of KKT-stationarity. As stated in the paper, our work addresses decentralized bilevel optimization (DBO) without the LLSC assumption. In this setting, the hypergradient is not well-defined due to the lack of invertibility of the Hessian of the LL objective. To see this, note that the computation of the hyper-gradient (if exists) requires Hessian inverse computation (cf. Eq. (5) in Ref. [1] for the expression of the hyper-gradient). However, without LLSC, there is no guarantee that the Hessian matrix is full-rank and it is only positive semidefnite when the LL objective function is just convex (i.e., the Hessian matrix could be singular).

Precisely because of the fundamental challenge of not having a well-defined hyper-gradient, one can no longer use the norm of the hyper-gradient in conventional bilevel optimization works as the stationarity measure. As a result, the stationary measure in bilevel optimization problems without LLSC has to be redefined and hence cannot be the same as conventional bilevel optimization works. To overcome this challenge, we reformulate the problem as a logically equivalent single-level constrained optimization problem in Eq. (3). Thanks to the logical equivalence, the optimal solution to this new single-level constrained optimization problem (characterized by the new problem's KKT system) implies the solution to the original bilevel optimization without LLSC. Further, the stationarity condition in the KKT system (one of the four KKT conditions) provides a natural stationarity metric for our subsequent optimization algorithm design.

Comment 1: What is the need for this algorithm in the ML community? This question arises from two main points: 1) Although this work avoids the strong convexity assumption, it still relies on the convexity assumption, whereas objectives in ML are often non-convex. Could you provide additional theoretical analyses that do not depend on convexity assumptions? 2) This work emphasizes the deterministic setting of the algorithm. While the deterministic setting is indeed important in optimization, I am curious about the challenges in analyzing convergence rates under a stochastic setting in the proposed algorithm. In ML, stochastic gradient descent is far more commonly used than deterministic approaches.

Our Response: Thanks for your comments. We will organize our responses corresponding to your two subquestions, respectively:

• 1) Convexity of the LL subproblem: Although bilevel optimization (BLO) problems arise in a large number of ML paradigms, BLO problems are highly challenging and their algorithmic designs as well as the associated theoretical performance understandings remain very limited. As a starting point, most researchers in the ML community focused on a subset of tractable BLO problems, where the LL subproblems are strongly convex (see [1] for an excellent recent survey on BLO). So far, even relaxing BLO problems to cases with merely convex LL subproblems turns out to the highly non-trivial from a theoretical perspective. Our work not only relaxes the LL subproblem strong convexity assumption in BLO but also extends the studies to decentralized settings that have important applications in distributed ML training, marking a significant theoretical advancement. No prior work has addressed this important setting in the literature. Thus, our work fills an important gap in the BLO literature. On the other hand, even though the reviewer is correct that many ML tasks have non-convex objectives, BLO with convex or strongly convex LL subproblems have found quite a few interesting applications in ML (e.g., adversarial robust training [2], model pruning with sparsity constraint [3], invariant risk minimization [4])

• 2) The Deterministic Setting: Just as in most subfields in optimization algorithms design for machine learning, we also follow the "determistic-->stochastic" development order in this new decentralized BLO area (see the recent BLO survey in [1] to see the development history of determistic BLO algorithms before their stochastic counterpart). Specifically, we start with the relatively more tractable determistic setting to obtain a full understanding on algorithmic designs for decentralized BLO without LLSC, without which the development for stochastic cases would be difficult if not impossible. Furthermore, deterministic methods serve as a theoretical foundation for stochastic extensions. Moreover, we note that the determistic setting is also important in its own right in ML scenarios with moderate dataset sizes (e.g., LLMs supervised finetuning with small and high-quality datasets), where full gradient evaluations are possible.

[1] Yihua Zhang, Prashant Khanduri, Ioannis Tsaknakis, Yuguang Yao, Mingyi Hong, and Sijia Liu, "An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning," arXiv:2308.00788.

[2] Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, and Sijia Liu, “Revisiting and advancing fast adversarial training through the lens of bi-level optimization,” in International Conference on Machine Learning, 2022, pp. 26693–26712.

[3] Yihua Zhang, Yuguang Yao, Parikshit Ram, Pu Zhao, Tianlong Chen, Mingyi Hong, Yanzhi Wang, and Sijia Liu, “Advancing model pruning via bi-level optimization,” in Advances in Neural Information Processing Systems, 2022.

[4] Martin Arjovsky, Leon Bottou, Ishaan Gulrajani, and David Lopez-Paz, “Invariant risk minimization,” arXiv preprint arXiv:1907.02893, 2019.

Thank you for the responses. Unfortunately, my concerns remain unaddressed. The responses are not convincing enough, I still believe the proposed method offers limited contributions to the machine learning community due to its reliance on the convex assumption and deterministic setting. This work might be more suited for mathematical conferences or journals. Furthermore, decentralized bilevel optimization has already been studied for over two years [1], and replacing the strongly convex assumption with the convex assumption does not pique my interest, as both are strictly assumptions in the ML community, significantly limiting the practical applicability of the proposed method. The paper largely builds upon the ideas and analysis of [2], extending them to the context of decentralized bilevel optimization (DBO). In addition, as claimed by the author, the proposed method can be applied to adversarial robust training and model pruning with a sparsity constraint, but I cannot find any experimental results regarding these two applications, I only find limited experimental results which are not sufficiently convincing. Furthermore, after reading the revised paper, my concerns about the readability of this paper have not been adequately addressed. After reading all the reviews and rebuttals, combined with the aforementioned reasons as well as the current state of this work, I regret to conclude that I am unable to recommend acceptance to ICLR.

[1] Chen, Xuxing, Minhui Huang, and Shiqian Ma. "Decentralized Bilevel Optimization." arXiv preprint arXiv:2206.05670 (2022).

[2] Liu, Risheng, et al. "Averaged method of multipliers for bi-level optimization without lower-level strong convexity." International Conference on Machine Learning. PMLR, 2023.

Our Response for 1: Thanks for your comment. We respectfully disagree with the assessment of limited contributions. Bilevel optimization is a key area in ML, with important applications in meta-learning and hyperparameter optimization. Its growing importance is evidenced in the long list of publications in the "Big Three" ML conferences as we have previously noted.

Moreover, it has been widely recognized in the research community that the watershed between easy and hard bilevel optimization problems is whether the lower-level problem is strongly convexity (LLSC) or just convex, regardless of whether the problem is deterministic or stochastic. Without LLSC, the ill-defined implict gradient problem renders traditional bilevel optimization methods under LLSC assumption inapplicable. More specifically, due to the ill-defined hyper-gradient, all existing bilevel optimization methods (e.g.[5-7]) that rely on hyper-gradient updates breakdown and their convergence performance analysis do NOT even have a proper convergence metric in the first place. Excerbating the problem is the lack of a guaranteed unique lower-level solution in general, which fundamentall changes the problem formulation and necessites the optimization of LL variables in the UL problem (cf. our problem formulations and other related DBO work with LLSC [1-4]).

Addressing decentralized bilevel problems without LLSC requires fundamentally new techniques for measuring stationarity and analyzing convergence. Our work directly tackles this challenge by introducing a novel stationarity metric and a new approach that not only handles LL convexity but also effectively addresses consensus errors, filling a clear gap in the literature and advancing the field meaningfully.

While the stochastic setting has been explored in works such as [1] mentioned by the reviewer and [2-4], they all rely on the LLSC assumption to to simplify their analysis using traditional stationarity measures and approaches. Specifically, as highlighted in Assumption 3.4 of [1], their work is focused on decentralized bilevel optimization under LLSC. Due to this fundamental difference in setting, we do not compare our sample complexity with [1]. Since Ref. [1] and other related DBO related work [2-4] cannot be used in non-LLSC setting, comparing their theoretical sample complexities and empirical convergence performances is infeasible.

[1] Yang, Shuoguang, Xuezhou Zhang, and Mengdi Wang. "Decentralized gossip-based stochastic bilevel optimization over communication networks." Advances in neural information processing systems 35 (2022): 238-252.

[2] Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. Interact: Achieving low sample and communication complexities in decentralized bilevel learning over networks. In Proceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, pp. 61–70, 2022.

[3] Peiwen Qiu, Yining Li, Zhuqing Liu, Prashant Khanduri, Jia Liu, Ness B Shroff, Elizabeth Serena Bentley, and Kurt Turck. Diamond: Taming sample and communication complexities in decentralized bilevel optimization. In IEEE INFOCOM 2023-IEEE Conference on Computer Communications, pp. 1–10. IEEE, 2023.

[4] Zhuqing Liu, Xin Zhang, Prashant Khanduri, Songtao Lu, and Jia Liu. Prometheus: Taming sample and communication complexities in constrained decentralized stochastic bilevel learning. In Proceedings of the 40th International Conference on Machine Learning, pp. 22420–22453, 2023b.

[5] Junyi Li, Bin Gu, and Heng Huang. A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7426–7434, 2022.

[6] Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. arXiv preprint arXiv:2102.03926, 2021.

[7] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In ICML, 2021.

Thanks for your comments. We are currently working on additional experiment results. We will provide the additional experiment results in both the revised manuscript as well as the response in here as soon as we finish the additional experiments.