Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the decentralized bilevel optimization problem. It proposes a gossip-based method which overcomes the challenges in computing the hyper-gradients in decentralized bilevel optimization method. With a strongly-convex lower level problem, the method is provably convergent and achieves the optimal rate (along with linear speedup) for both the general non-convex upper level problem and the PL upper level problem.
strengths_and_weaknesses: Strengths:
The paper is well-written as easy to understand. The considered decentralized bilevel optimization problem is an important topic. Several unique problems and theoretical challenges arising from the decentralization in a bilevel setting are addressed by the paper, and the theoretical result is also sound and convincing.

Weakness:
However, I do have several concerns: 1) Assumption A.1. (iv) requires the stochastic gradients to be bounded in expectation, which is stronger than the standard bounded variance assumption widely satisfied in practice, e.g. Assumption 3 in [1]; 2) In the proposed algorithm, computing the hyper-gradient for the upper level requires inverting a matrix $v_t^k$. The matrix has a size of $d_y \times d_y$, which is large if the network size is large. Therefore, inverting such a large matrix can be too computational intensive, especially for a local machine with limited computation power.

[1] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming.
questions: 1. As stated in previous section, why is Assumption A. 1. (iv), which is stronger than the standard bounded variance assumption, needed in the analysis? Is it possible to relax this assumption to the more standard one?

2. Can the authors explain more about the third key feature stated in line 180-183? Specifically, does the analysis demonstrate such an effect?
limitations: One unique challenge in decentralized bilevel optimization is the efficient computation of the upper level hyper-gradient, which requires the inverse of a large Hessian matrix. The method proposed in the paper requires a direct inversing operation done locally, which can limit the application when the local machine has limited computation power (e.g. in a federated learning setting). It would be great if a smarter decentralized algorithm can lift the requirement of directly inverting the Hessian matrix, while still enjoys the convergence guarantee.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper tackles the problem of Stochastic Bilevel Optimization (SBO) in a decentralized setting, using a gossip protocol for communication between the agents. The authors propose an approach based on a existing formulation of the gradient and a recent contribution (Ghadimi et al. 2020) to provide an (biased) estimate of the Hessian in a decentralized framework. They then provide a complete theoretical analysis of their method for both $\mu$-PL and nonconvex objectives. Finally, empirical results are provided for the two problems introduced in the beginning of the paper: hyperparameter optimization and policy evaluation.
strengths_and_weaknesses: Overall, the paper is very clear and easy to follow. SBO is thoroughly introduced and illustrated, and the main challenge of producing a decentralized approach (combining the recent formulation of the gradient with the Hessian estimation) clearly stated. Each step of the analysis is first motivated then commented, with an attention to providing easy-to-read quantities.
Empirical results are extensively commented and seem convincing about the validity of the approach.

Some remarks:
- Polyak-Łojasiewicz should be introduced at some point rather than be stated as "_PL_" from the start.
- l. 171: ensuring data privacy just based on the fact that raw data are not communicated is quite ambitious, to say the least.
- l. 174: it is true that the method would not collapse from a single failure in the network, but I think it is worth mentioning that the optimization objective would then be different, as the network would be missing a part of the dataset.

Typos:
- Step 9 of Algorithm 1: UnifoRm
-  Equation (3): should be $\nabla_x f$ rather than $\nabla f_x$
questions: - Is there another way of performing decentralized estimation of the Hessian over a network? If so, how would it compare to the method used here?
- What is the motivation to only use ring networks in the experiments? These networks are often slow in terms of "diffusion" and are a counter-example to the robustness mentioned on l. 174.
- I do not understand the notation on l. 139, is $\nabla_y f^k$ only Lipschitz continuous on $x$? on $y$?
limitations: Privacy if briefly mentioned, although it does not seem adequate to me.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, the authors studied the stochastic bilevel optimization problem in a decentralized way. The authors proposed a gossip-based distributed bilevel learning algorithm that solve both the inner and outer optimization problems in a single timescale. Furthermore, the sample complexities are optimal for $\epsilon$ and $K$, and the method achieves linearly scaling in network size. Although there are many existing works for the stochastic bilevel optimization, the successful work for decentralized SBO is still limited. This work solve the DSBO by estimating the $y^*(x)$ and handled the network propagation via gossip-based methods. The proposed method each agent solves an optimization problem collaboratively by sampling stochastic first- and second-order information using its data and making gossip communications with its neighbors. In addition, the theoretical convergence guarantees are also presented, which match the state-of-the-art results for non-federated stochastic bilevel optimization and central-server regime, and suggest that the algorithm exhibits the linear speed-up effect for decentralized settings. The method is verified by the experiments on decentralized ring networks. 
strengths_and_weaknesses: The strength of the work is the theoretical analysis and proposed method for decentralized stochastic bilevel optimization problem. As I mentioned, although there are many existing works for the stochastic bilevel optimization, the successful work for decentralized SBO is still limited. This work solve the DSBO by estimating the $y^*(x)$ and handled the network propagation via gossip-based methods. In addition, the theoretical convergence guarantees are also presented, which match the state-of-the-art results for non-federated stochastic bilevel optimization and central-server regime, and suggest that the algorithm exhibits the linear speed-up effect for decentralized settings. 

