Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of personalized bilevel optimization in a decentralized distributed learning system over stochastic and directed underlying communication networks. The major contribution of this paper is to propose an effective scheme termed HGP to compute the hyper-gradient, i.e., the gradient of hyperparameters in the outer-problem, in a decentralized way. Specifically, this paper first shows the failure of standard backpropagation in hyper-gradient computation on a directed network, then introduces a push-sum communication strategy to tackle the biasness of the hyper-gradient estimate. Moreover, the variance reduction technique is introduced to handle the large variance in the push-sum communication. This paper further derives an upper bound for the estimation error of the proposed method and evaluates it effectiveness empirically. 
strength_and_weaknesses: **Strengths:**
+ The discovery of the failure of standard backpropagation for hyper-gradient computation over directed networks is interesting, and the use of push-sum strategy sounds novel.
+ This paper is well-written in general and easy to follow.
+ The derivation of the estimation error bound is technically sound.

**Weaknesses:**
- Some assumptions in this paper need to be justified. 
I wonder if the assumption of knowing the receiving frequency in advance is reasonable. Although this paper said that it can be estimated by simulating several rounds, it will bring estimation error to the computation of hyper-gradients. Does the main theorem take such an error into consideration? 
In addition, please justify Assumption 5, which said that the edges are “undirected” in expectation. I wonder if this assumption still holds for standard (deterministic) directed networks.
- The relevance to some related work should be clarified.
Since the proposed method relies on the previously proposed recurrent backpropagation method, HPG should be compared with Grazzi’s work in detail, especially from the theoretical aspect. Specifically, what is the difference between using the sending edges and the receiving edges in principle? Will it bring any difficulty in theoretical analysis? Besides the error bound for VR-HGP, can you provide a bound for the standard HGP and compare it with Grazzi’s? 
Another related line of work is the push-sum method. It seems that the core innovation of HPG is to introduce such a method to the optimization of the outer-problem. Hence, I wonder what is the main difference from applying the method to the inner-problem as in previous works (perhaps more complex theoretical analysis)? 

clarity,_quality,_novelty_and_reproducibility: This paper is well-written in general. The comparison with related work on decentralized bilevel optimization is clear, though the relevance to previous hyper-gradient estimation methods and push-sum methods need to be clarified in more detail. In addition, several assumptions in theoretical analysis need to be further justified (please refer to the above **Weaknesses**). 
summary_of_the_review: This paper contributes an effective scheme for hyper-gradient computation in PDBO over stochastic and directed networks, where the use of push-sum communication to make an unbiased estimate is interesting. However, the relevance to previous hyper-gradient computation methods and push-sum communication methods should be explained in more detail, and several assumptions in theoretical analysis need to be justified.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a gradient-based bilevel optimization that reduces most personalization approaches to the optimization of client-wise hyperparameters. Then the authors propose a decentralized algorithm to estimate gradients with respect to the hyperparameters, which can run even on stochastic and directed communication networks. Empirical results demonstrated that the gradient-based bilevel optimization enabled combining existing personalization approaches which led to state-of-the-art performance, confirming it can perform on multiple simulated communication environments including a stochastic and directed network.
strength_and_weaknesses: Strength: 
- This study proposed a gradient-based PDBO, which reduces most personalization approaches to the optimization of hyperparameters possessed by each client. 

Weaknesses: 
- Assumption 2 is a bit too strong to require $y_i^*=y_i^{(T)}$ make it unpractical. The authors should provide some bound estimation for it.
- Empirical results using the settings of EMNIST classification is a bit too simple.  
 
clarity,_quality,_novelty_and_reproducibility: - paper is hard to follow. the authors better to provide some intuition or explanation for some derivations 

