First-Order Minimax Bilevel Optimization

Authors: yifan  yang
zhaofeng  si
siwei  lyu
kaiyi  ji
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 22:08:39

Abstract: Multi-block minimax bilevel optimization has been studied recently due to its great potential in multi-task learning, robust machine learning, and few-shot learning. However, due to the complex three-level optimization structure, existing algorithms often suffer from issues such as high computing costs due to the second-order model derivatives or high memory consumption in storing all blocks' parameters. In this paper, we tackle these challenges by proposing two novel fully first-order algorithms named FOSL and MemCS. FOSL features a fully single-loop structure by updating all three variables simultaneously, and MemCS is a memory-efficient double-loop algorithm with cold-start initialization. We provide a comprehensive convergence analysis for both algorithms under full and partial block participation, and show that their sample complexities match or outperform those of the same type of methods in standard bilevel optimization. We evaluate our methods in two applications: the recently proposed multi-task deep AUC maximization and a novel rank-based robust meta-learning. Our methods consistently improve over existing methods with better performance over various datasets.

Main paper: 
 introduction: 
 In this paper, we study a general multi-block minimax bilevel optimization problem given by minEQUATIONwhere the upper-and lower-level function f i and g i for block i take the expectation form w.r.t. the random variables ξ, ζ, and are jointly continuously differentiable, z * = z * 1 (x), ..., z * n (x) ∈ R dz×n contains all lower-level optimal solutions, and n is the number of blocks. The above problem has various applications in machine learning, including deep AUC maximization [24, 23] , meta-learning [16, 3] , hyperparameter optimization [17] , and robust learning [17] . This paper focuses on the setting with a nonconvex-strongly-concave minimax upper-level problem and a strongly-convex lower-level problem.To date, barring a few works on optimizing special cases of this problem [17, 24] , the solution algorithm to its general form has not been well studied. The primary obstacle lies in the significant computational cost per iteration, arising from the inherent structure of multi-block minimax bilevel optimization. To address this challenge, [17] considered a special case where y is the simplex variable, and introduced a single-loop gradient descent-ascent algorithm, based on the two-timescale bilevel on the sample level. Moreover, some other works focus on improving task-level robustness [28, 58] . In this work, we show that robust meta-learning can be formulated as a minimax bilevel optimization problem and solved with the proposed algorithm. 
reformulation as a minimax problem: 
 Motivated by [34, 38, 30] in single-machine bilevel optimization, we reformulate the lower-level problem as a value-function-based constraint and aim to solve the following equivalent problem:EQUATIONwhere z * i := arg min z g i (x, z). Inspired by [30] , we form a Lagrangian L i with Lagrangian multiplier λ ≥ 0 to approximate the original problem for each block i in eq. ( 2), asL i (x, y, z i , v i ) = f i (x, y, z i ) + λ g i (x, z i ) -g i (x, v i ) ,where v i is used to approximate the lower-level solution z * i (x) of the i th block. Then, we turn to solve the following surrogate minimax problem:EQUATIONwhere z = (z 1 , ..., z n ) ∈ R dz×n , v = (v 1 , ..., v n ) ∈ R dz×n and the standard basis vector e i has only one non-zero element of 1 at the i th coordinate. We show later in Section 4.2 that the gap between the gradients ∇F (x, y * (x), z * (x)) and ∇L(x, y * (x), z * λ (x), z * (x)) of the original and surrogate problems can be effectively bounded by O(1/λ), where y * (x) denotes the maximize of outer-objective F (x, •, z * (x)) and each vector z * λ,i (x) in z * λ (x) := (z * λ,1 (x), ..., z * λ,n (x)) denotes the minimizer of the Lagrangian function L i (x, y * (x), •, v) (where z * λ,i (x) has not reliance on v). This validates the effectiveness of the Lagrangian approximation for λ sufficiently large. Next, we propose two efficient algorithms, namely FOSL and MemCS, to solve the surrogate problem in eq. (3).As shown in Algorithm 1, we first sample a subset I t ⊂ S := {1, ..., n} of blocks without replacement. Noting that z i and v i are both block-specific variables, we then apply a stochastic ascent and descent step to update v i and z i for all block i ∈ I t as v i,t+1 = v i,t + η v -∇ z g i (x t , v i,t ; ξ t v,i ) z i,t+1 = z i,t -η z ∇ z L i x t , y t , z i,t , v i,t ; ξ t z,i , where the gradient of L i w.r.t. z has no dependence on v. Since the solutions w.r.t. variables x and y depend on all blocks, we use the average of stochastic gradient estimators from the selected blocks in I t to update y and x asy t+1 = y t + η y 1 |I t | i∈It ∇ y f i (x t , y t , v i,t ; ξ t y,i ) x t+1 = x t -η x 1 |I t | i∈It ∇ x L i (x t , y t , z i,t , v i,t ; ξ t x,i ).Note that our algorithm takes a simpler fully single-loop structure via updating {v i,t , z i,t } i∈It , x t and y t simultaneously at each iteration. Hence, it can also benefit from the hardware parallelism. In addition, different from the methods in [17, 24] that need to compute the higher order Hessian-or Jacobian-vector products, our method only uses the first-order gradients.Note that in the single-loop optimization of Algorithm 1, all block-specific parameters v i,t and z i,t of blocks in I t need to be stored for the updates at iteration t + 1. However, in some ML applications, Algorithm 1 Fully First-Order Single-Loop Method (FOSL) such as few-shot meta-learning, the number of blocks/tasks is often large, and hence Algorithm 1 can suffer from significant memory consumption. To address this challenge, we propose a memoryefficient method named MemCS in Algorithm 2. Differently from the single-loop updates in FOSL, MemCS contains a sub-loop of K steps of gradient descent1 in updating the block-specific variables v k i,t and z k i,t for k = 0, ..., K -1 with random initialization v 0 i,t and z 0 i,t . After obtaining the outputs v K i,t , z K i,t of this sub-loop, the remaining step is to update y t and x t via gradient ascent and descent similarly as in FOSL. 
assumptions: 
 Definition 4.1. A mapping f is L-Lipschitz continuous if ∥f (x 1 ) -f (x 2 )∥ ≤ L∥x 1 -x 2 ∥, for any x 1 , x 2 . We say f is L-smooth if ∇f is L-Lipschitz continuous.Since the overall objective is nonconvex w.r.t. x, we aim to find an ϵ-accurate stationary point. Definition 4.2. We call x as an ϵ-accurate stationary point of the objective function Φ(x) if E∥∇Φ(x)∥ 2 ≤ ϵ, where ϵ ∈ (0, 1] and x is the output of an algorithm.We use the following assumptions in the subsequent description. Note that these assumptions are widely adopted in existing studies [24, 17] . Assumption 4.3. For any x ∈ R dx , y ∈ R dy , z ∈ R dz and i ∈ {1, 2, ..., n}, f i (x, y) and g i (x, y) are twice continuously differentiable, f i (x, y, z) is µ f -strongly concave w.r.t. y and g i (x, z) is µ g -strongly convex w.r.t. z.The following assumption imposes the Lipschitz continuity on the upper-and lower-level functions and their derivatives. Assumption 4.4. For any x ∈ R dx , z ∈ R dz and i ∈ {1, 2, ..., n}, f i (x, y, z) is L f,0 -Lipschitz continuous w.r.t. x, g i (x, z) is L g,0 -Lipschitz continuous w.r.t. x, f i (x, y, z) is L f,1 -smooth and g i (x, y) is L g,1 -smooth. In addition, the second-order derivatives ∇ 2 f i (x, y, z) and ∇ 2 g i (x, y) are L f,2 -and L g,2 -Lipschitz continuous.Next, we make a bounded variance assumption for the gradients in the stochastic setting. Assumption 4.5. There exist constants σ f and σ g such that the variances E∥∇f i (x, y, z) -∇f i (x, y, z; ξ)∥ 2 ≤ σ 2 f and E∥∇g i (x, z) -∇g i (x, z; ζ)∥ 2 ≤ σ 2 g .The following assumption on block heterogeneity measures the similarities of the upper-level gradients ∇ y f i (x, z) for all i. This has not been discussed in previous works, but it is necessary for our approach as we explore a more general outer-maximization solution y * (x) for F , rather than for single f i .Assumption 4.6. For any x ∈ R dx , z ∈ R dz , there exist constants β th ≥ 1 and σ th ≥ 0 such that1 n n i=1 E∥∇ y f i (x, y, z)∥ 2 ≤ β 2 th E∥∇ y F (x, y, z)∥ 2 + σ 2 th .We have β th = 1 and σ th = 0 when all g i 's are identical.For simplicity, we fix the number of involved blocks |I t | = P for all t. Let y * (x) be the maximizer of F function w.r.t. y. Then, the overall objective of the original problem in eq. ( 1) w.r.t. x is given byΦ(x) := F x, y * (x), z * (x) ,where z * (x) is the lower-level minimizer and y * (x) is the maximizer of F (x, •, z * (x)). In addition, recall that the objective function of the surrogate problem in eq. ( 3) w.r.t. x is given by L * (x) := L x, y * (x), z * λ (x), z * (x) . We next characterize the difference between the gradients of the original and the surrogate problems. Proposition 4.7. Under Assumptions 4.3, 4.4, the gap between ∇Φ(x) and ∇L * (x) can be bounded as∇Φ(x) -∇L * (x) = O(1/λ).Due to the limit of space, the proof of Proposition 4.7 can be found in Lemma D.5 in the appendix. For a properly large λ, Proposition 4.7 guarantees that the stationary points of the original and surrogate problems are close to each other. However, too large λ can explode the gradient estimation variance, resulting in a much slower convergence rate. This trade-off makes the selection of λ important, as shown in our theorems later.We next give an upper bound on the gradient norm E∥∇L * (x t )∥ 2 of the surrogate problem. Denoteh t x := ∇ x L i (x t , y t , z t , v t ; ξ t x,i) and its expectation as h t x . Proposition 4.8. Under Assumptions 4.3, 4.4, 4.5, the consecutive iterates of Algorithm 1 satisfy:E∥∇L * (x t )∥ 2 ≤ 2 η x E L * (x t+1 ) -L * (x t ) -E∥ h t x ∥ 2 + η x L * ,1 E∥h t x ∥ 2 + 3L 2 f,1 E y t -y * (x t ) 2 + 3L 2 λ,1 n n i=1 E z i,t -z * λ,i (x t ) 2 + v i,t -z * i (x t )2 for all t ∈ {0, 1, ..., T -1}, where L λ,1 and L * ,1 are given in Lemma D.1 and Lemma D.6 in the appendix respectively.The proof of Proposition 4.8 can be found in Lemma E.1 in the appendix. The same result can be obtained for Algorithm 2 by replacing v i,t and z i,t with v K i,t and z K i,t . This proposition shows that the convergence rate of our algorithm relies on how fast the iterates y t , z i,t and v i,t converge to their optimal solutions at each iteration t. We next characterize the distance of y t to its optimal solution. Proposition 4.9. Under Assumptions 4.3, 4.4, 4.5, the iterates of y t generated according to Algorithm 1 satisfyE∥y t+1 -y * (x t+1 )∥ 2 -E∥y t -y * (x t )∥ 2 ≤ -O(η y ) • E∥y t -y * (x t )∥ 2 + O η 2 y |I t | • (σ 2 f + σ 2 th ) + O(η y ) • 1 n n i=1 E∥v i,t -z * i (x t )∥ 2 + O η 2 x η y E h t x 2 + O(η 2 x )E h t x 2 ,for all t ∈ {0, ..., T -1}.The proof of Proposition 4.9 refers to Lemma E.3 in the appendix. It can be seen that with properly small stepsizes η x and η y , there exists a descent of the optimal distance E∥y t -y * (x t )∥ 7 ) and λ = O(T 7 ). Then, we have 7 ), where C gap is defined in Lemma D.5, C 2 , C 3 are defined in eq. (39) in the appendix, andEQUATIONEQUATIONΨ t := L * (x t ) + K y E∥y t -y * (x t )∥ 2 + K z 1 n n i=1 E∥z i,t -z * λ,i (x t )∥ 2 + K v 1 n n i=1 E∥v i,t -z * i (x t )∥ 2 .Next, we characterize the sample complexity for FOSL. Corollary 4.11. Under the same setting of Theorem 4.10, our algorithm finds an ϵ-accurate stationary solution after T = O(ϵ -7 2 ) interactions. The total sample complexity for all involved blocks is P T = O(P ϵ -72 ).Compared with existing works [17, 24] , our algorithm is free from second-order derivative computations. In addition, the sample complexity of our algorithm matches the best result [30] of the same type of methods in standard single-block bilevel optimization.Next, we analyze the convergence for Algorithm 2 under the partial-and full-block participation. Theorem 4.12 (Convergence of MemCS). Suppose Assumptions 4.3, 4.4, 4.5, 4.6 are satisfied. Assume there exists some B > 0 such that ∥z * i (x t )∥ ≤ B for any x t , i = 1, ..., N . For the partial-block participation, by setting parameters η x = O(P 6 ) and taking ϵ sub = O(P -2 5 T -2 3 ), we haveEQUATION1 T T -1 t=0 E∥∇Φ(x t )∥ 2 ≤ 2C gap λ 2 + 2(Ψ 0 -Ψ T ) T η x + 4η x λ 2 P 1 + η x η y C 2 + η y P 24L 2 f,1 σ 2 th µ f + 4 3L 2 λ,1 + 12L 4 f,1 µ 2 f ϵ sub ≤O(P -1 5 T -1 3 ),where L λ,1 := 3λL g,1 , C gap is defined by Lemma D.5 in the appendix and Ψ t := L * (x t )+K y E∥y ty * (x t )∥ 2 . For the full-block participation, by settingη x = O(1), η y = O(1), η z = O(T -1 2 ), η v = O(1), λ = O(T 1 2 ) and taking ϵ sub = O(T -2 ), we have 1 T T -1 t=0 E∥∇Φ(x t )∥ 2 ≤ 2C gap λ 2 + 4 Ψ 0 -Ψ T T η x + 12 L 2 λ,1 + 4L 4 f,1 µ 2 f ϵ sub ≤ O(T -1 ).Note that the assumption ∥z * i (x t )∥ ≤ B can be removed when the domain of x is a closed convex set and projected gradient descent is used to update x [12, 15] . We next characterize the sample complexity for MemCS. Corollary 4.13. Under the same setting of Theorem 4.12,• For partial-block participation, our algorithm finds an ϵ-accurate stationary solution of Φ(x) after T = O(P -3 5 ϵ -3 ) outer iterations and K = O(log 1 ϵ ) inner iterations. The total sample complexity for all involved blocks is P KT = O(P 2 5 ϵ -3 ).• For full-block participation, our algorithm finds an ϵ-accurate stationary solution of Φ(x)after T = O(ϵ -1 ) outer iterations and K = O(log 1 ϵ ) inner iterations. The total sample complexity for all involved blocks is nKT = O(nϵ -1 ).Note that the per-block sample complexity of our MemCS algorithm takes an order of ϵ -1 , which improves that of the same-type F 2 SA [30] by an order of ϵ -0.5 , based on a refined analysis on the smoothness of the overall objective function. Corollary 4.13 also shows that MemCS achieves a linear convergence speedup w.r.t. the number P of blocks. As far as we know, this is the first linear speedup result in multi-block minimax bilevel optimization. 
