Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: In this paper, the authors study a multi-block min-max optimization problem and propose a single-loop randomized stochastic algorithm to solve this class of problems with provable convergence rate guarantees. It is shown that the achieved convergence rate is in the same order as solving stochastic nonconvex optimization problems. Multiple numerical results show the effectiveness of the method on multi-task AUC problems.
strengths_and_weaknesses:  The strengths of this paper:

1, this work considers a very general bilevel optimization problem, which covers a wide range of machine learning problems as special cases.

2, a stochastic multi-block minmax bilevel optimization algorithm is proposed, which takes the block structure of the problem, stochasticity of data samples, and variance reduction into account.

3, this paper also provides the theoretical convergence rate analysis of the proposed algorithm and shows that the achieved rate matches the optimal complexity of nonconvex optimization under a general unbiased stochastic oracle model.

The weaknesses of this work are

1,  (originality) the problem seems a combination of minmax optimization and bilevel optimization, especially under the conditions that the subproblem w.r.t. maximization is strongly convex and the lower-level problem is also strongly convex. How to position the novelty of this problem and algorithms among the existing work is not clear.

2, (quality) The major contribution is the theoretical convergence rate analysis, but what are the challenges of showing this rate was not discussed technically 

questions: Besides the above comments, there are also several questions:

1, it seems that the main motivation for having this model was from [37]. Why is the lower-level problem importantly incorporated in this model?

2, the paper focuses on the multi-block model. Why does only $\alpha$ have multi-blocks? how about $x$?

3, the algorithm uses the momentum term. Will this should give a faster convergence rate？ or which step (min, max, or lower-level problem) restricts the final convergence rate?

4, In theorem 2.7, if $\eta_1$ and $\eta_2$ are chosen according to lemma 2.4 and lemma 2.5, then the algorithm should not converge to an $\epsilon$-stationary point unless they are decreasing or proportional $\epsilon$? (because there is a $T$ in front of  $\eta_1$ and $\eta_2$).

5, I am confused that how the lower-level problem is formulated between lines 258 and 259.

6, is there an optimal solution for the lower level optimization problem because it is just an unconstrained quadratic problem?

7, the authors claimed that $1/\epsilon^4$ is the optimal complexity for nonconvex optimization under a general unbiased stochastic oracle model. Which reference showed the lower bound in this case so that we can claim this is the optimal complexity? To my understanding, variance reduction or accelerated technique, in general, can have a better complexity, especially I suppose that the authors should clarify the conditions under which the algorithm can achieve the optimal complexity.

 
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of multi-block min-max bilevel optimization, where the dual variables and the associated lower problem are divided into blocks. To reduce the computational expense, this paper proposes to sample a batch of blocks at each iteration and perform update only for those blocks. In theory, the sample complexity of the proposed algorithm matches the optimal order for stochastic nonconvex optimization. The proposed method is then applied to multi-task deep (partial) AUC maximization, which can be formulated as a multi-block min-max bilevel optimization problem. Extensive experiments also verify the effectiveness of the proposed method in this scenario.
strengths_and_weaknesses: Strength:

\+ This paper provides an interesting perspective of viewing the multi-task AUC maximization as a multi-block bilevel optimization problem. Such a generalization may inspire future research on this important area.

\+ This paper is technically sound, supported by non-trivial theoretical analysis and extensive experiments.

Weakness:

\- The block sampling and moving averaging gradient estimator have some overlap with previous work, which somehow affects the novelty of the algorithm design.
questions: This paper have briefly compared the use of block sampling with previous work [27]. However, I wonder whether it will bring anything new to the algorithm design or theoretical analysis, or it is just a direct application.