- unable to verify. code is not provided but the authors claimed in the paper to release code after review process 
summary_of_the_review: This study proposed a gradient-based PDBO, which reduces most personalization approaches to the optimization of hyperparameters possessed by each client. The approach is not practical since the assumption is too strong, and the experiment using EMNIST classification is a bit too simple.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a general formulation for learning personalized models in a fully-decentralized context. The problem is formulated as a bi-level optimization problem, where the outer-objective updates the local hyper-parameters given the optimal local parameters of the inner objective. The algorithm for optimizing such problem in a decentralized way is then derived, supposing that the communication graph is fully connected but only a few directed communication edges are active at each iteration.
strength_and_weaknesses: The paper is very hard to read, and hence it is difficult to assess the contributions and correctness of the derivations.

These are some of the reasons that make the paper difficult to parse:
1. Some notation and formulations are inexact, confusing or undefined:
- In Problem 1 and Problem 5, the index $i$ is used for two different thing: first for indicating the client's parameters to be optimized and then for indexing the terms of the sum. Also the size of $\xi_i$ is not provided and $p(\xi_i)$ is not formally defined.
- Right before Equation 2, it is said that "The i-th client in SGP updates its weight $\omega_i$" but Equation 4 do not update this parameter.
- Equation 4, the operation $[a \quad b]$ is not defined. I assumed it was a vector concatenation. Also $p()$ denotes here the message distribution, while it was used before for the local data distribution.
- (minor) In page 3, end of Section 2, $p_{ij}$ should be replaced by $p()$ ($p_{ij}$ cannot be a doubly stochastic matrix as it is defined as a scalar function).
- In Assumption 2, the stationary point is denoted by $y^\star$ while later one is referred to as $y^\star(\lambda)$.
- Overall, the equations are very hard to read because the notation is heavy. The paper would benefit from a simplification. For instance, the update matrices that depend on $y$ (resp. $\lambda$) should be called in a way that remind the reader of this dependence. The Jacobian is called $A$ and its estimate $u$.

2. It is not clear which criteria are used for determining if a set of parameters should be optimized in the outer or inner loop of the bi-level problem. For instance, why is the label weight vector of PDBO-DA considered a hyper-parameter, hence to be optimized in the outer problem, and not the parameters of the neural network? In the end, all the parameters of the model are specialized to the agent. 

3. Little intuition or explanation are provided for supporting the various derivation choices. For instance, why are truncated Neumann series and recurrent back-propagation needed to compute the outer gradient?

Finally, the interplay between agent similarity (usually referred to as mixing matrix) and model performance is never discussed in the paper. No assumptions are then made on the model for drawing directed communication edges, as the paper does not try (or guarantee) to recover the true mixing matrix. However, the performance of a personalized model depends on how often/well an agent communicates with similar agents. If existing works make more assumptions on the graph model, it is to guarantee a good estimation of the true mixing matrix, hence a good estimation of true local models.


clarity,_quality,_novelty_and_reproducibility: The paper is very hard to read. Because of its low clarity, I cannot judge the quality and the novelty of the results.
The code for reproducing the results was not submitted and in the empirical section the chosen model architecture is not described.
summary_of_the_review: The paper would require a major revision in order for the reader to appreciate its contributions. At this stage, the significance and potential impact of the work are limited because of the poor clarity of the paper and because of the lack of discussion or guarantees on the recovery of the true mixing matrix depending on the choice of random communciation model.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies Personalized Decentralized Bilevel Optimization (PDBO). Based on Stochastic Gradient Push (SGP) method, the authors propose Hyper-Gradient Push (HGP) method to estimate the hypergradient and analyze the estimation error of its variance-reduced version (VR-HGP). On top of the hypergradient estimation, they conduct experiments to solve PDBO problems and compare its performance to some existing algorithms.

strength_and_weaknesses: Pros:
1. This paper considers the general setting in decentralized training, i.e., the network is stochastic and directed.

 2. The formulation of PDBO is more general than previous papers, as discussed in Section E and Table 3 of the appendix.
        
3.  HGP method does not require computing exact Hessian or Jacobian, which is an improvement comparing to previous CDBO papers.

Cons:

1. Reformulating Eq. (5) as Eq. (6) is reasonable in practice (and is true under Assumption 2). However, in theory technically speaking the condition $y_i^* = y_i^{(T)}$ in Assumption 2 is unusual. It would be good if the reformulation (Eq. (6)) of Eq. (5) can be theoretically justified (e.g., via some error estimation) without assuming $y_i^*=y_i^{(T)}$ in Assumption 2.