applications and experiments: 
 In this section, we conduct extensive experiments in two applications: deep AUC maximization and rank-based robust meta-learning. More experimental results such as time and space comparison are provided in Appendix B.Deep AUC Maximization (DAM) addresses machine learning challenges presented by imbalanced datasets. In particular, the AUC (Area Under the ROC Curve) measures the likelihood that a positive sample's prediction score will be higher than that of a negative sample. As outlined by [24] , the DAM issue is structured as a multi-block minimax bilevel optimization problem:min w,a,b max α m j=1 Φ j u * j (w j ), a j , b j , α j s.t. u * j (w j ) = arg min uj g j (u j , w j ),where g j (u j , w j ) := 1 2 u j -w j -η∇L AV G (w j ) 2 , L AV G (w j ) := 1 n n i=1 ℓ(w j ; x i , y i ), ℓ denotes the task loss (e.g., the cross-entropy loss in binary classification tasks), and Φ j denotes the sample-level AUC loss function. The detailed formulation can be found in Appendix A.1. With the method in Section 3, we reformulate this problem as a single-level minimax optimization problem:min w,u,a,b max α,v L(w, u, a, b, α, v),where L(w, u, a, b, α, v) := m j=1 Φ j (u j , a j , b j , α j ) + λ g j (u j , w j ) -g j (v j , w j ) is the Lagrangian function of AUC loss function, and v j is the approximate optimal solution of g j .Settings. Following the work [24] , we assess our methodology using four datasets, namely CIFAR100 [29] , CelebA [40] , CheXpert [26] and OGBG-MolPCBA [25] , whose details are provided in Appendix B.1. We evaluate the effectiveness of our algorithm by comparing it with direct optimization on multi-block minimax AUC loss (mAUC) and compositional training on mAUC loss (mAUC-CT). The test AUC scores of mAUC and mAUC-CT for different datasets in Table 1 are derived from the original paper. Detailed configuration of experiments can be found in Appendix B.2.Results. The results of deep AUC maximization on different datasets are shown in Table 1 . The results indicate that our FOSL outperforms the mAUC method in terms of test AUC scores on all datasets and achieves comparative or better performance than mAUC-CT on various datasets. We proceed to visualize the AUC loss during the initial stages of training for all methods on CelebA, as depicted in Figure 1a and 1b . The figures illustrate that, in the initial stage, our method and mAUC-CT [24] exhibit a faster loss drop than mAUC, and our method achieves the fastest overall convergence rate. Furthermore, our approach exhibits a smaller fluctuation compared to other baseline methods. Impact of λ. To evaluate the impact of the hyper-parameter λ on training with FOSL algorithm, we conduct an ablation study on the CIFAR100 and the CelebA datasets. The test AUC scores along with training are depicted in Figure 1c and 1d . As shown in Figure 1c , our method sustains robust performance across a wide range of choices for λ. For example, training within a λ range of [2, 8] shows that the speed of convergence and the final test performance are not sensitive to the change of λ. A similar observation also holds for the CelebA dataset as shown in Figure 1d .5.2 Robust Meta-learning with Rank-based LossOur objective is to devise a robust meta-learning approach wherein, during each iteration, tasks with large loss values are filtered out, and the meta-model is updated with the remaining tasks. This approach effectively reduces the impact of tasks with noisy samples (noisy tasks), because deep learning models tend to acquire clean and simple patterns in their initial training stages [19] , such that noisy samples/tasks often have large loss values. Further justification can be found in Figure 2 .We first define g [i] as the i th largest element of the set G = {g 1 , g 2 , ..., g n }, such that g[n] ≤ g [n-1] ≤ ... ≤ g [1]. Denote the task-specific loss as g i (ϕ, w i ), where ϕ is the parameter of the meta-model and w i is the task-specific parameter. The proposed formulation is then given by:min ϕ F (ϕ, w * ) := 1 k n i=n-k+1 g [i] ϕ, w * [i] (ϕ) s.t. w * i (ϕ) = arg min wi g i (ϕ, w i ),whereg [i] ϕ, w * [i] (ϕ)is the i th largest task-specific loss given w * := w * i (ϕ), ..., w * n (ϕ) T , andw * [i] (ϕ)is the corresponding optimal task-specific parameter. With the Lemma 1 in [42] , by introducing an auxiliary variable γ, we can reformulate the problem as:min ϕ max γ F (ϕ, w * , γ) = 1 k n i=1 f i ϕ, w * i (ϕ), γ = 1 k n i=1 g * i (ϕ) -[g * i (ϕ) -γ] + - n -k n γ s.t. w * i (ϕ) = arg min wi g i (ϕ, w i ).Details about the derivation of the above formulation can be found in Appendix A.2. This formulation poses a non-convex optimization challenge for the primal variable ϕ, making it challenging to address using conventional optimization methods. Nevertheless, our proposed algorithm enables efficient resolution of this problem by reformulating the problem into a singlelevel minimax optimization problem as: min ϕ,w max γ,v L(ϕ, w, γ, v), where L(ϕ, w, γ, v) :=1 n n i=1 fi(ϕ, wi, γ)+λ gi(ϕ, wi)-gi(ϕ, vi) is the Lagrangian function of the rank based loss function, v is an approximate optimal task-specific parameter of the lower-level problem. Settings. We perform meta-learning experiments on few-shot learning tasks, focusing on the capability of rapid adaptation to new tasks with limited samples. Adhering to standard few-shot learning configurations, we carry out 5-ways 5-shot learning experiments on Mini-ImageNet [53] (referred to as Mini in Table 2 ) and Tiered-ImageNet [47] (referred to as Tiered in Table 2 ), where each task involves a 5-class classification task, with five samples per class used as training data. Since our robust meta-learning formulation is built on that of MAML [6] , we compare our method with MAML on both clean dataset and noisy dataset to evaluate the effectiveness and robustness of our algorithm. In the noisy setting, we adopt a standard noisy training scheme in meta-learning, where the labels in a noisy task are randomly flipped. Specifically, we employ two label flipping strategies: Flip, where in each iteration, a certain portion of tasks (60% in Table 2 ) are designated as noisy, and each sample within the task is assigned to one of all labels with equal probability; and Rand, where a random noisy ratio is assigned to each task in every iteration, determining the proportion of samples to be flipped by randomly assigning another label to them. Detailed configuration of experiments can be found in Appendix B.2.Results. Table 2 displays the test accuracies. These results show that in the presence of noisy tasks, both MAML and our MemCS method undergo a decline in performance across both datasets, yet our approach manages to sustain a reasonable performance. To further evaluate the resilience of our MemCS method against MAML, we executed additional experiments with escalating noise levels in the Flip scenario, with these findings detailed in Table 3 . The data clearly show a performance decrease for both methodologies as the noise ratio intensifies. Nonetheless, our approach exhibits a notably more gradual decline in performance as the noise ratio escalates, especially at higher noise levels, signifying superior robustness compared to MAML.Discussion. To show the effectiveness of our approach in facilitating robust learning, we have visualized the average losses for both clean and noisy tasks separately within the MAML training framework, as demonstrated in Figure 2 . The graphical representation uncovers a consistent pattern where the losses associated with noisy tasks consistently exceed those related to clean tasks throughout the training period. This pattern underscores our approach's capacity to lessen the detrimental effects of noisy tasks. Further, we examine the noisy tasks in the update mechanism at five distinct intervals during the training phase, illustrated in Figure 2 . The findings show that our methodology successfully deters the influence of noisy tasks on the meta-model's updates across both Rand and Flip scenarios, maintaining this protective measure throughout the training duration.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: We provide the code as the supplementary material.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion: 
 In this paper, we propose two fully first-order algorithms designed to address the challenges posed by multi-block minimax bilevel optimization problems: a fully single-loop algorithm, FOSL, and a memory-efficient double-loop algorithm with cold-start initialization, MemCS. We show that our methods can achieve comparative and even better per-block sample complexities than other methods with the same type in standard bilevel optimization. The experimental results indicate that our methods consistently demonstrate superior performance and robustness in applications on deep AUC maximization and robust meta-learning.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Data and experimental settings are provided in the experiment part in the main text.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]Justification: Error bars are provided in the experiments in Table 1 .Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The computational resources are described in the implementation detail part in the appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes]Justification: The authors have reviewed the Code of Ethics and make sure the research conforms with it.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This paper focuses on the theoretical analysis of multi-block minimax bilevel optimization problem, which does not have a social impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 
 
 Appendix: In this section, we provide a detailed introduction to the formulation utilized in Section 5.For a classifier model f (w), we have the AUC score function asAU C f (w) = P r f (w; x) ≥ f (w; x ′ )|y = 1, y ′ = -1 ,where P r(X) denote probability of an event X being true. One of the surrogate loss (AUC square loss [9] ) is given by:min w 1 n + n -yi=1 yj =-1 c -f (w; x i ) -f (w; x j ) 2 ,where n + and n -are the numbers of positive examples and negative examples, respectively, and c is the margin parameter. One can transfer this problem into an equivalent minimax optimization problem according to Proposition 1 in [37] by:min w,a,b max α Φ(w, a, b, α) := 1 n n i=1 ϕ(w, a, b, α; x i , y i ),whereϕ(w, a, b, α; x i , y i ) =(1 -p) f (w; x i ) -a 2 • I yi=1 + p f (w; x i ) -b 2 • I yi=-1 -p(1 -p)α 2 + 2α p(1 -p)c + pf (w; x i ) • I yi=-1 -(1 -p)f (w; x i ) • I yi=1 ,where a, b are margin parameters, p = n + /n. This formulation decomposed the individual examples, which is more favorable in stochastic scenarios. [59] proposed a compositional training algorithm for this problem. The compositional objective function is formulated as:min w,a,b max α Φ(w -α∇L AV G (w), a, b, α),where L AV G = 1 n n i=1 ℓ(w; x i , y i ), ℓ denotes task loss, e.g. cross-entropy in classification tasks. Consider a multi-block problem with m tasks. This problem can be reformulated as a multi-block minimax bi-level optimization problem [24] :min w,a,b max α m j=1 Φ j u * j (w j ), a j , b j , α j s.t. u * j (w j ) = arg min uj g j (u j , w j ),where g j (u j , w j ) := 1 2 u j -w j -η∇L AV G (w j ) 2 .Consider the formulation of Robust Meta-learning in Section 5.2:min ϕ F (ϕ, w * ) := 1 k n i=n-k+1 g [i] ϕ, w * i (ϕ) s.t. w * i (ϕ) = arg min wi g i (ϕ, w i ),whereg [n] ϕ, w * n (ϕ) ≤ g [n-1] ϕ, w * n-1 (ϕ) ≤ ... ≤ g [1]ϕ, w * 1 (ϕ) denotes task-specific losses. We define g * i (ϕ) := g i ϕ, w * i (ϕ) for simplicity in later formulations. The summation of the bottom-k losses is equivalent to the sum of all task losses subtracted by the sum of the top-(n-k) losses:F (ϕ, w * ) = 1 k n i=1 g * i (ϕ) - n-k i=1 g * [i] (ϕ) .With the Lemma 1 in [42] , we have:n-k i=1 g * [i] (ϕ) = min γ (n -k)γ + n i=1 [g * i (ϕ) -γ] + .Now we can convert the original upper-level problem to:min ϕ max γ F (ϕ, w * , γ) := 1 k n i=1 g * i (ϕ) -[g * i (ϕ) -γ] + - n -k n γ .The problem of robust meta-learning is then formulated as:min ϕ max γ F (ϕ, w * , γ) = 1 k n i=1 f i (ϕ, w * i , γ) := g * i (ϕ) -[g * i (ϕ) -γ] + - n -k n γ s.t. w * i (ϕ) = arg min wi g i (ϕ, w i ),where ϕ is the parameter of meta-model, and w = [w i , ..., w n ] T is the vector of task specific parameters.Inspired by [10] , we introduce a smoothed version of the upper-level loss function by incorporating Gaussian noise into the indicator function for alignment with the assumption of our MemCS algorithm:F (ϕ, w * , γ) = 1 k n i=1 f i (ϕ, w * i , γ) := g * i (ϕ) -[g * i (ϕ) -γ + ϵZ] + - n -k n γ ,where ϵ > 0 is the smoothing parameter, and Z ∼ N (0, 1) is standard normal random variable.Deep AUC Maximization. We assess our methodology using four datasets. The first dataset, CIFAR100 [29] , serves primarily for classification endeavors. Within the context of the multi-block deep AUC maximization challenge, we treat each of the 100 categories as an individual block, with samples belonging to a specific category considered positive for that block. This dataset comprises 60, 000 images, each measuring 32 × 32 pixels, divided into 50, 000 training and 10, 000 testing images. The CelebA [40] dataset encompasses 202,599 facial images, each annotated with a diverse set of attributes from 40 different features. The CheXpert [26] dataset includes 224, 316 chest radiograph images from 65, 240 patients, marked for 14 distinct observations. Adhering to the methodology proposed in [24] , we employ a simplified version of CheXpert with a reduced image resolution and omit the Fracture observation due to insufficient positive samples. Lastly, the OGBG-MolPCBA [25] dataset is employed to predict molecular properties, representing each molecule as a graph with atoms as nodes and chemical bonds as edges, featuring 437, 929 such graphs annotated across 128 properties.Robust Meta-learning. Our experiments are conducted over two popular datasets for few-shot learning: Mini-ImageNet [53] and Tiered-ImageNet [47] . Both datasets are subsets of the ILSVRC-12 dataset. Mini-ImageNet comprises 100 classes, each containing 600 images with dimensions of 84 × 84 pixels. The 100 classes are distributed among training, validation, and testing sets with a ratio of 64:16:20, respectively. In contrast, Tiered-ImageNet is a more extensive and challenging dataset, featuring 779,165 images annotated across 608 classes. These classes are further organized into 34 categories, with 20 categories designated for training, 6 for validation, and 8 for testing.Deep AUC Maximization. For the CIFAR100 and the CelebA datasets, we use the ResNet18 architecture. For the large-scale CheXpert dataset, we opt for the DenseNet121 model pre-trained on ImageNet. When dealing with the OGBG-MolPCBA graph dataset, the Graph Isomorphism Network (GIN) is used for training. All experimental runs are performed using a single NVIDIA RTX 6000 GPU. Regarding hyperparameters, we set the total training epoch to 2000 for the CIFAR100 and 100 for the OGBG-MolPCBA datasets, adjust it to 40 for CelebA, and reduce it to 6 for CheXpert. The learning rate for the optimal approximator v is uniformly set to η v = 0.1 across all experiments, with η w = η u = η v /λ to maintain gradient magnitude consistency between u and v. This consistency is vital due to the influence of the λ parameter in the Lagrangian function on the update process for u. Learning rate decay is applied to CelebA starting at the 30th epoch and to CheXpert at the 4th epoch, whereas no decay strategy is applied for CIFAR100 and OGBG-MolPCBA.Robust Meta-learning. We adopt the Adam optimizer to update the meta-model in the context of MAML. For the hyper-parameters of MAML, we set the learning rate of meta-model update as η meta = 0.02, and set the learning rate of fast adaptation as η adapt = 0.02, with an adaptation step of 15. To be consistent with the DAM experiments, we configure the learning rate of the optimal approximator as η v = η adapt = 0.02, and the learning rate of w and meta-model parameter ϕ as η ϕ = η w = η v /λ in the implementation. In practice, setting λ to 3 results in favorable performance.All experiments are conducted on a single NVIDIA RTX 6000 GPU using a widely used lightweight model featuring 4 convolutional layers (CNN4).This section presents the visualization of statistics throughout the training process and compares the computational costs with our method and AUC-CT [24] . To better grasp the training dynamics, we charted the test AUC scores across various training epochs for both the CIFAR100 and CelebA datasets, as shown in Figure A1 . The findings demonstrate that our method not only exhibits enhanced generalization capabilities but also greater stability.Moreover, to assess efficiency across varying dataset scales, we examined the average iteration times and total training time of our FOSL algorithm and AUC-CT [24] on different-sized datasets (32 × 32 in CIFAR100 vs. 224 × 224 in CheXpert) as detailed in Table A1 . Note that the training time largely depends on the implementation and hyperparameters, such as the number of sampled tasks and batch sizes per task, suggesting that computational costs can be adjusted by modifying these hyperparameters according to the dataset. The result in Table A1 shows the ability to control training costs for datasets of various scales, which is indicated by the small gap between the total training time on CelebA and CheXpert datasets. Additionally, our method demonstrated a faster training pace compared to AUC-CT [24] under the same training settings. Note that the implementation of AUC-CT [24] avoided the calculation of second-order matrices so that the computational cost is more controllable with an increased dataset scale.In this section, we compare our two proposed methods within the same experimental setting, i.e. robust meta-learning. To make it compatible with our FOSL algorithm, we slightly adjusted our training setting so that the number of training tasks in the dataset is known (20000 tasks) while maintaining the same testing procedures as those used with the MemCS algorithm. The results, including test accuracy, memory cost, and computational cost, are detailed in Table A2 . The result shows that using FOSL in a robust meta-learning setting can introduce a greatly increased memory cost, which is especially significant for a small model. However, the single-loop nature of FOSL can drastically shorten the average iteration time during training. This makes the FOSL algorithm a potentially advantageous choice in scenarios involving larger base models and fewer blocks.The original problem we solve here ismin x∈R dx max y∈R dy F x, y, z * (x) : = 1 n n i=1 f i x, y, z * i (x) = 1 n n i=1 E ξ f i x, y, z * i (x); ξ i s.t. z * i (x) = arg min z∈R dz g i (x, z) = E ζ g i (x, z; ζ i ) .Moreover, we define z * λ,i (x) = arg min z L i (x, y * (x), z, v) and y * (x) = arg max y F x, y, z * (x) . For the convenience of proof, we also defineΦ(x) = F x, y * (x), z * (x) = 1 n n i=1 f i x, y * (x), z * i (x) .For the notational convenience of FOSL, we define the estimators of client set I t asEQUATIONSince we sample tasks without replacement and our estimators are unbiased, we have the expectations of estimators asEQUATION)We also define the optimal Lagrangian estimator of x and its gradients as µg , both L i (x, y, z, v) and L(x, y, z, v) are ( λµg 2 )-strongly convex in z and L λ,1 -smooth in (x, y, z), where L λ,1 := 3λL g,1 .EQUATIONProof. Since λ≥ 2L f,1 µg ≥ 2L f,1Lg,1 , we have that∥∇ 2 zz Li(x, y, z, v)∥ = ∥∇ 2 zz fi(x, y, z) + λ∇ 2 zz gi(x, z)∥ ≥ ∥λ∇ 2 zz gi(x, z)∥ -∥∇ 2 zz fi(x, y, z)∥ ≥ λµg 2 , ∥∇ 2 zz L(x, y, z, v)∥ = ∥∇ 2 zz F (x, y, z) + λ∇ 2 zz G(x, z)∥ ≥ ∥λ∇ 2 zz G(x, z)∥ -∥∇ 2 zz F (x, y, z)∥ ≥ λµg 2 ; ∥∇ 2 Li(x, y, z, v)∥ = ∥∇ 2 fi(x, y, z) + λ∇ 2 gi(x, z) -λ∇ 2 gi(x, v)∥ ≤ L f 1 + 2λLg,1 ≤ 3λLg,1 =: L λ,1 , ∥∇ 2 L(x, y, z, v)∥ = ∥∇ 2 F (x, y, z) + λ∇ 2 G(x, z) -λ∇ 2 G(x, v)∥ ≤ L f 1 + 2λLg,1 ≤ 3λLg,1 =: L λ,1 .Then the proof is complete.EQUATIONTo measure that Lipschitz continuity of z * i (x) and z * λ,i (x) w.r.t. x, we take spectral norm of ∇z * i (x) and ∇z * λ,i (x) asEQUATIONwhere (a) uses Assumption 4.4. Similarly, for y * (x), we have ∇ y F x, y * (x), z * (x) = 0. Via implicit function theorem, we haveEQUATIONwhich indicates∥∇y * (x t )∥ ≤ 1 n n i=1 ∇ 2 xy f i x, y * (x), z * i (x) + ∇z * i (x) T ∇ 2 yz f i x, y * (x), z * i (x) • ∇ 2 yy F x, y * (x), z * (x) -1 ≤ 1 n n i=1 ∇ 2 xy f i x, y * (x), z * i (x) + ∇z * i (x) T ∇ 2 yz f i x, y * (x), z * i (x) • ∇ 2 yy F x, y * (x), z * (x) -1 (a) ≤ 1 + L g,1 µ g L f,1 µ f ,where (a) uses Assumption 4.3 and Assumption 4.4. Back to the second equation in eq. ( 8), with∥∇y * (x t )∥ ≤ (1 + Lg,1 µg ) L f,1 µ f , we have ∥∇z * λ,i (x)∥ ≤ ∇ 2 xz L i x, y * (x), z * λ,i (x), v + ∇y * (x) T ∇ 2 yz L i x, y, z * λ,i (x), v • ∇ 2 zz L i x, y * (x), z * λ,i (x), v -1 (a) ≤ 3λL g,1 + 1 + L g,1 µ g L 2 f,1 λµ g 2 λµ g (b) ≤ 12L g,1 µ g ,where (a) uses Lemma D.1 and (b)uses λ ≥ (1 + Lg,1 µg ) L 2 f,1 3µ f Lg,1 .Then the proof is complete.Lemma D.3. Under Assumptions 4.3, 4.4, the optimal solutions z * i (x), z * λ,i (x) and y * i (x) are L * ,z -, L * ,z λ -and L * ,y -smooth respectively, where we define L * ,z , L * ,z λ and L * ,y asL * ,z := L g,2 µ g 1 + L g,1 µ g 2 , L * ,z λ := 1 + 1 + L g,1 µ g L f,1 µ f + 12L g,1 µ g , L * ,y := 1 + L g,1 µ g + 1 + L g,1 µ g L f,1 µ f 2 L f,2 µ f + 1 + L g,1 µ g 2 L f,1 L g,2 µ f µ gfor any i ∈ {1, ..., n}, where we assumeλ ≥ 2L f,1 /µ g , (1 + Lg,1 µg ) L 2 f,1 3µ f Lg,1 , (1 + Lg,1 µg ) L f,1 L f,2 3µ f Lg,1 , L f,1 L * ,y 6Lg,1 1 + (1 + Lg,1 µg ) L f,1 µ f + 12Lg,1 µg -1 , (1 + Lg,1 µg ) L f,1 µ f + 1 L f,1Lg,1 .Proof. Since z * i (x) = arg min z g i (x, z), we have ∇ z g i x, z * (x) = 0, which indicates that∇ 2 xz g i x, z * (x) + ∇z * (x)∇ 2 zz g i x, z * (x) = 0.For any x 1 , x 2 ∈ R dx , we haveEQUATIONwhere (a) uses Assumption 4.3, 4.4 and(A -1 -B -1 ) = A -1 (B -A)B -1 ; (b) follows from Lemma D.2.Next, plug x = x 1 and x = x 2 into eq. ( 9) and differentiate these two equations, then we getEQUATIONand by using eq. ( 9), we getEQUATIONBy combining eq. ( 11), eq. ( 12) and taking norm, we have∇y * (x 1 ) -∇y * (x 2 ) ≤ ∇ 2 yy F x 1 , y * (x 1 ), z * i (x 1 ) -1 • 1 n n i=1 ∇ 2 xy f i x 1 , y * (x 1 ), z * i (x 1 ) -∇ 2 xy f i x 2 , y * (x 2 ), z * i (x 2 ) + 1 n n i=1 ∇z * i (x 1 ) -∇z * i (x 2 ) T ∇ 2 zy f i x 1 , y * (x 1 ), z * i (x 1 ) + 1 n n i=1 ∇z * i (x 1 ) T ∇ 2 zy f i x 1 , y * (x 1 ), z * i (x 1 ) -∇ 2 zy f i x 1 , y * (x 1 ), z * i (x 1 ) + ∇y * (x 2 ) • 1 n n i=1 ∇ 2 yy f i x 1 , y * (x 1 ), z * i (x 1 ) -∇ 2 yy f i x 2 , y * (x 2 ), z * i (x 2 ) (a) ≤ 1 µ f 1 + L g,1 µ g + 1 + L g,1 µ g L f,1 µ f L f,2 • ∥x 1 -x 2 ∥ + ∥y * (x 1 ) -y * (x 2 )∥ + 1 n n i=1 ∥z * i (x 1 ) -z * i (x 2 )∥ + L f,1 µ f 1 n n i=1 ∇z * i (x 1 ) -∇z * i (x 2 ) (b) ≤ 1 + L g,1 µ g + 1 + L g,1 µ g L f,1 µ f 2 L f,2 µ f + 1 + L g,1 µ g 2 L f,1 L g,2 µ f µ g ∥x 1 -x 2 ∥,where (a) uses Assumption 4.4 and Lemma D.2; (b) follows from Assumption 4.4, Lemma D.2, and eq. (10) . Similarly to eq. ( 10), from eq. ( 7), if we simplify the notation asEQUATION) For the first term in eq. ( 13), via Lemma D.1, we haveEQUATIONwhere (a) uses Lemma D.2; (b) follows from Lemmas D.2, D.3 and λ ≥ (1 +EQUATIONEQUATIONwhere (a) uses Assumption 4.4 and Lemma D.2; (b) uses λ ≥ (1 +Lg,1 µg ) L f,1 µ f + 1 L f,1Lg,1 . We also haveEQUATIONwhere (a) uses Lemma D.2. Combining eq. ( 14), eq. ( 15), eq. ( 16) with the results in Lemma D.1, we haveEQUATIONg,1µ 2 g 1 + 1 + L g,1 µ g L f,1 µ f + 12L g,1 µ g ∥x 1 -x 2 ∥.Thus, the proof is complete.Lemma D.4. Under Assumptions 4.3, 4.4, for any given x and , the gap between the optimal solutions of the lower-level problem z * i (x) and the surrogate minimax problem z * λ,i (x) can be bounded as∥z * λ,i (x) -z * i (x)∥ ≤ L f,0 µgλ , ∥∇z * λ,i (x) -∇z * i (x)∥ ≤ 1 λ • 1 µg L f,0 Lg,2 µg + L f,1 1 + 1 + Lg,1 µg L f,1 µ f + 6Lg,1 µ 2 g 1 + 1 + Lg,1 µg • L f,1 + L f,0 Lg,2 µg ,for any i ∈ {1, ..., n}, where we assume λ ≥ max2L f,1 µg , (1 + Lg,1 µg ) L 2 f,1 3µ f Lg,1 .Proof. For each block, we can have that∥z * λ,i (x) -z * i (x)∥ (a) ≤ 1 µ g ∇ z g i x, z * λ,i (x) -∇ z g i x, z * i (x) (b) ≤ 1 µ g λ ∇ z f i (x, y * (x), z * λ,i (x)) (c) ≤ L f,0 µ g λ ,where (a) uses Assumption 4.3; (b) follows from the definition of z * i (x) and z * λ,i (x); (c) uses Assumption 4.4. For the second part, since ∇ z g i x, z * i (x) = 0, ∇ z L i x, y * (x), z * λ,i (x) = 0, we have∇ 2 xz g i x, z * i (x) + ∇z * i (x)∇ 2 zz g i x, z * i (x) = 0, ∇ 2 xz L i x, y, z * λ,i (x) + ∇y * (x)∇ 2 yz L i x, y,z * λ,i (x) + ∇z * λ,i (x)∇ 2 zz L i x, y, z * λ,i (x) = 0, which indicates that ∇z * i (x) = -∇ 2 xz gi x, z * i (x) ∇ 2 zz gi x, z * i (x) -1 , ∇z * λ,i (x) = -∇ 2 xz Li x, y * (x), z * λ,i (x) + ∇y * (x)∇ 2 yz Li x, y, z * λ,i (x) ∇ 2 zz Li x, y * (x), z * λ,i (x) -1 = - ∇ 2 xz Li x, y * (x), z * λ,i (x) + ∇y * (x)∇ 2 yz Li x, y, z * λ,i (x) λ ∇ 2 zz Li x, y * (x), z * λ,i (x) λ -1 .Then the gap can be displayed as∇z * λ,i (x) -∇z * i (x) ≤ ∇ 2 xz gi x, z * i (x) - ∇ 2 xz Li x, y * (x), z * λ,i (x) + ∇y * (x)∇ 2 yz Li x, y, z * λ,i (x) λ • ∇ 2 zz gi x, z * i (x) -1 + ∇ 2 xz Li x, y * (x), z * λ,i (x) + ∇y * (x)∇ 2 yz Li x, y, z * λ,i (x) λ • ∇ 2 zz gi x, z * i (x) -1 - ∇ 2 zz Li x, y * (x), z * λ,i (x) λ -1 (a) ≤ 1 µg ∇ 2 xz gi x, z * i (x) -∇ 2 xz gi x, z * λ,i (x) + ∇ 2 xz fi x, y * (x), z * λ,i (x) + ∇y * (x)∇ 2 yz fi x, y, z * λ,i (x) λ + 3Lg,1 1 + 1 + Lg,1 µg • 2 µ 2 g L f,1 + L f,0 Lg,2 µg 1 λ ≤ 1 µg Lg,2∥z * λ,i (x) -z * i (x)∥ + 1 λ • L f,1 1 + 1 + Lg,1 µg L f,1 µ f + 1 λ • 6Lg,1 µ 2 g 1 + 1 + Lg,1 µg • L f,1 + L f,0 Lg,2 µg ≤ 1 λ • 1 µg L f,0 Lg,2 µg + L f,1 1 + 1 + Lg,1 µg L f,1 µ f + 1 λ • 6Lg,1 µ 2 g 1 + 1 + Lg,1 µg • L f,1 + L f,0 Lg,2 µg ,where (a) can be satisfied because∇ 2 zz g i x, z * i (x) -1 - ∇ 2 zz L i x, y * (x), z * λ,i (x) λ -1 = ∇ 2 zz g i x, z * i (x) -1 • ∇ 2 zz L i x, y * (x), z * λ,i (x) λ -∇ 2 zz g i x, z * i (x) • ∇ 2 zz L i x, y * (x), z * λ,i (x) λ -1 (a.1) ≤ 2 µ 2 g ∇ 2 zz f i x, y * (x), z * λ,i (x) λ + ∇ 2 zz g i x, z * λ,i (x) -∇ 2 zz g i x, z * i (x) ≤ 2 µ 2 g L f,1 λ + L g,2 z * λ,i (x) -z * i (x) ≤ 2 µ 2 g L f,1 + L f,0 L g,2 µ g 1 λ ,where (a.1) uses Assumption 4.3 and Lemma D.1. Then, the proof is complete.Lemma D.5. Under Assumptions 4.3, 4.4, the gap between ∇Φ(x) and H * (x) can be bounded as∇Φ(x) -H * (x) 2 ≤ C gap λ 2 ,whereEQUATIONL f,0 µg 4 and we assume λ≥ max 2L f,1 µg , (1 + Lg,1 µg ) L 2 f,1 3µ f Lg,1 .Proof. By the definitions of ∇F x, y * (x), z * (x) and H * (x), we haveEQUATIONFor any i ∈ {1, ..., n}, we haveEQUATIONEQUATIONwhere (a) follows from Assumption 4.3, 4.4 and eq. ( 7); (b) follows from Assumption 4.3, 4.4 and Lemma 1 in [44] ; (c) uses Lemma D.4. The proof is finished by substituting eq. ( 18) into eq. ( 17).Lemma D.6. Under Assumptions 4.3, 4.4, the gradient of Lagrangian function with optimal solutions H * (x) is L * ,1 -Lipschitz continuous in x, where we define L * ,1 := 1+12Lg,1µg + 1+ Lg,1 µg L f,1 µ f L f,1 + 1+ Lg,1 µg L f,0 Lg,2 µg +L g,2 1 µg L f,0 Lg,2 µg +L f,1 1+(1+ Lg,1 µg ) L f,1 µ f + 6Lg,1 µ 2 g 1+ 1+ Lg,1 µg L f,1 + L f,0 Lg,2 µgand we assume λ≥ 2L f,1 /µ g , (1 + Lg,1 µg ) L 2 f,1 3µ f Lg,1 , (1 + Lg,1 µg ) L f,1 L f,2 3µ f Lg,1 , L f,1 L * ,y 6Lg,1 1 + (1 + Lg,1 µg ) L f,1 µ f + 12Lg,1 µg -1 , (1 + Lg,1 µg ) L f,1 µ f + 1 L f,1Lg,1 .Proof. Recall that in eq. ( 6),H * (x) = 1 n n i=1 ∇ x f i x, y * (x), z * λ,i (x) + λ ∇ x g i x, z * λ,i (x) -∇ x g i x, z * i (x) .Then we haveEQUATIONBy taking norm, we have ∥∇H * (x)∥ ≤ 1 n n i=1 ∇ 2 xx f i x, y * (x), z * λ,i (x) + 1 n n i=1 ∥∇y * (x)∥ ∇ 2 xy f i x, y * (x), z * λ,i (x) + 1 n n i=1 ∥∇z * λ,i (x)∥ ∇ 2 xz f i x, y * (x), z * λ,i (x) + λ n n i=1 ∇ 2 xx g i x, z * λ,i (x) -∇ 2 xx g i x, z * i (x) + ∥∇z * i (x)∥ • ∇ 2 xz g i x, z * λ,i (x) -∇ 2 xz g i x, z * i (x) + ∥∇z * λ,i (x) -∇z * i (x)∥ • ∇ 2 xz g i x, z * λ,i (x) (a) ≤ 1 + 12L g,1 µ g + 1 + L g,1 µ g L f,1 µ f L f,1 + λ 1 + L g,1 µ g L g,2 ∥z * λ,i (x) -z * i (x)∥ + λL g,1 ∥∇z * λ,i (x) -∇z * i (x)∥ (b) ≤ 1 + 12L g,1 µ g + 1 + L g,1 µ g L f,1 µ f L f,1 + 1 + L g,1 µ g L f,0 L g,2 µ g + L g,2 1 µ g L f,0 L g,2 µ g + L f,1 1 + 1 + L g,1 µ g L f,1 µ f + 6L g,1 µ 2 g 1 + 1 + L g,1 µ g • L f,1 + L f,0 L g,2E L * (x t+1 ) -L * (x t ) ≤ - η x 2 E∥H * (x t )∥ 2 - η x 2 E∥ h t x ∥ 2 + η 2 x L * ,1 2 E∥h t x ∥ 2 + 3η x L 2 f,1 2 E y t -y * (x t ) 2 + 3η x L 2 λ,1 2 E 1 n n i=1 z i,t -z * λ,i (x t ) 2 + 1 n n i=1 v i,t -z * i (x t )2 for all t ∈ {0, 1, ..., T -1}, where we assume λ ≥ 2L f,1 µg .Proof. Recall the definitions of L * (x) and H * (x) in eq. ( 6). By using the smoothness of L * (x t ) in Lemma D.6, we have thatE L * (x t+1 ) ≤E L * (x t ) + E⟨H * (x t ), x t+1 -x t ⟩ + L * ,1 2 E∥x t+1 -x t ∥ 2 =E L * (x t ) -η x E⟨H * (x t ), h t x ⟩ + η 2 x L * ,1 2 E∥h t x ∥ 2 =E L * (x t ) -η x ⟨H * (x t ), h t x ⟩ + η 2 x L * ,1 2 E∥h t x ∥ 2 =E L * (x t ) - η x 2 E∥H * (x t )∥ 2 - η x 2 E∥ h t x ∥ 2 + η x 2 E∥H * (x t ) -h t x ∥ 2 + η 2 x L * ,1 2 E∥h t x ∥ 2 (a) ≤ E L * (x t ) - η x 2 E∥H * (x t )∥ 2 - η x 2 E∥ h t x ∥ 2 + η 2 x L * ,1 2 E∥h t x ∥ 2 + 3η x L 2 f,1 2 E y t -y * (x t ) + 3η x L 2 λ,1 2 E 1 n n i=1 z i,t -z * λ,i (x t ) + 1 n n i=1 v i,t -z * i (x t ) ,where (a) follows fromE∥H * (x t ) -h t x ∥ 2 = E 1 n n i=1 ∇ x L i x t , y * (x t ), z * λ,i (x t ), z * i (x t ) -∇ x L i x t , y t , z i,t , v i,t 2 (a.1) ≤ 1 n n i=1 E ∇ x L i x t , y * (x t ), z * λ,i (x t ), z * i (x t ) -∇ x L i x t , y t , z i,t , v i,t 2 (a.2) ≤ 3L 2 f,1 E y t -y * (x t ) 2 + 3L 2 λ,1 E 1 n n i=1 z i,t -z * λ,i (x t ) 2 + 1 n n i=1 v i,t -z * i (x t ) 2 ,and (a.1) uses Jensen inequality; (a.2) follows from Assumption 4.4 and Lemma D.1. Then, the proof is complete.Lemma E.2. Under Assumptions 4.3, 4.4, 4.5, 4.6, the estimators of v i , z i , y and x can be bounded asE∥h t v,i ∥ 2 ≤ 2L 2 g,1 E∥v i,t -z * i (x t )∥ 2 + 2σ 2 g , E∥h t z,i ∥ 2 ≤ 4(L 2 f,1 + λ 2 L 2 g,1 ) E∥y t -y * (x t )∥ 2 + E∥z i,t -z * λ,i (x t )∥ 2 + 4(σ 2 f + λ 2 σ 2 g ), E∥h t y ∥ 2 ≤ σ 2 f |I t | + (n -|I t |)σ 2 th (n -1)|I t | + 1 + β 2 th |I t | L 2 f,1 E∥y t -y * (x t )∥ 2 + 1 n n i=1 E∥v i,t -z * i (x t )∥ 2 , E h t x 2 ≤ E h t x 2 + 3(n -|I t |) (n -1)|I t | (L 2 f,0 + 2λ 2 L 2 g,0 ) + 3 |I t | (σ 2 f + 2λ 2 σ 2 g ).for any i ∈ {1, ..., n} and t ∈ {0, 1, ..., T -1}.Proof. By using the definition of z * i (x t ), we can have thatE∥h t v,i ∥ 2 ≤ 2E∥∇ z g i (x t , v i,t ; ξ v i,t ) -∇ z g i (x t , v i,t )∥ 2 + 2E∥∇ z g i (x t , v i,t ) -∇ z g i (x t , z * i (x t ))∥ 2 ≤ 2L 2 g,1 E∥v i,t -z * i (x t )∥ 2 + 2σ 2 g . Similarly, we have E∥h t z,i ∥ 2 ≤ 2E∥∇ z L i (x t , y t , z i,t , v i,t ) -∇ z L i (x t , y t , z i,t , v i,t ; ξ z i,t )∥ 2 + 2E∥∇ z L i (x t , y t , z i,t , v i,t ) -∇ z L i (x t , y * (x t ), z * λ,i (x t ), v i,t )∥ 2 ≤ 4(L 2 f,1 + λ 2 L 2 g,1 ) E∥z i,t -z * λ,i (x t )∥ 2 + E∥y t -y * (x t )∥ 2 + 4(σ 2 f + λ 2 σ 2 g ).Next, for the estimator of x, we haveEQUATIONwhere (a) uses unbiased estimation in Assumption 4.5. For the first part of eq. ( 20), since tasks are selected without replacement, we haveEQUATIONwhere (a) uses the unbiased estimation assumption in Assumption 4.5. For the second part of eq. ( 20), we haveEQUATIONwhere (a) used the Lemma A.1 in [32] ; (b) uses Assumption 4.4. By combining eq. ( 22) with eq. ( 21), the fourth inequality is proved. Last, for the estimator of y, we haveE∥h t y ∥ 2 =E 1 |I t | i∈It ∇ y f i (x t , y t , v i,t ; ξ y i,t ) (a) = E 1 |I t | i∈It ∇ y f i (x t , y t , v i,t ; ξ y i,t ) -∇ y f i (x t , y t , v i,t ) 2 + E 1 |I t | i∈It ∇ y f i (x t , y t , v i,t ) 2 (b) ≤ 1 |I t | 2 i∈It E ∇ y f i (x t , y t , v i,t ; ξ y i,t ) -∇ y f i (x t , y t , v i,t ) 2 + n(|I t | -1) |I t |(n -1) E 1 n n i=1 ∇ y f i (x t , y t , v i,t ) 2 + n -|I t | (n -1)|I t | • 1 n n i=1 E ∇ y f i (x t , y t , v i,t ) 2 (c) ≤ σ 2 f |I t | + (n -|I t |)σ 2 th (n -1)|I t | + n(|I t | -1) + β 2 th (n -|I t |) |I t |(n -1) E 1 n n i=1 ∇ y f i (x t , y t , v i,t ) 2 (d) ≤ σ 2 f |I t | + (n -|I t |)σ 2 th (n -1)|I t | + n(|I t | -1) + β 2 th (n -|I t |) |I t |(n -1) E 1 n n i=1 ∇ y f i (x t , y t , v i,t ) -∇ y f i x t , y * (x t ), z * i (x t ) 2 (e) ≤ σ 2 f |I t | + (n -|I t |)σ 2 th (n -1)|I t | + n(|I t | -1) + β 2 th (n -|I t |) |I t |(n -1) L 2 f,1 E∥y t -y * (x t )∥ 2 + 1 n n i=1 E∥v i,t -z * i (x t )∥ 2 (f ) ≤ σ 2 f |I t | + (n -|I t |)σ 2 th (n -1)|I t | + 1 + β 2 th |I t | L 2 f,1 E∥y t -y * (x t )∥ 2 + 1 n n i=1 E∥v i,t -z * i (x t )∥ 2 ,where Lemma E.3. Under Assumptions 4.3, 4.4, 4.5, 4.6, there exists δ v,1 , δ z,1 , δ y,1 such that the iterates of v i,t , z i,t and y t in Algorithm 1 satisfy1 n n i=1 E vi,t+1 -z * i (xt+1) 2 -E vi,t -z * i (xt) 2 ≤ -ηvµg + δv • 1 n n i=1 E vi,t -z * i (xt) 2 + 2η 2 v (1 + δv)σ 2 g + η 2 x L 2 g,1 δv,1µ 2 g E∥ h t x ∥ 2 + η 2 x L 2 g,1 µ 2 g + L * ,z 2 E∥h t x ∥ 2 , 1 n n i=1 E zi,t+1 -z * λ,i (xt+1) 2 -E zi,t -z * λ,i (xt) 2 ≤ - ηzλµg 4 + δz 1 n n i=1 E zi,t -z * λ,i (xt) 2 + (1 + δz) 2ηzL 2 f,1 λµg + 8η 2 z λ 2 L 2 g,1 E∥yt -y * (xt)∥ 2 + 144η 2 x L 2 g,1 δz,1µ 2 g E h t x 2 + 144η 2 x L 2 g,1 µ 2 g + η 2 x L * ,z λ 2 E∥h t x ∥ 2 + 8(1 + δz)η 2 z λ 2 σ 2 g , E∥yt+1 -y * (xt+1)∥ 2 -E∥yt -y * (xt)∥ 2 ≤ -ηyµ f + η 2 y (1 + δy) 1 + β 2 th |It| L 2 f,1 + δy E∥yt -y * (xt)∥ 2 + η 2 y (1 + δy) σ 2 f |It| + (n -|It|)σ 2 th (n -1)|It| + η 2 x δy,1 1 + Lg,1 µg 2 L 2 f,1 µ 2 f E h t x 2 + ηyL 2 f,1 µ f + η 2 y 1 + β 2 th |It| L 2 f,1 (1 + δy) • 1 n n i=1 E∥vi,t -z * i (xt)∥ 2 + η 2 x L * ,y 2 + 1 + Lg,1 µg 2 L 2 f,1 µ 2 f E h t x 2 ,for all t ∈ {0, ..., T -1}, where we defineδ v := δ v,1 + 3η 2 x L * ,z 2 (L 2 f,0 + 2λ 2 L 2 g,0 ), δ z := δ v,1 + 3η 2 x L * ,z λ 2 (L 2 f,0 +2λ 2 L 2 g,0 ), δ y := δ y,1 + 3η 2 x L * ,y 2 (L 2 f,0 +2λ 2 L 2 g,0) and we assume λ ≥ 2L f,1 /µ g , (1+Lg,1 µg ) L 2 f,1 3µ f Lg,1 , (1+ Lg,1 µg ) L f,1 L f,2 3µ f Lg,1 , L f,1 L * ,y 6Lg,1 1+(1+ Lg,1 µg ) L f,1 µ f + 12Lg,1 µg -1 , (1+ Lg,1 µg ) L f,1 µ f +1 L f,1 Lg,1 , η v ≤ µg 2L 2 g,1 , η z ≤ µg 32L 2 g,1 λ .Proof. For the iterations of the lower-level problem, we haveEQUATION)For the first term of eq. ( 23), we haveEQUATIONwhere (a) follows from Assumption 4.3; (b) uses Lemma E.2; (c) results fromη v ≤ µg 2L 2 g,1. For the second term of eq. ( 23), we haveEQUATION)For the last term of eq. ( 23), we haveEQUATION)where (a) use Lemma D.3 and Lemma 1 in [44] ; (b) definesEQUATION(L 2 f,0 + 2λ 2 L 2 g,0 ). By plugging eq. ( 24), eq. ( 25), eq. ( 26) into eq. ( 23), we haveE vi,t+1 -z * i (xt+1) 2 -E vi,t -z * i (xt) ≤(-ηvµg + δv)E vi,t -z * i (xt) 2 + 2η 2 v (1 + δv)σ 2 g + η 2 x L 2 g,1 δv,1µ 2 g E∥ h t x ∥ 2 + η 2 x L 2 g,1 µ 2 g + L * ,z 2 E∥h t x ∥ 2 .Then we get1 n n i=1 E v i,t+1 -z * i (x t+1 ) 2 -E v i,t -z * i (x t ) 2 ≤ -η v µ g + δ v • 1 n n i=1 E v i,t -z * i (x t ) 2 + 2η 2 v (1 + δ v )σ 2 g + η 2 x L 2 g,1 δ v,1 µ 2 g E∥ h t x ∥ 2 + η 2 x L 2 g,1 µ 2 g + L * ,z 2 E∥h t x ∥ 2 .Thus, the first inequality in the lemma is proved. Similarly, we haveEQUATION)We can bound the first term in eq. ( 27) similarly with eq. ( 24) asEQUATIONwhere (a) uses Lemma E.2 and λ ≥ maxL f,1Lg,1 ,σ f σg ; (b) uses η z λ ≤ µg 32L 2 g,1; we bound the second term in eq. ( 27) asEQUATION)and we bound the last term in eq. ( 27) similarly with eq. ( 26) asEQUATION)whereδ z := δ z,1 + 3η 2 x L * ,z λ 2 (L 2 f,0 + 2λ 2 L 2 g,0 ). By plugging eq. ( 28), eq. ( 29), eq. ( 30) into eq. ( 27), we haveE z i,t+1 -z * λ,i (x t+1 ) 2 -E z i,t -z * λ,i (x t ) ≤ - η z λµ g 4 + δ z E z i,t -z * λ,i (x t ) 2 + (1 + δ z ) 2η z L 2 f,1 λµ g + 8η 2 z λ 2 L 2 g,1 E∥y t -y * (x t )∥ 2 + 144η 2 x L 2 g,1 δ z,1 µ 2 g E h t x 2 + 144η 2 x L 2 g,1 µ 2 g + η 2 x L * ,z λ 2 E∥h t x ∥ 2 + 8(1 + δ z )η 2 z λ 2 σ 2 g ,After telescoping, we obtain1 n n i=1 E zi,t+1 -z * λ,i (xt+1) 2 -E zi,t -z * λ,i (xt) 2 ≤ - ηzλµg 4 + δz 1 n n i=1 E zi,t -z * λ,i (xt) 2 + (1 + δz) 2ηzL 2 f,1 λµg + 8η 2 z λ 2 L 2 g,1 E∥yt -y * (xt)∥ 2 + 144η 2 x L 2 g,1 δz,1µ 2 g E h t x 2 + 144η 2 x L 2 g,1 µ 2 g + η 2 x L * ,z λ 2 E∥h t x ∥ 2 + 8(1 + δz)η 2 z λ 2 σ 2 g .Then the second inequality in the lemma is proved. Last, for y t and y * (x t ), we haveEQUATIONWe can bound the first term in eq. ( 31) asEQUATIONwhere (a) uses the definition of y * (x t ) and eq. ( 5); (b) uses strong concavity of f i in y; (c) follows from definition of y * (x t ) and Assumption 4.4; (d) uses Lemma E.2. We can bound the second term in eq. ( 31) asEQUATIONwhere (a) follows from Lemma D.2. Also, we can get the bound of the last term as EQUATIONEQUATION(L 2 f,0 + 2λ 2 L 2 g,0 ). By plugging eq. ( 32), eq. ( 33), eq. ( 34) into eq. ( 34), we getE∥y t+1 -y * (x t+1 )∥ 2 -E∥y t -y * (x t )∥ 2 ≤ -η y µ f + η 2 y (1 + δ y ) 1 + β 2 th |I t | L 2 f,1 + δ y E∥y t -y * (x t )∥ 2 + η 2 y (1 + δ y ) σ 2 f |I t | + (n -|I t |)σ 2 th (n -1)|I t | + η 2 x δ y,1 1 + L g,1 µ g 2 L 2 f,1 µ 2 f E h t x 2 + η y L 2 f,1 µ f + η 2 y 1 + β 2 th |I t | L 2 f,1 (1 + δ y ) • 1 n n i=1 E∥v i,t -z * i (x t )∥ 2 + η 2 x L * ,y 2 + 1 + L g,1 µ g 2 L 2 f,1 µ 2 f E h t x 2 .Then the last inequality is proved. Thus, the proof is complete.We define the Lyapunov function asEQUATIONwhere the coefficients are given byEQUATIONFor convenience, we define the following constants:EQUATIONg,1EQUATIONWe also constrain the conditions as below:EQUATIONf,127µ 2 f L 2 g,1 3L 2 f,1 2 + 216L 2 g,1 L 2 f,1 µ 2 g + 864L 2 g,1 µg , ηx ≤ 1 16C1, ηy ≤ minEQUATIONPlugging Lemma E.1, Lemma E.3 into eq. ( 35) and using eq. ( 36), we have the descent in the Lyapunov function asEQUATIONProof. To simplify the problem, we assume |I t | = P for t = 0, ..., T -1. By taking summation of eq. ( 39) from t = 0 to T -1, we getEQUATIONBy using Lemma D.5 and eq. ( 40), we haveEQUATIONwhere (a) uses eq. ( 40); (b) takesη x = O(T -5 7 ), η y = O(T -2 7 ), η z = O(T -5 7 ), η v = O(T -4 7 ), λ = O(T 1 7), which satisfies eq. (38) . Thus, Theorem 4.10 is proved.Proof. From eq. ( 41), to achieve ϵ-accurate stationary point of the objective function Φ(x) in definition 4.2, we let1 T T -1 t=0 E∥∇Φ(x t )∥ 2 = O(T -2 7 ) ≤ ϵ.As a result, we can see that the epochs number we need is T = O(ϵ -72 ). The total sample complexity is P T = O(P ϵ -7 2 ). Then, we finish the proof.F Proofs of Theorem 4.12 and Corollary 4. E L * (x t+1 ) -L * (x t ) ≤ - η x 2 E∥H * (x t )∥ 2 - η x 2 E∥ h t x ∥ 2 + η 2 x L * ,1 2 E 1 |I t | i∈It ∇ x L i (x t , y t , z K i,t , v K i,t ) 2 + 3η x L 2 f,1 2 E y t -y * (x t ) 2 + 3η x L 2 λ,1 2 E 1 n n i=1 z K i,t -z * λ,i (x t ) 2 + 1 n n i=1 v K i,t -z * i (x t )2 for all t ∈ {0, 1, ..., T -1}, where we assume λ ≥2L f,1 µg .Proof. Recall the definitions of L * (x) and H * (x) in eq. ( 6). By using the smoothness of L * (x t ) in Lemma D.6, we have thatE L * (x t+1 ) ≤E L * (x t ) + E⟨H * (x t ), x t+1 -x t ⟩ + L * ,1 2 E∥x t+1 -x t ∥ 2 =E L * (x t ) -η x E⟨H * (x t ), h t x ⟩ + η 2 x L * ,1 2 E 1 |I t | i∈It ∇ x L i (x t , y t , z K i,t , v K i,t ) 2 =E L * (x t ) - η x 2 E∥H * (x t )∥ 2 - η x 2 E∥ h t x ∥ 2 + η x 2 E∥H * (x t ) -h t x ∥ 2 + η 2 x L * ,1 2 E 1 |I t | i∈It ∇ x L i (x t , y t , z K i,t , v K i,t ) 2 (a) ≤ E L * (x t ) - η x 2 E∥H * (x t )∥ 2 - η x 2 E∥ h t x ∥ 2 + η 2 x L * ,1 2 E 1 |I t | i∈It ∇ x L i (x t , y t , z K i,t , v K i,t ) 2 + 3η x L 2 f,1 2 E y t -y * (x t ) 2 + 3η x L 2 λ,1 2 E 1 n n i=1 z K i,t -z * λ,i (x t ) 2 + 1 n n i=1 v K i,t -z * i (x t ) 2 ,where (a) usesE∥H * (x t ) -h t x ∥ 2 = E 1 n n i=1 ∇ x L i x t , y * (x t ), z * λ,i (x t ), z * i (x t ) -∇ x L i x t , y t , z K i,t , v K i,t 2 (a.1) ≤ 1 n n i=1 E ∇ x L i x t , y * (x t ), z * λ,i (x t ), z * i (x t ) -∇ x L i x t , y t , z K i,t , v K i,t 2 (a.2) ≤ 3L 2 f,1 E y t -y * (x t ) 2 + 3L 2 λ,1 E 1 n n i=1 z K i,t -z * λ,i (x t ) 2 + 1 n n i=1 v K i,t -z * i (x t ) 2 ,and (a.1) uses Jensen inequality; (a.2) follows from Lemma D.1. Then, the proof is complete.Lemma F.2. Under Assumptions 4.3, 4.4, 4.5, we have the bounds of the estimators of y t and x t asE 1 |I t | i∈It ∇ y f i (x t , y t , v K i,t ) 2 ≤ 1 + β 2 th |I t | L 2 f,1 E∥y t -y * (x t )∥ 2 + 1 n n i=1 E∥v K i,t -z * i (x t )∥ 2 + (n -|I t |)σ 2 th (n -1)|I t | , E 1 |I t | i∈It ∇ x L i (x t , y t , z K i,t , v K i,t ) 2 ≤ E h t x 2 + 3(n -|I t |) (n -1)|I t | (L 2 f,0 + 2λ 2 L 2 g,0 )for any i ∈ {1, ..., n} and t ∈ {0, 1, ..., T -1}.Proof. For the estimator of y, we haveEQUATION≤ (n -|It|)σ 2 th (n -1)|It| + n(|It| -1) + β 2 th (n -|It|) |It|(n -1) L 2 f,1 E∥yt -y * (xt)∥ 2 + 1 n n i=1 E∥v K i,t -z * i (xt)∥ 2 (e) ≤ (n -|It|)σ 2 th (n -1)|It| + 1 + β 2 th |It| L 2 f,1 E∥yt -y * (xt)∥ 2 + 1 n n i=1 E∥v K i,t -z * i (xt)∥ 2 ,where (a) follows from the Lemma A. EQUATIONThen, the proof is complete.Lemma F.3. Under Assumptions 4.3, 4.4, for ∀δ ∈ R + , we assume that ∥z * i (x t )∥ ≤ B for some B < ∞. Then we havemax E∥v K i,t -z * i (x t )∥ 2 , E∥z K i,t -z * λ,i (x t )∥ 2 ≤ ϵ sub when K ≥ max 1 η v t µg log 2 ∥v 0 i,t ∥ 2 +B 2 ϵ sub , 1 η z t L f,1 log 3 ∥z 0 i,t ∥ 2 + L 2 f,0 4L 2 f,1 +B 2 ϵ sub, where η v t ∈ (0, 1 2Lg,1 ),η z t ∈ (0, 1 4λLg,1 ), λ ≥ L f,1 µg .Proof. From Lemma D.1, we have that L i is λµg 2 -strongly convex in z and we have that L i is 2λL g,1 -Lipschitz continue in z when λ ≥ L f,1 µg ; also, from Assumption 4.3, 4.4, we have that g i is µ g -strongly convex in v and L g,1 -smooth in v. According to Theorem 3.6 in [11] , by taking 0 < η v t < 1 2Lg,1 and 0 < η z t < 1 4λLg,1 , we haveE∥v K i,t -z * i (x t )∥ 2 ≤ (1 -η v t µ g ) K E∥v 0 i,t -z * i (x t )∥ 2 , E∥z K i,t -z * λ,i (x t )∥ 2 ≤ (1 - η z t λµ g 2 ) K E∥z 0 i,t -z * λ,i (x t )∥ 2 .To make sure E∥v K i,t -z * i (x t )∥ 2 ≤ ϵ sub and E∥z K i,t -z * λ,i (x t )∥ 2 ≤ ϵ sub for some ϵ sub ≥ 0, we let µg . Both can be achieved by takingEQUATION(1 - η z t λµ g 2 ) K E∥z 0 i,t -z * λ,i (x t )∥ 2 ≤3(1 - η z t λµ g 2 ) K ∥z 0 i,t ∥ 2 + E∥z * i (x t ) -z * λ,i (x t )∥ 2 + E∥z * i (x t )∥ 2 (a) ≤ 3(1 - η z t λµ g 2 ) K ∥z 0 i,t ∥ 2 + L 2 f,0 µ 2 g λ 2 + B 2 (b) ≤3(1 - η z t λµ g 2 ) K ∥z 0 i,t ∥ 2 + L 2 f,0 4L 2 f,1 + B 2K ≥ max 1 η v t µ g log 2 ∥v 0 i,t ∥ 2 + B 2 ϵ sub , 1 η z t L f,1 log 3 ∥z 0 i,t ∥ 2 + L 2 f,0 4L 2 f,1 + B 2 ϵ sub .Then the proof is complete.Lemma F.4. Under the Assumptions 4.3, 4.4, 4.5, the iterates of y t updates according to Algorithm 2 satisfyE∥y t+1 -y * (x t+1 )∥ 2 -E∥y t -y * (x t )∥ 2 ≤ -η y µ f + η 2 y (1 + δ y ) 1 + β 2 th |I t | L 2 f,1 + δ y E∥y t -y * (x t )∥ 2 + η 2 y (1 + δ y ) (n -|I t |)σ 2 th (n -1)|I t | + η y L 2 f,1 µ f + η 2 y 1 + β 2 th |I t | L 2 f,1 (1 + δ y ) • 1 n n i=1 E∥v i,t -z * i (x t )∥ 2 + η 2 x δ y,1 1 + L g,1 µ g 2 L 2 f,1 µ 2 f E h t x 2 + η 2 x L * ,y 2 + 1 + L g,1 µ g 2 L 2 f,1 µ 2 f E 1 |I t | i∈It ∇ x L i (x t , y t , z K i,t , v K i,t ) 2for any t ∈ {0, ..., T -1}, where we assume λ ≥ 2L f,1 /µ g , (1 +Lg,1 µg ) L 2 f,1 3µ f Lg,1 , (1 + Lg,1 µg ) L f,1 L f,2 3µ f Lg,1 , L f,1 L * ,y 6Lg,1 1 + (1 + Lg,1 µg ) L f,1 µ f + 12Lg,1 µg -1 , (1 + Lg,1 µg ) L f,1 µ f + 1 L f,1Lg,1 .Proof. For y and y * (x), we haveEQUATIONWe can bound the first term in eq. ( 43) asEQUATIONwhere (a) uses the definition of y * (x t ) and eq. ( 5); (b) uses strong concavity of f i in y; (c) follos from definition of y * (x t ) and Assumption 4.4; (d) uses Lemma F.2. We can bound the second term in eq. ( 43) asEQUATIONwhere (a) follows from Lemma D.2. Also, we can get the bound of the last term asEQUATIONwhere (a) uses Lemma D. EQUATION(L 2 f,0 + 2λ 2 L 2 g,0 ). By plugging eq. ( 44), eq. ( 45), eq. ( 46) into eq. ( 43), we getE∥y t+1 -y * (x t+1 )∥ 2 -E∥y t -y * (x t )∥ 2 ≤ -η y µ f + η 2 y (1 + δ y ) 1 + β 2 th |I t | L 2 f,1 + δ y E∥y t -y * (x t )∥ 2 + η 2 y (1 + δ y ) (n -|I t |)σ 2 th (n -1)|I t | + η y L 2 f,1 µ f + η 2 y 1 + β 2 th |I t | L 2 f,1 (1 + δ y ) • 1 n n i=1 E∥v i,t -z * i (x t )∥ 2 + η 2 x δ y,1 1 + L g,1 µ g 2 L 2 f,1 µ 2 f E h t x 2 + η 2 x L * ,y 2 + 1 + L g,1 µ g 2 L 2 f,1 µ 2 f E 1 |I t | i∈It ∇ x L i (x t , y t , z K i,t , v K i,t ) 2 .Then the proof is complete.F.4 Descent in the Lyapunov Function and Proof of Theorem 4.12We define the Lyapunov function asEQUATIONwhere the coefficient is given byK y = 3ηxL 2 f,1ηyµ f . We also constrain the conditions as below:EQUATIONPlugging Lemma F.1, Lemma E.3 into eq. ( 47), we have the descent in the Lyapunov function asEQUATIONwhere (a) uses Lemma F.2; (b) uses eq. ( 48) and takesK ≥ max 1 η v t µ g log 2E∥v 0 i,t -z * i (x t )∥ 2 ϵ sub , 2 η z t λµ g log 2E∥z 0 i,t -z * λ,i (x t )∥ 2 ϵ sub ; (c) defines C 4 := 3(L 2 f,0 +2λ 2 L 2 g,0 ) λ 2 • max L * ,1 2 , 3L 2 f,1 µ f L * ,y 2 + 1 + Lg,1 µg 2 L 2 f,1 µ 2 fand plugs in K y .Proof. For partial block participation, we take the summation of eq. ( 49) from t = 0 to T -1. Then we haveEQUATIONFor partial block participation, By using Lemma D.5, we haveEQUATIONwhere (a) follows from eq. ( 50); (b) follows from 1 ≤ P < n; (c) takes η x = O(P 3 ). Next, for full block participation (n = P ), we have the descent in the Lyapunov function for full block participation asEQUATIONEQUATIONTaking summation of eq. ( 52) from t = 0 to T -1, we haveEQUATIONBy using Lemma D.5 and eq. ( 53), we haveEQUATIONBy taking ηEQUATION2 ), ϵ sub = O(T -2 ). Then Theorem 4.12 is proved.Proof. For tasks participate in updates partially, by eq. ( 51), we can find the ϵ-stationary point in definition 4.2 once we take T = O(P -3 5 ϵ -3 ). Note that we set the error of sub-loop as ϵ sub = O(P - Similarly, by eq. ( 54), we can find the ϵ-stationary point in definition 4.2 once we take T = O(ϵ -1 ).Note that we set the error of sub-loop asϵ sub = O(T -2 ) = O(ϵ 2 ). Once we take η v = O(1) and η z = O(T -1• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.For MemCS, we focus on the few-shot setting such as meta-learning, where each block contains a small number of samples, and hence we use gradient descent here. However, the algorithm can also be extended to the stochastic setting.), we have the iteration number of sub-loop as K = O log( 1 ϵ ) . Thus, we have the total sample complexity nKT = O(nϵ -1 log( 1 ϵ )) = O(nϵ -1 ). 


Decision: This submission studies the multi-block minimax bilevel optimization problem. Two fully first-order algorithms, FOSL and MemCS, are proposed to address the high computation costs and high memory consumption issues of existing algorithms. The authors convert the original minimax bilevel problem into a simple minimax problem and propose FOSL (first-order single-loop algorithm) to solve the optimization problem efficiently. Then, the authors introduce MemCS with cold-start initialization to avoid storing the weights of blocks and reduce memory consumption.  The authors provide convergence analysis for the proposed algorithms. Experimental results on the benchmark datasets show that the proposed method can achieve better or comparable performance than the baselines.

Reviews: review: paper_summary: paper_summary: The paper introduces FOSL and MemCS that are two new first-order algorithms for multi-block minimax bilevel optimization, demonstrating superior sample complexities and robust performance in empirical evaluations on deep AUC maximization and robust meta-learning applications.
strength_weakness: strength_weakness: 1. The assumptions look quite strong, e.g., Assumption 5.3 requires strong convexity, Assumption 5.4 requires several boundnesses on the derivatives and high-order derivatives, which usually are not satisfied in practice.  
2. It appears that the memory costs have not been compared.
questions: questions: See weakness.
limitations: limitations: Not discussed.
paper_summary: paper_summary: This work studies the multi-block minimax bilevel optimization problem. To address the high computation costs and high memory consumption issues of existing algorithms, this work proposes two fully first-order algorithms, i.e., FOSL and MemCS. Specifically, the authors convert the original minimax bilevel problem into a simple minimax problem and propose FOSL (first-order single-loop algorithm) to solve the optimization problem efficiently. Then, they introduce MemCS with cold-start initialization, which avoids storing the weights of blocks and reduces memory consumption. Moreover, the authors also provide convergence analysis for the proposed algorithms. Experimental results on the benchmark datasets show that the proposed method can achieve better or comparable performance than the baseline.
strength_weakness: strength_weakness: 1. AUC-CT avoids the calculation of second-order matrices and shows comparable efficiency to the proposed first-order algorithm, which reduces the contribution of this work to improving algorithm efficiency. It would be better to provide more discussions.
2. It would be better to provide the memory consumption of baselines for better comparisons.
3. The proposed method only achieves comparable performance to mAUC-CT on CheXpert. It would be better to provide more analysis.
questions: questions: My main concern is about the contribution of this work to computational efficiency (especially compared to AUC-CT).
limitations: limitations: I cannot find the discussion about the limitations of this work.
paper_summary: paper_summary: This work proposes two novel fully first-order algorithms, named FOSL and MemCS, for multi-block minimax bilevel optimization problems. Specifically, the authors reformulate the lower-level problem as a value-function-based constraint and transform the minimax bilevel optimization into a surrogate minimax problem. FOSL and MemCS are proposed to solve the surrogate minimax problem by alternately updating the parameters through SGD. Theoretical analysis of the convergence is conducted and extensive experiments on deep AUC maximization and rank-based robust meta-learning show the effectiveness of the proposed method.
strength_weakness: strength_weakness: 1. I have concerns about the soundness of reformulating the minimax bilevel optimization as a minimax problem in Eq. 2. I hope the authors can conduct more analysis or provide some references that utilize the same technique.

2. I have a question about Proposition 4.9. Will it guarantee that $E|| y_{t+1}-y^*(x_{t+1}) || - E|| y_{t}-y^*(x_{t}) || \le 0$?
questions: questions: Please see the weakness.
limitations: limitations: No potential negative societal impact.
paper_summary: paper_summary: This paper proposes two novel algorithms, FOSL and MemCS, for multi-block minimax bilevel optimization problems, avoiding the high complexity of computing the second-order gradient. Their theoretical analysis is quite solid and their experiments show proposed algorithms have superior performance and robustness in applications.

Overall, the proposed algorithms are novel and well-justified with practical applications. However, further elaboration is needed regarding their practicality and efficiency.
strength_weakness: strength_weakness: Since the paper primarily claims the efficiency of the proposed first-order algorithms, the authors should discuss the scale of problems these algorithms are suitable for. For example, second-order methods may fail when dealing with a large number of variables. In contrast, first-order algorithms generally handle larger-scale problems better, but the paper lacks experimental comparisons in this regard. 

Besides, the gradient calculation procedure is not mentioned in the paper. I believe it is quite important for incorporating optimization problems in neural networks.

There is also a typo in the title of algorithm 2: Cold-star
questions: questions: - Since the theoretical proof is based on various assumptions, are there any restrictions on FOSL and MemCS? For example, do they only handle convex optimization problems? Including the previously mentioned issue of the optimization problem scale, I think the applicable scope of the two algorithms should be discussed in detail.

- Could the authors include a comparison of the runtime differences between FOSL, MemCS, and second-order methods? This would better illustrate the effectiveness of the proposed methods.

- In the experimental results, FOSL and MemCS perform better. Is this because these two algorithms have a better gradient estimator? The authors should provide an explanation for this.

- Additionally, I would like to know how the gradient of the optimization problem is calculated. Is it from implicit differentiation, unrolling methods, or are there any direct analytical solutions of the gradient?

If my concerns are well addressed, I would be happy to raise my score.
limitations: limitations: N/A

Comments: title: Response
comment: Dear Reviewers,

Thank you for taking the time to review our paper and for your valuable feedback. We have provided detailed responses to your questions and would greatly appreciate it if you could let us know if our responses adequately address your concerns, as the discussion period is approaching its end.

Best regards, 

The Authors
Dear Reviewer mptp,

Thanks so much for your updates and for raising your score. We are happy that our responses clarify your questions. We will take your suggestions into our revision.

Best, Authors
Thanks for your detailed explanation. I will raise my score to 6.