The weakness of the work is the experiments. The work only consider the artificially constructed decentralized ring networks, and only run two simple examples on hyper-parameter optimization and policy evaluation in Markov Decision Processes (MDP). I would suggest to evaluate the methods on multiple different networks to demonstrate the method effectiveness and scaling. Also suggesting more practical examples for validation purpose. For example, most experiments are running using only 5 nodes, far behind the practical decentralized setting, suggest nodes from 20 to 100, and network topology from ring network to many other variations.  
questions: The work only consider the artificially constructed decentralized ring networks, I would suggest to evaluate the methods on multiple different networks to demonstrate the method effectiveness and scaling.  
limitations: the authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the distributed bilevel optimization over a network under the non-convex cases and strongly-convex cases. This paper first develops a gossip-based distributed bilevel learning algorithm based on the stochastic gradient descent method. Then, the authors develop the convergence analysis to characterize the convergence behavior of the stated algorithm. The algorithm achieves an $\mathcal{O}\left(\frac{1}{K \epsilon^{2}}\right)$ sample complexity for nonconvex objectives and achieves an $\mathcal{O}\left(\frac{1}{K \epsilon}\right)$ sample complexity for $\mu$-PL functions, subsuming strongly convex optimization. 
strengths_and_weaknesses: Strengths:

This paper presents a clear problem formulation for the decentralized bilevel optimization problem motivated by several real-world applications. Besides, the proposed gossip-based distributed bilevel learning algorithm and experimental evaluations are mostly well explained.

Weaknesses:
1. This submission missed some important theoretical results of existing works. The state-of-the-art sample complexities (paper shown in Line.111 and Line.112) for the stochastic bilevel optimization problem is $\mathcal{O}(\epsilon^{-1.5})$, while the authors claim that the state-of-the-art sample complexity is  $\mathcal{O}(\epsilon^{-2})$.

2. The stochastic estimator seems infeasible. In machine learning applications,  $\nabla_{yx}^2 g$ is usually within a high-dimensional. The question is, in Algorithm 1, Line 4, how to compute the Hessian inverse with a relatively high-dimensional matrix?

3. Theoretical results: Even though this paper is the first paper to explore the decentralized bilevel optimization problem. The proof techniques seem regular, and the results in both nonconvex and strongly convex cases are not attractive. First, in the case of the nonconvex objectives, the sample complexity of $\mathcal{O}(\epsilon^{-2})$ per client is not a surprising result, and the state-of-the-art result (single-client bilevel optimization problem) already achieves the sample complexity of $\mathcal{O}(\epsilon^{-1.5})$. Second, the strongly-convex objectives are not widely used in real-world applications. It would be helpful if the authors could provide some motivational examples to support the reasons for further exploring the strongly convex decentralized bilevel optimization problem.

4. The experimental evaluations are weak. First, the Australia handwriting dataset and LR models are too simple. Evaluating the optimization algorithms using CIFAR10/ImageNet and deeper neural networks has become a standard requirement. Second, it would be better for the authors to provide additional experiments on different distributed network topologies (dense/ sparse). Third, the major contribution of this paper is to provide the convergence bound of the gradient norm. The authors should also provide the gradient norm comparison in the experiment section.




Minors:
1.Line 96: sammple --> sample

questions: 1. What is the definition of $F^*$ in Line. 229/237? 
2. The convergence result for Theorem 1 is for the $\epsilon$-stationary point, while the result for Theorem 2 is for $\epsilon$-optimal point, why not make them being consistent?
3. How to determine the Matrix W in your experiment? How does the network sparsity affect the Matrix W and the convergence result?
4. Are there any motivational examples of performing the decentralized bilevel optimization problems with strongly-convex objectives?
5. The Distributed policy evaluation for reinforcement learning shown in Section.6 shows in Line.285 that

$y_s^*(x) =\phi_{s}^{\top} x-\mathbb{E}_{ s' } [ 1/K \sum_k r^{k}( s , s' ) +\gamma  \phi_s^{\top}  x  |  s] $

However,  $ y^{*}(x)=\underset{y \in \mathbb{R}^{d_{y}}}{\operatorname{argmin}} \frac{1}{K} \sum_{k=1}^{K} g^{k}(x, y)$ in eqs.(1).

What is the g function in Line 285? In eqs(1), should the $y^*$ be the solution when optimizing the lower-level $g$ function, but not the direct result of a function?

6.  In Line.45, it shows that $x$ is a vector of hyper-parameters for a strongly convex regularizer $R$ and the loss function $l_i(y)$ only depends on $y$. However, eqs.(1) shows that the loss function includes both $x$ and $y^*(x)$.
 The question is: how to calculated $\nabla_x l_{i}( y^*(x) )$ shown in Eqs.(3) without x inside? Is $\nabla_x l_{i}( y^*(x) )$=0 ?The stated hyperparameter problem seems different from the bilevel optimization problem in (1).







limitations: N/A
review_title: null

Meta-review: metareview: This paper proposed a fully decentralized algorithm for bilevel optimization. Although the techniques are a combination of existing ones from bilevel literature and the decentralized optimization literature, but the setting considered is considerably sophisticated (i.e., both levels are distributed). The algorithm is a single-timescale, and the rates are good for both nonconvex and convex settings. The reviewers all appreciate the contribution of this work. Therefore I recommend acceptance of the paper. 
confidence: Certain
Decision: Accept