Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors formulate a new min-max multi-objective bilevel optimization problem and applied it in robust ML and HPO.
They also proposed a new algorithm to find a solution to the proposed new problem and establish its convergence rate and computational complexity.
strength_and_weaknesses: Strength
1. The authors did a thorough literature review w.r.t. robust learning and multi-task learning.
2. The authors created a new MOO bilevel problem, proposed a solution to it, and established its convergence rate.

Weaknesses
1. The main issue with this work is that the paper is trying to create an (unnecessary) multi-objective optimization (MOO) problem and address it. It is challenging to understand the benefit of formulating a MOO problem as a bilevel one instead of summing the objectives and using a single-objective solver or generating multiple Pareto-optimal solutions. Specifically, it is worth comparing the proposed formulation with the Pareto-optimal solutions considering that the proposed one only gives one robust solution and the Pareto front gives a full set of solutions. What is the complexity difference? What is the convergence difference? Besides, the Parent solution can be generalized easily to nonconvex use cases but can the proposed algorithm be extended to the nonconvex cases? How can the proposed one be justified to be beneficial? 
2. It is also interesting to convert problem (2) to (3) by replacing the objective in the leader problem with a weighted sum of multiple objectives. Though the equivalence might be straight for the authors, it seems not the case for the majority of readers. It will be good to prove why these two formulations are equivalent.
3. Equation (2) has a quite strong assumption that there are n different objective function pairs (fi, gi), i.e, the number of objectives in the leader problem and the follower problem is the same. This is usually not true considering that the number of leaders and the number of followers are usually not of the same magnitude.
4. The examples given in the introduction part, e.g., safety-critical, scenario-specific, etc are very unclear. What is a concrete example whose formulation is like (2)? This formulation is also different from the existing MOO works in Sinha et al., 2015; Deb & Sinha, 2009; Ji et al., 2017.
5. The authors assume the LL problem is unconstrained strongly convex and the UL problem is constrained weakly convex. This is again a very strong assumption and hardly satisfied in reality considering the main application is in RL and HPO.
6. For this iterative algorithm, how to choose the three learning rates alpha, beta and gamma are critical. The authors only give the chosen numbers at the end of the appendix but did not give any intuition on how they are selected especially how this matches what Theorem 1 suggested regarding these three learning rates.
7. In Theorem 1, the bias norm is bounded by a sequence bk. How to verify that b_k^2 <= alpha in practice?
8. The writing needs to be polished.
a. At the end of the first paragraph, there is typo 'Similar'.
b. In Table 1, it is not fair to list the problem solution and solving strategy together. Specifically, the single loop should not be listed with other columns.
clarity,_quality,_novelty_and_reproducibility: The authors present the problem formulation and their proposed solution clearly.
The problem formulation and the proposed algorithm are both original works.
Considering the complex parameter settings of the proposed algorithm, It is necessary to have the open-sourced code to reproduce all results in this work.
summary_of_the_review: The framework and algorithms are novel enough but the benefit of the way formulating the problem compared with the existing MOO formulation is skeptical. The strong assumption w.r.t. the leader and follower problems is another concern. Considering this, it is hard to recommend its publication in its present form.

------------------------
I have read the authors' replies. The response has not significantly changed my view of the paper, and thus I would like to keep the same score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies robust solution for bilevel optimization under min-max multi-objective form. The main idea is build the problem by a min-max upper-level objective function and using weighted sum of weakly convex functions li instead of a single weakly convex function. To solve such a problem, the SGD(projected SGD) to iterate $y$, $x$ and $\lambda$. Some applications such as robust representation learning and robust hyperparameter selection  are provided to evaluate the performance. 
strength_and_weaknesses: Pros:
1. This paper builds a frame for such a specific bilevel optimization problem, which has not been considered before. The proposed algorithm is simple and easy to implement with a single-loop structure. 

2. In the reformulated problem in (3), the upper level problem turns to optimization a maximization problem over a simplex. This new component requires some new treatments.  Comprehensive convergence rate analysis is provided to justify the algorithmic designs. 

3. The algorithm itself is easy to understand and apply. Experiments seem to support the proposed algorithm well. 

Cons:
1. Excluding the nicely designed problem itself, the algorithm is not that surprising given existing single-loop algorithms such as Hong et al., 2020 in bilevel optimization. It looks like applying SGD (projected-SGD) to a specific problem. I wonder how the authors implement the hypergradient in practice? Is there any instructions here? 

2. For the experiments, e.g., in Fig. 5, why does the variance look so large? 

3. The analysis seems to follow from TTSA (Hong et al., 2020), and yields a similar rate of $K^{-2/5}$. It seems that some other SGD types of bilevel methods like stocBiO (Ji et al., 2021) have better complexity. Can it be used here for improved complexity?

4. It seems to me that the complexity still has space to be improved using some strategies like variance reduction. Can the authors elaborate more on this? 
clarity,_quality,_novelty_and_reproducibility: The quality, clarity and originality of the work need to be refined. 
summary_of_the_review: Overall, I feel this work does a good job in designing a novel from of bilevel problem. It provided a precious frame for further and finer solution. I tend to accept this work but with a conservative score given the above questions. However, I am open to change my mind based on other reviewer’s comments and the authors’ feedbacks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors consider a class of bilevel optimization problems in which he objective function of the upper level is a maximum over $n$ different functions for each one a separate lower level problem is given. In particular, they propose a single-loop algorithm in which a gradient descent update is performed for both upper and lower level decision variables per iteration. The authors then provide simple complexities of finding a stationary point of the upper level problem and optimal solutions of the lower level ones.
strength_and_weaknesses: The problem under consideration is interesting, however, a similar problem already studied by (Hu et al., 2022) with minor differences. Moreover, their sample complexity is in the order of ${\cal O}(1/\epsilon^2)$ which is better than the one in this work ${\cal O}(1/\epsilon^{2.5})$ when $n=1$. Thus, the authors need to discuss why their result is worse for the case of $n=1$. Moreover, a table is required to compare the proposed complexity bounds with the existing ones.
clarity,_quality,_novelty_and_reproducibility: The complexity results proposed in this work is worse than the best-known results. This needs to be clearly discussed and clarified. The authors need to show under which setting, their results are better and why it is specifically worse for the classical case of $n=1$.
summary_of_the_review: The paper needs more discussion and comparison with the existing works.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers robust, multi-objective min-max bilevel optimization problems. Such problems are motivated by applications such as multi-agent reinforcement learning and hyperparameter optimization. Their study with multiple objectives is initiated by this work. The specific assumptions about the upper level (UL) and lower level (LL) problems involve weak convexity for UL and strong convexity for LL. For this setting, the paper introduces an algorithm based on (projected) SGD applied to the two level problems. The paper proves that the proposed algorithm converges as $\tilde{O}(\sqrt{n}K^{-2.5}),$ where $n$ is the number of objectives in the formulation and $K$ is the number of iterations. The paper further illustrates how the proposed techniques can be used to address problems in robust representation learning and robust hyperparameter optimization.

The paper is written well and was judged technically sound, with non-trivial technical results. However, its relationship to TTSA (Hong et al, 2020) was not completely clear and should be discussed more in a revised version. The AC and the reviewers appreciated the originality and novelty of the overall approach, and hope that this paper will stimulate more research on related problems.
justification_for_why_not_higher_score: I did not see enough enthusiasm from the reviewers about the technical strength/novelty. 
justification_for_why_not_lower_score: I think it is worthwhile to publish papers with good conceptual contributions (instead of just looking for delta improvements to well established problems).
Decision: Accept: poster