2. (Assumption 2) The authors claim "To apply implicit differentiation, we introduce the following assumption as in Grazzi et al. (2020)", but is "$y_i^* = y_i^{(T)}$" assumed in Grazzi et al. (2020)? It seems that in Grazzi et al. (2020) they only require $y^*$ to be unique instead of accessibility in $T$ steps. "$y_i^*=y_i^{(T)}$" seems to be a strong assumption that is not included in papers about non-asymptotic convergence of bilevel optimization. Besides, carefully analyzing the error incurred by $\|y_i^* -y_i^{(T)}\|^2$ is not a trivial problem in bilevel optimization literature. For example, Chen et al. (2022) uses a novel way to deal with this error (see Lemma 3 therein and the order of $T$ in Theorem 1 and Proposition 2) and successfully reduce the sample complexity comparing previous works on bilevel optimization.

3. (Theorem 1) This theorem characterizes the hypergradient estimation error. How can we apply this in real PDBO algorithms to solve (5)? Should we just use $v^{(\lambda)} + c^{\lambda}$ as the hypergradient and then use single-agent gradient descent, or should we still run some decentralized algorithms to solve (5)? It is unclear how we should use the estimation (i.e., $v^{(\lambda)} + c^{\lambda}$) mentioned in Theorem 1 to run PDBO. It would be better if there is another theorem characterizing the convergence results (e.g., sample complexity) of PDBO using this estimation.

4. (Mini-batch) We need to use mini-batch method (i.e., setting $b$ in Theorem 1 to be large enough) for HGP. However, some of the previous CDBO papers (e.g., Yang et al. (2022)) do not require mini-batch method.

Questions: 

 ("Suppose the i-th client is responsible for computing the i-th block of $u^{(m+1)}$ and $v^{(m+1)}$, ...", Section 4.2.) What happens after all the agents finish the computation of their own blocks? Is there a central node collecting all the blocks to obtain $v^{(M)}$?

References:

[Chen et al., 2022] T. Chen, Y. Sun, and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient
methods for bilevel problems. Advances in Neural Information Processing Systems, 34, 2021.\\

[Grazzi et al., 2020] R. Grazzi, L. Franceschi, M. Pontil, and S. Salzo. On the iteration complexity of hypergradient
computation. In International Conference on Machine Learning, pages 3748–3758. PMLR, 2020.\\

[Yang et al., 2022]S. Yang, X. Zhang, and M. Wang. Decentralized gossip-based stochastic bilevel optimization over
communication networks. arXiv preprint arXiv:2206.10870, 2022.
clarity,_quality,_novelty_and_reproducibility: The quality, clarity and originality of the work need to be improved. See Strength And Weaknesses.
summary_of_the_review: Overall, I feel that the proposed method has several benefits than previous ones, but there are quite a few limitations and questions left. I tend to reject this time, but am open to increase the evaluation based on the other reviewers' comments and the authors' response.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the problem of Personalized Decentralized Bilevel Optimization (PDBO). The authors first introduce a gradient-based
bilevel optimization that reduces most personalization approaches to the optimization of client-wise hyperparameters.  Based on Stochastic Gradient Push (SGP) method, the authors propose Hyper-Gradient Push (HGP) method to estimate the hypergradient and analyze the estimation error of its variance-reduced version (VR-HGP). Also, experimental results are provided to solve PDBO problems and compare its performance to some existing algorithms.

The reviewers had some initial concerns, many of which were alleviated by the author response, but some still remain (please see the reviews). In particular, the reviewers still felt unconvinced about the basic assumptions as well as how strong is the role of mini-batches. Once these concerns are addressed (in a new version), the paper will provide a set of nice contributions. 


justification_for_why_not_higher_score: Two of the reviewers were in favor of rejecting the paper. 
justification_for_why_not_lower_score: -
Decision: Reject