Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a new algorithm, Prometheus, for the composite stochastic bilevel optimization problem in the decentralized setting. In particular, the paper considers the setting where we have a distributed optimization problem on $m$ agents, each of which has a loss function of the form $l(x) + h(x)$ where $l(x)$ has bilevel, finite-sum structure and $h$ is a constraint function with an easy-to-compute proximal operator. The agents are connected to each other via a decentralized network (i.e. there is no central node to exchange iterates with, and therefore the agents have to solve a consensus problem as well during the optimization process). The bilevel optimization problem is nonconvex-strongly-convex (the outer function is nonconvex and smooth, the inner function is strongly convex), this problem has been solved before in the decentralized setting, but only with simple projection constraints (e.g. as in [1]). The algorithm introduced here, Prometheus, solves this problem in the setting where $h$ can be an arbitrary constraint but whose proximal operator is easily computed. Prometheus achieves the same communication complexity and local sample complexity as INTERACT-VR from [1], but can do so under more difficult constraints.

[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. MobiHoc 2022
strength_and_weaknesses: - (Strength) The introduced algorithm, Prometheus, achieves a sample complexity of $\mathcal{O} (\sqrt{n} K \epsilon^{-1} + n)$. This is currently the best-known sample complexity for finite-sum stochastic bilevel optimization problems. The same can be said for the communication complexity $\mathcal{O} (\epsilon^{-1})$.

- (Strength) The proposed algorithm can handle complex constraints through the use of the proximal operator, enabling more applications than previous algorithms.

- (Strength) The authors introduce a new recursive estimator for the stochastic gradient of the bilevel problem (see eq. 5), and this new estimator seems to show some benefits in practice over the conventional estimator used by previous works.

- (Weakness) The authors do not give many examples of the constraints their algorithm can solve, and their relevance to practice. The motivating examples all do not really make use of the new proximal formulation. 

- (Weakness) The benefits of the new recursive estimator are only illustrated in one experiment, and it is difficult to see the benefit since Figure 1 only tests out this estimator on a single matrix with fixed norm. Can you plot how the estimator performs for varying norm of ||A^-1||? How about with increasing variance? There is too little information to figure out how it performs empirically.

- (Weakness) It is not clear why the ordinary inverse Hessian estimator does not work for this problem, given that it works just fine for INTERACT-VR and achieves the same rate for the unconstrained setting.

- (Weakness) The discussion about the necessity of VR is a little misleading. The authors introduce a variant of Prometheus without variance reduction, and then give an upper bound for this variant that shows it does worse than the variance-reduced version. However, this is not a correct way to show the necessity of some technique-- at best, it provides some evidence for this and nothing more. The correct way would be to give a lower bound, but no such lower bound is given here.

- (Weakness) The authors do not really explain why the proximal setting is significantly more difficult than the projected setting. In ordinary, non-bilevel, stochastic optimization, the extension from the projected case to the proximal case is very simple and straightforward. What is the source of difficulty here?
clarity,_quality,_novelty_and_reproducibility: - (Quality and Clarity) The paper is reasonably well-written, though I believe a table of notation would be immensely helpful. There is so much notation in the paper and it is very easy to get lost.

- (Reproducibility) While the main contribution of the paper is theoretical, the code used to run experiments is not provided. Therefore, the paper's experiments are not reproducible. This reduces the value of the paper for future work that would seek to build on it.

- (Novelty) While the paper relies on SARAH/SPIDER-style estimators for variance reduction, it introduces a new estimator for the stochastic gradient of the bilevel problem that is interesting in its own right. The algorithm Prometheus as a whole isn't very novel outside of this, and as the authors state can be seen as an extension of INTERACT-VR [1] to the proximal case.


[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. MobiHoc 2022
summary_of_the_review: I think this is a paper which is quite borderline, but for which the weaknesses outweigh the strengths. My biggest concern with this paper is that I am not sure where the difficulty is in the new proximal setting. I cannot really see it in the proof, and I don't think it is highlighted enough. Moreover, the experimental evaluation is not enough to see the benefits of some of the proposed techniques (like the new stochastic gradient estimator). The discussion on the necessity of variance reduction is somewhat flawed (for the reason outlined above), and as such I'd prefer to see that section rewritten as well.

-----------------------

Post-rebuttal summary: 
I thank the reviewers for their long, detailed responses. The examples given are satisfying to me, and I think there is some technical difficulty that the authors have overcome here. However, after discussion with other reviewers, I am not convinced the technical novelty here may not be enough, especially given that the Hessian estimator used is not novel. As such, I can not recommend acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors study the problem of decentralized stochastic bi-level optimization problems with upper level constraints. The authors propose Prometheus, an algorithm that combines ideas from bi-level optimization, proximal gradient computation for constrained optimization, variance reduction for stochastic optimization as well as gradient tracking for decentralized optimization. With all of the components combined, the algorithm achieves $O(1/\epsilon)$ communication and sample complexity, a state of the art result. To demonstrate that at least some complexity is necessary, the authors showcase that even removing one component, variance reduction, can lead to solutions that do not asymptotically converge to the true solution. The theoretical results are complemented with experimental evaluations.
strength_and_weaknesses: Regarding strengths, to the best of my knowledge no other work has jointly combined tools from variance reduction, decentralized optimization, proximal gradients for constrained optimization and bi-level optimization in a single algorithm. All of the tools are unified in a single analysis in order to obtain an optimal sample and complexity result.

Regarding weaknesses, there are two points where additional elaboration may help make the contribution of this work clearer.

In Section 4.1.2, the authors propose a new Hessian inverse estimator that is based on the Taylor series approximation for the inverse matrix. To me it seems very similar to the Hessian inverse estimator of [1]. It also uses the same Taylor approximation formula and the same recursive update. Could the authors elaborate on the differences with [1]?

In Section 4.4, the authors highlight that variance reduction is necessary to achieve the $O(1/\epsilon)$ convergence rates in sample and communication complexity. My understanding is that this phenomenon would also appear in a stochastic optimization problem with domain constraints. This is independent of the source of the noise (sampling of $f$ or $g$) and orthogonal to the decentralized aspect. It would be appreciated if the authors would highlight which aspects of 4.4 are unique to their problem.



[1] Pang Wei Koh, Percy Liang, Understanding Black-box Predictions via Influence Functions, ICML 2017

clarity,_quality,_novelty_and_reproducibility: In terms of clarity, I refer the authors to the points above. The writing is of high quality and the problem studied is novel. Providing the code or at least code samples would make the results even more reproducible.
summary_of_the_review: In summary, I am in favor of accepting this work and I am open to further increasing my score if the authors address my concerns above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies constrained decentralized bilevel optimization where the inner-loop problem is finite-sum, smooth and strongly convex,  and the outer-loop problem is finite-sum, smooth and nonconvex. By combing (a) gradient tracking, (b) variance reduction and (c) a pseudo-gradient trick based on proximal operator, the paper designs a decentralized algorithm with both sample complexity and communication complexity matching the unconstrained setting.
strength_and_weaknesses: # Strength

- I find this paper very well written. Since I am unfamiliar with the previous  literature in this topic, the clean and concise writing of this paper makes it quite easy for me to understand the intuition behind the algorithm and the key ideas in the proof.

- This setting seems to be important, and hasn't been addressed by previous works. The designed algorithm looks quite reasonable and the derived complexity aligns with my intuition for finite-sum optimization and two-timescale style algorithms.

# Weakness (and questions)

- Since the inner-loop problem is strongly convex and smooth, one could expect that (also easy to show?) the $y_i$ variable will always stay sufficiently close to $y_i^\star (x_i)$. This means the analysis of the proposed algorithm is very similar to the existing works for distributed composite smooth nonconvex optimization? Therefore, it is a bit unclear to me how much technical novelty the submission possesses in terms of either algorithmic design or techniques used in the analysis.

- This is a rather general question about the motivation of considering general topology in decentralized optimization: Can you provide a non-artificial practical problem where the network topology is not a star and the network-consensus matrix trick is indeed deployed for the sake of distributed optimization? I'd like to see some real application with supportive reference, not just some scenario that only exists in the introduction of a theory paper. 

# Technical correctness

I only performed a high-level check of the proofs and they look correct to me.



clarity,_quality,_novelty_and_reproducibility: In Table 1, do you mean $m$ by $K$?
summary_of_the_review: Overall, I am positive with the submission and am willing to support its acceptance if my questions can be well addressed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper considers the problem of constrained decentralized stochastic bilevel optimization, and proposed an algorithm that achieve the same rate as Liu et al. 2022, but can additionally address the constrained and non-smooth setting. Compared to Liu et al. 2022, the algorithm proposed in this paper further use techniques of the proximal steps and different Hessian estimator. 

This is a borderline paper has both pros and cons. During the AC-reviewer meeting, reviewers agree that the results are new and solid. However, they found that proximal steps relatively standard in optimization to dealing with constraints and non-smoothness. Even though reviewers agree that the proximal extension may not be trivial in the setting of bilevel optimization, they are not convinced why analyzing the proximal steps are very challenging in this setting. The Hessian estimator used in this paper is almost the same as Koh and Liang 2017. Although authors claim difference in two "key aspects" in the revised version, both differences look minor. We believe this paper would improve significantly if it can properly highlight the true challenges of this paper compared to Liu et al. 2022, and justify why the new results are novel and significant (instead of just a relatively expected extension from prior works). Given the current form we recommend rejection.
justification_for_why_not_higher_score: This paper reads incremental comparing to Liu et al. 2022, the additional technical novelty may not be sufficient for ICLR.
Decision: Reject