Typo: line 254, sigmod -> sigmoid
limitations: Limitations of this work have been properly discussed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies a bilevel multi-block (multi-objective), where the inner level is a per-block convex minimization problem, while the outer level is a min-max problem involving multiple blocks. The paper proposes a novel algorithm which contains existing algorithms for min-max optimization and single-block bilevel optimization as special cases. This algorithm makes use of non-standard technique to obtain the implicit gradient for the outer level variable, and enhances the outer level optimization with a momentum based updated. This algorithm is then analyzed in terms of the convergence to a stationary point, and key aspects of this novel analysis is highlighted and discussed. The main convergence rate matches the optimal convergence rate for stochastic nonconvex min-max and bilevel optimization separately, highlighting the tightness of the result. The paper then proposes two related applications of this multi-block bilevel problem -- multi-task (partial) AUC maximization for training neural networks. One non-trivial contribution in the application of the multi-block bilevel problem to partial AUC maximization is a novel formulation of partial AUC maximization as a min-max bilevel problem. Empirical evaluation of the proposed algorithm on these applications with data from different domains (images, graphs) and different neural network architectures highlight the improved performance of the proposed scheme against various baselines.

strengths_and_weaknesses: ### Strengths:

- This paper studies a novel generalization of the (recently well-studied in machine learning literature) bilevel problem to multiple objectives. The problem (1) is infact a more general form of recent problem studied in [8]. Beyond the more general problem, the proposed algorithm also makes use of a momentum enhanced gradient update that is yet another novelty over the recently proposed [8] for the min-max multi-block bilevel problem.


- The authors do a great job at positioning the problem and the novel results against existing literature on bilevel, min-max, multi-block bilevel problem. This level of clarity makes it easy to understand the originality in the paper.

- The discussion of the main theoretical results clearly highlights the various strengths of the analysis. One such strength is that the convergence does not require a minimal data batch or block-batch size. Furthermore, the result shows that the algorithm can benefit from increasing both the data batch and task batch size. This is very nice property of the algorithm and analysis, and this property was empirically demonstrated with experiments.


- The empirical evaluation considers various datasets from different domains and different neural network architectures, highlighting the generality of the proposed problem and algorithm.


### Weaknesses:

- It is not clear with no common application such as those in [8] of representation learning or hyperparameter optimization (which are multi-task extensions of the well-studied bilevel problems) are considered in this paper to evaluate the proposed general algorithm.

- One aspect of the proposed algorithm that estimates the outer level gradient with equations (2) and (3) is that it is not clear how feasible this scheme is for practical problems without a special structure (like the hessian $\nabla_{yy}^2 g_i$  is the Identity matrix). The Neumann series allows one to approximate the matrix inversion with a series of more practically efficient matrix-vector product. But the proposed scheme requires one to take the full inverse for each iteration. The authors mention this weakness as one of the limitations. 

- Various aspects of the formulation of the partial AUC maximization as problem (1) is unclear. First, in the vanilla AUC maximization problem, there is a positive $\alpha$ even for the single-task (or single-block) problem. However, in the reformulation of the partial AUC maximization problem in the equations between lines 253-254 and 258-259, there is no $\alpha$ present in the single-task problem. Then, in the multi-task extension in equation after line 260 on page 7, $\boldsymbol{\alpha}$ and $\alpha_k, k \in [1, \ldots, m]$ are introduced without any context, and the problem itself appears to have various typographical errors since the $\max_{\boldsymbol{\alpha} \in \mathbb{R}^m}$ appears to be outside the $\sum_{k = 1}^m$. Moreover, it is not clear why we dont need  $\max_{\boldsymbol{\alpha} \in \mathbb{R}_+^m}$ (implying positive $\alpha_k$s).


- Given the decoupled nature of the $\alpha_k$s in the (partial) AUC maximimization problem, and the assumptions on problem (1), it is not clear why the problem cannot be formulated a standard min-max bilevel optimization problem:


