First-Order Minimax Bilevel Optimization
Authors: Yifan Yang
Zhaofeng Si
Siwei Lyu
Kaiyi Ji
Venue: NeurIPS 2024 poster (2024)
Keywords: Bilevel Optimization
Machine Learning
Meta Learning
Primary area: optimization

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.

First-Order Minimax Bilevel Optimization
Yifan Yang', Zhaofeng Si", Siwei Lyu and Kaiyi Ji Department of Computer Science and Engineering University at Buffalo
Buffalo, NY 14260
{yyang99, zhaofeng, siweilyu, kaiyiji) edu
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 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 fully single-loop structure by updating all three variables simultaneously. and MemCS a memory-efficiem double-loop algorithm with cold-start initialization. We provide comprehensive convergence analysis for both algorithms under full and partial block participation, and show that their sample complexities match or outperform those of the type of methods in standard bilevel optimization. We evaluate our methods in two applications: the recently proposed multi-task deep AUC maximization and novel rank-based robust meta-learning, Our methods consistently improve over existing methods with better performance over various datasets.
Introduction
In this paper, we study a general multi-block minimax bilevel optimization problem given by
min max F(x. y, = n i=1
Σ
((,, = Σ (<(((,,...<())))))))
seR vERdv
s.t. 2x = arg min gı(z, () (x, zERd.
(I)
where the upper- and lower-level function ft and g, for block take the expectation form w.r.t. the random variables ç. Ç. and are jointly continuously differentiable, z = (af (z), = (x)) ) E Id, xx contains all lower-level optimal solutions, and is the number of blocks. The above problem has various applications in machine learning. including deep AUC maximization [24] 23), meta-learning
[]6]B), byperparameter optimization (17). and robust learning [17). This paper focuses the setting with momconnex--tronglyycoooe. minimax upper-level problem and a strongly-convex lower-level problem.
To date, barring 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 multi-block minimax bilevel optimization. To address this challenge, [17] considered special case where is the simplex variable, and introduced a single-loop gradient descent-asees ascent algorithm, based on the wwo-timescale bilevel
These authors contributed equally to this work.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

framework in [22] proposed single-loop matrix-vector based algorithm for a special case of our problem, where each upper-level function fi is evaluated only at the 4th. coordinate of y. However, these methods require computing the expensive second-order derivatives (i.e., the Hessian matrix or Hessian- vector product) per iteration, and the more efficient first-order approaches have not been explored yet. In this paper, we propose two efficient first-order minimax bilevel algorithms and further apply them to two novel ML applications. Our contributions are summarized as follows.
By converting the original minimax bilevel problem into simple minimax problem, we first propose a fully first-order single-loop algorithm named FOSL, which is easy to implement by updating x, y and z simultaneously, and is computationally efficient without the calculation of any second-order Hessian or Jacobian matrices. We provide a convergence analysis for FOSL under a practical block sampling without replacement setting and show that its sample complexity matches the best-known result of the same type of methods in standard bilevel optimization. Technically, we characterize the gap between the reformulated and original problems and need to deal with the interplay among four variables in the error analysis.
In the settings where the number of blocks is substantial (e.g.. in few-shot meta-learning). it becomes impractical store all block-specific parameters to perform the single-loop optimization. To this end, we also propose a memory-efficient method named MemCS via start initialization, which randomly initializes a new weight for each sampled block, without saving it for the next iteration. We then analyze the convergence of MemCS under the partial-block block and full-block participation, and show that it can achieve better sample complexity than the same type of methods in standard bilevel optimization.
We further apply our approaches to two ML applications: deep AUC maximization and robust meta-learing. The first application pertains to the established field of AUC Maxi- mization, while the second explores a novel application known as Rank-basee Robust Meta- Learning. We show the effectiveness of our methods over a variety of datasets including CIFAR100, CelebA, CheXpert, OGBG-MoIPCBA, Mini-ImageNet and Tiered-ImageNer
2 Related Work
(Minimax) bilevel optimization. Bilevel optimization, introduced in (2]. has been extensively
studied, with constraint-based methods [33 20 50 [1) and gradient-based methods 45
49
57
emerging as two predominant types of approaches. The constraint-base based methods (e.g., 34
38 30
33 (54) reformulated the lower-level problem as a colute-funttion-bae based constraint, and solved it via
different constrained optimization algorithms. More recently, [16] 23 studied the minimax bilevel optimization problem and proposed single-loop algorithms with applications to robust machine learning and deep AUC maximization. In this paper, we propose two efficient, fully first-order algorithms with solid performance guarantees. recent years, there has been a growing interest in maddentt-based methods due to their efficiency in solving machine- problems. Within this category, Iterative Differentiation (ITD) based methods [6]
39 49 27] and Approximate
Implicit Differentiation (AID) based methods I 33 45 14 27
22
are two important classes
distinguished by their approaches to approximating hypergradients.
Deep AUC maximization (DAM). DAM methods are aimed to mitigate the impact of imbalanced data in binary classification by directly maximizing the area under the ROC curve (AUC), perfor- mance metric less affected by imbalanced data. As the AUC is difficult to optimize directly, research on DAM primarily focuses on devising effective optimization methods for its continuous surrogates proposed to reformulate the deep AUC maximization problem as a minimax optimization problem. providing the foundation for stochastic DAM algorithms developed in recent
21 46 8
(37]
years [59 60 18 24 Among them, the most relevant work (24] formulated the DAM problem as a multi-block minimax optimization problem. In this work, we will use this form of DAM to demonstrate the effectiveness of our algorithm. A more comprehensive overview of DAM methods can be found in the survey [56].
Robust meta-learning. Meta-learning provides effective solutions to multi-task learning in few-shot learning settings. In meta-learning, one trains meta-model that can be quickly turned into a model that adapts to new tasks with only few updates. Meta-learning algorithms in real-world applications must be robust to handle corrupted or low-quality data such as outliers. The majority of robust meta-
learning methods encompass filtering [55), re-weighting [48 28 31 36), and re-labeling 43 52 61

---

on the sample level. Moreover, some other works focus on improving task-level robustness 22 58 In this work, we show that robust meta- neta-leannng can be formulated minimax bilevel optimization problem and solved with the proposed algorithm.
3 Algorithms
3.1 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 casttion-bbsed constraint and aim solve the following equivalent problem:
min maxx
(, 1=1
s.t. (1( m.) g z7) S O,
where 2 == arg min_ (e 2). Inspired by 30 we form a Lagrangian L; with Lagrangian multiplier to approximate the original problem for each block in eq. (2) as
(x y, 24, 21) = fi(z. y, 2) + (0,(2z 2,) ge( u.))
where i; is used to approximate the lower-level solution 27 (z) of the in block. Then, we turn to solve the following surrogate minimax problem:
n Σ
min max L(x, 2,2 V.V
Li y, ze;, ve:),
where (21, 2n) E Rdxx, has only one non-zero element of 1 at the ien coordinate. We show later in Section 4.2 that the gap between the gradients F y" (x)) and VL(x, y (x), (x(x), z (x)) of the original and surrogate problems can be effectively bounded by O(1A), where y (2:) denotes the maximize of outer-objective F(x,', z (x)) and each vector (x) in 2 == (x), ..., x (x)) denotes the minimizer of the Lagrangian function (z (z), (where 2t. (x) has not reliance on v). This validates the effectiveness the Lagrangian approximation for sufficiently large. Next, we propose two efficient algorithms, namely FOSL and MemCS, to solve the surrogate problem in eq.
(UI,.., Un) Rd.xn xn and the standard basis vector e
3.2 FOSL: Fully First-Order Single-Loop Method
As shown in Algorithm ! we first sample subset C == {1, n) of blocks without replacement. Noting that 2; and are both block-specific variables, we then apply a stochastic ascent and descent step update v and 2; for block E Ig
U1 Ui +
V Vegi 5t..)
Zi,++1 ب4, 2. (Tt. Dt. 2i,6, Mi,ti
where the gradient of L, w.r.t has no dependence on v. Since the solutions w.r.t variables and depend on all blocks, we use the average of stochastic gradient estimators from the selected blocks in It to update y and as
yt+1 = Dt + fly
V VyJi(Eee Mes Ui. Et,
sEl.
Fe+1 = - - T1e [Ta
V2C,(Tes Bis Z4,4 Et.
eeh
Note that our algorithm takes a simpler fully single-loop structure via updating (Vi,e, 2i,e he.. Zt and y 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, method only uses the first-order gradients.
3.3 MemCS: Memory-Efticien Cold-Start Method
Note that in the single-loop optimization of Algorithm [ block-specific parameters Ue,t and 21,t of blocks in 4, need to be stored for the updates iteration + 1. However, in some ML applications,

---

Algorithm Fully First-Order Single-Loop Method (FOSL)
1: Input: initialization (x0 number of iteration rounds T,, learning rates (Te, My Nex TJo
2: (or(= 0, 1,1,,..... .......TT do
3: Sample blocks Le
for do
5: 01,141 11,t - 7/ ( (iri..))
6: 2j,++1 Zi,t 1/2 V. L Zi,es (.,r)
end for
8:
yc+1 = yt + Th [i Dien, Vyli(zr, De, va,es Enr))
9: 4141 = Th TT. ExEr, VaLil Me, Re,es ei, Ci.
10: end for
Algorithm 2 Memory-Fiffciiet Cold-Start (MemCS)
1: Input: initialization (2o.9o): ). number of iteration rounds T,, learning rates (yee My Us To
2: for (= 0, 1, ..... T
do
3: Sample blocks /e S
do 5: Random initializations e. Ai,t
for
6: for = 0, 1, ...,... Th V v (Ite; . Mi Viet
do
7:
k+1
8:
F. 2,,t n7= V. V. Ut, 2l.e 2
end for
end
11: Mo+1
Eiet, VyJi(an, (i Jo+1 Te TT Eien, V (zL, 28 v5
= Ht + De
12:
13:
end for
such as few-shot meta-learning, the number of blocks/tasks often large, and hence Algorithm can suffer from significant memory consumption. To address this challenge, we propose memory- efficient method named MemCS in Algorithm 2 Differently from the single-loop updates in FOSL, MemCS contains a sub-loop of K steps of gradient descen in updating the block-specific variables od and =,, for à 0, ..., K with random initialization e., and zf.-- After obtaining the outputs K =K of this sub-loop, the remaining step is to update yt and Dz via gradient ascent and descent 2..1 z1,2
similarly as in FOSI..
4
Main Results
4.1
Assumptions
Definition 4.1. A mapping f is L-Lipschitz continuous if [[f(=)) f(x2)) < L|[= xall, for any T1, We say f is L-smooth f is L-Lipschitz continuous.
Since the overall objective is nonconvex w.r.t. we aim to find an e-accurate stationary point. Definition 4.2. We call z as an e-accurate stationary point of the objective function ((x) [ e, where E (0, 1] and E is the output of an algorithm.
We use the following assumptions the subsequent description. Note that these assumptions are widely adopted in existing studies [24] 17].
Assumption 4.3. For any IRd y RRd,, 2 E IRd and i E (1,2, n). (ar, y) and ge y) are twice continuously differentiable, V. is pty-ononglyy concave w.r.t. y and gi is My strongly convex w.r.t. z.
The following assumption imposes the Lipschitz continuity on the upper- and lower-level functions and their derivatives.
For MemCS, we focus on the few-shot setting such as meta-learning where each block contains small number of samples, and hence we use gradient descent here. However, the algorithm can also be extended to the stochastic setting.

---

Assumption 4.4. For any z R E R and i E [1,2,...,n) fi y. is L.p-Lipschiz continuous w.r.t. I, gi gz 2) Lipo-hipschitz continuous w.r.t. 2, (z, is Lm.--smooth and ge(a, y) is -mooth.. In addition, the second-order derivatives V fx ys 2) and V gi (z, y) L and L Lypsships continuous.
are
Next, we make a bounded variance assumption for the gradients in the stochastic setting.
Assumption 4.5. There exist constants of and dg such that the variances V Vi(,,, W, 2) S o and El z) - Vgi z; c)ll < oz
The following assumption on block heterogeneity measures the similarities the upper-level gradients V Vyfi( 2) for all This has not been discussed in previous works, but is necessary for our approach as we explore a more general outer-maximizane
solution y (x) for F, rather than for single fi-
Assumption 4.6. For any Rd, E Rd there exist constants Ber 2 1 and oth 2 0 such that
B V V.
oi..
We have 8th and th when all gi are identical.
4.2 Convergence analysis
For simplicity, we fix the number of involved blocks [/e| = P for all Let y²(z) the maximizer of F function w.r.t. Then, the overall objective of the original problem in eq. w.r.t. a is given by
(x)
F 1 (I)) 22),2"()) (x)),
where z² (ar) is the lower-level minimizer and y (x) is the maximizer of F(x, "err,,,²(x))) (x)). In addition. recall that the objective function the surrogate problem in eq. ① w.r.t. given by (z
((x, 3/ (x), 2 (x), z" (z)). 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 VL* can be bounded
as
- -(11))
Due to the limit of space, the proof of Proposition 4.7 can be found Lemma D.5 the appendix. For properly large X, 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 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| VL* (x;))) of the surrogate problem. Denote hy (Ir,, Vt, 2t, o²; E.,) and its expectation as ht Proposition 4.8. Under Assumptions 4.3
4.4
4.5
the consecutive iterates of Algorithm satisfy:
2 E E (x(+)) (xx))
E 12
B. yy (xx))l1
3
a
A.1
E Ila.e xxx + Il - 27 (x:))
for all t 10. T 1), where Lx.1 and L,,1 given in Lemma D.1 and Lemma D.6 in the appendix respectively.
The proof of Proposition 4.8 can found in Lemma obtained for Algorithm by replacing Ui,t and zi,, with off and ={5,- This proposition shows that the convergence rate of our algorithm relies on how fast the iterates yt, Zi,t and va,s converge to their optimal solutions at each iteration t. We next characterize the distance of y to its optimal solution.
the appendix. The same result can be
5

---

Proposition 499. Under Assumptions 4.3 4.4
4.5
the iterates of y generated according to Algo-
rithm satissf
My
Bl (2(++)112 -Bllye - y² (x+)1? - -O(n)
y" (x+))
+ O
(0) + o
[7]]
+ +((n)
- -
o
Th fly
E. 1
0
|1
17
for all 1. E (0,-.., 1}.
The proof of Proposition referss small stepsizes 7/2 and 77y, there exists a descent of the optimal distance Ellye - y (2,)]] which is critical for the final convergence analysis. Similar results are obtained for vi, and Zi,r- Combining the above propositions and the auxiliary lemmas in the appendix, we get the following result for Algorithm |
refers to Lemma
E.3 in the appendix. It can be seen that with properly
Theorem 4.10 (Convergence of FOSL), Suppose Assumptions 4.3
4.6 are satisfied. Set parameters The = O(T )). fly = O(T 4). 17=- = O(T 8), n7e = O(T and X = O(T+). Then,
4.3
we have
gap X2
4 4 100-wy VT)
2n (1 1 ? + n=d
+ n=d C2
+
+
The
P
fly
(m²)) nl
+ A(11y + (11=))A2 + +
<)
where Cyap is defined in Lemma 12.5 C2 C3 are defined in eq. (39) in the appendix, and 1/,
L (xx1) KyEllye y" (xx)]( + K= n 2im1
E
21,1 23, [12
K E. E Ellu,, 2, (xx)
Next, we characterize the sample complexity for FOSL.
Corollary 4.11. Under the same setting of Theorem 4.100 our algorithm finds an e-accurate stationary solution after T O 3) interactions. The total sample complexity for all involved blocks is
PT OPPE))
Compared with existing works [77 244, our algorithm is free from second-order derivative computa- tions. 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 Z 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 || (xx))l S B for any
N. For the
partial-block participation, by setting parameters Th = O(P T ). fl O(P- Tè)
- 1), 7=
O 1 T ), qo 0(1), x = O(P ( and taking caub = O(P -0P00PPP--000 TT B), we have
T
E (z)2)
2C X²
+
2( Wr)
4mad?
(1+
C2 +
n2
24I f. 0
T 1=0
Tn
P
71y
p
12L4
31.2
Caud S0(- b),
19g
where Lx.1 == 31L Cgap is defined by Lemma D.5 in the appendix and W L (xt) 13
v" (2. For the full-block participation, by setting 7 = =O(), Fy 0(1), ?= = O(T-5)
Te = 0()), A= = (T+)) ) and laking <sub = (T-22), we have
1 T
E (()2))1
20
20gap gap
4(Vo- Wr)
12
L3 +
4L4 f11
Eaub I.
T
X
Tn
Note that the assumption (x+)] < B can be removed when the domain of x is closed convex
set and projected gradient descent is used to update x 12 15). complexity for MemCS.
We next characterize the sample

