A Gradient Method for Multilevel Optimization
Authors: Ryo Sato
Mirai Tanaka
Akiko Takeda
Venue: NeurIPS 2021 Poster (2021)
Keywords: multilvel optimization
hyperparameter optimization
gradient method

Abstract: Although application examples of multilevel optimization have already been discussed since the 1990s, the development of solution methods was almost limited to bilevel cases due to the difficulty of the problem. In recent years, in machine learning, Franceschi et al. have proposed a method for solving bilevel optimization problems by replacing their lower-level problems with the $T$ steepest descent update equations with some prechosen iteration number $T$. In this paper, we have developed a gradient-based algorithm for multilevel optimization with $n$ levels based on their idea and proved that our reformulation asymptotically converges to the original multilevel problem. As far as we know, this is one of the first algorithms with some theoretical guarantee for multilevel optimization. Numerical experiments show that a trilevel hyperparameter learning model considering data poisoning produces more stable prediction results than an existing bilevel hyperparameter learning model in noisy data settings.


Reviews:
[{"review_id": "vz2L8byttrJ", "reviewer": "Reviewer_RnFj", "summary": "Authors propose a gradient based method to solve multilevel optimization problems. In addition , they propose an new estimator based on a tr-level optimization problem, which seems to perform statistical better than usual bilevel hyperparameter optimization.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed estimator and algorithm seem very new to me. Theorems and experiments are convincing.\nThe main problem is the clarity of the paper: I spent quite a bit of time on the paper, and I did not understand the proposed algorithm.\nI would not be able to implement the algorithm myself.\n\nCould you instantiate the algorithm on a simple tri-level optimization example? (at least in appendix?) Maybe this would help to understand. (I spend some time on Figure 5 in appendix but it did not help me)\nIn particular I did not fully understand part 3.2 and part 4.1, I would recommend to try to smooth a little these parts\n\nIf authors manage to make the paper clearer, I will raise my score.\n\n--------------------------------------------------------------------------------------------------\n\nComments after author response.\n\nAuthors have answered my questions, I think the paper is interesting and significantly new.\nThus I will raise my score to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8h"}, "extra_text": {}}, {"review_id": "KLjmSABV0Ae", "reviewer": "Reviewer_gn5o", "summary": "The authors propose an approximate algorithm for multilevel optimization problems. The presented method can be considered an $n$-level extension of a related and previously published algorithm for bilevel optimization. It relies essentially on replacing optimal solutions in lower-level problems by respective $T$-step gradient descent approximations. That way, the original multilevel problem can be approximated in terms of an unconstrained problem depending only on top-level variables. After an an introduction and discussion of related work, the authors describe how the objective of the approximate problem can be differentiated with respect to the top-level variables. Moreover, assumptions are given under which the original problem admits an optimal solution. And it is shown that the optimal value of the approximate problem converges to a solution of the original problem in the limiting case $T\\rightarrow\\infty$. Finally, the authors report numerical results obtained through application of their method to two different trilevel optimization problems.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "From my point of view, this is an interesting paper. The original problem formulation **(1)** is very general and should be applicable in many contexts. However, as the authors also state in their conclusion, their method does probably not scale well to multiple levels. Moreover, I think that the presented numerical examples are somehow narrow because not only the level is limited to $n=3$ but also the number of optimization variables is in both presented examples quite small.\n\n In a maybe different but related context, the technique of using algorithmic iterates to replace optimal solutions of lower-level problems has been applied frequently (see, e.g., **Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing (Monga, Li, Eldar, 2021)** for a recent overview). I think, a few references to that body of work would have been appropriate.\n\nIn the numerical experiments section, the authors mention that they used automatic differentiation. I think it should be possible to minimize the approximate objective relying only on automatic differentiation. Maybe the authors could clarify whether they did so or used their own **Algorithm 1**, or a mixture of both.\n\nFinally, I have to say that I did not check the proofs in the supplementary material in detail. Apart from that, I would say that this is a borderline case where I tend to reject due to the mentioned limitations.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "IAlu2cNZB6h", "reviewer": "Reviewer_cJPD", "summary": "A gradient method for multilevel optimization is proposed with convergence guarantee demonstrated by both theoretical analysis and numeric experiments. This is initial theoretical work in nonconvex multilevel optimization. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This study focuses on theoretical study of multilevel optimization that has very few existing works. The advantage over these existing works is clear, i.e., this work has both nonconvex theoretical guarantee and experimental evidence. The extension from bilevel optimization methods and its convergence proof are non-trivial. Related work seems to be adequately cited. \n\nQuality: The proposed gradient method has convergence guarantee which is supported by both technically sound theorems and experiments. The weakness, i.e., large complexity under large n, is also supported by Theorem 6. The work is complete. However, it would be more convincing if you add analysis of convergence rate or computation complexity to achieve epsilon accuracy, and add numeric comparison with existing multilevel optimization algorithms (such as [19, 21]). \n\nClarity: This paper is clearly written and well organized. Some points may need more explanation which I will list later. \n\nSignificance: The results are important initial steps into the theoretical research of multilevel optimization, yet there are still many works for future research. I think the theoretical results are likely to be used and surpassed by future theoretical studies of multilevel optimization, and this gradient method could be applied to multilevel optimization applications of small n. (e.g. n=3). \n\nSome questions and advice:\n\n(1) You said your Assumption 1 is extended from [11], but I saw these assumptions in [12] not [11]. \n\n(2) In the equation right below eq. (5), I think $\\Phi_i^{t_i}$, $t_i$, $T_i$ should be $\\Phi_j^{t_j}$, $t_j$, $T_j$ respectively, yes? \n\n(3) At the end of your introduction, you said “For example, if it is extended recursively using T steepest-descent sequential updates at each level, the problem size can be increased with $T^n$ variables. On the other hand, our formulation has polynomial-size $nT$ variables. ” \nCould you explain how your method differs from “T steepest-descent sequential updates at each level” that uses $T^n$ variables? How did you decrease to $nT$ variables? \n\n(4) In Theorem 4, do you mean the “optimal function value”? \n\n(5) Typo: In line 2 of Algorithm 1: “for i:=2,…,n”.\n\n(6) In Theorem 6, how are p and q defined? What objective function-related variables or hyperparameters affect p and q. Also, do p and q<1 or >1? That I think makes much difference. \n\n(7) Since $\\widetilde{F}_1$ is $L$-smooth, convergence rate of $||\\widetilde{F}_1||$ (or maybe distance to a stationary point) is perhaps available, and the work can be more comprehensive if the overall complexity (defined as iteration complexity $\\times$ complexity per iteration in Theorem 6) to achieve $||\\widetilde{F}_1||<\\epsilon$ is provided. That might be added to supplementary due to the page limit.\n\n(8) In your first experiment, it converges significantly faster and in a more direct path to the optimal point with smaller T2 and T3, how to explain? How do T2 and T3 affect your second experiment? \n\n(9) In your first experiment, what is an update of $x_3$? Is it one implementation of line 5 of Algorithm 1 for i=3? Why do you use the number of updates of $x_3$? \n\n(10) In your second experiment, I think it better to define $||\\cdot||_{1^*}$ explicitly or cite the reference that has the definition. \n\n(11) In your second experiment, is this optimization problem borrowed from or inspired by any other references, or designed by yourself? If former, it is better to add citations. \n\n(12) It could be better to compare your gradient method with existing multilevel optimization algorithms in experiments, such as [19, 21]. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Both the authors and I agree that the major limitation is large gradient computation complexity for large n, so the authors left cheaper approximate gradient computation for future research. \n\nAnother limitation I think is the lack of overall computation complexity required to achieve epsilon-accuracy, which looks not hard to derive from the theorems in this paper. \n\nBoth the authors and I do not think this theoretical work could have any potential negative societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "I think this work has no ethical concerns.\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "About 4 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewer anonymously agree that this paper proposes a novel and non-trivial method for an important problem. Some reviewers have also raised concerns regarding clarity that have been addressed by the authors during the rebuttal phrase. I urge the authors to incorporate their feedback in the camera ready.
Decision: Accept (Poster)