$$
\min_{\mathbf{x}} \max_{\boldsymbol{\alpha} \in \mathcal{A}} F(\mathbf{x}, \boldsymbol{\alpha}, \mathbf{y}(\mathbf{x})) := \sum_{i = 1}^m f_i(\mathbf{x}, \alpha_i, \mathbf{y}_i(\mathbf{x})
$$
with

$$
\mathbf{y}(\mathbf{x}) = \arg \min_{\mathbf{y}:= \lbrace y_i , i \in [1, \ldots, m] \rbrace } \sum_{i = 1}^m g_i(\mathbf{x}, y_i).
$$

One difference is in the proposed algorithm is that only a subset of the blocks are chosen, but in the extreme where all the blocks are chosen in each iteration, this is just a standard min-max bilevel solver such as the one that might be used to solve the single-task version of the AUC maximization problem listed in the equation between lines 223-224. If this assessment is true, I think it would be good to understand what improvement the proposed problem formulation and algorithm brings over just looking at the multi-block problem as a single min-max bilevel optimization problem and solving it thusly. 


questions: - Regarding [8] considering "a special case where $f(\mathbf{x}, \cdot, \mathbf{y})$ is a linear function", this is infact true. But there is an assumption (Assumption 2.2)  on strong concavity w.r.t. $\alpha$, and I think the linear form of [8] does not satisfy that assumption. So does this mean that the $\min_{\mathbf{x}} \max_{i \in [1, \ldots, m]} f_i(\mathbf{x}, y_i(x))$ $\equiv$ $\min_{\mathbf{x}} \max_{\alpha \in \Delta_m \subset \mathbb{R}^m} \alpha_i \cdot f_i(\mathbf{x}, y_i(x))$ does not fit in the version of problem (1) studied in this paper? Note that $\Delta_m$ is the $m$-dimensional simplex implying $\alpha_i \geq 0 \forall i \in [1, \ldots m]$ and $\sum_{i = 1}^m \alpha_i = 1$.

- The $\max_\alpha$ in AUC maximization is there even for the single block problem so it is not clear what is the effect of this $\max_{\boldsymbol{\alpha}}$ in the multi-task setting. It does not appear that the $\boldsymbol{\alpha}$ is forcing some form of robustness across the tasks as something like the $\min_{\mathbf{x}} max_i$ of [8] would have. Is that a correct assessment? Can you please elaborate of the effect (if any) of the $\max_{\boldsymbol{\alpha}}$ in the multi-block setting?

- Is the main contribution in subsection 4.3 the formulation of multi-task pAUC maximization as problem (1)?

limitations: The authors do explicitly discuss one limitation of their work. I do not think there are any potential negative societal impact of this work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper investigated how to optimize multi-task deep auc maximization problems. In particular, this paper proposed a novel efficient algorithm for multi-block min-max bilevel optimization problems. The theoretical analysis demonstrated that this algorithm can achieve $O(1/\epsilon^4)$ convergence rate, matching the optimal complexity for nonconvex optimization. The empirical results confirm the efficacy of the proposed algorithm. 

Overall, this algorithm is novel and it is well reasoned with practical applications. The theoretical analysis is also solid.  Thus, this is a strong submission with significant theoretical and empirical contributions.
strengths_and_weaknesses: Strengths:
- The proposed algorithm is novel. It provides an efficient solution for optimizing the important AUC maximization problem. It should have wide applications in real-world data analysis tasks because the dataset in real-world applications is typically imbalanced. 
- The technical contributions are solid. The authors provide a rigorous analysis for the convergence rate. And the convergence rate can match the optimal complexity of standard nonconvex optimization problems. 
- The extensive experiments with different datasets and models have shown better performance than existing methods. This confirms the efficacy of the proposed algorithm. 


Weaknesses:
- In the experiment, is a class viewed as a task?
- It would be good if Section 3 could be moved before Section 2.1. Then, it will be much clear what applications belong to this kind of problem. 
- It looks like there is a typo in Line 526: Assumption ??
questions: - In the experiment, is a class viewed as a task?
- It would be good if Section 3 could be moved before Section 2.1. Then, it will be much clear what applications belong to this kind of problem. 
- It looks like there is a typo in Line 526: Assumption ??


====post rebuttal=====

Thanks for your answers. 

This is a novel method for the important AUC maximization problem. It can benefit a lot of real-world applications. Thus, I am raising my rating and suggest acceptance.
limitations: NA
review_title: null

Meta-review: metareview: This paper propose novel algorithm for a class of minimax problems. The iteration complexity is established. The proposed algorithm is applied to AUC maximization -- a very important problem in machine learning. Considering the contributions in both theory and practice, this is a solid work to the machine learning community. 
confidence: Certain
Decision: Accept