---

Corollary 4.13. Under the same setting of Theorem 4.12
For partial-block participation, our algorithm finds an e-accurate stationary solution of (xx) after T (0(P-E--)) outer iterations and = OOlog t) inner iterations. The total sample complexity for all involved blocks is PKT Ö(Pic
For full-block participation, our algorithm finds e-accurate stationary solution of (xx) after T = O(e²)) outer iterations and K = Oloo }) inner iterations. The total sample complexity for all involved blocks is n nKT Onc
Note that the per-block sample complexity of our MemCS algorithm takes an order of E which improves that of the same-type FASA 30 by an order of -0.5 based on refined analysis on the smoothness of the overall objective function. Corollary 4413 also shows that MemCS achieves linear convergence speedup w.r.t. the number P of blocks. As far as we know, this the first linear speedup result in multi-ble block minimax bilevel optimization.
5 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 time and space comparison provided in Appendix
5.1 Deep AUC Maximization
5.1.1 Formulation
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 multi-block minimax bilevel optimization problem:
m
min max w.a.b
by
s.l. (w(w)) = arg min 9j (uy, Wz),
Lavc(w,) = 1 Σ [(w w 24 V:). E denotes the task loss (c.g., the cross-entropy loss in binary classification tasks), and o denotes the sample-level AUC loss function. The detailed formulation can be found in Appendix [A.I With the method in Section we reformulate this problem as single-level minimax optimization problem:
where (u,, wy)
uy (w, L ))
min max L(w, u, a, a, w.u.a,b a.v
where L(w, u, a, a) == ET (u ag by, a.) + (g wy) go g w;)) is the La- grangian function AUC loss function, and v, is the approximate optimal solution of gj.
5.1.2 Results
Settings. Following the work [24] we assess our methodology using four datasets, namely CIFARI00
(2). CelebA 40). CheXperi 226 and OGBG-MoIPCBA (25), whose details are provided Ap-
pendix B.T 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 [ are derived from the original paper. Detailed configuration of experiments can found in Appendix B.2
The results of deep AUC maximization different datasets are shown in Table 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 Laland lb The figures illustrate that, in the initial stage, our method and mAUC-CT (4 exhibit a faster loss drop than mAUC, and our method achieves the fastest overall convergence rate. Furthermore, our approach exhibits smaller fluctuation compared to other baseline methods.
Results.
7

---

Table 1: Test AUC score with 95% confidence interval on different datasets for AUC maximization.
CIFARI00
CelebA
CheXpert
OGBG-MoIPCBA
mAUC
0.9044 (0.0015)
0.9062 (0.0042)
0.8084 (0.1455)
0.7793 (0.0028)
mAUC-CT22
0.9272 (0.0014)
0.9192 (0.0004)
0.8198 (0.1495)
0.8406 (0.0044)
FOUL()urS)
0.9540 (0.0009)
0.9267 (0.0018)
0.8166 (0.0051)
0.8516 (0.0014)
CRANTCC
1420
0.00
(a)
(b)
(d)
Figure 1: Visualization results of FOSL experiments. (a) Training AUC loss over iteration rounds during the initial stages of training. (b) Training AUC loss over time during the initial training phase. (c) Impact of Ả on test AUC score throughout training on the CIFARIO 100 dataset. (d) Impact of on test AUC score throughout training on the CelebA dataset.
Impact A. To evaluate the impact of the hyper-parametts conduct ablation study the CIFARIO 100 and the CelebA datasets. The test AUC scores along with training are depicted in Figure Ic and Id] As shown in Figure [C] our method sustains robust performance across wide range of choices for X. For example, training within Ả range of [2. 8] shows that the speed of convergence and the final test performance are not sensitive to the change of X. A similar observation also holds for the CelebA dataset shown in Figure ld
on training with FOSL, algorithm, we
5.2 Robust Meta-learning with Rank-based Loss
5.2.1
Formulation
Our objective to devise 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 Figure 2
We first define 9[r] as the izh largest element of the set G = {91, 92. ... In such that gin] S 9nn-1] S
S -1]- Denote the task-specific loss as (Ø, wi). where ø is the parameter of the meta-model and we is the task task-specific parameter. The proposed formulation is then given by:
minF( (o
Σ i=n 1+1
( wHy (0) s.t. 1 (Ø) = arg min gi ws),
where gi (g, win (o) is the ien largest task-specific loss given w" := [w) w (0)) and (o) is the corresponding optimal task-specific parameter.
With the Lemma in 42). by introducing an auxiliary variable y, we can reformulate the problem as:
1 Σ gi (0) lot (0) - -7]+
n k n
min max F(b, w ,n, Ji u (z)
s.t. ( =agg min (Ø ws).
we
Details about the derivation of the above formulation can be found in Appendix A.2 This for- mulation poses non-convex optimization challenge for the primal variable Φ. making it chal- lenging to address using conventional optimization methods. Nevertheless, our proposed algo- rithm enables efficient resolution of this problem by reformulating the problem into a single- level minimax optimization problem as: ming. max-.v L(d,, w, v), where L(Φ. w, w) := f(((, E 7) > (g) (0) v;)) the Lagrangian function of the rank based loss function, is an approximate optimal task-specific parameter of the lower-level problem.
8

---

Table 2: Test accuracy (%) on the Mini- ImageNet and the Tiered- Barge-- datasets for meta-learning.
Table 3: Test accuracy (%) Mini- Mini-Imaged ImageNet and Tiered-Iman -eree--- with different noisy ratio for Flip setting.
Dataset
Method
Clean
Flip
Rand
Dataset
Method
Noisy
0.2
0.4
0.6
0.8
MAML
64.75
52.75
52.50
Mini
McmCS(ouur))
69.25
57.50
60.25
Mini
MemCS
MAML
64.75
69.25
59.50
65.00
56.50
61.75
57,50
52.75
53,50
42,00
MAML
66.25
44.75
54,25
Tiered
MAML
66.25
63.75
53.25
44.75
39.00
MemCS(
67.25
57.00
59.75
Tiered
MemCS
67.25
66.50
62.75
57.00
54.50
MAlL
MAML
6:2
icee
621
(b)
(c)
(d)
Figure 2: The portion of tasks being noisy during training for MAML and MemCS on Mini-ImageNet.
5.2.2 Results
Settings. We perform meta-learning experiments on few-shot learning tasks, focusing the capability of rapid adaptation to new tasks with limited samples. Adhering to standard few-shot learning configurations,
carry out 5-ways 5-shot learning experiments on Mini-ImageNee [53] (referred to as Mini in T and Tiered-ImageNet [47] (referred to as Tiered in Table 2) where each task involves 5-class classification task, with five samples per class used 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 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 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 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 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 performance as the noise ratio escalates, especially higher noise levels, signifying superior robustness compared to MAML.
Discussion. To show the effectiveness of our approach in facilitating robust learning, have visualized the average losses for both clean and noisy tasks separately within the MAML training framework, demonstrated in Figure 2 The graphical representation uncovers 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 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 's updates across both Rand and Flip scenarios, maintaining this protective measure throughout the training duration.
6 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

---

memory cenoory-fffciiet 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.
Acknowledgement
Yifan Yang and Kaiyi Ji were partially supported by NSF grants CCF-2311274 and ECCS-2326592. Zhaofeng Si and Siwei Lyu were partially supported by an NSF research grant IIS-2008532
References
[1] Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. arXiv preprint arXiv:211..45500, 2021.
[2] Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973.
[3] Liam Collins, Aryan Mokhtari, and Sanjay Shakkottai. Task-robust model-agnostic meta- learning. Advances in Neural Information Processing Systems, 33:18860-11s 18871, 2020.
[4] Corinna Cortes and Mehryar Mohri. Auc optimization vs. rate minimization. Advances in Neural Information Processing Systems, 16, 2003.
[5] Justin Domke. Generic methods for optimization based modeling. In Artificial Intelligence and Statistics, pages 318 326. PMLR, 2012.
[6] Chelsea Finn, Picter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1126-113 1135. PMLR, 2017.
[7] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In International Conference on Machine Learning, pages 1165-1173. PMLR, 2017.
[8] Wei Gao, Rong Jin, Shenghuo Zhu, and Zhi-Hua Zhou. One- sic-ppass optimization. In International Conference on Machine Learning, pages 906-914. PMLR, 2013.
[9] Wei Gao and Zhi-Hua Zhou. On the consistency auc pairwise optimization. arXiv preprint arXiv:1208.0644 2012.
[10] Camille Garcin, Maximilien Servajean, Alexis Joly, and Joseph Salmon. Stochastic smoothing of the top-k calibrated hinge loss for deep imbalanced classification. In International Conference on Machine Learning, pages 7208-7222. PMLR, 2022.
[11] Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023.
[12] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: 10w.:080222244 2018.
[13] Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint arXiv: (tf.:::660.55444 (604.05447, 2016.
[14) Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. International Conference on Machine Learning, pages 1748-3758. PMLR, 2020.
[15] Riccardo Grazzi, Massimiliano Pontil, and Saverio Salzo. Bilevel optimization with a lower- level contraction: Optimal sample complexity without warm-start. Journal of Machine Learning Research, 24(167):1-37, 2023.
10

---

[16] Alex Gu, Songtao Lu, Parikshit Ram, and Lily Weng. Nonconvex min-max bilevel optimization for task robust meta learning. International Conference on Machine Learning. 2021.
[17] Alex Gu, Songtao Lu, Parikshit Ram, and Lily Weng. Min-max multi-objective bilevel opti- mization with applications in robust machine learning. In International Conference on Learning Representations, 2023.
[18] Zhishuai Guo, Mingrui Liu, Zhuoning Yuan, Li Shen, Wei Liu, and Tianbao Yang. Communication-effiiii distributed stochastic auc maximization with deep neural networks. In International Conference Machine Learning, pages 5864-3874. PMLR, 2020.
[19] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. Advances in Neural Information Processing Systems, 31, 2018.
[20] Pierre Hansen, Brigitte Jaumard, and Gilles Savard. New branch-and bound rules for linear bilevel programming. SIAM Journal scientific and Statistical Computing. 13(5): 1990:1194-1220 1992.
[21] Ralf Herbrich. Large margin rank boundaries for ordinal regression. Advances in Large Margin Classifiers, pages 115-132, 2000.
[22] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application actor- critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
[23] Quanqi Hu, Bokun Wang, and Tianbao Yang. A stochastic momentum method for min-max bilevel optimization. 2021.
[24] Quanqi Hu, Yongjian Zhong, and Tianbao Yang. Multi-block min-max bilevel optimization with applications in multi-task deep auc maximization. Advances Neural Information Processing Systems, 155229552-295666 2022.
[25] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs Advances in neural information processing systems, 33:22118-22111 2020.
[26] Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-Ileus, Chris Chute, Henrik Marklund, Behzad Haghgoo, Robyn Ball, Katie Shpanskaya, et al. Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison. In Proceedings of the AAAI conference artificial intelligence, volume 33, pages 590- 990-597, 2019.
[27] Kaiyi Ji, Junjie Yang. and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 1882-48922 PMLR, 2021.
(28) Krishnateja Killamsetty, Changbin Li, Chen Zhao, Feng Chen, and Rishabh Iyer. A nested bi-level optimization framework for robust few shot learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7176-7184, 2022.
[29] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[30] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning. pages 18083-18113 PMLR, 2023.
[31] Kuang-Huei Lee, Xiaodong He, Lei Zhang, and Linjun Yang. Cleannet: Transfer learning for scalable image classifier training with label noise. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5447-5456, 2018
[32] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via scsg methods. Advances in Neural Information Processing Systems, 30, 2017.
11

---

[33] Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urta- sun, and Richard Zemel. Reviving and improving recurrent pack-propagation In International Conference Machine Learning, pages 3082-3091. PMLR, 2018.
[34] Gui-Hua Lin, Mengwei Xu, and Jane J Ye. On solving simple bilevel programs with nonconvex lower level program. Mathematical Programming. 144(1-2)) (1111)):7773000 2014.
[35] Bo Liu, Mao Ye. Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 35:17248-177 17262, 2022.
[36] Chenghao Liu, Zhihao Wang. Doyen Sahoo, Yuan Fang, Kun Zhang, and Steven CH Hoi. Adaptive task sampling for meta-learning. In Computer Vision-ECCC 2020: 16th European Conference, Glasgow, UK, August 23-28. 2020, Proceedings, Part XVIII 16, pages 752-769. Springer, 2020.
[37] Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic auc maximization with deep neural networks. arXiv preprint arXiv=:908. 10831, 2019.
[38] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A sunee-ffunctoon-bseee interior-point method for non-convex bi-level optimization. In International Conference on Machine Learning, pages 6882 6892. PMLR, 2021.
[39] Risheng Liu, Yaohua Liu, Shangzhi Zeng, and Jin Zhang. Towards gradient- based bilevel opti- mization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34:8662 8675, 2021.
[40] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[41] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference Artificial Intelligence and Statistics, pages 1540-1552. PMLR, 2020.
[42] Siwei Lyu, Yanbo Fan, Yiming Ying, and Bao-Gang Hu. Average top-k aggregate loss for supervised learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(1):76- 86, 2020.
[43] Soufiane Mallem, Abul Hasnat, and Amir Nakib. Efficient meta label correction based on meta learning and bi-level optimization. Engineering Applications of Artificial Intelligence, 117:105517, 2023.
[44] Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
[45] Fabian Pedregosa.
Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning, pages 737-746. PMLR, 2016.
[46] Alain Rakotomamonjy. Optimizing area under roc curve with syms. In ROCAI, pages 71-80, 2004.
[47] Mengye Ren, Eleni Triantafillou, Sachin Ravi, Jake Snell, Kevin Swersky, Joshua B Tenen- baum, Hugo Larochelle, and Richard S Zemel. Meta-leamiig for semi- supersue few-shot classification. arXiv preprint 1803. 00676, 2018.
[48] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference on Machine Learning, pages 4334 4343. PMLR, 2018
[49] Amirreza
Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots Truncated back- propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
[50] Chenggen Shi, Jie Lu, and Guangquan Zhang. An extended kuhn-tucker approach for linear bilevel programming. Applied Mathematics and Computation, 162(1):51-63, 2005,
12

---

[51] Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2):276-295, 2017.
[52] Haoliang Sun, Chenhui Guo, Qi Wei, Zhongyi Han, and Yilong Yin. Learning to rectify for robust learning with noisy labels. Pattern Recognition, 124: 124:108467, 2022.
[53] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
[54] Xiaoyu Wang, Rui Pan, Renjie Pi, and Tong Zhang. Effective bilevel optimization via minimax reformulation. arXiv preprint arXiv:2305. 13153,...,3,,... 2023.
[55] Zhen Wang. Guosheng Hu, and Qinghua Hu. Training noise-robust deep neural networks via meta-learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 4524 4533, 2020.
[56] Tianbao Yang and Yiming Ying. Auc maximization in the era of big data and ai: A survey. ACM Computing Surveys, 55(8):1-37, 2022.
[57] Yifan Yang. Peiyao Xiao, and Kaiyi Ji. Achieving O(c-l.6) complexity in Hessian/Jacobia--Fii stochastic bilevel optimization. arXiv preprint arXiv:2312.03807, 2023.
[58] Huaxiu Yao, Yu Wang, Ying Wei, Peilin Zhao, Mehrdad Mahdavi, Defu Lian, and Chelsea Finn. Meta-learning with an adaptive task scheduler. Advances in Neural Information Processing Systems, 34:7497-7509, 2021.
[59] Zhuoning Yuan, Zhishuai Guo, Nitesh Chawla, and Tianbao Yang. Compositional training for end-to-end deep auc maximization. In International Conference on Learning Representations, 2021.
[60] Zhuoning Yuan, Yan Yan, Milan Sonka, and Tianboo Yang. Large-scale robust deep auc maximization: A new surrogate loss and empirical studies medical image classification. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3040-3049, 2021.
[61] Guoqing Zheng, Ahmed Hassan Awadallah, and Susan Dumais. Meta label correction for noisy label learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11053-11061, 2021.
13

---

A Specifications of Applications
In this section, we provide a detailed introduction the formulation utilized in Section 5
A.1 Deep AUC Maximization (DAM)
For classifier model /(w), we have the AUC score function as
AUC(f(w)) Pr(f(w;)) 2 1, 1, -1),
where Pr(X) denote probability of an event X being true. One of the surrogate loss (AUC square loss (9) is given by:
min
Σ
Σ (c-
7
My
where n, and n._ are the numbers of positive examples and negative examples, respectively, and is the margin parameter. One can transfer this problem into equivalent minimax optimization problem according to Proposition in 337 by:
min max ((W, a.,,a) w,a.b a
b,
where
o(w,a,b, a, =(1 p)([(w; a)2 g1 p(f(w; - -b)² .I -1- p(1 p)a²
+ 22 - p)c p-ppppwwe (w;;):;) L,, -,;=-1 (1- (1:))[(w;:)) Ill,=),,
where a, b are margin parameters, p= 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 max ( a (VLvva(W),
w.a,b
where LAVG = Σ f(w: 24, V:), denotes task loss, e.g. cross-entropy in classification tasks. Consider multi-block problem with m tasks. This problem can be reformulated multi-block minimax bi-level optimization problem [24]:
min max w.abb
s.l. (w,,) = arg min yj (uj, Wj),
u,
where dj (uj, wj) = u (w, (V
A.2 Robust Meta-learning
Consider the formulation of Robust Meta-learning in Section 5.2
n Σ
minF (Ø, w²) inn-k+1
gal u (Ø)) s.t. w (Ø) arg min (0, w:), w.
where g(m] (o, i (0)) S Iin -n-- (0, w- < ... S (o, w (0)) denotes task- specifciiiic losses.
We define of (Ø) == (b, / (Ø)) for simplicity in later formulations. The summation of the bottom-k losses is equivalent the sum of all task losses subtracted by the of the top-(n-k) losses:
F(b. w
9f (0)
Σ T=1
With the Lemma in 42 we have:
Σ (o( = min { (m k)y + > (Ø) - 77+
km
14

---

Now we can convert the original upper-level problem to:
1 "
min max F(O, w", ,7) = A:
Σ (0) - (0) 7]+ n
The problem of robust meta-learning then formulated as:
min max F(Ø, w ,)) 1 k 1=1
Σ fild, ui = (0) - 19f 7
71 1:
s.t. w (6) arg min gi (0, wa).
where è is the parameter of meta-model, and w = [W wn] 17 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(o. w 7) = Σ filo wi = (0) - (o) - 7 + <0A
n
n
where 6 > is the smoothing parameter, and Z ~ (0, 1) is standard normal random variable.
B
Implementation Details and Extra Experimental Results
B.1
Datasets Description
Deep AUC Maximization. We assess our methodology using four datasets. The first dataset, CITARIO0 (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 specific category considered positive for that block. This dataset comprises 60, 000 images, each measuring 32 x 32 pixels, divided into 50, 000 training and 10, 000 testing images. The CelebA 440] dataset encompasses 202,599 facial images, each annotated with diverse set of attributes from 40 different features. The CheXpert (26) dataset includes 224, 316 chest radiograph images from 65, 240 patients, marked for distinet observations. Adhering to the methodology proposed in (44. we employ simplified version of CheXpert with 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 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-Imagehe [53) and Tiered-Imagehi [47]. Both datasets are subsets of the ILSVRC- 12 dataset. Mini-ImageNee comprises 100 classes, each containing 600 images with dimensions of 84 x 84 pixels. The 100 classes are distributed among training, validation, and testing sets with ratio of 64:16:20, respectively. In contrast, Tiered-Imagee Imrred- 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 for testing.
B.2 Implementation Details
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-MoIPCBA graph dataset, the Graph Isomorphism Network (GIN) is used for training. All experimental runs are performed using single NVIDIA RTX 6000 GPU. Regarding hyperparameters, we set the total training epoch to 2000 for the CIFAR100 and 100 for the OGBG-MoIPCBA datasets, adjust it to 40 for CelebA, and reduce it to for CheXpert. The learning rate for the optimal approximator is uniformly set to // 0.1 across all experiments, with The Th / X to maintain gradient magnitude consistency between u and v. This consistency vital due to the influence of the À parameter in the Lagrangian function the update process for
15

---

0.0
Table Al: Comparison of average iteration time and total training time of our method and AUC- CT small scale dataset (CelebA) and large scale dataset (perett
0.0
1AGC
KALK
100L
Method
CelebA
CheXpert
Pasts
Figure A1: Test AUC score along with training epochs the CIFARI00 (left) and the CelebA (right) datasets.
FOSL
0.55s/8. 2h
0.78s/7.3h 0.83s/7.7h
AUC-CT 24
0.69s/10.3h
Table A2: Comparison between FOSL and MemCS on robust meta-learning task.
Algorithm Best Test Accuracy
Model Parameter Size
Average Iteration Time
MemCS FOSL
69.25
0.433MB 61 611.167MB
3.15s
67.75
1.42s
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 GGBG-MoIPCBA.
Robust Meta-learning. We adopt the Adam optimizer to update the meta- meta-model in the context of MAML. For the byper-parameters of MAML, we set the learning rate of meta- medel update as Umeta = 0.02, and set the learning rate of fast adaptation as "odopt = 0.02, with an adaptation step configure the learning rate of the optimal approximator as A/v Madoot = 0.02, and the learning rate of w and meta-model parameter e as Me 7/ = / iÀ in the implementation. In practice, setting 3 results in favorable performance. All experiments are conducted on a single NVIDIA RTX 6000 GPU using a widely used lightweight model featuring convolutional layers (CNN4).
of 15. To be consistent with the DAM experiments,
B.3 Extra Results on Deep AUC Maximization
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 CIFARION and CelebA datasets, as shown in Figure Al 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] different-sized datasets (32 x 32 in CIFAR 100 vs. 224 x 224 in CheXpert) as detailed in Table A1 Note that the training time largely depends 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 Salle|ATshoweer the ability 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 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.
B.4
Comparison between FOSL and MemCS
In this section, we compare our two proposed methods within the same experimental setting, i.c. 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 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 robust meta-learning setting can introduce a greatly increased memory cost, which is especially significant for small model. However, the single-loop nature of FOSL can drastically shorten the average iteration time during training. This makes the FOSI. algorithm potentially advantageous choice in scenarios involving larger base models and fewer blocks.
16

---

C
Notations
The original problem we solve here is
min max F(r,y, :- : Σ (1 segdl vERdy
E Ec
s.t. 27 arg ming 2) = (e[a(1, (G) G)] =ER
Moreover, define (x) arg min, Li(x, y² (1), 2, and y" (x) arg max, F(x, 2,),,, For the convenience of proof, we also define
n
(()))(()))) =
For the notational convenience of FOSL, we define the estimators of client set It as
h
he ==
Ca yc: 2i,e v2.s St.i)
ke
h
| == Vyfi(Ee, Us (/,))
ke
( == VeLi (2.)
[+
M == Vi
RE
Since we sample tasks without replacement and our estimators are unbiased, we have the expectations of estimators as
n
7 =
h
Vzhilare yes Ze,es waxe) seee
71
h E[hg]
The V f Bc, (at, v(t))
h2 E[h[]
[ = V ViLiFEe Be. Zi,e, more
Mg. = E[ =
Th = Veg(Ee, m8t))
(5)
We also define the optimal Lagrangian estimator of x and its gradients as
L. (x)x):
1
Σ
n
H'(x):
Σ
(1)x))= = (x
Vel(E.n'(0) + VVo -,oo (6)
n
17

---

D Proofs of Preliminary Lemmas
D.1 Some basic properties
Lemma D.I. Under Assumptions 4.3 4.4 for VX 2بية both Li 21 2, 0) and [(x, Ur 2, v) are
Aph 2
strongly convex in and Ls,1 -s..sohh in (a, yr 2), where LA.1 := 32Lg,11
Proof.
Since x 2 2 2
2 La.
we have that
2 A/g
V (,,,, = (() 2
|3244:/hh8.aa:aHH133../....A..10 F1. Adg.
[V AV (2,,))) - r||| - bn + 2 S 3ALy,11 =: LA,,
IV (, e)|l
|| < 4, + 2 S 3Rbg,1 =: LA.1-
Then the proof is complete.
Lemma D.2. Under Assumptions
4.3 4.4
for z max { 2بيم (1 +
Laii) Ag
3rl Lgg }. we have
L3
Mg
|[ (x)1 < 1,1,, Pg [1V23, < 12h
and (zy(()) v [1 L
Lr
ur.
Proof. Recall that we define (x) arg min, ge 2) and (z) == arg min, (x), 2, v).
Then we have (z, (x)) = 0 and V.Li (x), (x), =x, = O. Via implicit function theorem, we obtain
=0 (x), (1))
Va (,, +
0.
(7)
To measure that Lipschitz continuity of (x) and (x) w.r.t x, we take spectral norm of (1) and (z) as
[+)())) =| V2 (x))
(0)
x
Lg
1ig
[+), = (1
(z)
(8)
where (a) uses Assumption 4.4 Similarly, for of (z), we have v,F(e,,(00, = 0. Via
implicit function theorem, we have
2 10
+ (V
(9)
which indicates
Vy)())))
<
18

---

||[ vy F Fl,, y (z), z' (+))
I1
L1111
Mg
where (a) uses Assumption 4.3 and Assumption 4.4 [ - (1+
Back the second equation in eq. 8 with
Ee.11 Pv
Leat
we have
(v)]
+ (Vy (1..
|1[ Cz (z). (x) ||
1n.
g. 17,11 2
3, (1
My Apg Apg
VΛ (b)
12Lg.1
Mg
Iand) L7 Then the proof is complete.
where (a) uses Lemma D.I and (b) uses À 2 (1 +
Lemma D.3. Under Assumptions Lexex and Lu -mooth respectively. where we define La,e, Linex and L as
4.3 4.4 the optimal solutions 2 (x), 2x)((z) and y (x) are Lr,
I'g.2
1 Igg.1
2
I9911
L
12
Lin
Lenex ==
11 1
pg
Pg
Fg
ugg
1++ L1g1 + +(1
L0.1
L111
2 L1.
[1
Lg11
2 L
Lun =
Nn
Ug
Pi
ue
Un
for any i E n., where assume X 2 {2T (1 +
La.1
1.7
(1
Laa Lyakpa Lesko,u (1 (1+ Lei
) Lea +
12b
-1 ((1 + La. Lfa
+ 1)
Lia Lra)).
Ha 3pyboa" 6b..1
Au Hy
Ly.1
Proof. Since 2/ (x) arg min, (x 2). we have Tagi (2, x* =xx)) 0. which indicates that
v ( + (=*(x)V (z, =x())) = O.
For any æ1, 22 E Rd, have
V 2 - Vz)
V2 a g (z), [a [V2 (x2))))))
<
(2)
V
2
(
(0)
96
[1,
V2 (2 2 (x2))
0g
Lg
+
V2
F2,
27 (x2)) Vi (z), (=)))
4
L 1.2
l.
(102 xzll + (m)) 2 (x2)
1
4g
Hg
(6) L,g.2
Tzg.1
2
+
|| - -x2ll.
(10)
Hg
Mg
19

---

where (a) uses Assumption 4.3 4.4 and (A-1-B-)
- B- =
(b) follows from
Lemma D.2 Next, plug x = and x x2 into eq. ( and differentiate these two equations, then
we get
my [i = (VV" =
+ +Vy ( (1t
(II)
and by using eq. 9 get
(Vy (x1)) h/t
+ +Vz - (x))))
+ (
[aga///aa))a_/leee/(((aal(t))ll (12)
By combining eq. 11 eq.
12) and taking norm, we have
(x)) - Vy (12)
by F (1 y F (x)))
(V=((n)) - VV(a))) (
(V2 ( (M, (1)
(x2))
ト
-
v (0))) (,
(0)
1
1 +
Lg.11
+ (1
1 L
L,
ugg
(|m1
- xeel + (xr2) - 32 (x22))
1 Σ
|| (x1) 2, (12)))
i=1
L511
1
Σ
225 (01) V27 (x2)
Ms
n
(8)
Ly.1
(1
L
L12
+
(1+
L..1
Lg,1
||| #2|1,
Bg
Pg
1ig Piligg
where (a) uses Assumption 4.4 and Lemma D.2,
(b) follows from Assumption
Lemma D.2 and
eq. (0). Similarly to eq. (10), from eq.
7 if we simplify the notation as
A = v2 (en
C, (IL. (z1) (x,)), vi) + (T'((x1) (t), v1).
B. = v (T)
A₂ = ("2_
+ (Vy' Li 8 (21), 2x,(z),
B₂ v2 Co (1)
then we have
[=),( = =1 ArB |1
20

---

<I((A1
A2) || 11
<||A1 A2ll
B 11
|
|| -
< A|| A2ll | || ||T 1--1111113 1/551 11-111100 11 Ball- (13)
For the first term in eq.
13 via Lemma
D.I
we have
||A - Azll
,3AL,,1 (1|21 - x21l + 11 (21) - y (22)) + (22) - (x22))
+ 112 Vy (x1) - (x2))
+ 1 Vy (x2) 1- (1|=1 -2/l +
- ((a)) |2 - xx)()))
(0)
3Alg (1+ 9 1111/112)
(x)) ( =x,
Mg H4
+ L11
Vy)"(11) - Vy((x22)
(8)
1 (1+
Lg
L11
12
||21-
-22l1
L, x2
Hg
H9
g.1
L
12Lg.11
1 +
1
+
||
x2ll
(14)
Mg
Pf
Mg
where (a) uses Lemma D.2
(b) follows from Lemmas D.2 D.3 and A 2 (1 +
ب (c)
333 وy,1
uses X > L..
[1 + (1
Fina + 126,11 1 By using Lemma D.1 we have
| S 3p1y
2
6
1ig 14
B 11 S Apg
2
|| [1 B2l < 33 9. ||:11 -1 and
|| = V2 #2 Li [2, yn (x2) 2x, (122) 02) + (Vy
< 22 22 C. (12, 3² (x2) (x22) 02)
+ V (x2)
(21),
(0)
L9.1
1
(b)
(11 + )bg +
S 2A
(15)
Ug
M&
where (a) uses Assumption 4.4 and Lemma
D.2
(b) uses X 2 ((1 + ايي ديا
+ 1) E.y. We also
have
B1 - B2ll =3NLg (1|= x221 + (11) - (122)) + (01) xx
L..1
L1.1 + 12L
L 1 1 [
| x211,
(16)
Mg
Mí
Mg
where (a) uses Lemma D.2 Combining eq. have
[4p
eq.
15
eq.
(66)
with the results in Lemma D.I we
| - V S11A1 - A2ll
|
||
+ ||/2 ||
1| 1 11- || - B2ll
18Lg.1
2412 9.1
( 1+ (1
Lg.1 Lイ2 + 12Lg,1
||01-222 x2ll
Mg
mg
bg
Thus, the proof is complete.
D.2 Gap of Lower-level Optimal Points
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 2, (x) and the surrogate minimax problem (x) can be bounded as
T,p.0 Max
[x)x(()) 2: (x)) <
-
[V=i)(() vei( 1
1
1
Leponz + T.pa (1 (1 +
Lad) ) Lrn
1g
Mg
Mgg
6Lg.1
(1 (1+ bn)))
(1r.a + L1100bo122
Mg
for any i E {l,..., n2,, where we assume X >
max
2h.11
igg
(1 +
3p
by.
21

---

Proof. For each block, we can have that
- -
V
(= V2
2 (x))
Hg
1
VaJi(z, (2), (+))) ( L
My
Ug
where (a) uses Assumption 4.3
(b) follows from the definition of (z) and (x)( (c) uses
Assumption 4.4 For the second part, since (z, 0, Cz, (z), (x) = 0. have
(=.,(((.8,3, Vis =0
= 0.
which indicates that
(x) = - (x))
(e),(()=
+ (2
+ VV (a, (x)) (x))
A
Then the gap can be displayed as
[x) - (2((=)] <
(2,
[2.
V2 (x,,"(a,v'
[r,
1
V (z, (x)) (xx
Vinli (xx) Vy ((
(1 (1+ 12a)) 2 (Ln1 + I >
3gg
pgg 123
Mg
5
1
- -
Tig
+ +
T.p,1 (1 (1+
Loi
L5.11 145
14g
My
6Lg,1
(1+ (1+ (1+ P/
(1(1)) (Lea+ + 15o0112)
X
1ig
1i
1
1
Loaloi + +L,,11 [1+ (1+ Lenr Lea
X
Pg
Hg
Ng
1.
6Lg.1
[1+(1+ 1ng1)) (Lea+ L5
where (a) can be satisfied because
V2 (1,
v2
(z, (t)))
= =1|V 0: (1.
V2 La (z. (x), (z) (x))))
A
22

---

(a.1)
2
+1V ( (x))1
2
+ =1,2211((,(1))) - (x))l)
19
2
[
Igg0l1g22 1
)
2
M9
where (a.1) uses Assumption 4.3 and Lemma D.I Then, the proof is complete.
Lemma D.5. Under Assumptions 4.3
the gap between (T(x) and H (x) can be bounded as
Cgap X2
v - H (x)]1 -
where Cgap = 3 3(1 + max { 22 (1+ Mg
17
17,1
L1.0)
+ (1+
+
1.2 p
31
(L..0)
and we assume X >>
Mo
+ Led) 1
Ne 3ps T.g.3 }.
Proof. By the definitions of VF(z. 2 and (x), we have
=
< V
(17)
For any E {1,..., we have
= +1444//0k00000140000000000444441
S 3/ \|
+3 34tp://0000000022.00000000000110
+ 31 [12-://c440000033006000010111100
3 31/
- -V
(4)
12
311
1+
- (x)
V2 22 (x,
(2.
V
V.g
V.
Vegli (x) (1,) - - I
+ 61 22 (z) -2()))
Vagi( 25, (x,
(b)
3
1
1 1. (x) (1)) 6x. (1+
L2
Lig.1
- (())]
23

---

(
3
1
1 2
L5.0 My
-
1
L
9.1
3
2
L.00
My
X2
(18)
where (a) follows from Assumption
4.3
4.4
and eq. ④
(b) follows from Assumption 4.3
4.4
and
Lemma in 44] (c) uses Lemma D.4
The proof is finished by substituting eq. (T8) into eq. 17p.
Lemma D.6. Under Assumptions 4.3
4.4 the gradient of Lagrangian function with optimal solutions
H. (xr) is Le, -Lipschitz continuous in x, where we define Lie,1
= (1 12b +(1+ La.2)
Lia
1+ 12n Lg.obi
1ro0u. L X 2 (2L (1
T..aoe + L1,11 (1+
Ms )) دييا (1+ (1+
bx
MM
Mg
Ma
and we assume
Ap (1
27
ball عياوي بey
(1+ (1+
Hg
Ma
My 3 6
+
12
((1+
+ 1)
Lra
Po
19g
Rg
14
Tog.
Proof. Recall that in eq. 4
(x) 1
Vaf + +VVol(()))) (z))
n
Then we have
n
VH (x)
2 (V
-Vnng (x)))
(19)
By taking norm, we have
(+)(
v2 (e.
V2 (1
+
n
V 2. ni (z) Vz,
71
+ +1
22 (2, (z))) (2,,,(,,
+ ||V2) V2)(2)) V V2 (I, (x))|]
1 + 12 (1 (1+ Lg.1 L
T.p11 + 2 ( 1+
Lg.1
L T.,2ll23, +x()))
Ng
14g 14
pgg
+ Abg, || (z)x) - V2, (x)
1 12
+ +(1 Ig.11 ) Ls2
Lg,11
Lg,0
H$ L1a +
1+
Pg
kig
Hg
L1g.gg22 + I. + (1 + Lgga T.s,1
+ T.g.2
1gg
1gg
My
14g
66gg11
(1+ (1 Lon1)
(Ly,1 + L1,0gg12
+
11
1gg
where (a) uses Assumption complete.
4.4 and Lemma
D.2 (b) follows from Lemma D.4 Then, the proof is
D
24

---

E Proofs of Theorem 4.10 and and Corollary 4.11
E.1 Descent in Objective Function
Lemma E.1. Under Assumptions 4.3 tive iterates of Algorithm ! satisfy:
4.4
4.5
and Lemma D.6 for 1 smooth (x)), the consecu-
IE (1(+1) - 6 (xx1]
Li,
31
112 B1TL" (x+))1 - The E
11
E
ni,1 +
E 11 - (xx))l
2
2
2
31 L3
E
Σ
|
(1x))
+
1
Σ
| (xx))
2
2m1
for all I E {0, ....,, T 1}.
where we assume X
24
Hg
Proof.
Recall the definitions of L (x) and (x)) in eq.
6 By using the smoothness of L (x:) in
Lemma D.6, we have that
E [[("(( [I++1)]
La.1
<R(] + R(H Te41 Fe41 r2))
R B11,5111 - -x
2
[ - The RH" (zx), M2)) + LLLL..1 E h2
2
1
Lo.1
=E(C"(z))
ne (H (2x), k1)
+
Elln" 11
2
(x())(=))
1E EI| (z:)]1
7x
Th El H. (ax) - -ht 11 +
L.
E Ellh 12
2
2
(a)
<E(C (2+)]
The E| (z:)]1²
22
11,1111
nh
El h111
1.1
B
y (xx))l
2
2
2
31/a 12
E
1
xxx
1
Σ
||uta - 2 (mv))
2
where (a) follows from
B1| (x:)
E
V L.
V Ve, 21,0, 21,, va.1)
n
(a.1)
1
E
V ( (2 (x)) 2 (zx)
V
Ve, (e. 2..1 11
1=1
(a.2)
3 - y (x:))
3 E
Σ
2 - 2x,
||
+ Σ | 23 (=)))
and (a.1) uses Jensen inequality; (a.2) follows from Assumption is complete.
4.4 and Lemma D.I Then, the proof
E.2 Bounds of Estimators
Lemma E.2. Under Assumptions 4.3
4.4 4.5 4.6
the estimators of Us Zi, and x can be bounded
as
E| 2I <
- (2,) 20 g B||,,112 < 4(L3,1 + x2213,,) (Elyy- - y² (xt)1 Ella,, - =x,(()))11)) + 4(03 + x20z).
25

---

of
+ (n- -ol-oo
Pih
+ (1+
T. Blluur yx((x)
Elleaa =7 (xx))1²)
[1
(n - Ta
Ie
1=1
Bl 1| s B 1|
+ 3(n - [1el)
(n 1) [t] 'f.0 + 2221. +
3
(0) +2802)
[tc
for any i n) and t {0, 1, ...,. 1}.
Proof. By using the definition of 27 (2z), we can have that
E h 11 < 2E V (x Ui Ei,t) V Vagi u Va (a (x:)))
2
U/, 2 (xt)] + 20
Similarly, we have
E 11 < 2 1 M/s Z4,10 U2a)) V C. Mr 2. u.r &
+ 2E V L. Bc, 23,01 U1,1) V Cx (xx)) (x)), u1,111
< <(L + L2 Bl (xxe El 3" (x)))) + 4(07 + 1oog)
Next, for the estimator of x, we have
B
=E
V
24,1, 02, 21,
T+
VEL.
(
EE
Cx (Iez Me, Mor
24,5 (.,,)
V Ci 24,4 21,
[
+
E
(20)
SEL.
where (a) uses unbiased estimation in Assumption 4.5 selected without replacement, have
For the first part of eq. (20). since tasks are
B
1
Va Uh. Riets me.s)
T2
iEL
(0)
E
VL 2.. V.L, (1, 21,1, vt.)
Lel²
2
3
0 2X
(21)
1
where (a) uses the unbiased estimation assumption in Assumption we have
4.5
For the second part of eq.
20
Ci Mer Zi,e, 2,,)
Tcl
FEL.
( n([T.
n V L, (ste 2i,4, w2.s)
n - [Td]
V Lo (t, yc, Zi,e, vice)
[T
(n 14
1=1
3(n 1) (L + 2X
< 7 ||
(22)
where (a) used the Lemma A. in 132 (b) uses Assumption 4.4 By combining eq.
22 with eq.
21
the fourth inequality proved. Last, for the estimator of y, we have
B
E
=E
It ET
26

---

1
3e - V De, Us.e)
R.
V
T
[Tel
SE
iEl
V Vysi Me, 0,.3 Me
Me,
n((4,1 - 1)
2
n - [e]
44 (n 1) E
V Mc. Bl.e)
+
E
V Vyfi(rr Ve. BLe
(n -))[del
(n- [ |0
n 1) + 18.88/00 (n
|Tel)
(n - 1)141
11 -11-
71
(n (n-144)ort
[el (n -0-11 1)]4||
n - 1) + 23, (n
[Te)
+
E
V Vf - (x))
[L 1)
1=1
(e) of
(n |1 10t
+
[T
(n - 1)|4e]
[ - 1) + 83,, (n2 (Iel
f (Elly- - -V +x0+)
1
Ellsa 2 (xx))l)
[L 1)
n i=1
(n 10
82 [1,
+ (1+
L7, [Bllve 8" (xr)) +
- - (xx))))
(n 1)144]
where (a) uses Assumption 4.5 (b) follows from the Lemma A.1 in (32] (c) uses Assumption 4.5
4.6, (d) follows from definition y (z) arg max, 1. Σ. fo (2. U. 2 (z)): (e) uses Assumption 4.4
and (f) uses Beh 2 1. Then, the proof is complete.
E.3 Descent in Approximation Errors
Lemma E.3. Under Assumptions 4.3
4.4
4.5
4.6
there exists d,,1, dz,1, Syy1 such that the iterates
of Vi,t Zia and yt in Algorithm 7 safisy
o1.11 2 (s(+t))]'
18| Bll 27 (zx |1
1 1 Σ
Mello + 5c)
Bllei. (xx))] + 2n
5.)0
El 11
12g
+ Ie.=
B11b"11
+ 1/2
2
E |,,11 z (e(+1)) )2
- E|| 3,,1 - [==(11
naApi
6.2
1 Σ
El
23, (x)((1 (1 (1+b))(
Ellye 2 (*.))
Ap1lg
1=1
144n F |
144
BlIbh111 + 8(1 + 62)722203
+
82,1113
1
2
Br+1 V (I++1)l1 1)1 Ellye - 1/ (2=)))1
Mully + (1 + 6,) [1.
L3 + 8y
Ellye 1" (2=)))
+ 11 + 6,))
[T.]
03
+
(n- 1o).
(n TT
+ 8y,1
2
1
Ly.1
11
1 12
1
13,11 )
(1 + 5y))
Bllexe 2 (xx))1
Tx
27

---

Lay (1
Lig,1 2
1/5
Mgg
for all 1 E {0,..., }}. where we define 8n == 80,1 + L (L,,0 + 22 g.0). 82 == 8n,1 +
2
3n 1n..0
2 1 +2x22
22,0) (..00.00 8y == 69.1+ 3n 2 +2x 2), and we assume À 2 {2L Mg: (1+ Lo. Lra + 12b -1 (11 L be +11 L1.1 1.
ku
L..1 12
3uy bg. (1+ L ) Lea Leasbay (1+(1+
He
pg 3ug 6Lg.1
Mg My ns
Ag as Lg
lu S 26, 72 S 322
My
Proof. For the iterations of the lower-level problem, we have
Ellvac--1 - 2, (1++1)ll 2l? -Bllo - 27 (2t)]l + E1|l (xx) (xc+1)))
+ 2E DEE(0,++1 - 27 (2x), 2, (24) - (
(23)
For the first term of eq. (23). we have
E 01,411 2/ (xx)]
-Bllui, - 27 (x)) - h6
= -Blee, - 2²(xx)11² + B - Vi 2 (zt), Ny.s)
-Blloc, (xx)) + B -21, 21 Fist 2 (1z), V (se,; vie)) - Ve 2x (xx)))
(a)
2 (1 2 ) Bl| 2 (xx))1
+ / |4
(1)
2g + 21 g. 1u5, 2/ (1+)) 2n/00
11 nolly)
E U/2t - 2/ (x)) + 217000
(24)
where (a) follows from Assumption 4.3; (b) uses Lemma E.2 (c) results from n/ S second term of eq.
For the
21
23 we have
I x1+1l1
n.-29.1 19
E E (Iz) - 27 (0++1)) ) S
E m
EE
11.
(25)
2
For the last term of eq. (33). we have
(E,,01+1111111 (x,), (x:) 2 (11+2))
BB( (x,), V= (1)) 21))
-2B(T - ==x),, (1++1) - - (1=) - (1.(()) - xi))
-2B(cio+1 (z)), V2, (z.)mahh))
-2B(vi,+11 - =7 -=x))) (1)(0))0011111 -
E
V (2 Aill
+ - 2 (x))
E
2/ (
- (x)) (2) - 2z)1
(4)
5 21
01.41 - (x:) E
22 75
+ EE
0l.++1 T
2/ (z0)) -1,,11 xell
<6
11,0-11 - 2, (xx)
s.1
B A ||
E1
60,111
2
T.. L..
2 (I2,,0 + 2x ) |T|
Mi,e41 - 2/ (x+))l
( -6, 2/ (x:))]
2 9.1
L 7 || + n no E 1h
(26)
8 5
2
44 (b) defines 6, = 5.,1 + 3r (L),0 + 222
where (a) use Lemma D.3 and Lemma in
By plugging eq. (24). eq. 25 eq. 26 into eq. 23 we have
El| clleeet11 2 (x++1))
B Bsleer. 2, (xx))]
28

---

2( Mo 8,))elose -oote-=f0ee (xx)) 21 + 6.)o
L B 1
11
+
[1
Lu.e
80.1143
fig
2
Then we get
B Bllott11 - -=((xx+)))--BBll11
-Bl[ - =
(1x))1
<( - Molly + +,,)
E Vi.e - <x(==)] + 21 + 5,)0
i=1
2h 122 9.1
T.2 1 Plg
Li,z
B
11
n
B1
8 1m,
Thus, the first inequality in the lemma is proved. Similarly, we have
Bl (x, =B|| - x =3 - (x++1)1
+ - (tE) (x2411)
(27)
-
We can bound the first term in eq. 27 similarly with eq. 24)
I 22,0+1 21=22
<B||zi, - (x)()) + + E1
- (2),),,)
BBl - =xx,(==))1 7
-5 v.C. (ae, Ur, 2.., V.L. b.
2n. V.C. (3e, Ue, (x,) - V2Li VV. (1))),
=B] - (xx)) + = 1l
25,
- 25, (z.)) V 7 (Fr, Us. zi,s m..) V (z., (z:),
- (z. V f (I+; Ve, (x+))
V V f (x,
<(1 - n2 ) - (xx)) (2x) )|( + E11
+ 1=AA1g Ell 21,e - (x,))1
21/= El V (1e, Vc, 23. (x.)) - - V. (xx), (x))))
m= n=AAiy
B 21,1 (x:(1
2n, 2 Elly: (xx)))
2
Aptg
Bli2s,1 - (x:(1= + 2n 2mrb3
+ 881 L (x))))
Aptg
12 B|| 21, (x,01
2
(1)
A=
B B||z,,1 (x:))
21/ 21/1117111 + -
v" (x)))²++8)2x'+
(28)
Aplo
where (a) uses Lemma and X > max
Lia ail } (b) uses n7 S Lg. og
Mg 321
we bound the second
term in eq.
27 as
144T.2 E (2)) (x(+111
144
2.2 9.
9.1 22
Elix: 3141112
E
1
(29)
and we bound the last term in eq. 27 similarly with eq. (6) as
2B 2B(21,41 - =x, (2r) (1x) - (x+(()))))
25.E|| 24,41 - - (2x)) 2
144m
E
2/
E
(30)
62.11²
2
3n br. (I7,00 + 222 10). By plugging eq.
where 8- = 62,1 +
28 eq.
29
eq.
30
into eq.
27
2
have
E [1,0111 25,0(1041)1 1| -E El|2,,1 111,,,--5500 (x)))
29

---

DeApa 4
2
+ 5z 1.)BBll2tt 2x, (2x))1 + (1 6z)
+ - Ellbt (xx)))
Aply
144
12
144 Vilee
11 +
B Bllh", 122 8(1 66)
6g,1
2
After telescoping, we obtain
23,411 23,4(11+1||
- Bl12,,
(2)s)11
6z) n A
1 Σ
E
2,, (x=))) (1 (1+b0 oz)
8n122
Ellye y (xx))
11
Apty
144m
144
E |1
El 8(1 + 6, 2
11
2
Then the second inequality in the lemma is proved. Last, for ye and y (2t)), we have
E [ y² 1 =B Bllbt111 y (xx))l + Elly" v 11l
+ 2 2E<11++1 (xt), v0 (xx) s (Es+1)).
(31)
We can bound the first term in eq. (31) as
E Ilv++1 y" (xx))²
=Elly/ + hi (1xx)l
=Flly y² (ax))l + 1
+ 2ny Bly n" (sxe)
(a) Ellye - y² (x0)1 + n
+ 11, 1/1 -y" (x())))
1
Σ
V y (2t,
1=1
+ 2n, [2 11 y² (x())) 1
n
V (rl(
Vyli(se, (1)),
(b)
< Elllv - 3" (x+)11 + + 11
+ 1/ ( [tyElll Elyyy - 3² (x.))1 + 1
n
(1t, Vyde Ber 2, (ar)))
EE
Vy
2 Ellye 119i --" (xx))1
(0)
Ly my 1.1
1 n
2
(1 Tolly Bll - "" (xx))1 + + 1
Ellei, - (2x)11
24
n
(1)
Dulls
+ 1i +
L3
E Elyy
y" (xx))1 + n/
of
(n 1e
2
[g]
[1g]
(n 4)
+
Mly T.
+
(1 1 +
32
2
f.1
1
2 (xx)))
(32)
where (a) uses the definition of y (xx) and eq.
5 (b) uses strong concavity of S; in y (c) follows (d) uses Lemma E.2 We can bound the second term
from definition of y" (2:) and Assumption 4.4 in eq. (31) as
(a) (xyy 3² (c 2
(1+
La.1
2 2
Fe+1 = 1/ (1
T Lg.1
E Elr,
agg
Mgg
/4
(33)
where (a) follows from Lemma D.2 Also, we can get the bound of the last term as
21 (1 y²())) " (xx) y² (I++1))
30

---

2E vm))
-x1)
-2B(1(+1 v²(x)), 1/ (1(+1) (0())) V1y (1)((1
2111 - y"(x+)] 1/2 Vy
+ 2200|| yc+1 - (xx) 11 (2(+1)
- (x+) - Vyy(Iz) -x)] x+)
(a)
6y Bllbet (0())) )|
+
nh
1
Lg,1
$
E
Mg
|4
+ B M1+ y" (xx1)] Lr | - -x0 ||
(6)
8y 15.1111 Bllec+ (xx)) 22 + ,y.1
n
(1 1
Lg.1
1.1
E
14g
L 10 10++1 v¹ (xx)) 1|2 || - xzll
+
L..V
E
| - xz 11
2
2
3 .1 (13,0 + +22 L2,2) ) |Bllec+ 8² (xx))l
6,11 +
Lg.1
1.2
ViLon R |
Vi
+
1
11?
6y.1
by
Lug11
Le n
R, Me+1 |
y² (1x)
+
1
E
E
(34)
5y.
Mg
2
where (a) uses Lemma D.2 and Lemma D.3] (b) use Lemma D.3 and Lemma in [44]; (c) follows
from Assumption 4.4, (d) defines 8y 5y.1 +
3n Lexx
(,,,0 + 22,0) By plugging eq. (32).
2
eq. 33
eq.
34
into eq. (34) we get
E
1+++1
y² 1 Ellye - 3² (x+e)1
Molly + (1 + +b0) + 82h
T2 + 8g
Bllye y" (xx))1
[Tel
+ +1 + +8y)
og
+
(n- - 10 th
Th
1
Ig,11
)
2T2
E i 2
14]
(n 1)14
Hgg
+
1g T.2
+ ng
2
(1 (1+ +
B2g
17,1
(1 + +y))
Σ Ellei, (x.))1
[Lel
Loa + (1+
Lg,1
L?
2
1gg
Then the last inequality is proved. Thus, the proof is complete.
E.4 Descent in the Lyapunov Function and Proof of Theorem 4.10
We define the Lyapunov function as
1 (x)) + K2Ellv (2x))) + K;
E El|a 2x)(2
+ K n
Ellui, 2/ (xxe)1
(35)
where the coefficients are given by
Th 2
3LJ 2
216L2 g.
LJ.1
864T.
n=
54L.
7=
54L2
Ky
K₂
K.
fly
n=A
B4g
Pg
8y.1
nopl
8
D=Apag
0v.2
n/14g 4
(36)
31

---

For convenience, we define the following constants:
L..1
5
Le.e
5
111L
C == max
2
Ag
11
2
Hg
Mg
2
2
3L
fa
216L
g.1
L7,1
864L
Lany
+ (1 + La. L7,11 }
My HI S
P
Ag
2
62208 4
16
3L
21
2
L3
86-L
(1 + L1g.1 1,7,1
C2 == max
Hg
1 max
4
2161
L7,1
861
(0g + okn) }.
C3= ==
(37)
Pg
Hg
We also constrain the conditions as below:
A
2L
.11
+
Lgg.1
1
(1 + Lod L L5 Leahon (1 + (1+
Lg L.p.1
+
12Lg.1
-1
14
3p
Lg.1"
6
14g
14
Mg
L..2
11,11
Laa
L
L1.0
os 16L7,
3L4,1 +
216L2 13,1
864L
((1 +
+ 1)
Hg
Lig.1
Lgg
Lg.0
By 27,
9.1
mg
The 1 1601
M/ I min
P4
M S min {
14g
4
8(1 + P 24,1
(1+ P.. )uy
664L g.1
Bgg
2
Mg
Th
1h
1
1
17 S min|
1812
Mgg S
L
Nl
S
12C²
12C²² 1/
S
17
12C²²
n1212
I -min
1
14
12
S min
/
f7y
16C1 1 36L La
n
16C,;
36L.
g.0
"2
1
min
(38)
N
|66
: 9.0
Plugging Lemma
E.1
Lemma
into eq.
(35 and using eq. (36). we have the descent in the
Lyapunov function as
V++1 V, - T E| H2 (1: + Te
nnd2
1 +
+
+
Ci 10-9(12,.) + +0g))
2
[,
T/y
(1=1)
no
+ (1 + nr (1=A)x² + no ))
(39)
Proof. To simplify the problem, we assume [4e| P for t 0, O,...,? T 1. By taking summation of eq. 39 from f = to T - 1, we get
1 (vo- (7) + T H (x.)) < 2
12
n
nod
1 +
+
C2
P
nl
(n=
7n
t=
+ (n + nh (n= + 72) C3
(40)
By using Lemma D.5 and eq. 40
we have
2 T-1
Σ
E
V
(2.))
T Σ
2
E ( - H. (x))1
Σ
E (1
T
T
(a) gap + 4(Vo VT)
4n
(1+
?r + nx
nod2
+
+
Cz
Tne
P
nl
(1:2)
n
+ 4 411y + (1==))2 + +nnd))
(
<
(T 7):
(41)
where (a) uses eq. ( (b) takes 7h = O 4), Th, = a) O(T -, +
O(T
x O which satisfies eq. (38). Thus, Theorem 4.10 is proved.
0
32

---

E.5 Proof of Corollary 4.11
Proof. From eq. (41
achieve c-accurate stationary point of the objective function ((x) in we let T Ei= El| (2, = O(T S c. As a result, we can see that the epochs
definition 4.2
number we need is T O(e 3) ). The total sample complexity is PT O(Pe )). Then, finish the proof.
F Proofs of Theorem 4.12 and Corollary 4.13
E.1 Descent in Objective Function
Lemma F.1. Under Assumptions 4.3
4.5 and Lemma D.6 for L (x)),, the consecu-
live iterates of Algorithm satisfy:
(x+e1) (xx)
s 122 (x))(1))))1 2
112
BI
1
E
1
Σ
V
K Ci Be,
Ri,e: u//t))
2
2
2
[1o]
iEL.
+
3nz _
1.1 E8 Mt 3² (xx))1
+
37/
1
E
1
Zi,e
K
(x=))|
1
Σ
K
27 (ot) 12
for all I E (0,1, T 1}. where we assume
2hr1
Proof. Recall the definitions of C (xr) and H (x) in eq.
16.
By using the smoothness of L (xx) in
Lemma D.6. we have that
L
E L (#1+1)]
C (zx) + B(H [e)1 22) + <
E
xrll
2
[E[c (x:)
n.
+
L
V Cx yeo
2,,00 (gtt)
K K
2
iEL
-E[C* (xx)]
The Eli (sx))]
Tn BBBl 11
+ The
EE H (xx)) 1 T
2
2
1: L.
E
V Co Vc, 2,,1 K
2
2
[Ze|
iel
(a)
E L (x+)
The E| (xx))1
Te B1iT111?
2
2
1/
L.
3/1 T-2
E
V
Coee S/. 2x5 2/51
+
E
y1 - y (xx))
2
[Lel
2
ich
+
3n
L3
E
1
K 25.0
(x))
Σ
a
|, - 23 [cc2))1]]
2
i=1
where (a) uses
E 71' (Ix) - 11
n
V n C. (2) Vz Mes 2x, o(fs) |
E n
E v La (Ir, (x)) - V VoLa (xt, Ues
F3,0: [2,t] 1|
K 16
(a.2)
<
1 - 3 (1+)11
+ +33 E
1 Σ || (x+
o 2 (zx) (2x
and (a.1) uses Jensen incquality; (a.2) follows from Lemma
D.I Then, the proof is complete.
33

---

F.2 Bounds of Estimators
Lemma E.2. Under Assumptions
4.3
4.4
4.5
we have the bounds of the estimators of ys and x as
E
Vuli(Te; yt, uftt)
1
th
(Ellyr yxx)))
+ n Σ Ble 2 (x:))l))
1
I
[t]
(n 14e1)07
+
(n 1)(Ta]
2
3(n - (Tal)
Σ
VaLi Me. 2 o55
5 18 <1111001'' [6t]1++
(n - 1)1/[] (L 22,
14
ie4,
for any i E {I...,n] n and t E (0.,,.., 1}.
Proof. For the estimator of y, have
B
V VI Mes v(.)
(e)
1)
1 n2
Vufi(ee, Mes v/.1)) |
n [r] +
(n 1)llel Σ Vulil ve, eiii))
4+ 1)
( (n Ie Joû
T0 1) + (,2 -1411 R
1 v Vufi(ze, ufft)
(n T]
[Te((n 1)
(n 1Le 10%
(n 1)
< 1) + B7, (n - [x(]
Σ
Vafi(ae, Uc, 0fh) (
[T 1)
1=1
69 (n Me 1o%
ne(1e 1) + Bb, (n [el) 13,1 (Bliv-- - (x.)))
Bl (xx)))
(11
1)
[1,
1)
(n Me Doã.
+ (1+
8i [T.
17,, (Elvy- - (x,))
Bl B 2, (mx)))
1)
where (a) follows from the Lemma A.1 in 32 (b) uses Assumption 4.5 4.6 (c) follows from
definition y" (xx arg max, 1 E." fe( (x)): (d) uses Assumption and (e) uses Bea 2 1. n Next, for the estimator of y, we have
(a) ( 4e - 1)
E
Σ EE7.
VeLilse. We. 2 K K
E
K K V La Dr, 20,0 v/,e)
TH
(n
+ (n 1)
[Tel
1
E
V Li Uc. 21,11 u5fi))
K
i=1
3(n [T&])
< M+
(L} + 2X I 12,0)
(42)
(n 1)|4
Then, the proof is complete.
F3 Bounds of Sub-loop Errors
Lemma F.3. Under Assumptions
4.3 4.4 for V8 RR,, we assume that [x=2l S B for some
B < 0o. Then we have
max
Ellos
2 (xx))
E - 2x, (xx))1 S Eaub
3 (1
27.0 +1²)
2 1++..)++.3))
when K 2 max
log
log
where qi (0, 22,,).
Mi
coub
ni Ly,1
caub
oi E (0, Txby..1 ), X 11.11
Ag
34

