Bilevel optimization has gained prominence in various applications. In this study, we introduce a framework for solving bilevel optimization problems, where the variables in both the lower and upper levels are constrained on Riemannian manifolds. We present several hypergradient estimation strategies on manifolds and analyze their estimation errors. Furthermore, we provide comprehensive convergence and complexity analyses for the proposed hypergradient descent algorithm on manifolds. We also extend our framework to encompass stochastic bilevel optimization and incorporate the use of general retraction. The efficacy of the proposed framework is demonstrated through several applications.
Paper
Similar papers
Peer review
Summary
This paper studies Riemannian bilevel optimization, where variables of both lower and upper level problems are constrained on Riemannian manifolds. The authors propose several hypergradient based algorithms via Neumann series and automatic differentiation. Convergence analysis is provided for the proposed approaches. Experiments on synthetic problems, hyper-representation learning, meta-learning, unsupervised domain adaptation are provided to demonstrate the effectiveness of the proposed methods.
Strengths
1. The studied topic is of interest to bilevel optimization research. As far as I know, this should be the first work to study this type of research. 2. The analysis is comprehensive. The algorithms cover AID and ITD based hypergradient approximations. 3. Quite a few experiments are provided to support the theory.
Weaknesses
1. More motivation examples should be provided to validate the importance of bilevel optimization on manifolds. In the experiments, for example, in manifold meta-learning, it would be good to compare the method with meta-learning methods without the orthogonality constraint. 2. Assumption 1 may be quite strong. It requires all iterates z_1,…, are bounded in a compact space. The analysis in previous standard bilevel optimization does not require this assumption. 3. Main results contain complex constants and are a little bit hard to parse. Some simplifications may be helpful here. 4. The extension in 3.3 will be more interesting if Hessian-vector rather than Hessian-inverse is considered.
Questions
See weakness for information.
Rating
7
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
See weakness for information.
On Assumption 1: I agreed with the concerns raised by Reviewer 4rfq regarding Assumption 1, which is typically a strong assumption in bilevel optimization. As I am not very familiar with the literature on manifold optimization, I am not very confident in validating the correctness of this assumption. Hope the authors can provide more evidence here. I found several related works on bilevel optimization on manifolds, e.g., [1][2]. I wonder whether similar assumptions are also made there. [1] Riemannian Bilevel Optimization, Li and Ma, 2024. [2] Riemannian Bilevel Optimization, Sanchayan Dutta, Xiang Cheng, Suvrit Sra, 2024.
Thank you for your further comments. We kindly refer you to our responses to Reviewer 4rfq regarding clarifications on Assumption 1. In summary, we have revised Assumption 1 to only require domain compactness and unique geodesic for the lower-level problem. Such an assumption is unavoidable in the Riemannian optimization literature. Regarding your question on whether similar assumptions are used in [1,2], **yes, both [1,2] use assumption on the bounded domain.** Specifically: - [1] states explicitly in Assumption 4.2 that $\tau(\iota, \text{dist}(y^{k,t}, y^*(x^k)))$ is bounded by $\tau$ for all $k, t$. Because by the definition of $\tau(\iota, c) = \frac{\sqrt{|\iota| } c}{\tanh(\sqrt{|\iota|}c)}$, $\tau(\iota, c) $ is an increasing function over $\iota, c$. Thus bounded $\tau(\iota, c)$ suggests a bounded domain, i.e., $\text{dist}(y^{k,t}, y^*(x^k)) \leq D$ for all $k, t$ for some constant $D$. - [2] also requires such an assumption, which can be seen from Page 30 where they also require a constant upper bound on $\tau(\kappa, d_{\mathcal{N}} (z_k^{(t)}, y_k^*) )$ for all $k, t$, which implies a bounded domain. -------------------------------------------------------- We hope this addresses your concern, and we will incorporate additional discussions in our revised paper. As the discussion period deadline approaches, we would greatly appreciate your acknowledgment of our responses if there are no further questions. Thank you again for your time. [1] Riemannian Bilevel Optimization, Li and Ma, 2024. [2] Riemannian Bilevel Optimization, Sanchayan Dutta, Xiang Cheng, Suvrit Sra, 2024.
Summary
The paper proposes an RHGD algorithm (Algo 1) to solve the bilevel optimization problems (line 11). - Thm 1 proves the convergence to a stationary point of $F$ when using different approximations of the hypergradient. - Thm 2 shows the convergence under stochastic setting. - Thm 3 proves the convergence with cheaper retraction. Both synthetic numerical tests and applications to real problem are provided.
Strengths
The paper is well-written. The theoretical results are solid and the contributions are new to me. The algorithm is fully implementable. What I like is the convergence is not only established for the Hessian inverse but also its cheaper approximation. The synthetic experiment is carefully designed.
Weaknesses
1. Assumption 1 is too strong: it requires the trajectory of $z$ to be in the unique geodesic neighborhood of $z^*$. 1. Assumption 2 is slightly too strong, does this mean many simple functions like quadratic functions: $f(x, y)=|x|^2+|y|^2$ do not satisfy this assumption?
Questions
1. Could you please clarify the synthetic problem in Sec 4.1 satisfies all the assumptions? I only find that Assumption 3 is verified. Assumption 2 is automatically satisfied due to the compactness of the Stiefel manifold. However, could you clarify how to verify Assumption 1? 1. Maybe it is a dumb question, but in Sec. 3.1, why HINV and AD are different?
Rating
8
Confidence
4
Soundness
4
Presentation
4
Contribution
4
Limitations
Small typo: In line 112 there are 2 negative signs.
Summary
This paper presents a framework for addressing bilevel optimization problems in which variables of both lower- and upper-level problems are constrained on Riemannian manifolds. It introduces multiple hypergradient estimation strategies on manifolds and investigates their estimation error. The paper includes convergence and complexity analyses for the proposed hypergradient descent algorithm on manifolds. Furthermore, it extends these advancements to stochastic bilevel optimization and the utilization of general retraction on the manifolds. The paper also demonstrates the practicality of the proposed framework through several applications.
Strengths
1. The paper is well-written and is easy to read. 2. This paper derives the intrinsic Riemannian hypergradient using the implicit function theorem, proposes four strategies for estimating the hypergradient, and provides estimation error bounds for all the proposed strategies. 3. This paper presents the Riemannian hypergradient descent algorithm for tackling bilevel optimization problems on manifolds, providing convergence guarantees. Furthermore, it extends the framework to the stochastic setting and incorporates retraction mapping on the manifolds.
Weaknesses
1. Firstly, my primary concern pertains to the novelty of this paper. The algorithm proposed in this paper appears to mirror the framework introduced in a prior work [42]. Therefore, it is crucial to delineate the similarities and disparities between this paper and the referenced study [42]. 2. The experimental results should include a comparison with the methods presented in [42]. 3. The analysis of retraction on manifolds lacks depth and should include the convergence results of three additional hypergradient estimators. 4. Assumption 1 seems to be excessively strict, which is unusual in common bilevel optimization. Moreover, the notation $D$ in $d(x_1,x_2)\le D$ may be confusing. Furthermore, Assumptions 2 and 3 could be inferred from Assumption 1, indicating that this paper may not necessitate Assumptions 2 and 3.
Questions
1. The notations $C_{hinv}$, $C_{cg}$, $c_{ns}$, and $C_{ad}$ in Theorem 1 are not utilized in the main body of the paper. 2. Can the stochastic bilevel problem studied in this paper be extended to the general stochastic setting, i.e., $\underset{{x\in \mathcal{M}_x}}{\min} F(x) = \mathbb{E}[f(x,y)]$ and $y^*(x) = \underset{y\in\mathcal{M}_y}{\text{argmin}}~ \mathbb{E}[g(x,y)]$? 3. For other questions, please see the weaknesses above.
Rating
6
Confidence
4
Soundness
3
Presentation
3
Contribution
3
Limitations
NA
Summary
This paper introduces a novel approach for solving bilevel optimization problems where both upper and lower-level variables are constrained on Riemannian manifolds. The authors propose four hypergradient estimation strategies (HINV, CG, NC, AD), analyze their estimation errors with convergence and complexity analysis, and generalize to stochastic bilevel optimization and general retraction. The paper also shows many applications of the framework including hyper-representation over SPD matrices, Riemannian meta-learning, and unsupervised domain adaptation.
Strengths
1. The proposed framework extends bilevel optimization to Riemannian manifolds, which fills a gap in this field. 2. The paper introduces multiple hypergradient estimation strategies and provides a thorough theoretical analysis. 3. Practical Relevance: Demonstrates the applicability of the framework through several machine learning applications, including hyper-representation and meta-learning.
Weaknesses
1. Assumptions: The framework relies on assumptions such as geodesic strong convexity and Lipschitz continuity, which may limit its applicability in some practical scenarios. 2. The practical performance evaluation is limited to synthetic and small-scale problems, which may not fully represent its utility in large-scale real-world applications.
Questions
1. What are the computational trade-offs when choosing between the different hypergradient estimation strategies?
Rating
6
Confidence
3
Soundness
4
Presentation
2
Contribution
3
Limitations
The authors acknowledge that the framework relies on some strong mathematical properties that limit its broader applicability and may be improved in the future.
Thanks so much for the responses. I will keep my rating and raise my confidence.
Summary
This paper addresses bilevel optimization problems where variables of both the lower and upper-level problems are constrained on Riemannian manifolds. To solve such problems, the authors propose a hypergradient descent algorithm under the key assumption that the lower function is geodesically strongly convex and establish its iteration complexity. To efficiently estimate the hypergradient, several methods with error bounds are also proposed. Additionally, the paper provides several interesting application examples of bilevel optimization on Riemannian manifolds and presents numerical results for these examples.
Strengths
- This paper generalizes the widely used hypergradient descent algorithm to the Riemannian manifold setting and provides a comprehensive analysis of the proposed algorithms. - The paper includes four approaches to estimating the inverse of the Riemannian Hessian and a stochastic version of the proposed algorithm. - The theoretical analysis is solid, with estimation error bounds and the iteration complexity of the proposed algorithm presented. - The numerical results are extensive, showcasing results on four interesting Riemannian bilevel optimization application examples.
Weaknesses
- A closely related work is [42], and although the authors claimed key differences in Section 1, some points should be clarified. - The various hypergradient estimators beyond conjugate gradient and Neumann might be standard. Do the other estimators show better performance? - While the paper presents interesting applications (see instances given in Section 4.2), these problems can also be solved by the methods in [42]. The authors should provide a numerical comparison of the methods. - Shall the authors include the complexities of the methods in [42] in Table 1? - The estimations of the inverse Hessian are also widely used in Euclidean space. - The assumption of geodesic strong convexity for the lower function is too strong for the Riemannian setting, making the application examples in the paper less typical. Additionally, it should be noted that the lower-level problem in Section 4.2 is constrained in Euclidean space.
Questions
1. Why are the performances of “hinv-20” and “hin-50” similar in Figures 1(a) and 2(a)? 2. Why is “hinv” more efficient, as shown in Figure 1(b)?
Rating
6
Confidence
4
Soundness
3
Presentation
3
Contribution
3
Limitations
Yes, the limitations are acknowledged.
I would like to thank the authors for their responses. I am raising my score to 6.
I thank the authors for the response. My concerns are addressed. I keep my score.
Dear authors I appreciate your detailed rebuttal and I am so sorry for replying a little late. W1: I don't agree assumption 1 is an 'unavoidable requirement'. In the rebuttal, the author gives some examples of papers using the same condition, and I will take one of them [63] as an example. They require the manifold to be Hadamard, i.e., unique geodesics (I understand you must require unique geodesic for convex function to exist). However, I don't see any requirement for the iteration to be in a compact set in that paper. Could you please point out where is ' All iterates are contained in a compact neighbourhood' in that specific paper? The rebuttal also states 'This assumption can be satisfied for compact manifolds and by restricting the domain of interest.' I don't think the problem is that trivial because 1. compactness manifolds with no boundary (e.g., Stiefel manifold) leads to the non-existence of convex functions and non-existance of unique geodesic. 2. if you restrict the domain, how can you guarantee the iteration stays in that domain? This is the reason I think the assumption is too strong. W2: I agree with you it can be inferred from assumption 1. But again, assumption 1 is too strong, making me think assumption 2 is too strong. But I can take assumption 2 if you convince me assumption 1 is not strong. Q1: I am so sorry I do not think my question is that trivial. For Stiefel manifold, compactness in Assumption 1 is automatically satisfied, but where is unique geodesic (smooth inverse of exponential)? For SPD manifold, it is not that simple. What you really do is, fix a domain -> fine a step size as stated in Thm. 2, i.e., step size depends on the selection of domain. How can you simply run the algorithm and then find the domain containing all iterations? What is your step size in this case? Q2: thank you for the clarification. Best wishes reviewer
We sincerely appreciate the follow-up questions and would like to take this opportunity to address them in detail. We understand that our previous response statement "This assumption can be satisfied for compact manifolds and by restricting the domain of interest" (given as part of our response) might not be appropriate. What we mean is compact **subset** of a manifold, which allows unique-geodesic and geodesic convex functions. This is, for example, considered in [63] for analyzing geodesic (strongly) convex functions. All the theorems, i.e., Theorems 9, 10, 11, 12, 13, 14, 15 assumes a bounded domain and make use of the diameter of the domain $D$, which is defined in Theorem 9. With the above clarifications, we proceed to answer your individual questions. **1. On Assumption 1.** Regarding our Assumption 1, we now believe that our current phrasing in the paper may have caused some confusion. We wish to clarify that our analysis only requires the unique geodesic specifically for the manifold associated with the lower-level problem. We also highlight that the compactness requirement for the upper-level problem is not strictly necessary for analysis. The compactness assumption on the upper-level problem was initially included to facilitate a more natural interpretation of Assumptions 2 and 3. However, in contrast, for the lower-level problem, compactness on the domain and the uniqueness of the geodesic are essential for establishing linear convergence, based on [63]. We plan to rewrite Assumption 1 as follows. **Assumption 1.** All the iterates in the lower level problem are bounded in a compact subset that contains the optimal solution, i.e., there exists a constants $D_k > 0$, for all $k$ such that $d(y_k^s, y^*(x_k)) \leq D_k$ for all $s$. Such eighbourhoods admit unique geodesic. We take $D := \max_{k} (D_1, ..., D_k )$. **2. Could you please point out where is 'All iterates are contained in a compact neighbourhood' in that specific paper?** In Theorem 15 of [63], when analyzing convergence for geodesic-strongly convex functions, the the definition of parameter $\epsilon = \min (1 / \zeta(\kappa, D), \mu/ L_g )$ depends on the diameter of the domain $D$, which is defined in Theorem 9. This suggests the bounded domain is still assumed in the analysis, and thus corroborates our claim that the bounded domain assumption is unavoidable in this case. **3. On Assumption 2.** We remark that Assumption 2 is also made in the Euclidean bilevel analysis [35], even without assuming Assumption 1. See the first bullet point of Assumption 2 in [35] where function Lipschitzness implies bounded gradient. **4. Stepsize depend on selection of domain.** This is a misunderstanding. First, we do not 'select' a domain. The bounded domain is mainly introduced for analysis purpose as we have explained above. Second, we do not choose stepsize based on the domain. The stepsize is selected based on the Lipschitz constants of the objective function, i.e., from Assumption 2, 3. This is also the case for Euclidean bilevel analysis [35]. See, for example, Theorem 1 in [35]. As commented above, Assumption 2 can be made independent of the Assumption 1, and thus, the stepsize can be chosen independent of the domain. ------------------------- In summary, we sincerely thank you for all the questions, which have largely helped to improve the clarity of the paper. We will ensure a more clear presentation and discussions of the assumptions in our revised version. In particular, we will include the revised assumption as given above. Given the rebuttal discussion is coming to the end, we would greatly appreciate if you could kindly acknowledge our response if there are no further questions. Thank you again for your time.
Dear authors and reviewer JBnb I appreciate your comment and I learn a lot from it. I also thank reviewer JBnb for the insightful discussion. I am fully convinced that assumption 1 is not strong. I am not convinced by 4 in the last reply by the authors, but I don't think that stops me from liking the paper anymore. I still believe that assumptions 1 and 2 are uncheckable for your example but that happens in curved spaces since manifolds are complicated. In summary, I didn't check all the technical details in the paper, but I like the paper, I think the topic matches the conference and the contribution is clearly shown. I would increase my rating. Best wishes reviewer
Thank the authors for clarification. I have increased my score to 6.
Thank you!
Dear ACs and Reviewers We are greatly encouraged that our rebuttals have effectively addressed your concerns, resulting in positive adjustment to the scores (Reviewer CDbu, Reviewer Bnza, Reviewer 4rfq) and to the confidence (Reviewer kqCt). We sincerely appreciate your recognition of our contributions as well as the constructive feedback that has improved our paper. Thank you for your invaluable time and insightful comments throughout this process. Regards Authors
Decision
Accept (poster)