---

Proof. From Lemma D.1 we have that L; is Ads stronogyyy convex in and we have that C is
2
2ALig,--Lipschit continue in when بيي; also, from Assumption 4.3 4.4, we have that gi Mgg
is My-strongly convex in v and Ls.1-smooth in v. According to Theorem 3.6 In [T by taking
0 < 1/² < ن
and 0 < vi < "xL.,'' we have
Bllugt K 2 (xt) s (1- - (g K BBloo - (x:)))
2 (1- 1i
Al4a
E|| k zx, (2xe) s =1
K [ = - x (zre))
2
To make sure El 2 (xx) S csub and E| = - (2x) 1|2 S Csub for some Caub 2 0, we let
(1 - 12) K EleeA, - 2 (x,))] - 2(1 - ni n₂) k (11u,,,11 + B²) S Esub,
and
Di ATH yk El 2/. - (z))1
(1
ni AMAaye yK (11=9,e12 2 + (xx) (x,011 + (x:))l)
<3(1
2
(a)
ni AMA K
[1=2,,11 113 + I
S3(1
+ B²
2
n2g2
(M)
<3(1
nf AMg )k
[|=2,o12 +
L
+ B²
2
4T.7,
Sepub:
where (a) uses Lemma D.4 (b) take
A 2
24/1
Both can be achieved by taking
Mg
12
1 log
2(102e 12 B²)
311 + JL,,
+ B²)
K2 2 max
log
Caud
11. L
Coub
Then the proof is complete.
Lemma F.4 Under the Assumptions satisfy
4.3
4.4 4.5
the iterates of yv updates according to Algoritim
E Mt-1 (xx++1)11 111ye
y" (x:))) ||
nills + n1((1 + +5²z) 61)(1
L + 8y
Bllyr (xx))l + n + 5y) (n 14 in (n - 1)
[T,]
(1
32h
1
+ 1/9
1.1.1
(1 + 5,))
E
El 2x=)1)
14
[Ll]
1=1
+ by.1
2
1+
Lg.1
2 p3
E
1 ||
Mg
+ 1/
Loy
+
(1+
Lgg.1
2 L2 n
E
V Va Ue, 2 K.
2
bgg
[el
iEh.
for any t E {0,..,,'' - 1}, where we assume
x > (2L5./Hup) (1 + [y
3p (1 +
L2
Hg
) La2k22 Lysker (1 (1+ +
) مب
Las
12h,11
-1 ((1 +
L
Lea + 1)
Lea
}.
Pg 3pphga 6lg.11
ne Mf
Po
Mg ps
Iog.
Proof. For y and y" (æ), we have
E [1441 3² (x++1))1 11f2-EEll Ellb4411 - y² (Ix))] + EElly - y (2(+
+ 22 (EE41 v² (xt). v" (xx) - v (x(+11))
(43)
35

---

We can bound the first term in eq.
4 as
E Me+1
y" (x11)
=E y/ +
1
V
gfi(ar, v1,0 32 (wre)
[Te
=Bllye
v" (202) 11
+ my
E
V Vuli(rss us)
[ell
iEle
+ 2ny Y1 (xe),,
ve ( Wer off))
[Tu
SEL
(6) Elyye 3 (x=))]] + E
VyJi(Is, u1/t)
[Tel
iELe
1
+ 2ny E yt 10 (x+t,
=
V VyJi(T,, Me, v5,) - 30
+ 2ny Ut 50 (1t),
1
V Me. (xr))
Vuli (ul(
n
(6)
<Bllyc
y2 (x2 112 + n
V yyse( Me, u
[+d
iEle
( (er Bo 1²)
1
+ 170 [urlEllve 3² (x1)) +
-2 '" (x:))1
(1 Mulfy BBly
3 (2=))l²+
1
V ff (i
iET,
my Li,1 1 Σ
Ello 2f
71
(4)
nolls + +nn (1(1
B2
y (x:))1² + 2 (n |T,1)0
E
"y (n 1)
[1
+ no (1
83 [1
47,11
1
12
B E - (x:))1
(44)
M1
71
where (a) uses the definition of y² (z.) and eq.
5 (b) uses strong concavity of fa in ys (c) follos (d) uses Lemma F22 We can bound the second term
from definition of y (xx) and Assumption 4.4
in eq. (43) as
(0) Elyy" (x)) - y² (1141)1
Lg,1
I2 41
(1+
E
x1+1l1
Mg
n2
1 1
Lg11
2
2
f
E
Σ
Vyfilze,
Ve o
(45)
Mg
4
ieh,
where (a) follows from Lemma D.2 Also, we can get the bound of the last term as
2E (ve 1² (Ix), v² (x.)) 3 (z++1)
2E(1441 (xx), Vy" (x:) -21) 21))
2E(MM44 - (xx) v²" (Ie+1) y² (xx) Vy (x:)((44)))) Iz))
-2E|| - ~"'<xe>) Il Vy (xx)
+ 2E [1+1
2 - 2² "xx))) 1120 (x++1) (xx)) (2)(1)))4111xx
36

---

b2 R M++1 - yy [1=)]|=
+ ne
1
1
2 L
R.
A1 1
8y,1
Mg
+ E 16+1 50(2)))
-L F
=zel²
Th
2 21,7111
56y, Bll 2/ (xx))]
+
1 +
B
A1 2
5y.1
Mg
11
Lu E 1/+1 y2 (x+))l² || - =01ll==
Lxn
D2+1 10141-1477 xell
2
3 (L3 + 2x0 (/000))
37
0 +
L8
1llue+1 - 3 (xx))]
2
+
(1
1
Lg
2
f.
R 114 1|
TioL TE.
The
Σ
V Viler Ve: 2 (Kk
8,11
Hgg
2
[tl
SEL.
(c)
S 6y 18| 11+11 - "/ (2xxx)) (1x)
me
11
Lgg.1
T
2
f.11
| ||
69.1
Myy
14
2 LM. E
+
V Lrt,
Mbs 3,,0 (11
K
(46)
2
[Tel
iE4
where (a) uses Lemma D.2
D.3 and Lemma 1 in (b) follows from Assumption 4.4 (c) defines
by dy, +
3n Lan
(1,00
2x 2 (.0) By plugging eq. (4). eq. (55). eq. 46 into eq. 43 get
E Vt+1 (2(x122) Elyy v" (21))1
3
1 + 8y Bllyr y² (xxx)) 2 + v + 8y) (n 14|)07
Mulls + (1 5④) (1
[
(n [e
+
+ +nī
(1 + 6g))
1
Σ
Ellui,e - (x)))
Hy
[el
2m
Lgg11
+ yy.1
1+
Pgg
Lan
Leg.1
2 L
V VaCi 2 (
+
1/2
+
E
2
Ug
2
[el
ich
Then the proof complete.
F.4 Descent in the Lyapunov Function and Proof of Theorem 4.12
We define the Lyapunov function as
v(x): = L())) + Ky - 3" (xx))1
(47)
where the coefficient is given by Ky 3rg 13,1
We also constrain the conditions as below:
DoMl
Mylls
uy
5y11
T/ S 3T.,,''
S min
{ (1 +
82 Piy 8(1 +
8 1.2
S
14
Hy 18L2 1.1
Low
+ (1+
6L
L2
< min
Thu
12L (13,0 + 22² L2,0)
2
Mg
12
Th
n3
(1 6Lg.1
6 6/21,,1
1gg
Lg.1 12
L..1 جرادب
max
/T.g.///: (1
(1
+
Hg
334
Lg
Hg
3 L.
37

---

Lrn1kay (1+ (1 6.g11
gg Lf1
1 -1 (11
L
+
+
1
(48)
Hg
Py
Hg
Hg
Py
L
Plugging Lemma
F.1 Lemma
E.3 into eq.
(47
we have the descent in the Lyapunov function as
V4+1
V
s 2 H2 (xx))1
(1
Kulla
- (1
4
)
2
L3 Hij
E
17-
Tly
Mg
+ n/
[.,,1
+ K3
Lnn 2
+
(1+ Lg
)
2 1
B
Σ
VeLi( Uk. 2i,t0 mi.1)
K x |
2
My
14g
[1e]
kele
+ 2ky
2
(n |1,110
3m L3,1
E3
[
n
||
|=ft
+ 1
n Σ
| =7 (1+)
(1 1)
2
n1
1=1
+ +2Kg
+ +12 (12
(1+
17,21
1
Σ
n
K
21 (xx)]l
14/
71
(0)
1/e E H² (xx))
11
Kylle
4
(1 +
Lg
2 =
17x
2
2
Fhy
14
L
Kg
(1
Lg
2 1
E B1hh
2
2
Pg
+ 1/2
[u,11 + Kg
Lun
+
(1
Lgg11
2 L3
3(n - I+()
(1i30 + 2x L3.0)
2
2
Mg
(n - 1)
+ 22 (n - 10
31 1x,1
B
[
Σ
||
K - (x)))
+ n Σ cu - 2, (x)]]
(n 1)
n
4k 1.711 1
Σ
Blle 27 (xx))l²
14
11
(9)
Te E/ H" (xx)]1 +
2
[nn1
+ K2
Ling + (1+ 11g.1 ) 2 13111
3(n ((el) [Tel)
(4),0 + 2222 Lg.0)
2
2
2
Myg
Hjj
(n 1)1le
+ 2K 2 (n- - 14e1002
12L//11 /11
313,1 +
(n 1)11e1
14
Esub
(o) The Bl (x:))) + n/ (1 [1
The
Ca
(n {1
+ na
[.
1L
2
7l
(n 7el
(n T)
126
+ 1h
3 +
Caubs
(49)
where (a) uses Lemma F22
(b) uses eq.
48
and takes
2E
0
2 (x=))l²
2 log
21 2x, (1=))
K 2 max
log
1/ Fig
Esub
mi App
EpUD
(c) defines C == 31L, +2x2
max
F...1
322,1
I...y
+ (1 +
Lgg1 Mg
2 17,11
}}
and plugs in Ky.
Ms
F5 Proof of Theorem 4.12
Proof. For partial block participation, we take the summation of eq. we have
49 from 1 = 0 to T - 1. Then
Th E (z:))1 <v(r)) ((TT + The (1 1
nx
(n P)A²
C
(n P)P
n P 6L2 22
12L4 127
+ 72T (n P)P Py
+ nh
3L +
Coub.
(50)
For partial block participation, By using Lemma D.5
we have
T-1
T-1 Σ
Bl - H' (x:))l
(1t))1
1=
38

---

(0) 2C 20ppp gap
(()((x)) ((TT))
+ +417 [1+
7
C1
(n PI
X²
The
fly
(n 1)P
2AL3,,
12L f.1
+ 11)
n1
+4 (322,11 +
Caub
(n
1)P
(0) 2C gap
2( 2(1)(
(xT))
+
4m
(1
7
C +
Thy
24
f. ih
X²
The
f/
P
1
12L4
4
3
+
11
Coub
2Cgap
2(
(TT)
+ 4m )2
(1+
7/
C2 )
24T,
f.1
o
X²
T
7/
P
1
12L
+ 4
1
+
Coub
(c)
I 50(P-tT-3) )).
(51)
where (a) follows from eq. 50 (b) follows from S P < n; (c) takes The = O(P3T-3).
Ty O(P-tT--)
(PPPTT Esub = 8PP-8T--)
Next, for full block participation (n P), we have the descent in the Lyapunov function for full block participation as
12L, 1²
The -/ B B| H (x:)11 + 7h 313,1 +
((x+1)) (xxe) I
Eeub.
(52)
2
Taking summation of eq.
52
from t 0 to T - 1, we have
1
T
T-1
ne
E
H
[2))]
< <V())) - (xTT) + ns
3L3,1 +
12L4
Csub.
(53)
T
2
nr
1=0
By using Lemma
D.5
and eq.
53
we have
2 T-1 Σ
E ()) - Hx:)))
E|H
(x,))1
+
t=0
1=U
t=
2Cgap
4 4(V((z)) (KTT)
4L4
+ 12
T +
Esub
x2
TTe
14
2Cgap
4(V(2z) (2T))
4L4
X2
Tne
+ 12
22 +
M.
m4
Csub
-)(T
(54)
By taking 7/- = ((1), Bly = 0 (T+)) Crub = 2(T Then Theorem 4.12 proved.
Li
F.6 Proof of Corollary 4.13
Proof. For tasks participate in updates partially, by eq. 51 we can find the e-stationary point in definition 4.2 once we take T = O Note that we set the error of sub-loop as Esub = O +
= (Ee)). According to Lemma F.3 once we take The = O(1) and 7= 10P-0pP---''- -o---r-- - we have the iteration number of sub-loop as K Oloo(?))). Thus, have the total sample complexity PKT = 5 log = -3)
Similarly, by eq. 54 we can find the e-stationary point in definition 4.2 once we take T = O(E ). Note that we set the error of sub-loop as Eaub = ( O(e²). Once we take т) ((1) and
?/= (T we have the iteration number of sub-toop K (log(!)). Thus, have the
total sample complexity nKT O(ne- log(3) )) = ((ne
39

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and introduction in this paper accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
40

---

Justification:
The limitation of previous works is discussed in the Introduction part.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
We provide complete assumption in the main text and full proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide detailed setting of the experiments in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
41

---

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 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. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 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 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 NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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 (nttps://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ /ttppp.cc/pbllc/guideeee http://oeeuuiiisssoooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
42

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
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 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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 accompanied by enror bars, confi- dence 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 library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 96% CI, if the hypothesis of Normality 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 range (c.g. negative еттог 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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.
43

---

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 compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: cttpss/c/cp/.i.c/t.ccccceeeeeeee
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 reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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 tied to particular applications, let alone deployments. However, if there is 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, 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 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 unintentional) misuse of the technology.
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).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
44

---

Answer: [NA]
Justification: The datasets used in this paper contain widely used real-world data; This research does pre-trained LLM other generative models.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have introduced all datasets with proper reference in the experiments part.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the bataasesssppprsstttt paperswi theode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
45

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "6vCdP6XkLW", "reviewer": "Reviewer_iRgq", "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.", "questions": "See weakness.", "limitations": "Not discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces FOSL, a novel fully first-order single-loop algorithm for minimax bilevel optimization, simplifying the problem structure and achieving competitive sample complexity without second-order computations. MemCS is proposed as a memory-efficient method with cold-start initialization, addressing challenges in scenarios with numerous blocks and demonstrating improved sample complexity compared to traditional methods.", "weaknesses": "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.  \n2. It appears that the memory costs have not been compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer iRgq for the time and valuable feedback!\n\n**W1: The assumptions look quite strong, e.g., Assumption 5.3 requires strong convexity, and Assumption 5.4 requires several boundnesses on the derivatives and high-order derivatives, which usually are not satisfied in practice.**\n\nA: Thanks for your question! Assumptions 5.3 and 5.4 have been widely adopted by existing works on bilevel optimization, such as [1][2][3]. The same set of assumptions in our paper have also been made by other studies on multi-block minimax bilevel optimization such as [4]. \nThis is also easily verified in our applications of robust meta-learning and deep AUC maximization. In the robust meta-learning setting, the lower-level problem is optimizing a linear layer with cross-entropy loss, which satisfies the strong convexity assumption. The maximization in the upper-level minimax problem is a combination of a negative hinge function and a linear function, making it a concave function. In deep AUC maximization application, the lower-level function uses square loss, which also satisfies the strong convexity assumption. The maximization in the upper-level minimax problem is a negative quadratic function, which is concave. We intend to investigate relaxed assumptions in our future study.\n\n[1] Approximation methods for bilevel programming. \n\n[2] Bilevel optimization: Convergence analysis and enhanced design. \n\n[3] A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. \n\n[4] Multi-block min-max bilevel optimization with applications in multi-task deep AUC maximization. \n\n**W2: It appears that the memory costs have not been compared.**\n\nA: Thank you for highlighting this point. We evaluated the memory cost of our MemCS method against the baseline method in the robust meta-learning setting on the Mini-ImageNet dataset, using the same training configuration as shown in Table 1 below. Our results demonstrate that the MemCS method achieves better performance and robustness compared to MAML, with lower computational costs. Additionally, as the number of lower-level update steps increases, MAML’s memory cost rises significantly, whereas our MemCS method maintains consistent memory usage, showcasing the scalability of our first-order algorithm. Due to limitations in time and computational resources, we will provide a more detailed comparison of different settings in a future revision of our paper.\n\nTable 1. Memory cost in robust meta-learning application.\n| Lower-level update step number |   MAML   |  MemCS   |\n|:-----------------------:|:--------:|:--------:|\n|         t = 10          | 8560 MB  | 7762 MB  |\n|         t = 15          | 12006 MB | 7739  MB |\n|         t = 20          | 15478 MB | 7632 MB  |\n|         t = 25          | 18922MB  | 7817 MB  |\n|         t = 30          | 22368 MB | 7444 MB  |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vPwVJgZNzX", "reviewer": "Reviewer_Mt97", "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.", "questions": "My main concern is about the contribution of this work to computational efficiency (especially compared to AUC-CT).", "limitations": "I cannot find the discussion about the limitations of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors convert the original minimax bilevel problem into a simple minimax problem and solve it by first-order single-loop algorithm.\n2. The authors provide a comprehensive convergence analysis on the proposed method.\n3. The proposed method is easy to converge and outperforms the baselines on CIFAR-100, CelebA and OGBG-MolPCBA.", "weaknesses": "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.\n2. It would be better to provide the memory consumption of baselines for better comparisons.\n3. The proposed method only achieves comparable performance to mAUC-CT on CheXpert. It would be better to provide more analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer Mt97 for the time and valuable feedback!\n\n**W1: 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.**\n\nA: In the theoretical sections of [1], the authors proposed approximating the hypergradient by estimating second-order matrices. However, in their experiments, they discarded the second-order information for implementation efficiency, leading to a larger approximation error. In contrast, we proposed to address the minimax bilevel optimization problem in a first-order manner, proving that our algorithms maintain a bounded approximation error. This also explains why our method achieves a higher accuracy than AUC-CT in the experiments.\n\n[1] Multi-block min-max bilevel optimization with applications in multi-task deep AUC maximization. \n\n**W2: It would be better to provide the memory consumption of baselines for better comparisons.**\n\nA: Thank you for bringing up this point. We evaluated the memory cost of our MemCS method compared to the baseline method in the robust meta-learning setting on the Mini-ImageNet dataset, using the same training configuration as outlined in Table 1. Our results indicate that the MemCS method achieves better performance and robustness than MAML with lower computational cost. Additionally, as the number of lower-level update steps increases, MAML’s memory cost rises significantly, while MemCS maintains consistent memory usage, demonstrating the scalability of our first-order algorithm. Due to limitations in time and computational resources, we plan to include a more detailed comparison of different settings in a future revision of our paper.\n\nTable 1. Memory cost in robust meta-learning application.\n| Lower-level update step number |   MAML   |  MemCS   |\n|:------------------------------:|:--------:|:--------:|\n|             t = 10             | 8560 MB  | 7762 MB  |\n|             t = 15             | 12006 MB | 7739  MB |\n|             t = 20             | 15478 MB | 7632 MB  |\n|             t = 25             | 18922MB  | 7817 MB  |\n|             t = 30             | 22368 MB | 7444 MB  |\n\n**W3: The proposed method only achieves comparable performance to mAUC-CT on CheXpert. It would be better to provide more analysis.**\n\nA: Thank you for highlighting this phenomenon. The mAUC-CT[1] implementation employs a simpler structure that directly avoids second-order derivative computations, which may be advantageous for the large-scale CheXpert dataset. However, this simplification introduces an additional approximation error, resulting in the mAUC-CT method experiencing significant variance ($\\pm 0.1495$), as shown in Table 1 of the main text. In contrast, our algorithm achieves a much smaller variance ($\\pm 0.0051$) compared to mAUC-CT.\n\n[1] Multi-block min-max bilevel optimization with applications in multi-task deep AUC maximization.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mJXuNsGu9s", "reviewer": "Reviewer_pAAu", "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.", "questions": "Please see the weakness.", "limitations": "No potential negative societal impact.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The proposed method is sound and efficient.", "weaknesses": "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.\n\n2. 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$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer pAAu for the time and valuable feedback!\n\n**W1: 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.**\n\nA: This is a good question. The lower level problem in Eq.(1) aims to find an optimal solution $z_i^*$ of $g_i(x,z_i)$. In Eq. (2), the lower-level problem is converted into a constraint $g_i(x,z_i) - g_i(x,z_i^*) \\leq 0$. Since $g_i(x,z_i)$ has a unique minimizer $z_i^*$, this constraint is satisfied if and only if $z_i=z_i^*$. As a result, the objective function in Eq. (2) becomes $\\min_x\\max_y \\frac{1}{n}\\sum_{i=1}^nf_i(x,y,z_i^*)$, which is the same as that in Eq. (1). Similar techniques also appear in [1][2][3]. \n\n[1] On solving simple bilevel programs with a nonconvex lower level program. \n\n[2] A fully first-order method for stochastic bilevel optimization. \n\n[3] A value-function-based interior-point method for non-convex bi-level optimization.\n\n**W2: 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})\\\\| \\leq 0$?\n\nA: Proposition 4.9 does not guarantee that $\\mathbb{E}\\\\|y_{t+1}-y^*(x_{t+1})\\\\| - \\mathbb{E}\\\\|y_{t}-y^*(x_{t})\\\\| \\leq 0$ for **all** $t$. This is due to the existence of the positive error terms $O(\\frac{\\eta_y^2}{|I_t|})(\\sigma_f^2+\\sigma_{th}^2)$, $\\mathcal{O}(\\eta_y)\\frac{1}{n}\\sum_{i=1}^n\\mathbb{E}\\\\|v_{i,t}-z_i^*(x_t)\\\\|^2$, $\\mathcal{O}(\\eta_x^2/\\eta_y)\\mathbb{E}\\\\|\\tilde{h}_x^t\\\\|^2$, $\\mathcal{O}(\\eta_x^2)\\mathbb{E}\\\\|h_x^t\\\\|^2$. \n\nThese terms have no direct correlation with the negative term $-\\mathcal{O}(\\eta_y)\\mathbb{E}\\\\|y_{t} - y^*(x_{t})\\\\|^2$, and hence it cannot guarantee that their summation together is negative. \nInstead, this inequality can be understood as follows. By rearranging Proposition 4.9, we have \n$$\n\\mathbb{E}\\\\|y_{t+1}-y^*(x_{t+1})\\\\|^2 \\leq (1-\\mathcal{O}(\\eta_y))\\mathbb{E}\\\\|y_{t}-y^*(x_{t})\\\\|^2 + O\\bigg(\\frac{\\eta_y^2}{|I_t|}\\bigg)(\\sigma_f^2+\\sigma_{th}^2) +\\mathcal{O}(\\eta_y)\\frac{1}{n}\\sum_{i=1}^n\\mathbb{E}\\\\|v_{i,t}-z_i^*(x_t)\\\\|^2 + \\mathcal{O}(\\eta_x^2/\\eta_y)\\mathbb{E}\\\\|\\tilde{h}_x^t\\\\|^2 + \\mathcal{O}(\\eta_x^2)\\mathbb{E}\\\\|h_x^t\\\\|^2.\n$$\n\nThis indicates the decay of the optimality distance $\\mathbb{E}\\\\|y_{t}-y^*(x_{t})\\\\|^2$ over iterations. The positive error terms $O(\\frac{\\eta_y^2}{|I_t|})(\\sigma_f^2 + \\sigma_{th}^2)$ and $\\mathcal{O}(\\eta_x^2)\\mathbb{E}\\\\|h_x^t\\\\|^2$ are negligible in the final convergence analysis because they are proportional to the square of the stepsizes $\\eta_x$ and $\\eta_y$. By choosing sufficiently small stepsizes, these terms can be made sufficiently small (e.g., see the proofs of Theorem 4.10). The error term $\\mathcal{O}(\\eta_y)\\frac{1}{n}\\sum_{i=1}^n\\mathbb{E}\\\\|v_{i,t}-z_i^*(x_t)\\\\|^2$ can be merged into the descent term of iterate $v_{i,t}$ (see the details in Lemma E.3). The error term $\\mathcal{O}(\\eta_x^2/\\eta_y)\\mathbb{E}\\\\|\\tilde{h}_x^t\\\\|^2$ can be canceled out by the negative term $-\\mathbb{E}\\\\|\\tilde{h}_x^t\\\\|^2$ in Proposition 4.8 for stepsize $\\eta_x$ sufficiently small.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hFQu8uSEjt", "reviewer": "Reviewer_mptp", "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.\n\nOverall, the proposed algorithms are novel and well-justified with practical applications. However, further elaboration is needed regarding their practicality and efficiency.", "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.\n\n- 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.\n\n- 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.\n\n- 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?\n\nIf my concerns are well addressed, I would be happy to raise my score.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and well-structured, with strong motivation and clear logic.\n\nThe authors provide a reformulated version of minimax bilevel optimization problems and demonstrate the gap between the reformulated and original problems. The convergence analysis is also solid and thorough. \n\nThey also validate the experimental results of FOSL and MemCS in Deep AUC Maximization and meta-learning cases respectively.", "weaknesses": "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. \n\nBesides, the gradient calculation procedure is not mentioned in the paper. I believe it is quite important for incorporating optimization problems in neural networks.\n\nThere is also a typo in the title of algorithm 2: Cold-star", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer mptp for the time and valuable feedback!\n\n**W1: 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.**\n\nA: From the perspective of scale, compared to deep AUC maximization, the application of meta-learning is comparably a larger-scale problem due to the vast number of tasks and number of variables. The need to calculate the second-order derivative introduces high computational cost to second-order methods (e.g. MAML), making it hard to scale in this problem. However, as a first-order method, our algorithm can scale well in the meta-learning setting. In Table 1 we show the memory consumption of our MemCS compared with MAML with a different number of lower-level update steps. As a second-order method, MAML's memory cost increases with lower-level update steps, whereas our MemCS algorithm maintains stable memory consumption. Additionally, Table 2 (referenced in the answer to Question 2) shows that the average iteration time of MemCS is only one-third that of MAML. This demonstrates that our algorithm is more efficient in terms of both memory and computational costs. We will conduct further studies on larger-scale problems in our future research.\n\nTable 1. Memory cost in robust meta-learning application.\n| Lower-level update step number |   MAML   |  MemCS   |\n|:------------------------------:|:--------:|:--------:|\n|             t = 10             | 8560 MB  | 7762 MB  |\n|             t = 15             | 12006 MB | 7739  MB |\n|             t = 20             | 15478 MB | 7632 MB  |\n|             t = 25             | 18922MB  | 7817 MB  |\n|             t = 30             | 22368 MB | 7444 MB  |\n\nThanks for pointing out the typo and please see the response to the gradient calculation in **Answer to Q4**.\n\n**Answer to Q1:** This is a good point. Our methods can handle non-convex optimization problems, because the overall objective function $\\Phi(x):=F(x,y^*(x),z^*(x))$ is generally non-convex with respect to $x$. The concavity/convexity assumptions are made only for the maximization problem in $y$ and the minimization problem in $z$. These two optimization problems are much easier to solve than optimizing $\\Phi(x)$ and usually satisfy the convexity property. This can be more clearly seen in our applications of meta-learning and deep AUC maximization. In our application of the robust meta-learning setting, the lower-level problem is optimizing a linear layer with cross-entropy loss, which satisfies the strong convexity assumption. The maximization in the upper-level minimax problem is a combination of a negative hinge function and a linear function, making it a concave function. In our deep AUC maximization application, the lower-level function uses square loss, which also satisfies the strong convexity assumption. The maximization in the upper-level minimax problem is a negative quadratic function, which is concave. \n\nIt is also worth mentioning that our assumptions, such as lower-level strong convexity, Lipschitz continuity, and bounded variance, are primarily made for theoretical analysis. These assumptions have also been adopted in existing theoretical works on bilevel optimization (e.g., [1][2][3]) and minimax bilevel optimization (e.g., [4]). For practical use, our algorithms can also be applied to broader applications where these assumptions may not hold; however, in such cases, the convergence guarantee may not be developed.\n\nWe will add the above discussions and the applicable score of our algorithms in the revision. \n\n[1] Approximation methods for bilevel programming. \n\n[2] Bilevel optimization: Convergence analysis and enhanced design. \n\n[3] A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. \n\n[4] Multi-block min-max bilevel optimization with applications in multi-task deep AUC maximization. \n\n**Answer to Q2:** Thank you for the suggestion. We have conducted a further evaluation of the average iteration time for our proposed algorithms and the second-order method in a robust meta-learning setting, as detailed in Table 2. The results demonstrate that our algorithms run significantly faster than the second-order method.\n\nTable 2. Average iteration time of different algorithms on the robust meta-learning setting.\n|         Method         | Second-order method | FOSL  | MemCS |\n|:----------------------:|:-------------------:|:-----:|:-----:|\n| Average iteration time |        9.41s        | 1.42s | 3.15s |\n\n**Answer to Q3:** The reasons for the improved performance of FOSL and MemCS differ between the two applications. For deep AUC maximization, the answer is yes. In the implementation of the baseline method (mAUC-CT), second-order information is discarded, whereas we leverage this information through the calculation of the hyper-gradient. For robust meta-learning, our method is specifically designed to address the minimax bilevel optimization problem. This design allows for easy integration with rank-based methods, enhancing the robustness of training and consequently leading to better performance.\n\n**Answer to Q4:** This is a good question. In this work, we use $\\nabla \\mathcal{L}^*(x) = \\nabla_x F(x,y^*(x),z_{\\lambda}^*(x)) + \\lambda(\\nabla_x G(x,z_{\\lambda}^*(x)) - \\nabla_x G(x,z^*(x)))$ as the gradient to update $x$, which is a first-order approximate of the vanilla hypergradient $\\nabla \\Phi(x)$. Proposition 4.7 shows that the gap between $\\nabla \\mathcal{L}^*(x)$ and $\\nabla \\Phi(x)$ is proportional to $1/\\lambda$, and hence can be made sufficiently small by choosing the regularization parameter $\\lambda$ large enough. Since $y^*(x),z_{\\lambda}^*(x),z^*(x)$ can not be obtained directly, we use $\\nabla_x \\mathcal{L}(x_{t},y_{t},z_{t},v_{t}) = \\nabla_x F(x_t,y_t,z_t) + \\lambda(\\nabla_x G(x_t,z_t) - \\nabla_x G(x_t,z_t))$ to approximate $\\nabla \\mathcal{L}^*(x)$ at the $(t+1)_{th}$ iteration.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)