On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
Authors: Ekaterina Borodich
Alexander Gasnikov
Dmitry Kovalev
Venue: ICML 2025 poster (2025)
Keywords: convex optimization
saddle-point problems
gradient methods
minimax optimization
Primary area: optimization->convex

Abstract: We revisit the smooth convex-concave bilinearly-coupled saddle-point problem of the form $\min_x\max_y f(x) + \langle y,\mathbf{B} x\rangle - g(y)$. In the highly specific case where function $f(x)$ is strongly convex and function $g(y)$ is affine, or both functions are affine, there exist lower bounds on the number of gradient evaluations and matrix-vector multiplications required to solve the problem, as well as matching optimal algorithms. A notable aspect of these algorithms is that they are able to attain linear convergence, i.e., the number of iterations required to solve the problem is proportional to $\log(1/\epsilon)$. However, the class of bilinearly-coupled saddle-point problems for which linear convergence is possible is much wider and can involve general smooth non-strongly convex functions $f(x)$ and $g(y)$. Therefore, *we develop the first lower complexity bounds and matching optimal linearly converging algorithms for this problem class*. Our lower complexity bounds are much more general, but they cover and unify the existing results in the literature. On the other hand, our algorithm implements the separation of complexities, which, for the first time, enables the simultaneous achievement of both optimal gradient evaluation and matrix-vector multiplication complexities, resulting in the best theoretical performance to date.

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
Ekaterina Borodich 123 Alexander Gasnikov 43 Dmitry Kovaley
Abstract
1. Introduction
In this paper, we consider the following saddle-point opti- mization problem with bilinear coupling function:
We revisit the smooth convex-concayy bilinearly- coupled saddle-point problem of the form min, max, fx) + (y, Bz) g(y). In the highly specific case where function f(x) strongly con- vex and function g(y) is affine, or both functions are affine, there exist lower bounds on the number of gradient evaluations and matrix-vector multi- plications required to solve the problem, as well as matching optimal algorithms. A notable as- pect of these algorithms is that they are able to attain linear convergence, i.c., the number itera- tions required to solve the problem is proportional to log( (og(1/).. However, the class of bilinearly- coupled saddlc-point problems for which linear convergence is possible is much wider and can involve general smooth non-strongly convex func- tions f() and g(y). Therefore, we develop the first lower complexity bounds and matching opti- mal linearly converging algorithums for this prob- lem class. Our lower complexity bounds are much more general, but they cover and unify the exist- ing results in the literature. On the other hand, our algorithm implements the separation of com- plexities, which, for the first time, enables the simultaneous achievement of both optimal gradi- ent evaluation and matrix- vector multiplication complexities, resulting in the best theoretical per- formance to date.
min max [F(x; v) [(x) + (y. Br) - g(v)), (1) #EX yEY'
where X' = RR and y = R&d are finite-dimensional Fu- clidean spaces, B E Rdyxda is a coupling matrix, and [(x): X + R and g(y): y + R are continuous func- tions. We aim to solve problem (1) in the fundamental setting where both functions f(x) and g(y) are convex and smooth.'
Saddle-point problems of the form (1) appear in various fields such as economics (Von Neumann & Morgenstern, 1947), game theory (Roughgarden, 2010), and statistics (Berger, 2013). Moreover, these problems have wide range of applications machine learning, including supervised learning (Zhang & Xiao, 2017; Wang & Xiao, 2017; Xiao et al., 2019), reinforcement learning (Du et al., 2017), com- puter vision (Chambolle & Pock, 2011), robust optimization (Ben-Tal & Nemirovski, 2002; Liu et al., 2017), distributed optimization (Lan et al., 2020; Scaman et al., 2018; Ko- valev et al., 2021; Yarmoshik et al., 2024; Kovalev et al., 2024), and the training of generative adversarial networks (Mescheder et al., 2017; Nagarajan & Kolter, 2017).
1.1. First-Order Methods and Linear Convergence
The majority of machine learning applications of prob- lem (I) involve high-dimensional spaces X' and y. In this scenario, the most widely used and often the only scal- able optimization algorithms are are first-order methods. These methods implement an iterative process to find an approx- imate solution to the problem using the evaluation of the gradients of the functions f(x) and g as well as matrix- vector multiplication with the matrices B and B More specifically, they perform iterative updates of the current es- timate of the solution until it converges to the exact solution up to a given accuracy. One of the main goals of our paper is to develop efficient first-order optimization methods for
'Higher School of Economics YYandex Rescarch 'vaannkovv Institute for System Programming. Trusted AI Research Center 'Innopolis University. Correspondence to: Dmitry Kovalev <dakovalev @ @gmail.com>, Ekaterina Borodich <borodich, ed pdwphytcchhcdus.. Alexander Gasnikov <gas- nikov@ yandexx.addd....
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
A function is called smooth if it is differentiable and has Lipschitz-continuuus gradient. See Section for an equivalent formal definition.

---

On Linear Convergence in Smooth Convex-Concave CooppeerrlyCoupeed Saddle-Point Optimization
solving problem (I).
which is special case of problem (1) with strongly convex function f(()) and affine function g(v)-
In this paper, we are interested in first-order methods for solving problem (1) that are able to achieve linear conver- gence. That is, we are interested in algorithms that can find an c-approximate solution to the problem using at most log//e))())) gradient evaluations and matrix-vector mul- tiplications, where (-)) hides universal constants, >> is an arbitrary precision, and K 2 1 is constant that possibly depends on the internal properties of the problem such condition numbers, etc.
Unfortunately, apart from the cases of bilinear min-max games and affinely constrained minimization, the question of finding optimal algorithms for solving problem (1) is far from being resolved, even in the fundamental strongly- snnvex-strongyyconeee
setting. Although separate lower bounds on the gradient evaluation and matrix-vector mul- tiplication complexities have already been developed by Nesterov (2013) and Zhang et al. (2022b), respectively, the existing sate--o-thheaiie algorithms (Kovalev et al., 2022b; Thekumparampil et al., 2022; Jin et al., 2022; Du et al., 2022; Li et al., 2023) cannot simultaneously reach these bounds. The main reason is that these algorithms perform the same number of evaluations of the gradients fxx)) and Vg(y)) and matrix-vectur multiplications with the matrices B and B at each iteration while solving the problem, whereas the lower bounds on these numbers (Nesterov, 2013; Zhang et al., 2022b) can be significantly different. Thus, to reach the desired lower bounds, an optimal algorithm would have to implement the separation of complexities by skipping gra- dient evaluations and/or matrix-vector multiplications from time to time. Borodich et al. (2023); Alkousa al. (2020); Sadiev et al. (2022); Lan & Ouyang (2021) attempted to develop efficient first-order methods with the complexity separation for solving the problem; however, these algo- rithms are not able to achieve optimal complexities by a substantial margin, see Section 5 and Table 1 for details.
In this work, we also intend to consider problem classes where linear convergence is possible in principle. A typical and one of the most fundamental examples of such a class is problem (I) with strongly convex functions f(z) and g(y). There are plenty of linearly converging first-order optimiza- tion methods in this ting, which include the gradient descent ascent (Zhang et al., 2022a), the extragradient method (Korpelevich, 1976), and the optimistic gradient method (Gidel et al., 2018). More- over, there is an array of algorithms that enjoy improved, or accelerated, convergence rates (Kovalev et al., 2022b; Thekumparampil et al., 2022; Jin et al., 2022; Du et al., 2022; Li et al., 2023) with the help of the Nesterov momen- tum trick (Nesterov, 2013). Another fundamental problem class where linear convergence is possible is the class of bilinear min-max games, which is a special case of prob- lem (I) with affine functions/ fx) and (3y). Such problems can be solved using the corresponding algorithms with lin- ear convergence rates (Azizian et al.. 2020; Li et al., 2022). Finally, Kovalev et al. (2022b) developed algorithm for solving the general smooth convex-concave problem (1)
set-
The situation is even worse in other cases, such as the stronglycomme--coccae or comve--stronlb--concaee set- tings, where only one of the functions f(x) g(v) is strongly convex, or the convex-concave setting, where nei- ther of the functions is strongly convex. To the best of our knowledge, there are no lower complexity bounds that would cover these cases, with the exception of the highly specific cases of bilinear min-max games (Ibrahim et al., 2020) and affinely constrained minimization (Salim et al., 2022). Therefore, the question remains unresolved as to whether the current tfat-oof-the-art linearly converging algo- rithms for this setting (Kovalev et al., 2022b; Sadiev et al., 2022) are optimal or not.
and provided a set of sufficient conditions under which the proposed algorithm attains linear convergence.
1.2. Optimal Algorithms and Complexity Separation
In this paper, we are concerned with the task of developing optimal algorithmss, which is one of the ultimate goals in optimization research. This task can be divided into two key parts. The first part involves finding lower bounds on the oracle complexity of solving the optimization problem, i.e., the number of oracle calls, such as gradient evalua- tions or matrix-vector multiplications, required to find an approximate solution to the problem. The second part is to find optimization algorithms that match these lower bounds. Such algorithms are called optimal because their oracle complexity cannot be improved due to the lower complexity bounds. For example, in the case of bilinear min-max games, lower bounds were proposed by Ibrahim et al. (2020) and matching optimal algorithms were developed by Azizian et al. (2020); Li et al. (2022). Similarly, Salim et al. (2022) developed lower bounds and optimal algorithms for smooth and strongly convex minimization with affine constraints,
1.3. Main Contributions
The above discussion reveals significant gaps in the cur- rent theoretical understanding of smooth convex-concave saddle-point problems with bilinear coupling. In particu- lar, the existing lower complexity bounds are insufficient, and the state-of-the-art optimization algorithms are limited. Summarizing these gaps leads to the following open re- search question: Is it possible to develop optimal lin- early converging first-order optimization method for solving the smooth convex-concave bilinearly-couple saddle point
2

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-ooupled Saddle-Point Optimization
problem (I)? We provide positive answer to this question
2. Preliminaries
and present the following key contributions:
2.1. Main Definitions and Assumptions
In this paper, we use mathematical notation, which is mostly standard and is therefore described in Appendix A. Fur- ther, in this section, we provide a formal description of the assumptions that we impose on problem (1). First, we de- fine the (strong) convexity and smoothness properties of a differentiable function.
(i) We describe the class of smooth convex-concave paddle-point problems of the form (1) for which it is possible to achieve linear convergence in Section 2. We establish the first lower complexity bounds for this class. In particular, we show that to find an c-approximate solution to problem (1), any first-order optimization method requires at least (H.,) evaluations of the gra- dient V fzr), (Kyy evaluations of the gradient Vg(y), and Ö (Kizy) matrix-vector multiplications with the ma- trices B and T where Kg, Ky, and Kay denote cer- tain condition numbers associated with functions f(x), (VV), and matrix B.?
Definition 2.1. A differentiable function h(x): Rd - R is called u-strongly convex for μ 2 0 if the following inequal- ity holds for all x'' E Rd:
D2 x') 2 p z²11².
(2)
A differentiable function h(x): IRd + R is called convex the same inequality holds with μ =
(ii) We show that our lower complexity bounds are tight. That is, we develop the first optimal algorithm that matches these lower bounds. This algorithm imple- ments the complexity separation, allowing us to si- multaneously achieve both optimal gradient evaluation and matrix-vecte vector multiplication complexities. To the best of our knowledge, such a result has never been established in the literature, even in the fundamental mrongly-convern saaovee-ttronlyy-ooe cooongy setting.
Definition 2.2. A differentiable function h(x): R - R is called T-smooth for T. 2 0 if the following inequality holds for all x, x' E ER4:
Da(r, x') S 1 L.Ix x'112
(3)
Next, we formalize the (strong) convexity and smoothness assumptions that we impose functions fx) and g(y) as Assumptions 2.3 and 2.4. Note that we allow the strong convexity constants μl and Hy to be zero, thus covering the case of non-strongly convex functions (xx) and g(y).
(iii)
As a side contribution, we develop a new algorithm for solving a class of composite monotone variational in- equalities. Just like the current state-of-the-art method of Lan & Ouyang (2021), our algorithm implements the separation of complexities, but enjoys substantially im- proved convergence rates and works in much broader range of settings, Refer to Section 4 and Section 5.2 for details.
Assumption 2.3. Function f(x):: X - R is pu-strongly
convex and L,-smotth for L, > Pr 2 0.
Assumption 2.4. Function g(v): y + R is By strongyy
convex and sm-othh for Ly By 2 0.
Finally, the next Assumption 2.5 describes the spectral prop- erties of the coupling matrix B.
Our lower complexity bounds are much more general than the existing lower bounds for the special cases of strongly- sonvex-strongly-concaee (Nesterov, 2013; Zhang et al., 2022b), bilinear (Ibrahim et al., 2020), and affinely con- strained (Salim et al., 2022) optimization. On the other hand, our lower bounds recover and provide unification of these existing results. Besides, our optimal algorithm shows the best theoretical performance "on the market", which, to the best of our knowledge, outclasses all existing meth- ods in the literature, with the exception of the algorithms of Azizian et al. (2020); Li et al. (2022) and Salim et al. (2022); Kovalev et al. (2020), which are already optimal in the aforementioned specific cases of bilinear and affinely constrained optimization, respectively.
Assumption 2.5. 0, such that
There exist constants Lay > Mays Pys Z
2 Pay
min
B
(B))
B)
Vf(x) E range B for all x E x
Amin
B
B)
otherwise
(BBT)
Vg(y) E range B for all y E y otherwise
2 M
miin
Amin
(BB T)
Lay Amax A B)
Amax (MBx
Additionally, we assume that if May >> 0 and Myz > 0, then
May = Pyz-
Further, to shorten the notation, we gather all the parame- ters defined in Assumptions 2.3 to 2.5 into a single vector π = (Lz, Ly Leys Pzz Pys Mays Myx) E II, where II C RR denotes the parameter set.
Here, (-) hides the logarithmic factor (eg)) and univer- sal (and possibly additive) constants. The precise definitions of Kaz, Kys and Kay are provided Section 2.
3

---

On Linear Convergence in Smooth Convex-Concave Siiineaarl-Coupled Saddle-Point Optimization
2.2. Key Assumption for Linear Convergence
to avoid addressing some corner cases where the condition numbers small, which neither theoretically prac- tically interesting. It should be noted that Assumption 2.7 does not impose any fundamental restrictions;" it is merely introduced to streamline our complex theoretical findings.
As discussed in Section we are interested in algorithms for solving problem (1) that exhibit linear convergence. We introduce the key Assumption 2.6, which will enable us to establish linear lower complexity bounds and devise optimal linearly converging algorithms.
Assumption 2.7. For all π E the following additional constraints are satisfied:
Assumption 2.6. Parameters π E II satisfy the inequality min (6xz by) 0, where ór and by are defined as follows:
La > Aftes Ly > 4fbys V Vialy > 4 mmxx (aay Mazz
Lay > 18 max Pays Pyz v MaHly
02 Me + MaayLLy 8y My + Le.
(4)
2.3. Structure of the Solution Set
To better understand this assumption, consider the standard primal and dual reformulations of problem (1), which are given as follows:
In this paper, we denote the solution set of the saddle-point problem (1) as c X x V. Under Assumptions 2.3 to 2.5, (x", ,y"" E S if and only the following first-order optimal- ity conditions hold:
min
P(x) = f(x) + 9" (Bx)],
(5)
max yEY
Vf(x)) + B y
Vgly") Bx* = 0.
(7)
Moreover, under Assumption 2.6, the solution set is al- ways non-empty and has an affine structure, as indicated by Lemma 2.8.
One can show that the primal objective function P(x) and the dual objective function - (y) satisfy the quadratic growth condition (Anitescu, 2000; Karimi et al., 2016) with constants 62 and 6,, respectively. This fact provides a good starting point for understanding why linear convergence is plausible under Assumption 2.6. On the other hand, Ko- valev et al. (2022b) showed that this assumption is sufficient for developing a linearly converging algorithm. Moreover, in Section 3, we obtain Theorem 3.2, which implies that Assumption 2.6 is also necessary for achieving linear con- vergence, thus making both a necessary and sufficient condition.
Lemma 2.8. Under Assumptions 2.3 to 2.6, the solu- rion set S of problem (1) is nonempty and is given as S = Sg x Sy, where S = Arg minzex P(x) and S. Arg max D(y). Moreover, the primal and dual solu- tion seis S. C X and Sy C y have the following affine structure:
{0}
He >0 otherwise
=x=x" +
ker B
(8)
We also need to characterize the linear convergence rates of the first-order methods that we consider in this paper. Such rates are typically expressed via the condition numbers as-
[0}
My My>0 otherwise"
S, = 5² +
ker B
sociated with a given optimization problem. Consequently, we define the following condition numbers for problem (I):
where (z",8") ) E S is an arbitrary solution to problem (1).
We also define weighted squared distance function R3 (I, 3) follows:
Le
Ly 5y" Kay
L2 5,
Kx
Ky
(6)
8
R² R2,,, (x.v) 6_ dist (i;t? + 5y dist? Sy).
(9)
The condition numbers Ki and Ky correspond to the fune- tions fx) and g(v), respectively. These be seen extensions of the standard condition numbers Uz/ and Ly/Hg, which are commonly used in smooth and strongly convex optimization (Nesterov, 2013). Similarly, the con- dition number fazy associated with the bilinear coupling term is a generalization of the standard condition num- ber (2x/ which is widespread in strongly-convex- strongly-concave saddle-point optimization (Zhang al.,
We going to this function measure the quality of given approximate solution to problem (I) in both lower complexity bounds and the convergence analysis of optimal algorithms.
3. Lower Complexity Bounds
3.1. First-Order Saddle-Point Optimization Methods
2022b; Ibrahim et al., 2020).
In this section, we present lower bounds on the number of gradient evaluations and matrix-vector multiplications re- quired to solve problem (1), These lower bounds apply to
Further, we would like to ensure that the condition numbers defined in equation (6) are lower-boue bounded by some small universal constants. This is achieved by the following addi- tional A Assumption 2.7 on the parameter set II. It allows us
In particular, is always possible increase the smoothness constants Lz, Tay and Tazy to satisfy Assumption 2.7.

---

On Linear Convergence in Smooth Convex-Concave Billncarly-Couplec Saddle-Point Optimization
specific class of algorithms that refer as first-order saddle-point optimization methods. A formal description of this class is provided in Definition 3.1. This definition is mostly inspired by the common linear span assumption (Nesterov, 2013; Zhang et al., 2022b; Ibrahim et al., 2020). However, the standard existing definitions focus only on iteration complexity. This is insufficient in our case, as we need to derive more specific lower bounds on the numbers of gradient evaluations and matrix-vector multiplications. Therefore, in Definition 3.1, we introduce continuous execution time parameter 7 2 0 and assume that the evalu- ation of the gradients fz)) and Vy(y) takes time Ty and Ty, respectively, while matrix-vector multiplication with matrices B and B takes time TB- A similar approach was previously used in distributed optimization by Scaman al. (2017: 2018); Kovalev al. (2024), where they had to ensure distinction between communication and local computation complexities.
MBT (7) C X and MB(r) C y are defined as fol- lows:
span (zz, Byy (2,z) e M(T--a]]) 2 TB
MBT(F) =
< 7B
MD(() Span([Bz,y) Bz.y: (2.0) E M(T M(T-m))) <
Ø
(iv) Initialization and output. At time 7 0, the algo- rithm must initialize the memory with the zero vector, that is, M2
{0}. At any time T 2 O, the algorithm must specify a single output vector from the memory, (co((T)Bo(7)) E M(r).
3.2. Lower Bounds
In this section, we present our lower complexity bounds. We start with Theorem 3.2, which shows that it is not pos- sible to obtain a linearly converging algorithm for solving problem (1) if Assumption 2.6 does not hold. The proof can be found in Appendix F. This theorem indicates that there exists a specific "hard" instance of problem (1), such that any first-order saddle-point optimization method fails to converge in terms of the distance to the solution set and converges sublinearly in terms of the primal-dual gap. It is important to clarify that the main purpose of Theorem 3.2 is to demonstrate the impossibility of attaining linear con- vergence in general if Assumption 2.6 does not hold, rather than to provide tight lower complexity bounds for this set- ting. Thus, we leave further investigation of the general case of problem (I) under Assumptions 2.3 to 2.5 for future work.
Definition 3.1. An algorithm is called a first-order saddle- point optimization method with gradient computation times Tf, Ty > O, and matrix-vector computation time 7B 0, if it satisfies the following constraints:
ii Memory. At any time 0, the algorithm main- tains memory, which is represented by set M(T)= = (T( x (T),), where (T) C X and M2 C Y. The memory can be updated by computing the gra- dients fxx) and Vg(y). and by performing matrix- vector multiplications with matrices B and B This is represented by the following inclusions:
Mz(r) C My(r) U.T (r),
(10)
Theorem 3.2. Let π E 11, Rs > 0, and > 0 be ar- bitrary parameters, distance, and precision, respectively. Suppose that Assumption 2.6 does not hold, i.e., without loss of generality, óх = 0. There exists a problem (1) satis- fying Assumptions 2.3 to 2.5 with parameters n, such that dist(0; S2) R.z, and for any first-order saddle-pone op- timization method and execution time T >> 0, the following inequality holds:
My(T) Mg(T) U MB(T),
where sets (T),,, Mg(T), MBT (T), and MB(T) are defined below.
(ii) Gradient computation. At any time 7 2 0, the algo- rithm can update the memory by computing the gra- dients f=( and Vo(y), which take time Ty and Tg. respectively. That is, for all 7 2 0, sets My( X and (gg(M) C y are defined as follows:
dist dist"( (To(T))
R
(11)
Moreover, to reach precision on the primal-duat gap ( < e by any first-order saddle-point optimization method, the execution time T must satisfy the following inequality:
((z, Vf(x) & SEMaaT-TTT) 7 T2T1
My(r)=
a
7 <<TI
Mg(7)= (paan((y. Volz): y U M,(T Ty)H) -T))) T To.
t <TT9
72 2 (T) dist(O;
d Sx) (.))
(12)
(iii) Matrix-vector multiplication. At any time 7 2 0, the algorithm can update the memory by performing matrix- vector multiplication with matrices B and B
Now, we are ready to present lower complexity bounds for problem (1) under Assumptions 2.3 to 2.7 in Theorem 3.3. The proof can be found in Appendix G. The lower bound on the total execution time in equation (13) contains the
which takes time TB That is, for all 7 2 0, sets
5

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Coupled Saddle-Point Optimization
terms ((v ) D (yy)y) and P (izz)) These terms can be respectively interpreted as gradient evaluation complex- ities with respect to the gradients V f(r) and Vg(y), and matrix-vector multiplication complexity with respect to the matrices B and B as they are respectively multiplied by the corresponding times Ty. Tg. and TB- In addition, these complexities are proportional to the logarithmic factor (o]()/)), making them linear as we previously discussed.
where px(=): 2 + R. (=(::: 2 + Z. Vector =' defined in equation (14) is often called weak solution to the mono- tone variational inequality. In the setting of this paper, it is equivalent to the strong solution"; refer to Kinderlehrer & Stampacchia (2000) for details.
Further, we assume that the gradients (z)(z) and operators (2(2) are monotone and Lipschitz with respect to the norm I-11,, where P E S These assumptions are commonly used in the literature and are formalized through the follow- ing Definitions 4.1 and 4.2 and Assumptions 4.3 and 4.4. Note that Assumption 4.3 implies that each function pz(2) is convex and smooth.
Theorem 3.3. Under Assumption 2.7, let II, R >>0 O, and > 0 be arbitrary parameters, distance, and pre- cision, respectively. Suppose that Assumption 2.6 holds. There exists a problem (1) satisfying Assumplions 2.3 to 2.5 with parameters n, such that R2 (0,0) = R², and to reach precision R2,,,, (Ho(T), < by any first-order saddle-point optimization method, the execution time must satisfy the following inequality:
Definition 4.1. An operator G(r): R - Rd is called J-- strongly monotone with respect to the norm |1-IIp for μ uz0 0 if the following inequality holds for all x x' RR.
(G(x) - -0(-)G()), x-==),==x)))) -a) 2 ul| x IP.
(16)
T 2
52
TJ
Km
+
Tg
T
Kay
(13)
An operator G(x:): Rd + Rdd is called monotone if the same inequality holds with μ 0.
where (1(-) hides the multiplicatiive facto log a universal constant.
eR²
>>> 0 is c
Definition 4.2. An operator G(z): R2 - R is called M- Lipschitz with respect to the norm I|-Ipp for M 2 0 if the
The result in Theorem 3.3 has two important merits. First, this lower bound is tight, which we prove by developing matching optimal algorithm in Section 4. Second, by making an appropriate restriction of the parameter set II, we can recover the existing lower complexity bounds for the important and fundamental special cases of strongly-convex- strongly-coneave saddle-point optimization (Zhang et al., 2022b; Nesterov, 2013), bilinear auddle-point optimization (Ibrahim et al., 2020), and strongly convex minimization with affine constraints (Salim et al., 2022). On the other hand, our result applies to an arbitrary choice of parameters E II. Therefore, Theorem 3.3 and our definition of the condition numbers Kg, fiy, and Kiyy in Section 2 provide unification and substantial generalization of the existing results. See Appendix D for additional discussion.
following inequality holds for all x; x' E Rd:
[[G(x) G(z')l S M| x' ll..
(17)
Assumption 4.3. For all 1 S i S n, the gradient Vp;(z) is monotone and L,-Lisschitz w.r.t. ||-lpp.
Assumption 4.4. For all S i S n, operator Qi(z) is monotone and M,-Lipschitz w.r.t. ||-1Ip.
4.2. Optimal Sliding Algorithm for Monotone Variational Inequalities
Now, we are ready to present our new algorithm for solv- ing the variational inequality problem (14). One of the key ideas behind the development of this algorithm is new perspective on the celebrated accelerated gradient method of Nesterov (2013). In particular, single step of this algo- rithm, applied to minimizing an L-smooth convex function h(=): 2 - R. can be seen as applying a single step of the standard gradient method to the function hz(2) with the fixed stepsize 1/L, where (2): Z + R is defined as follows:
4. Optimal Algorithm
4.1. Monotone Variational Inequalities
In this section, we develop an optimal algorithm for solving problem (I). To do this, we consider a more general mono- tone variational inequality problem of finding 2" E C₂ such that
he(2) = a, 2aaa where z' E Z. (18)
Indeed, the stepsize 1/L is suitable, since one can show that function he(2) L-smooth as well. Hence, using the standard recursion for the gradient descent, for all 2, we obtain the following inequality:
p(²*) - p(=) + (Q(z), - 2) S 0 for all 2 E Cz, (14) where C₂ is a closed and convex subset of the finite- dimensional Euclidean space 2 = Rdd,, and differentiable convex function p(2): 2 > R and continuous monotone operator Q(z): 2 + 2 have the following finite-sum struc- tures:
2 ++1 - =11² + hr (1) } |||=- =112 +h.))) (19)
*Vector 2" E C. is strong solution to the variational inequality if f(22)) - -p()) + (Q(="). 2) < 0 for all E Cz. Refer to Lan (2020, proof of Theorem 3.3) for the proof.
p(z) = p))),
Q(2) = -i Qx(2),
(15)
6

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-ooupled Saddle-Point Optimization
Next, we can define zd+1 +2 (1-0)) and use the definition of function hz(z)) in equation (18), the convexity of function h(2)), and the definition of Ote in equation (20).
Using Corollary 4.6, we can show that Algorithm 1 achieves the optimal complexity separation for solving the variational inequality problem (14) as long gorithm 1 matches the existing lower complexity bounds for this problem (Nesterov, 2013; Ouyang & Xu, 2021) and theoretically outperforms the existing state-of-the-art algo- rithm of Lan & Ouyang (2021), which is designed for the case n 2 with additional restrictions. See Section 5.2 for details.
(1). Thus, Al-
This gives the following recursion:
1 +||
=11² + aj (1= -h()]] S 2 - - =112 +
- h())],
which implies the accelerated convergence rate [h(=') ming h==)] = ((LE)(E², where I > 0 is the initial dis- tance to the solution. Overall, the derivations above offer a vast simplification compared to the standard proof of Nes- terov (2013).
4.3. Application to the Main Saddle-Point Problem
In this section, we show how to adapt Algorithm 1 solve the main problem (1) and reach the lower complexity bounds in Theorem 3.3, To do this, we define a diagonal matrix P E 84 as follows:
Inspired by the sliding algorithm of Lan & Ouyang (2021; 2016); Kovalev et al. (2022a), we apply series of transfor- mations of the form (18) to functions (z) in recursive fashion. This leads, subject to some additional details, to Algorithm I for solving problem (I4).? 7 Moreover, using the considerations above, we obtain the key theoretical result in Theorem 4.5. The proof can be found in Appendix K.
P= diag (
(24)
and consider special instance of problem (14), where n 3, Z = C2 = X' x V. operators (z(2) = Qi v) are defined as follows:
Theorem 4.5. Let Assumptions 4.3 and 4.4 hold, where M,, L 2 and M; + L; > O. Let on be defined recursively as follows:
Q1 v) 0,
Qz(x,v)= = Oa B r
(25)
Q2 y) O,
B
On, y
an = 0141
(1 0411 2
v1 V (1+ for t 1. (20)
and functions pz(2) = p;( y) are defined as follows:
Then the output Zoot of Algorithm 1 for solving problem (14)
Pi (I 8) fz) P2(2, 8) gly),
satisfies the inclusion Zows E C2 and the inequality
(26)
Pa(a, y) 2/4 |Ba Vg(um))l )| - B y V (Tm)))
p(zou) - p(=) + (Q(2), Zour - z)
where Ain
(Jin; Min) 2 and Ba, B, 2 are defined
4'L L,
2'
T3 )
=11m - =|B. (21)
IT 1 T3
IT
B₂ = 1/(4Ly),
By 1/
(27)
From the optimality conditions (7), one can conclude that this variational inequality problem instance is equivalent to the original problem (1) as long as function pa(z) is re- placed with zero. However, the additional quadratic regular- izer (2(2) helps to achieve the optimal linear convergence rates in all cases where 62 > O and 5y > O, even when Pb = and/or 1hy = O. Moreover, this regularization does not break the convergence to the exact solution x" of the original problem (1). Indeed, it easy to show that Vps(2") converges to zero long Zin converges to 2
Furthermore, we can reorder functions (z) and operators Q=(=) in ascending order of the values of the Lipschitz constants L, and M,. which leads the complexity result in Corollary 4.6. The proof can be found in Appendix L.
Corollary 4.6. Under the conditions of Theorem 4.5, to ensure the following inequality
p(zou) - -(()== + (Q(2),(2())))))))) Zone - 2) < En|| - =x11p (22)
for all z E C2 and > 0, it is sufficient perform no more than
Next, we apply Algorithm to solve the variational inequal- ity problem instance defined in equations (14), (25) and (26). Using Theorem 4.5 and Corollary 4.6, we obtain the fol- lowing result in Theorem 4.7. The proof can be found in Appendix M.
6 max { 1
1
(23)
computations of the gradient Vp.(z) and operator Q+(2)
for 1 1sism n.
'From the definition a in equation (20), it follows that ar E (0, 1] and o, = 22 + ta; "The pseudocode for the proposed Algorithm is postponed to Appendix due to space limitations.
'hhe algorithm of Lan & Ouyang (2021) works in the case n = 2, where Qi(=) = Oa, and p2(z) = 0. RRefer the proof of Theorem 4.7 in Appendix K for more details.
7

---

On Linear Convergence in Smooth Convex-Concave cotincearl-Coppeed Saddle-Point Optimization
Theorem 4.7. Under Assumptions 2.3 to 2.7, functions P=(2), operators Qı(z), and matrix P defined in equa- tions (24), (25) and (26) satisfy the conditions of Theo- rem 4.5 with the following parameters:
algorithms for the stronggy-ooowaa-stronn-----m-m case
(Kovalev et al., 2022b; Li et al., 2023; Jín al., 2022; Du et al., 2022; Thekumparampil et al., 2022; Borodich et al., 2023; Chambolle & Pock, 2011; I; Alkousa et al., 2020), the wrongly-convex-cones case (Kovalev et al., 2022h; Sadiev et al., 2022), and the convex-concave case (Kovalev et al., 2022b). This comparison summarized in Table 1, which is postponed to Appendix C due to the page limit. One can observe that our optimal result is substantially better compared to all the listed algorithms.
L1 = Kay L2 = Kiys
La = Kays
(28)
M M2 =0 M3 Vezy
Moreover, the inpul Zin (Mins yim) and the oulput Aout
(ooa You) of Algorithm 1 satisfy the inequality V (Zou)
2 V (zm) as long as the numbers of inner iterations {T:}-=1 are chosen according to the proof of Corollary 4.6 in Ap-
Once again, it is worth highlighting that the complexity of our algorithm matches the complexities of the algorithms of Salim et al. (2022) and Azizian et al. (2020); Li et al. (2022), which are optimal in the more specialized cases of affinely constrained minimization and bilinear saddle- point optimization, respectively. We provide a detailed discussion of the lower complexity bounds in these cases in Appendix D.
pendix I. Here, the Lyapunov function (=) = (x., v) is defined as follows:
(2) = R2,5, (2. v) + 12D ( (29)
where: 2" (a", 3²* = projs (2in) = projs( (-owr)
Theorem 4.7 implies that we can reduce the value of the Lyapunov function (Ir,y) defined in equation (29) by constant factor with a single run of Algorithm 1. Hence, we can apply the standard restarting technique to this algorithm and obtain the complexity result in Corollary 4.8. The proof can be found in Appendix N.
5.2. Algorithm for Solving the Variational Inequality Problem (14)
Here, we consider the variational inequality problem defined in equations (14) and (15) in the case n = 2, where func- tion p2(2) and operator Q1 (2) are zero. This is one of the simplest yet most important special cases of problem (14) as discussed by Lan & Ouyang (2021). We compare Algo- rithm for solving this problem with the algorithm of Lan & Ouyang (2021). Let R 2 0 be the following distance parameter associated with the constraint set C.:
Corollary 4.8. Under the conditions of Theorem 4.7, to reach precision R2 (x.y)= S c, it is sufficient to perform
((V Roz) O W and O(VRay) computations of the gra- dients V (x)) and V Vgly), and malrix-vector multiplccations with the matrices B and B", respectively. Here, (-) hides the multiplicative factor log c, Rº = R2 (0, 0) is the initial distance, e E (0, R2), and e 1 + 12kz + 12ky-
R == sup || 2 sEC.
(30)
The complexity result in Corollary 4.8 matches the lower complexity bounds in Theorem 3.3 up to universal and/or additive constants. Hence, this result is optimal. Moreover, to the best of our knowledge, this result theoretically out- performs all existing state-of-the-art algorithms, including the algorithms of Kovalev et al. (2022b); Li al. (2023); Jin et al. (2022); Du et al. (2022); Thekumparampil et al. (2022); Borodich et al. (2023); Alkousa et al. (2020); Sadiev et al. (2022); Chambolle & Pock (2011). See Section 5.1 for additional discussion.
We compare the numbers of evaluations of the gradient Vp1 (z) and operator Q2(2) required by both algorithms to find vector Zout E C2 that satisfies the following accuracy criterion:
sup P(Zont - p(2) + (Q(=), Zonr - 2) Se. zEC.
(31)
where > is arbitrary precision. Note that the pa- rameter R is finite only if the constraint set is bounded. However, we can easily tackle this issue by following the standard approach and replacing the constraint set C. with its intersection with the ball fa E Z || zu S D), where D > 0 is positive parameter. Refer, for instance, to Nesterov (2007).
5. Comparison with Existing Results
5.1. Algorithms for Solving the Main Problem (1)
The theoretical complexity of Algorithm 1 with restarting, applied to solve the smooth tllinearly-oouples saddle-point optimization problem (1), is established in Corollary 4.8 and is proven to be optimal due to the lower complexity bounds in Theorem 3.3. We compare this result with the theoretical complexities of the existing state-of-ther art lin- early converging first-order methods. These include the
The comparison of Algorithm with the algorithm of Lan & Ouyang (2021) )) is summarized in Table 2, along with the corresponding lower complexity bounds (Nesterov, 2013; Ouyang & Xu, 2021). The table is postponed to Appendix C due to the page limit. One can observe that the theoretical complexities of these algorithms coincide up to universal
8

---

On Lincar Convergence in Smooth Convex-Concave Bilincarly-Coupled Saddle-Point Optimization
constants when y R M2Rt/e. However, Algo- rithm 1 can significantly outperform the algorithm of Lan & Ouyang (2021) in the case where v L > M2Re /e. It is important to highlight that this case is worth consid- ering, as it plays an essential role in achieving the optimal complexities in Corollary 4.8 for the main problem (I). In addition, the algorithm Lan & Ouyang (2021) only works in the case n 2 with the additional restrictions described above. On the other hand, using the result in Corollary 4.6, it is easy to verify that our Algorithm can achieve the optimal complexity separation for n > 2, provided that = (1).
saddle point problems. arXiv preprint arXiv:2307.1294. 2023.
Chambolle, A. and Pock, T. A first-order primal-dual algo- rithm for convex problems with applications imaging. Journal of mathematical imaging and vision, 40; 40:120-11 140-140, 2011.
Du, S. S., Chen, J., Li, L., Xiao, L., and Zhou, D. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pp. 1049- 1058. PMLR, 2017.
Du, S. S., Gidel, G., Jordan, M. I., and Li, C. J. Opti- mal extragradient-basee allinearly-couple saddle-point optimization. arXiv preprint arXiv:2206.055. 085733, 2022.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S. A variational inequality perspec- tive on generative adversarial networks. arXiv preprint arXiv: 1802. 10551, 2018
Acknowledgements
Ibrahim, A., Azizian, w., Gidel, G., and Mitliagkas, I. Linear lower bounds and conditioning of differentiable games. In International Conference on Machine Learn- ing, pp. 4583-4593. PMLR, 2020.
This work was supported by grant, provided by the Ministry of Economic Development of the RF in accor- dance with the subsidy agreement (agreement identifier 1000000313325P4G0000
and the agreement with the Ivan- nikov Institute for System Programming of the RAS dated June 20, 2025 No. 139-15-2025-011.
Jin, Y., Sidford, A., and Tian, K. Sharper rates for separable minimax and finite sum optimization via primal- dual ex- tragradient methods. In Conference on Learning Theory, pp. 4362-4415, PMLR, 2022.
References
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence of gradient and proximal -raddient methods under the
Alkousa, M., Gasnikov, A., Dvinskikh, D., Kovalev, D., and Stonyakin, F. Accelerated methods for saddle-point problem. Computational Mathematics and Mathematical Physics, 60:1787-1809, 2020.
condition. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pp. 795- 811. Springer, 2016.
Anitescu, M. Degenerate nonlinear programming with quadratic growth condition. SIAM Journal on Optimiza- tion, 10(4):
2000.
Kinderlchrer, D. and Stampacchia, G. An introduction to variational inequalities and their applications. SIAM, 2000.
Azizian, W., Scieur, D., Mitliagkas, I., Lacoste-Julien, S., and Gidel, G. Accelerating smooth games by manipulat- ing spectral shapes. In International Conference on Arti- ficial Intelligence and Statistics, pp. 1705-1715. PMLR, 2020.
Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Ben-Tal, A. and Nemirovski, A. Robust optimization- methodology and applications. Mathematical program- ming, 92:4534480, 2002.
Kovalev, D., Salim, A., and Richtárik, P. Optimal and practical algorithms for smooth and strongly convex de- centralized optimization. Advances in Neural Information Processing Systems, 33:1 23:18342-18352 2020.
Berger, O. Statistical decision theory and Bayesian anal- ysis. Springer Science & Business Media, 2013.
Kovalev, D., Gasanov, E., Gasnikov, A., and Richtarik, P. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time- varying networks. Advances in Neural Information Pro- cessing Systems, 34:22325-2255 2021.
Borodich, E., Kormakov, G., Kovalev, D., Beznosikov, A., and Gasnikov, A. Optimal algorithm with complexity sep- aration for strongly convex-strongly concave composite

---

On Linear Convergence in Smooth Convex-Concave BilincarlyCouppee Saddle-Point Optimization
Kovalev, D., Beznosikov, A., Borodich, E., Gasnikov, A., and Scutari, G. Optimal gradient sliding and its applica- tion to optimal distributed optimization under similarity. Advances in Neural Information Processing Systems, 35: 33494-33507, 2022a.
Nesterov, Y. Introductory lectures on convex optimization:
A basic course, volume 87. Springer Science & Business Media, 2013.
Ouyang, Y. and Xu, Y. Lower complexity bounds of first- order methods for coneeve bilinear saddle-point problems. Mathematical Programming. 185(1): 2021.
Kovalev, D., Gasnikov, A., and Richtárik, P. Accelerated primal-dual gradient method for smooth and convex- concave saddle-pe point problems with bilinear coupling. Advances in Neural Information Processing Systems, 35: 21725-21737, 2022b.
Roughgarden, Algorithmic game theory. Communica- tions of the ACM, 53(7):78 86, 2010.
Kovalev, D., Borodich, E., Gasnikov, A., and Feoktistov, D. Lower bounds and optimal algorithms for non non-smooth convex decentralized optimization over time- varying net- works. arXiv preprini arXiv:2405. 18031, 2024.
Sadiev, A., Kovalev, D., and Richtárik, P. Communication acceleration of local gradient methods via an accelerated primal-dual algorithm with an inexact prox. Advances Neural Information Processing Systems, 35:21777~ 21791, 2022.
Lan, G. First-order and stochastic optimization methods for machine learning, volume Springer, 2020.
Salim, A., Condat, L.,, Kovalev, D., and Richtárik, P. An op- timal algorithm for strongly convex minimization under affine constraints. In International conference on artifi- cial intelligence and statistics, pp. 4482-4498. PMLR, 2022.
Lan, G. and Ouyang, Y. Accelerated gradient sliding for structured convex optimization. arXiv preprint arXiv:1609.04900 2016.
Lan, G. and Ouyang, Y. Mirror-prox sliding methods for solving class of monotone variational inequalities. arXiv preprint arXiv:2111.00900 2021.
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Mas- soulié, L. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Interna- tional Conference Machine Learning, pp. 3027-3036. PMLR, 2017.
Lan, G., Lee, S., and Zhou, Y. Communication-effiiie efficcien algorithms for decentralized and stochastic optimization. Mathematical Programming, 180(1):237-284, 2020.
Scaman, K., Bach, F., Bubeck, S., Massoulié, L., and Lee, Y. Optimal algorithms for non-smooth distributed opti- mization in networks. Advances in Neural Information Processing Systems, 31, 2018.
Li, J., Yu, Y., Loizou, N., Gidel, G., Ma, Y., Le Roux, N., and Jordan, M. On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging. In International Conference on Artificial In- telligence and Statistics, pp. 9793-9823 PMLR, 2022.
Thekumparampil, K. K., He, N., and Oh, S. Lifted primal- dual method for bilinearly coupled smooth minimax opti- mization. In International Conference Artificial Intel- ligence and Statistics, pp. 4281-441-44 1281-4308. PMLR, 2022.
Li, J. Yuan, H., Gidel, G., Gu, Q., and Jordan, M. Nes- terov meets optimism: rate-optimal separable minimax optimization. In International Conference on Machine Learning, pp. 20351 20513. PMLR, 2023.
Von Neumann, J. and Morgenstem, O. Theory of games and economic behavior, 2nd rev. Princeton university press, 1947.
Liu, Y., Yuan, X., Zeng, S., and Zhang, J. Primal-dual hybrid gradient method for distributionally robust opti- mization problems. Operations Research Letters, 45(6): 625-630, 2017.
Wang, J. and Xiao, L. Exploiting strong convexity from data with primal- first-order algorithms. In Interna- tional Conference on Machine Learning, pp. 3702. PMLR, 2017.
Mescheder, L., Nowozin, S., and Geiger, A. The numerics of gans. Advances in Neural Information Processing Systems, 30, 2017.
Xiao, L., Yu, A. W., Lin, Q., and Chen, W. Dscovr: Random- ized primal-dual block coordinate algorithms for asyn- chronous distributed optimization. Journal of Machine Learning Research, 20(43):1 2019.
Nagarajan, V. and Kolter, J. Z. Gradient descent gan opti- mization is locally stable. Advances in Neural Informa- fion Processing Systems, 30, 2017.
Yarmoshik, D., Kovalev, D., Rogozin, A., Kiselev, N., Dorin, D., and Gasnikov, A. Decentralized optimization with coupled constraints. arXiv preprint arXiv:2407.020 02700200, 2024.
Nesterov, Y. Dual extrapolation and its applications to solv- ing variational inequalities and related problems. Mathe- matical Programming, 109(2):319334) 2007.
10

---

On Linear Convergence in Smooth Convex-Concave Centteearl-Coopllce Saddle-Point Optimization
Zhang. G., Wang, Y., Lessard, L.., and Grosse, R. B. Near- optimal local convergence of alternating gradient descent- ascent for minimax optimization. In International Con- ference on Artificial Intelligence and Statistics, pp. 7659- 7679. PMLR, 2022a.
Zhang. J., Hong, M., and Zhang, S. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1)9001-93, 2022b.
Zhang, Y. and Xiao, L. Stochastic primal-dual coordinate method for regularized empirical risk minimization. Jour- nal of Machine Learning Research, 18(84):1-42, 2017.

---

On Linear Convergence in Smooth Convex-Concave Couplee Saddle-Point Optimization
Appendix
A. Notation
In this paper, we use the following notations: S" and 84+ denote the sets of p x p symmetric and symmetric positive defimite matrices, respectively; Ip denotes the x p identity matrix, Jpxq and Opxg denote the p x all-ones and all-zeros matrices, respectively, Jp Jyxp and Op = pxp: cy E IR" denotes the j-th unit basis vector, 1p = (I..... 1) E TR" O, (O,...,,)) 0) RR. In addition, |I-I1 denotes the standard Euclidean norm of vector, and (:-)) denotes the standard scalar product two vectors, ||-IIp- | (-)ll and (,-) = -P((),)) denote the weighted Euclidean norm and scalar product, respectively, where E S Amin (.), min( and Amax() (.) denote the smallest, smallest positive, and largest cigenvalues of a symmetric matrix, respectively; mmax()) and min (+) denote the largest and smallest positive singular values of matrix.
For nonempty closed convex set A C Rd and vector E Rd, we define the standard distance function dist(r; A) as follows:
dist(x; A) min z'EA
x - x'||-
(32)
For differentiable function l(x),, we denote the Bregman divergence associated with h(x) as (x(,,, which is defined as follows:
Da x/) = h(x) h(x')(()))))))))))) - -V -M
(33)
For proper, closed, and convex function h(x), we denote its Fenchel conjugate as h- (xx), its Moreau envelope as MA (r),
and its proximal operator as (x) These are respectively defined as follows:
h hx)x) = sup ((x, x²) h(x)),
Mx min h(x') 2X
>z' x=12))
(34)
prox (x) = arg min h(x') || x²12)
2x
12

---

On Linear Convergence in Smooth Convex-Concave Ceatnnarll-Couplle Saddle-Point Optimization
B. Algorithm 1 Pseudocode
Algorithm!
1: input: Fin E C₂
2: parameters: P E S faili C CR++,
3: for {Li)==1 {M, 18 C R_, (Telk=1 E (1,
l....,, do
4: = Zin
5:
p.(2) (2)))
6: end for
7: Zout -Recursiverrocedure[]]
8: output: Aour E Z
9: & Auxiliary Recursive Procedure:
function RecursiveProcedure(( f1,..., xx-
11: if 1 n then
12:
return arg mic E Pb:
nit An
13:
else
14:
20 = 2/, 11... 1.0
15:
for 14 = 0...., Tk do
16:
for i 1...., 12 do
17:
Pi
kch
(2)
Ct Pj
1itt.ntkkk (2)
(ar 2 + (1 met
i2 k: i< k
P
18:
4 kdi
= Li II Oity
19:
M
Mi II (at./ (21;-1) -1)
L K::1, 1./11... M lill
20:
21:
kit
V Tpttthmat (oh + Qi(ck
m
||2 " d 1 + (2, A k i= k i K
Pi
k:h
(2) poite (2)
end for
24:
tty..tt 1 1/2 Recursiveerooceuure(/ +, 1,tt,...,,
25:
20+1 Oct, t1...,44 1,t+1122 + (1 10,,,,,,3
a1, )zt
A kitt Qu(z Qu ( 1 1.t2-1/2)
26:
Qn
27:
" 12-1 11+1 2 442 + (H
ki p)-
kit
Q
28:
for 1 k ,...,, do
29:
to- to +10...... 2 2 Te4
30:
end for end for return 2
31:
32:
33:
end if
34:
end function
13

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Couplel Saddle-Point Optimization
C. Tables
Table I. Comparison the optimal complexity of Algorithm 1 for solving the main problem (1) developed in this paper (Theorem 3.3,
Corollary 4.8) with the existing stale-of-the-art linearly-covverging algorithms in the sommgllyyoonvee---toonyyyoooomo strongly-convex- concave, and convex-coneave settings.
Complexity (I)
Algorithm
(z)
Vg(y)
B and B
Strongg--ooveexstrongyy--ocess
(ftz; Myy
and Pay May 0)
Kovalev et al. (2022b); Li et al. (2023)
Jin et al. (2022); Du et al. (2022)
La Mn
Lay Paply
My
Thekumparampil et al. (2022)
Borodich et al. (2023)
Lg
Lag
He
Chambolle Pock (2011)
N/A (2)
Luyy
Vilsilu
Alkousa al. (2020)
L Mx
Luy V Thy /PxMu
/PrMy
Optimal (3) (this paper)
Lay
<PsMu
Strongly-convex case (Jam) Myz > O and Pay = Mby 0)(5)
Kovalev al. (2022b)
Lex Myz
Lex
L Mig
Myz
Sadiev al. (2022)
Lay Pyx
1.2 Pige
L Ui
N/A
Leg Pyy
Lis
1 Mig
Optimal () (this paper)
Lax
Lx
Pi
Muy
Myv
Mir
Convex-concave case (Nuzy
Myr
0 and
Psx
Mly
0)
Low Lav/books
La
Kovalev al. (2022b)
+
May
Optimal (3) (this paper)
Jr
Lay v Ln
May
Pry
For brevity, we omit universal constants and logarithmic factors such as log (2) Requires computation of the proximal operators of functions (x) and/or g
Lower complexity bounds established in Theorem 3.3. These bounds are matched by Algorithm 1,
which is established by Theorem 4.7 and Corollary 4.8.
Here, the lower bounds were also established by Zhang et al. (2022b); Nesterov (2013).
(his case is symmetric to the convex-strongly-comm case, which we omit for brevity.
Table 2. Comparison of Algorithm with the algorithm of Lan & Ouyang (2021) for solving the variational inequality problem defined in equations (14) and (15) the case n 2, p2(=) 0, Q2(2)= = 0.
Complexity
Algorithm
Pp)
Q2(2)
Lan Ouyang (2021)
Li1e +
Man?
Algorithm (this paper)
0
L R2
O MrR²
Lower Bounds (Nesterov, 2013; Ouyang & Xu. 2021)
14

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Couplel Saddle-Point Optimization
D. Additional Discussion of the Lower Complexity Bounds
As mentioned in Section 3.2, the lower complexity bound in Theorem 3.3 recovers several important problem classes, which are special instances of problem (1). We can recover these problem classes by imposing additional constraints on the parameter set I1.
ii) The class of smooth strongly-oover--tnnngyyyoomwww saddle-point optimization problems corresponds to the constraint
May
Myy O.
(35)
In this case, the lower bound in equation (13) becomes the following:
L Ty
Ly V
Lay VHaHy
Ω
Tf
+
TB
(36)
Hx
My
where (2) hides universal constants and logarithmic factors. This result recovers the existing lower complexity bounds of Zhang al. (2022b); Nesterov (2013).
(ii) The class of bilinear saddle-point optimization problems is obtained by choosing
L Ly = O, M4x My O,
T Tg = 0, May Myz O,
(37)
and the lower bound in equation (13) turns into the following:
Lay
(38)
Pay
This result recovers the existing lower complexity bound of Ibrahim et al. (2020). Note that strictly speaking, we cannot choose Lar = Ly = 0 due to Assumption 2.7. However, this is not an issue, because Assumption 2.7 allows us to choose arbitrary Lg, Ly > such that Ly = 5juyy and still obtain the lower bound (38) from equation (13). In addition, as mentioned Section 2, this assumption not fundamental restriction but is rather used to avoid covering uninteresting corner cases in our theoretical proofs.
iiii) The class of smooth strongly convex optimization problems with affine constraints is obtained by choosing
Ly Pyy =0= 0, Pay
O,
Tg O.
(39)
In this case, the lower bound in equation (13) becomes the following:
Ln
Lay
Lx
á
Tf
TB
(40)
Pi
Pyg
Hhr
which recovers the existing result of Salim et al. (2022). Similarly to the previous case (ii), we can choose T.y / instead of L, to satisfy Assumption 2.7 and still obtain the lower bound (40).
It is worth mentioning the work of Ouyang & Xu (2021), who offer sublinear lower complexity bounds for this problem class. However, their result does not contradict ours since they consider the case Pyn = 6, = 0, i.e., Assumption 2.6 does not hold. is also important to highlight that affinely constrained optimization problems, where jzyz = O, hold limited interest. Indeed, in this setting, it typically assumed that 22 = A (BBT), ) which, by definition, is always nonzero.
15

---

On Linear Convergence in Smooth Convex-Concave Callinerll-Couuple Saddle-Point Optimization
E. Proof of Lemma 2.8
We define linear spaces C, c X and by C V as follows:
[0}
Az
by { {0}
My otherwise
Cx
(41)
ker B
otherwise
ker B
One can show that the following identity holds:
F(z + dz dn) = F(x,y) for all (I, E X x y and (dz, E Lx x byy
(42)
Indeed, for the saddle part, we obviously have (y + dy, Bxx +2)) (w. Br). Furthermore, can show that f(x + da) fz) and g + dyy) = g(v). Indeed, Assumptions 2.5 and 2.6 and equation (41) imply ff(x) E C and Vg(v) E c. Hence, we obtain
f(x + do) - f(x) = [( (Vf(x + d2 (2. d2 = 0,
sly + dy) g(u) J. (Valy dy 1), dy 0, which conludes the proof of equation (42). addition, it easy to show that
dom f"() Ci and domg g+) C b.y
(43)
Consider the following saddle-point problem:
min max F(x, y). ce vEG
(44)
We can show that this problem has a unique solution (r))))) E C x C,, which, together with equation (42), implies Lemma 2.8. Let us further prove this statement.
One can show that funetion P(x)) is strongly convex on L. Indeed, if pr 0 this statement is obvious. Otherwise, Assumption 2.6 implies May O, which in turn implies the strong convexity of function g (Bær on & thanks to the strong convexity of function g" (v). The strong convexity of function 9* (y) is implied by the smoothness of function g(v).
Next, we show that dom P(-) * Ø, which immediately implies dom P(-) C * Ø, thanks to equation (42). Indeed, if Hyy > O function g" (y) is smooth, which implies dom P(.) = X. Otherwise, Assumption 2.6 implies Plyz > 0, which in turn implies Vg(v) range B for all E y. Hence, there exists x E - such that Bx = Vg(y) for some y J. On the other hand, Vy(y) E dom g" (.), which implies Bz dom g²(-) and dom P(.).
The strong convexity of P(x:) on f and the fact that dom P(-) N2 + Ø imply that there exists unique solution x" C to the following problem:
min P(x).
(45)
rEC
Similarly, there exists unique solution C. to the following problem:
max D(y).
(46)
yEL!
Moreover, vectors xt and y² are solutions to the primal and dual problems in equation (5), respectively, thanks to equation (42).
Let Mx) = (Br). Vector x" is solution to the problem min (f(x) Mxx)]. Hence, standard theory implies -Vf(=*) E Oh(x*), or
M(x) ( - (Vf()) for all x E X.
(47)
From this inequality, for arbitrary ker B, obtain
(Vf(x)) x x²),
16

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Coupled Saddle-Point Optimization
which implies Vz(=") range B
Hence, there exists y Ly such that Vf(x=) -B y, which for all x E X, implies
h(x) 2 h(xx) + (v, Bx Br*).
Hence, for all range B, we obtain
g²)z 2 9 (Bx") (v, Bz").
In addition, this inequality holds for all E 3 due to equation (43). Hence, E 00y (Bx"), which implies Bx* Vg(v). We also have x² E ( y)- Hence, is solution of problem (46), which implies y = y". It remains to observe, that (a", ,y" satisfies the first-order optimality conditions (7). Hence, the strong duality holds in both problems (1) and (44), which concludes the proof.
17

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Couplel Saddle-Point Optimization
F. Proof of Theorem 3.2
Note that the condition 8- = 0 implies pa and pay = 0. Consider the following special instance of problem (1):
min max f(u)) Le || 1 + Myw Uz) My l1yll
min E E yER
(48)
where f(x): R2d + is the Smoothh function proposed by Nesterov (2013, Theorem 2.1.7). This problem has a single solution (u, 0,0) E Rd41 x IR Rd, where - = arg min,,, f(uz). Moreover, the primal-dual gap is owerrbounded
as follows:
P(ugy 02) - ( 2 -
Thus, the statement of Theorem 3.2 trivially follows from Theorem 2.1.7 Nesterov (2013).
G. Proof of Theorem 3.3
The proof of Theorem 3.3 relies the following Lemmas G.1, G.2 and G.3. The proof of Lemma G. 1 is available in appendix H. The proof of Lemma G.2 is available in appendix I. The proof of Lemma G.3 is available in appendix J. Lemma G.1. Under conditions of Theorem 3.3, the execution time can be lower-bounded follows:
T T2 Ω (Tr Vkg log cR² + Tg
Riy log eR²
(49)
Lemma G.2. Under conditions of Theorem 3.3, let Pys Mye and p 2 Hkfy Then the execution time can be lower-bounded as follows:
T T2 Vizy log elt"
(50)
Lemma G.3. Under conditions of Theorem 3.3, let Mor My > O and Mally 2 max 1ggz) Then the execution time can be lower-bounded as follows:
2 TB
/lizg log elt
(51)
It remains to obtain the lower bound ( /Ray log alt without the additional assumptions that were made in Lemmas G.2 and G.3. It can be done by considering the following special cases:
(i) Case frr My O. In this case, have May Myn 0 due Assumptions 2.5 and 2.6. We replace My 0 with a very small value My > 0 and apply Lemma G.2 obtain the desired result.
(ii) Case μ4 = and Byy >
(ii.a) Case Hyz >> 0. We can apply Lemma G.2.
(ii.b) Case Myz = 0. This case is symmetric to case (iii.b).
(iii) Case Pg > 0 and bly
(iii.a) Case Jay > 0. This case is symmetric to case (ii.a).
(iii.b) Case Pay = 0. In this case, we have Myz > due to Assumption 2.6. We can replace by with very small value My and apply Lemma G.2 to obtain the desired result.
(iv) Case Pg > 0 and Mly >0 O.
(iv.a) Case Mally 2 max max( 22 We can apply Lemma G.3.
(iv.b) Case Hally < M2g.. We can apply Lemma G.2.
(iv.c) Case Hally < p This case is symmetric to case (fv.b).
This concludes the proof.
18

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Copplel Saddle-Point Optimization
H. Proof of Lemma G.1
Case Pay > O. consider a special instance of problem (I), where = y R2 functions f(x) and g(v) and matrix B defined as follows:
f(x) Ma ||~:1²
Le Ma Fx F A()).x))
+
2
(52)
g(v) = Ly 11y11
B May
where matrix F (dxd is defined follows:
(53)
2
This problem instance has unique solution (u". 1/") E X x V, which is given as follows:
x arg min de ||t|| La Ur Fa A(ef,)), x);
Pay Ly
V² x.
(54)
The rest of the proof similar the proofs of Lemmas G.2 and G.3.
Case May O. In this case, assume Myz O, otherwise instance of problem (I), where X' Rd+1 and y I, functions f(z) and g(y) and matrix B are defined follows:
use the proof of the previous case. We consider special
He ||-|| + Lg My
f(x) = f(uz, Ux)
Fu 11
A(e ux),
2
2
(55)
g(y) = by
2 |Bu1?
B Mya [0 ......... 1].
where (Mz, Uz); Un Rdd, f22 IR, and matrix F E Rdd-1)xd is defined as follows:
(56)
This problem instance has unique solution (x* 1²*
(u uh 3²) X V, which is given as follows:
arg min
Pz
|| 1| La
Ma
Fu,
A(e un),
1 D² 0.
(57)
ZEX
2
2
The rest of the proof is similar to the proofs of Lemmas G.2 and G.3.
19

---

On Linear Convergence in Smooth Convex-Concave Billnearly-Coupter Saddle-Point Optimization
I. Proof of Lemma G.2
consider the following "hard" instance of problem (1):
Linear spaces X' and y' are defined as X (Rd) and y (Rd where
3n
May
3n and
By
n (2,3,...))
(58)
3n
Man = 0
(ii) Function f(x) is defined as follows:
f(x) Σ f((x)),
(59)
where the notation (Z),.... Fan) E (Rd)an, and functions f((x;): R - R are defined as follows:
|/ + ( 8z) 1121 [ 1
i (l,...,7) mn i {n + 1.... 2n} i {2n + 1,..., ,n3
M(=)
(60)
1211 + [(Lx F2 A(e 2)
where A IR will be determined later, 8 is defined follows:
82 = Ma 4/ Ly
(61)
and matrices F1 E x224//2jxd and F2 E R2((d-1)/2]xd are defined as follows:
1
0
-1 0
F1
V2
(62)
0 1 -1
F2
1
0
0
0
1
-1
V2
(iii) Function g(y) is defined follows:
((v) = Σ (1()),
(63)
where we use the notation y = (y1..... :.n,)) E (RR')",, and functions (vr): Rd - IR are defined as follows:
1 Elllsall ==
Ly
May > O
(v(1))
where Ly
(64)
llllllll i n2....,
My May =
(iv) Matrix B E dd is defined follows:
E 2 La
Ray > 0
B
(65)
E' 60 La
Pay 0
20

---

On Linear Convergence in Smooth Convex-Concave Ceatinearl-Coopplee Saddle-Point Optimization
where matrix E E R is defined follows:
times
7t lines
B
Ok
7t-1 tines
E
(66)
OK
B
3
lines
-
3
and matrix E' E R (3nn1)))x) 1)x3n is defined as follows:
B
times
B
7- limes
E
(67)
0
8
times
3
8
where 0,8,7 O are defined follows:
Lay
Lay
2pzy
B
(68)
Vn
One can verify that the problem described above satisfies Assumptions 2.3 to 2.5. Indeed, each function go (=)) is obviously Ly -mosohh and -yy-olyyylyy convex, and each function f((z) Ls-sth and py-strongly convex due the fact that
o2 maxx (Fi) = max (F2) = 1, and Urr 82 < La. where the latter inequality is implied by Assumption 2.7 as follows:
8- =M Ms + 4/ Ly < Lx + Li = L..
(69)
Moreover, we establish the following Lemma I.1, which describes the spectral properties of matrix B. The proof available in Appendix I.1.2.
Lemma 1.1. Let E (2,3....) and a,, 3 > 0. Then > O. the singular values of matrix E defined in equation (66) can be bounded as follows:
ny²
8²
a²
min
min
E
max
EE) < max {2nr? 2 2(n
1)32 Ao2)
(70)
9n
and for ry = 0, the singular values of matrix E' defined in equation (67) can be bounded as follows:
12 a²
min
S (a tinn (E'))² < 2 (E') < max {2(n + 1) 4a2)
(71)
36
9m2
Using Lemma 1.1 and the definition of 01,3, 3,,,, in equation (68), we can show that matrix B satisfies Assumption 2.5 as long as n is defined as follows:
Lar
(72)
6/ly
21

---

On Linear Convergence in Smooth Convex-Concave Billncarly-Couptce Saddle-Point Optimization
Indeed, the definition of n in equation (72), the definitions of az B in equation (68), and Lemma 1.1 imply
Pry Myy S o
min
E
o
max
E
Lay
(73)
in the case May > O, and
Piz S (a (E')²
o max E'')
S
L
(74)
in the case May = O. Moreover, it is not hard to verify that range B T = X' in the case Pay > 0 and range B = y in both cases. Also note that n 2 3 due to Assumption 2.7.
Next, we establish the following Lemma 1.2, which describes the solution to the problem defined above, the proof available in Appendix I.1.1.
Lemma 1.2. For all d E 2.. the instance of problem (1) defined above has unique solution (z", (x".9") E X y Moreover, there exists a vector (x" 11) E (La,p)"= (Lo.p)" TM such that the following inequality holds:
Ro (x ,2) C2
(75)
where Cj > 0 is some constant that possibly depends on the parameters a II, but does not depend on d, La.g C IRd is linear space which is defined for p E (0, 1) as follows:
0
0
0.
Ca.p range
0 8²
(76)
1 0
p²
and p E (0, 1) satisfies the following inequality:
1
p max
1 89
(77)
Firy 346
Let (x9,89) = (xf, ..,,...,.............. ah. vi.... ... vh.) E X' x y be defined as follows:
(4 (. prolapan((e ( ((x", "y") = tn, & P) ,y",,
(78)
where P ddd is the orthogonal projection matrix onto the linear space span( C R2, which is given as follows:
P (e))
(79)
Then vector (x vP) from Lemma 1.2 satisfies the following relation:
p,, ..... + (Uz, vyy) & (0,0, ....., (ny @ (I. (x) v²) (uz, Uy) @ 1,,10,,p²
where Ug (Uz,1 Uz,n,) R=, Ux (V,,1, ... Ux,n,) R==
(80)
M (I..l..... My,my) ) E R"y,
Byy = (...,...., Ugmmy)) E RR"
Hence, we can obtain the following relation:
R² R2 (2 .00)
5z |x 21 + 6,118* - 112
5z [In,
@ (I. P))x" 1| + 5, @ (I. - P))
8x [Ing
@ (Ia Px) - - + +1 5 [In, @ (Ia - P)) yp + 2
25 (In,
s (L. P))(=- =2)11 + 25, (In, 2 (I. (r) )?)
s (I. P))x011 + 25, (I,, 8 ())y))) 11
< 26 2I, 8 (I, 91) 26, @ (I. P)) 112 + 2R (0
2(0 + ,, 1,,
2 2
[| 0, 1,0, .... .) 2R 6.o, (x",1)
22

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Coupled Saddle-Point Optimization
[d/2|-1
- =2 +
Σ
jim
L(d- 121-1//1-11
+ +2(6g|1uia1) + 6y11oy113)
Σ
p 4م
+ 2 (x y²)
1=0
2(5 112 + b |ll 12) /L/4/21)
1-p² pt
+ 2(6x11uz) + 8 11 (1 p1((d-1//21) + +2R (2 .8)
pd
2(0x]1(uer U2)11 + Syl uy)l1)) + 2R 1))),
1 1-p p² where (a) uses the definition of (z (0) in equation (78); (b) uses Young's inequality; (c) uses equation (80) and the properties of the Kronecker product.
Further, we fix k E (1....,d) d). using the sparse structure of the matrices F1, F2 and E defined in equations (62) and (66), respectively, and using the standard arguments (Nesterov, 2013; Ibrahim al., 2020; Zhang et al., 2022a; Scaman et al., 2017; 2018; Kovalev et al., 2024), we can show that the output vectors TT( = (T( = (T). ................................ Vo.3n No.3.. E Y satisfy the following implication:
Fo)a(()) E A' and
T TS D. Tan(k- - 1) + (T)(()))oo(T) (T) E span(tei....... .elee,........ e
(81)
ny where D > is universal constant. The right-hand side of this implication for all i E (1.....nnz) ) and j (1,...,nyll implies the following:
(8) 1 00ll x0012 + + (0yllvo(T) 1- 1112-R23-o 222,,(0",10
R2 (Fo(T),
2
R2
[d/2]-1
(5 uxll 1|2 + +.5gl 15y11uyy1 112)
2
1= b/22
(5x le 112 + +8yllupl1
[(d 1)/23-1 -1
+
Σ
0&3 - R2 R2 (I 7))
2
1= )=((k-1)/2 1)/2]
(6.1luml1 112 + 8yllun/1
(1 4///1 - 0 (l//21)
2(1
(6n || 1|2 + +.5y 11.y 11
(p 1)/21 (lld-11//11
R2 (2,,,((0,1 x²)
2(1 /²))
(8-1l
(+)) + 6g Sy 2/)l ())1l)) (1²²) - -220-1)
R2 R355, (x. ,19)
2(1 pt)
(p
22
R² b, (x", ,30 - -2R2
R2 (29))/)
4
-22--1
R2 Ba 8 (x. 000) - -(1+ (p2k - -22l-1)
R (2
4
2
(8) (م²
22d-1)
R7 8, (20 y0) -
(1+ (02k - (2d_1)
2 C C=p2
4
where (a) uses Young's inequality; (b) uses equation (81) and the expression for (x ) in equation (80); (c) uses the previously obtained upper bound on R2,,,, 5, (x", y²); (d) uses Lemma I.2.
Next, we establish the following Lemma I.3, the proof is available in Appendix I.1.9.
Lemma L.3, For all d E (2.3....), the unique solution to the instance of problem (1) defined above satisfies the following relation:
RI, (a0; (,4,," y0 ) Br.d
(82)
23

---

On Linear Convergence in Smooth Convex-Concave Ceatnnarrl-Couplle Saddle-Point Optimization
where Brdd O is a constant that possibly depends d E (2,3,-. and the parameters a E II, Moreover there exists
d E {2, 3........ such that the following inequality holds:
min
B > 0
(83)
de (d.d+
Using Lemma 1.3, for d 2 d, can further sownr-bound R3 (oo(T))o((7) as follows:
R (Io(T)) vo())) (p²k -220-1) Br Brdd (1 (1+ (p2* 12
C. C₂A2
(84)
2
Next, we can choose A = R/ / Ba to ensure Ro,
(20, = R² and obtain the following:
(p2t.
p2)4)
R² - (1+ (p2 - )
C₂ RRR2p p2d
Ri,0, ( (2)(T))
4
2 | (p2k -pp--pen -20-1)
Bud
(p2k
-p2d11
C₂ R2 p2d
R²a
min de Brdd
2k R2
where (a) uses Lemma I.3; (b) is implied by choosing large enough value of d. The rest of the proof uses the lower bound on in Lemma 1.2 and is almost identical to the final steps of the proof of Lemma G.3 in Appendix J.
I.1. Proofs of Auxiliary Lemmas
1.1.1. PROOF OF LEMMA I.2
In this proof, consider the case May 0, since the case May 0 is almost identical. Using the first-order optimality conditions (7) in problem (I), we obtain the following expression for the optimal dual variable y² E y::
L
1/29
y" Vg" BBx") + -y-
E
2 L
x,,
(85)
1/p2
where the optimal primal variable is the solution to the primal minimization problem equation (5):
x= arg min f(x) + +9 (Bz)..
(86)
=EX
Moreover, using the definition of functions f(x) and g(v) in equations (59) and (63) and the definition of matrix B in equation (65), we can rewrite this problem as follows:
g
82 | x2all 11
min Σ f1::))
1|
sntill
Σ
(an((r)
241
2/11
2n++1
(87)
22
2n
2n-1
a²
||
21
+
Σ
|1,11
+
| - 11
2
2
2phy
i=
imn+1
It is also not hard to verify that the following inequality holds:
Σ (((x)) +
- ||,,
32
n2,82
xn+1l1 2 nnf EI +
||
In+1
(88)
2j1
where equality is attained if and only if 21 = In. Consequently, the problem can be further reformulated as follows:
2n
2n-1
min nM bg (In+1) + nM Mn (I2n) +
Σ
+
|0+11 - -x:l??
(89)
xEX
2
2py
i=n+1
1
i=n+1
24

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Couple Saddle-Point Optimization
where functions (222),22(2) Rd
IR are defined follows:
82
Le
8g
h1(2)=
||=
|F
2
2
(90)
Lx
-
by
h2(2) 2
|
+
|F22|
A(e), 2),
2
and Mazan (2) and M Mazho (2) are the corresponding Moreau envelopes. Moreover, the solution x² satisfies the following relations:
2. -prox hy (#++1)
(91)
2n+1
Din = -prox B h2 (I2m)
Further, we perform the minimization in the variables 2n+2. 12 Using the first-order optimality conditions, we obtain the following relations:
bnjly a²
2 +
22 = ri-1 + J3+1 for iE (n 2,...., 2n - -)--
(92)
This is nothing else but a linear recurrence, which is not hard to solve. Let q > be the smallest root of the following characteristic polynomial:
dally a²
+
= q=1+d.
(93)
which is given as follows:
V4a² + 5atly - Voelt
q
(94)
V4a² dally + Vōslt
Then v **22.-..; .......,;33))....... ; can expressed as follows:
3 x+ (g" - gi + x2n x3 (q--1 - 91-1)
n+
(g--1 91 nn
(95)
Moreover, observe the following:
2n
8
a²
Σ
|
2
| - 1??12
2/4y
i=
2n
8y
2n 1
a
Σ
||
12
+
(1|=;11 + +|11//111 112
2(x
2
1=++1
1=++1
8
a
2n-1
8-
a²
2n a
(1
+1 12) 11²)+
+ Σ
+
|
My (x
24hy
i=n+2
2
My
i=+t1
8
a²
2
(1 11 +1122m111²)
(10 2 + (12m x2n-1))
2
2/h
2p
2n
a²
Bupty a
+
+
|| -4
(15 1441
+ xi-z)
2p
1=
8
a
a² 2p
(1 112 2 +11122111 112
(15741 2742) + (ogn zzn-1))
8x
d²
(b)
+
(1<i+111²
1| 11
2
2phy
25

---

On Linear Convergence in Smooth Convex-Concave Billncarly-Couplee Saddle-Point Optimization
a²
(112
-2--) 1|2 + | -0==2--22-1 + 2 122 9-1)
2p4
(9" g¹ gl-
8x
a²
1 (qn - qe-n + - 9 9-11
(1 11? + 1| 113)
24y
( n)
a²
(q
-1-
| z2n 1?
2
(qa
9l-n)
8n
a²
(1- 9) -m
(10 112 ||
2
(1 + 1m-
a
(1 (1 + 9)
| x22 1|?
2p
a(
- 1p-
8y wia
ana2 2ph
(11 + || (12)
|| xz2nll
2fly
where (a) uses equations (93) and (95); (b) uses equation (95), and Wns 1/ > are defined as follows:
(1 9) -
(1- (1 + ②) a(9 - -
Wn
Vn
(96)
(1 + 9=
In addition, we can observe that the following relation holds:
1 | x², min (11= ai+1l1?
xÿn 11?))
(97)
=ER
Therefore, the problem can be further reformulated follows:
8
ana²
Vnaa
min min Meg hi (1x+1) +
||
|on+1 - =112
=EX seRe
2n
2npty
nffl
(98)
8n
wna²
Vn
+ May #8 b2 (122)
+
+
||020||
+
|2:2n - =1(2
2n
21/
Let functions hf (z), hi (z): Rdd + be defined as follows:
6z ana²
(=) = M gg (,) (z)
+
+
12112 j= 1=1,2
(99)
2n
2n1ty
and let functions h+t (2), h2 1 (2): Idd + IR be defined as follows:
(2)
(2) M may ht (2), 1,2. 2
(100)
Then the latter problem reformulation can be rewritten as follows:
arg min h (2) (())+1 h (2),
(101)
SERd
and the solution x² e X satisfies the following relation:
prox Bw,
at (2*),
z3 = prox may A (z*).
(102)
Next, we establish the following Lemma 1.4, which is used to obtain the explicit expressions for the Moreau envelopes. The proof available in Appendix 1.1.3.
26

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Copple Saddle-Point Optimization
Lemma 1.4. Let function l(z): IRd IR be defined as follows:
h(z) = - ||2||
F2 1F2
--H
(b, 2)2
(103)
2
where L > p=>000 O, and F E Rexd and b E IRd satisfy the following assumptions:
FF Ip. Fb
(104)
Then for À > O, the Moreau envelope (x) is given follows:
Mx)(2)
MA
||
LA 1A-AA pA F2 Bx(b, 2) Cx.
(105)
2
where constants L, > yx > 0 and Bx, Cx E R. are defined as follows:
|||6112
LA = 1A+1/D) === (A+1///))) BA = (1+ C2
(106)
2(1 + Au)
Using Lemma and definition of functions h1 (=), in equation (90), we can express functions h (z), 15 (z) as follows:
1x+ (2)
L+ -p
||
|1 + const,
2
(107)
hラ (z) = +
L+ - 1
||
+
F2 A+ (ef 2) + const,
2
2
and functions (=), (=) can be expressed as follows:
(2) +
|| I++ +++
F1 const,
2
(108)
1++ (2) = 2
|| I++ /
++
F22||2 ++ (0) 2) + const,
2
where constants L > a+ are defined as follows:
L+ =
Hy 3²
+
8_
wn
1² =
(1
1
+
Hy
-1
+
3
+
w
(109)
L
n4y
0r
8²
nP
constants L++ p ++++ > O are defined as follows:
L++
1F
2
nfy
++
1+
1
+
nfy 2v,
-1
(110)
and constants A+, A++ defined follows:
BA A+
2v, a 2+ 2v, npy
A
(111)
32 + 0n
Next, we establish the following Lemma 1.5, the proof is available in Appendix I.1.4. Lemma I.5. Let = (2,,..., 2d) (.,...,,,) E RRdd be defined as follows:
L - F2 B(ef,2)
arg min
2||2|12
(112)
=ERd
2
where L 4 >> 0, and matrix E (dd-1)xd 1)xd is defined as follows:
1
F
(113)
22
27

---

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupeed Saddle-Point Optimization
Then there exists z" E Esaan P,... (p...(()......,0--111)) (b-1))) such that the following inequality holds:
Bp
11 - -211 2μ
(114)
where p E 1) is defined as follows:
VL. V/
P VL + V/
(115)
From Lemma 1.5, the definition of z" in equation (101), and the definition of functions hy(=), 11 (=), and h (2) in equations (90), (107) and (108), it follows that there exists 2 (( p2-1)) such that the following inequality holds:
A++ pr
|| -=-1= 5
(116)
241
where p E 10 defined as follows:
VL+ 1++
P VL+
(117)
Finally, we obtain the desired statement of Lemma I,2 with the help of the following Lemma I.6. The proof is available in Appendix 1.1.8.
Lemma 1.6. Let vector (x", )²)
o., Vi. . vi. X V be defined as follows:
of = =porcaaa..0 (x/), vi projca. (1h))
(118)
where vector (x',3)) (#1...., Nn 1/1 ......,,n) E X is defined as follows:
proxey (#'+1) 32
i {I,...,
prox nng
1o (29) 2on0
i = m +1
#/ 11- o² (4"
2n
4 (1
(n 1) (1 ()
i {n + ......, 2n 1}
- ()
(119)
prox may by
(29)
i 2n
prox Hy b2 (1/2n)
i E (2n + 1, ,,...,3n)
y' = Vg (Br').
Then the following inequality holds:
Ri_ (I. (1)))))) Cx C2APp2
(120)
where Cr > 0 is some constant that possibly depends on the parameters a E
remains to lower-bound p. done with the help of the following Lemmas 1.7, 1.8 and 1.9, the proofs are available in Appendices 1.1.5, I.1.6 and I.1.7, respectively.
Lemma 1.7, Under assumption patty pla the following ineqality holds:
2.
(121)
Lemma 1.8. The following inequalities hold:
Wn < (n 2 2)0mt1 Myy
a 1
(122)
Vn 4(n
1)
Lemma 1.9. Constants L and p+ defined in equation (110) satisfy the following inequality:
L
1
1
> 1 1 max
(123)
1++
86
55
5
28

---

On Linear Convergence in Smooth Convex-Concave Sellinearly-Cupplel Saddle-Point Optimization
Using Lemma 1.9, lower-bound p follows:
+1
alT
6g
V87-
86
max
220
M
V87 +
86
by
1
2200
max
My
346
v 220
Ley
max
V /Ra
Myx
346
IM
max
- 89
71
1
Veay
346
where (a) uses the definition of p in equation (117); (b) uses Lemma 199; (c) uses the definition of Kay in equation (6); (d) uses the definition of n in equation (72), which concludes the proof.
1.1.2 PROOF OF LEMMA L.1
Let matrices W, W Rixi be defined for i f1...., 1} as follows:
W =
W =
(124)
-1
2 -1
-1
2
-1 2
Then using the definition of matrix in equation (66), can write the matrix EET as the following block matrix:
n
Bry
By
By
03
(I, + JJ)
By
a.3
EE
(125)
a² @
033 n times
.0,
o.3
dg soung i
8L, Jn)
Furthermore, let matrices Q Q e ((++))x(*++) be defined for E {1...., n2 as follows:
a a
wW!
033 times
.0
0g3 n times
.0
Q
a
Q
a8
(126)
8² (I, + JJ)
88 (I, Jw)
It is not hard to verify that the following matrix inequality holds:
On-1
Q² 2 82
(127)
I
29

---

On Linear Convergence in Smooth Convex-Concave Bilinearly- Saddle-Point Optimization
Moreover, show that for i (I,...,n).
n). matrices Q5s Q satisfy the following inequalities:
a + 1)
Q
(c (c)+))
nt +
(128)
a²
Q
n n+ (c n+ (c]+it
Indeed, let prove equation (128) by induction. The base case 1 is trivial:
a²
a
.............. a,3
a3
a²
Qi
(e (ef
(129)
(In + Jn)
n
a3
Furthermore, for an arbitrary index i (,...., ni 1}. we can show that
Q
a
0
................................
a²2
a
0
2
a
a (m-ti)
Q
0
Qi-1
which is nothing else bu the induction hypothesis (128) for the index i, and where (a) uses the induction hypothesis (128)
for the index 1; (b) uses Young's 's inequality. Next, we can obtain the following inequality for the matrix EE T
ny²
By..... .......... By
ny²
By ................................
By
Bry
Br
03
(I, + Jn)
(n++1) J. n
DD
By
0
By
0,3
-0.3
033
-aB.
033
Qh-1
Qn-1
-08
J
O
Q
-0
Q n-
(e
2n+
n1
This implies the following inequality for the matrix EE
2(n + 2)
2(n a²
EE
DE
Jn
3n(n
1)
3n
1)
n +
1=1
Oat1
2a²
3n(n 1)
O
30

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Couplel Saddle-Point Optimization
where (a) uses the facdt that Σ/=1 for the matrix EET;
2(x+4)
Furthermore, using equation (127), we can obtain the following inequality
3m(n
0 2n
EE
O
82
I
Next, we can obtain the following inequality for the matrix EE
n7?
B7
By
8y
-a
(I, + Jn))
EE
By
0.3
08
-0
Qn-1
ny?
B7
By
B7
038
(I,, + Jn)
IY
B-
023
0x3
0B
2no
2n-1
2n 2
0
IY
B + 88 (1
1
2n-1 2n
Jn
2n
8
82 J
0
0
IY
In
2
0
O 2n-22
where (a) uses equation (128); (b) uses Young's inequality; (c) uses the fact that J, I nI,, Furthermore, we can obtain the following inequality for the matrix T
ny²
By
By
By
a,
[L, + Jn)
EE
By
033
-a3
2na
2n
2n-2
31

---

On Lincar Convergence in Smooth Convex-Concave Billncarly-Couplee Saddle-Point Optimization
ny²
37
By
By
g p(++1) J
IY
n
By
00,3
- a..
2no
2n
2
By....... ................................ By
By
IY@
3.9
2n
Br
O 2n
ny²
O
3
O 2n-2
where (a) uses the ineqality obtained above; (b) uses the fact that J, wlm; (c) and (d) use Young's 's ineqality. Now, we sum all the inequalities for the matrix EE obtained above with positive coefficients 0,, f2. 0g. 04 and obtain the following:
01
02
8 In
EE
(130)
Og
2a² 3n
1n-1
O₂ B
Choosing 01 = 3, 7. 02
18. 0g = 1. and 01
1.
36 implies the following:
ny 2
a²
EE
min
Isn.
(131)
4
36
9n²
Finally, we obtain the following inequality for the matrix EET:
2ny²
3 + (2
Jn
3a2
-a²
a2
2a²
-a²
2
2a
22
2
3a
B82 (I, 2Jn))
2n²² 2
2(n + I)
I
(2n + 11.22,
2nn + max 2 2,2n2
1) 4o Isn-
where (a) uses the expression for the matrix EE and Young's inequality; (b) uses Young's inequality, which concludes the proof the case 7 0. The remaining case 7 = is trivial extension of the case 7 > 0.
32

---

On Linear Convergence in Smooth Convex-Concave Cittincarl--Copllee Saddle-Point Optimization
1.1.3. PROOF OF LEMMA I.4
Using the definition of the Moreau envelope, we get
Mar arg min z'ERd
1 2X
|1 -1'==11"
M 12211 =112 2
L- / |F2111 (b, 2/)-
(132)
2
Using the first-order optimality conditions, we get
1 オ b + (0=
18 + (I-- (1) z'
(133)
Hence, we obtain the following:
MA
(a)
2
2|1 +
11
2
1122112 +
- μ || (b,
2X
2
1
||
2
||
- 2 + b)
2X
h
1
||21|
]
1
1 bl2
2A
2
1
|
2 x b1b
21
(1+n) '1, -12-((+1)) F Tp (=+p1++(++1)) 'FFT) 'F
| 2
| 2 + b12
2A
2
(*+*) " (++ PFT FT (+od
|
112
2X
2 X
ITAP Is x3(6-n) FTF
1
1
|=
UI
2X
MA
||
I,
F2|12 2 (2, ((1 -pxata A(Lx
2
2
|b
2
12 X2 FF)F
MA
||
LA MA
F2|1 1xx
A(1 - \pa) |1b1|2
2
2
2
8 MA 1=1
LA - pI F2 2b(bb22) - Cx,
2
2
where (a) uses the definition of the Moreau envelope; (b) uses the expression for 2': (c) uses the Woodbury matrix
identity; (d) uses the assumption FFT Ip; (e) uses the definitions of Lλ and μxù (f) uses the assumption F Fb O; (g) uses the definitions of B, and Cx. which concludes the proof.
1.1.4. PROOF OF LEMMA I.5
One can verify that vector satisfies the following linear system:
(2ula + (L =TFFFFF F) Bey
(134)
which can be rewritten as follows:
(L + 3p) - -(L - 11)
[
2B
- [I. - 11) 2(I + pb)
-(T - p1)
(135)
(I. 1)) 2(I + 11)
-(I - 1d)
-(L [ 41)
(L + 3p)
Let d Rdd be defined as follows:
2B
20
(0,p² p9
(136)
(1 p) - 1))
33

---

On Linear Convergence in Smooth Convex-Concave Sellinerll-Couuple Saddle-Point Optimization Then observe that
(2pl2 + (L - 1D Bei -Bppe
(137)
which implies
(2ula + (L (DF-FFFFF) F) (2 - = -Bp²ey
(138)
Hence, we obtain the following inequality:
1|20 - 2|| Bp
(139)
2/
which concludes the proof.
1.1.5. PROOF OF LEMMA 1.7
We can upper-bound n as follows:
1+ 1 1-9
exp
nlg
IVE
n(1 - 9)
exp
q
IA exp
Lag
- 9
614y
Lay
2v dap
exp
6/Hyx
44a² + 8alty Volly
2V Woollll V40² + datty + v Vollt))
Luy
exp
6/ta
4a²
AV82My(a (osHt)
(d)
Lay
cxp
6/ty
4a²
V Matty + 441
Pu (a + / Holly 4p2 Ux
Lay
by
Loy
exp
6/byx
a²
(a + Pyo / 1 4122 Auly Hyo / 1+ by
Lay.
In
I/ exp
6ptz
a²
Lay.
Myp v2(a aa + Hyyer v2)
exp
6pty
a²
V2
2 2
5 exp
+
Towy
V2
2
WV
exp
+
27
2
where (a) uses the concavity of the logarithm; (b) uses the definition of n in equation (72); (c) uses the definition of in equation (94); (d) uses the ineqality va+b I vā + vb for a, b > 0: (c) uses the definition of ó in equa- tion (61); (f) uses the assumption Maly S 112g and the assumption Лyz > 0, which, together with Assumption 2.5, implies Pzy & Myzi (g) and (i) use Assumption 2.7; (h) uses the definition of a equation (68), which concludes the proof.
34

---

On Linear Convergence in Smooth Convex-Concave Sitiinecrl--Coupeed Saddle-Point Optimization
1.1.6, PROOF OF LEMMA I.8
We can upper-bound wn follows:
( - (g)(1 2m1
Wn
(1 + 9m
(b)
n 3
5 (1 -q)(1 - -q" (1 9)²
q
j=0
(n 2)(1 -9)²
4(n 2)0
(
(V40² 4a2 + 6ally + (o11n) 2
(n 2)
where (a) uses the definition of wi in equation (96): (b) uses the fact that q 2 0: (c) uses the fact that q S 1; (d) uses the definition of q in equation (94). Next, can upper-bound Un follows:
( q(a 2² Vn (1- (1 +
2n
(
S 2(n 111
S 4(n - 1).
where (a) uses the definition of in equation (96); (b) uses the fact that 0 S q S (c) uses Lemma 1.7, which concludes the proof.
1.1.7. PROOF OF LEMMA 1.9
First, we can lower-bound
L+ PT as follows:
L
(a) 8 + Lusty
8 Le
82
+ ana
A1TTrr - -3a)
=1
88
+
una?
320 + (32 + 8rpter
6n + map
wn
)) (82 + LaHty)
nily
Brr
+
888 + (B2 + Botty)
@ Be 1 w.a2) +w02)) )) (B2 Laaky)
+
28
62 + (n-1) (.22 + )otty)) ) (B2 + Listt)
3 Lzx
20
B2 +
(n-1) 32 Mxfy pLyy byy )) (32 + Lx
41t22
1
LaLz
1
28
62 + (n-1) B2 + Mlyz (1 + 4/1e) (++44h
(52 + Lotty)
+
28
B2 (n-1) (B2 + 2p2z)))
(B2 + Lafty)
g L.
+
25 ( (n-1)
1 +
2n2
n² L +
Lz
Lx
1 +
2 11 + (n-1) (1 Hb) (1
Latty
n
36
Lu Py + 8z (1
+ 36 Iiett)
2 21 +
37
370 (uăz + 1/2 bolt))
8, (p + 36 Lzlty)
35

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Coupled Saddle-Point Optimization
where (a) uses the definition of L+ and xt in equation (109); (b) uses equation (69); (c) uses Lemma I.8; (d) uses the definition of 62 in equation (61); (e) uses the assumption Ma/ly S Uge and the assumption Myx > which, together with
Assumption 2.5, implies May S Myni (l) uses Assumption 2.7; (g) uses the definition of /3 in equation (68); (h) uses the
definition of n in equation (72). Furthermore, we can lower-bound
L je as follows:
1+
9 yz
21+
=1
1et
370
(p + 30
LL(
37
+
1 5o1ly
L
36
IV8
9p
1
37
2 +
Mully
+
44y
36
IV3
9p2z
1
37
+
36 Myn
1
1
4Mx
Ly
IV@
9p
81
1+
1
37
2
2
+ (p
185
10
IV
where (a) uses equation (69) and the definition of 8, in equation (61); (b) uses the assumption Malty S 1 and the assumption Pyz 0, which, together with Assumption 2.5, implies May S Pywi (c) uses Assumption 2.7. Next, we can lower-bound ++ +++ as follows:
20 2T
(L+ - 1²) (1+
2 t.
20 -nyynt
1t
L 202
(6 IV
3L
10p=
apy (1+
20
3L+
10μtt
(1+
2n(n 2n(n-119,
Du, It
3L+
10μ
(1+
IV
3L*
3 yz
+
10pct
(1
1,t
10
4=
22z
+ Buy
T,
3p
1
10
+ 11 x + 221
828,
+
8z Wa
3p
1 +
10
ET 212
+ 2 (n+1)6e
wky
3/22 yir
3 yz
1
21
122
+ 2 M
(n+1)6
+ (n-2)62
10
#t 22 + S2083e)
n
n
2 yz
1+
8m (ng,- 2 2 L.My)
10
37 Toe 11 R- (1 11))
3/122
27 ym
2 11
2 1
10
378, (n². + Je (ullty)
4
3705,,
(My +
13 L
36

---

On Linear Convergence in Smooth Convex-Concave Citinnearl-Couuplee Saddle-Point Optimization
27
() 27 2
2 1
370628,
1480625y
21+
55
where (a) uses the definition of L++ and ,=* in equation (110); (b) uses the previously obtained inequality yt TŪ L (c) and (g) use Lemma L8; (d) uses the definition of in equation (68); (c) uses the definition of n in equa- L tion (72); (f) uses the definition of μ in equation (109); (h) uses the previously obtained lower bound on RT: (i) uses the definition of by in equation (4); (i) uses the definition of 8 in equation (61) and the definition of dz in equation (4).
Furthermore, we can lower-bound F as follows:
+++
P'g
u++
6g
55
HzHy + Iy M +
L, p +
1 u
L buy
(
16
1
1 +
2
1
+
55
Hu +
Hay L.g
25
55
86'
Lny
where (a) uses the definitions of 6- and 6y in equation (4): (b) uses the assumption Mally M2y and the assumption Myz 0,
which, together with Assumption 2.5, implies May I Myzi (c) uses Assumption 2.7, which concludes the proof.
1.1.8. PROOF OF LEMMA I.6
First, we can upper-bound || - x='l as follows:
|
1| (a)
prox my (1'++1) prox
23 (1)+
+ ||prxx 2rn 17 (2-)
prox
nay 20
11 (2²)
2n-1
(#'n+1 2 (gg2)
2m) + (2/2 x22) (g (m+1) (((nt))1)) 2
(g- - -1
1mn+2
+ ||prox an
Mi (2 - prox nay
Agt (2")1?
20
3n
+
||prox me hi (I/2m) ---ppoxxu nit (1
1
(b)
< T2/12441
In 1 + =1/1 11
2n-1
(#/ 2 (2 -g--2)
(2bg x22)(g (n+-1) (((+1)-1)
Σ
+
(9D-1 -l-
kmn-22
+ 1| 212 + +11la - 12
21
1 + n2 (11 x 112 + 11-ien xm
2R-1
2n 9i-209 20
+2
|:/2411 21 1|2
(0 9 n2
i=++2
2n 11
(m+11)
9 (n+1)-
+2 2
| 222nn1
(0- 1n
i=++2
2 2 Σ
(9) - -)2
2|12
2=
(1 - +att 112 + 11 I2ā 112)
(g - /1=
(
2||2 - 201
37

---

On Linear Convergence in Smooth Convex-Concave Bilinearly-Couplie Saddle-Point Optimization
(g' - 1/ -
+
n. + 2
aan nnj (2") - -prxx Juv I|prox
A1 (2*)l²
(q- - 9 ql-n)
2
==1
(g' 19
+ 2
(q- g²
I|prxx nil hig (2") 20n
proxx
20, hg (2*)11
nuy
(e)
n-2
(q' -9-1)2
2 + 2n +
(g q(-n
n-2
(q¹ - 9 9-
(At pa 2 2
IN
2 + 2n +
(q--1
101 pM
where (a) uses the expressions for x in equations (91), (95) and (102) and the definition of x' in equation (119); (b) and (e) use the nonexpansiveness of the proximal operator; (c) uses Young's 's inequality; (d) uses the definitions of x and 2²n in equation (102) and the definitions of 2'x+1 and zin, in equation (119); (f) uses equation (116); (g) uses the definition of A ++ in equation (11 I), and C² 2 0 is a constant that depends on the parameters æ E II.
Next, we can upper- bound Re,,, (x',1)) as follows:
R3 (xl, v/)
(0)
5z ||' x01 12 + dylls' - 112
5m ||
x² + 8yl V (Bx(') -
by BB x²
8g 82112' xx' +
(8)
6y L
x 5z 1/
x 113 +
|| - x x²113
ng
(0)
6 12
C² C²A2P' pdd
C" A2
where (a) uses the definition of &, in equation (9); (b) uses the definition of y in equation (119) and the expression for y² in equation (85); (c) uses the (1/ (, -smoothnesss of function g (y): (d) uses Assumption 2.5; (e) uses the previously obtained upper bound on || - x² 2 and C# 2 0 is constant that depends on the parameters π E II.
Furthermore, we can express I'nn as follows:
22
prox apy 2
hoj (z")
(b)
npy Vhg 71++(22 (29)
2v,
Ia Miyy
(1+
( Ia (I++ - 1 -1+t (utt)//FF.. F22)
22 + At
2
1lyl ++
Tup (L+ -utt)
F. F22" + Attee
20,
20,
2
(11
np (L+
(
La
F.J FT F2 (p.....p')
(L+ -1++)
2u,aa
20,
+ +
A(C Ad + 20" x.2n F. F2) (e)..,,, + AO! 7,
AC of + AC 2m (p................... ,c)
+ AC 2m (0, - p), (p (11
-p- 1),...)
38

---

On Linear Convergence in Smooth Convex-Concave Billncarly-Couplee Saddle-Point Optimization
AlCm.2n (1,,,n) 0,.,..) + A(pp
(0.10))) + A(p + p²(p
where (a) uses the definition of x' equation (119); (b) uses the properties of the proximal operator and the definition of h (z) in equation (100); (c) uses the definition of hzt(() in equation (108); (d) uses the adapted version of the definition of 2" in equation (136); (c) uses the definition of + in equation (11 1); (f) uses the definition matrix F2 in equation (62),
and C²22 *m R are constants that depend on the parameters и E II. From this expression, we can conclude that the
following inequality holds:
| x2n S A Cx
(140)
where C, 2 O is some constant that depends on the parameters π E II. Similarly, we can obtain the following inequality:
6z11=' 20 + 5ylle' 10 < A² A?
(141)
where C 2 is some constant that depends on the parameters E II. Therefore, we obtain the following inequality:
R2 v²)'v) 2R (x',8') 26,lll'' 2012 + 20, 1
s 2( + A2p
C. P2
which concludes the proof.
1.1.9. PROOF OF LEMMA I.3
Functions ((x) and g(y) defined in equations (59) and (63) are quadratic. Hence, the optimality conditions (7) can be written the following form:
G + +B yf = Ab
(142)
Gyy Br* =0, 0,
where (0gn. 1n) ef Rndd, and G2 dd and Gy E Raydxndd are symmetric matrices that be expressed from d E (1,2.... and the parameters и E IT using the definitions of functions fx) and g(v) in equations (59) and (63). Hence, the solution (x",y") can be expressed as follows:
x² = A A-QQ-1
(143)
y" A BQ-1
where Q₂ RRnddxnad defined as follows:
Q = G + T G
(144)
Note that matrix G +B G, B is invertible due to Assumptions 2.3, 2.4, 2.5 and 2.6:
G B G = 5 d O
(145)
Furthermore, using the definition of (x. ) in equation (78), we obtain the following:
(x" 0 yy 9²) (In.-n) ny (La P1)(2" 8²)
= (In--ny [Ia P)) G,,,,,
Hence, it is easy to observe that R3,, 5, (x 10,))== = A for some constant Br,a 2 that depends on d E (2, and the parameters E II. Finally, need to show the existence of d (2,3.... such that for all A >> 0 the following inequality holds:
R2
R (,0,8%)
min Bad = min dd(d,dt1....
0.
(146)
de(d,4+1....
12
39

---

On Linear Convergence in Smooth Convex-Concave Billncarly-Couplee Saddle-Point Optimization
To do this, lower-bound R (1") y²) follows:
R3 R5, (x v0) 2 6x (1l [1 Fn+1 112 1| x22 11²)
(
6g (II - P) 112 I1(Ta P) 13)
56.1l(La (1 + x2n)1?
1
1 (Ia (prox z0azhh bi (2*) + prox -n mn (2'))
] P2
aNl
(Vh) (2*) + Vh (2 )))
20
1 28 (Ia 1|2
6 [T. 1)=011
25 P)(=" =
[A+ pa
2) 28
2u++
(0)
2A++ D2
'A++p"
8
26
(L
1++)
2p+++
28
8xp pxp
(A++)2
(L++)²
22
6 A²
a
20
8up2d
(2V + npy (B2 + (1
(I+++22 2(ut+)²²
where (a) uses the definition of 20 in equation (78); (b) uses the convexity of 11.112: (c) uses the expressions for 2 and æin. in equation (102); (d) uses the properties of the proximal operator and the definition of h3 1x:+(2) (z) in equation (100); (e) uses the definition of 2" in equation (101); (f) uses Young's s inequality; (g) uses equation (116); (h) uses the adapted version of the definition of = in equation (136) in the proof of Lemma 1.5 in Appendix 1.1.4; (i) uses the definition of A++ in equation (111). It is not hard to verify that
oz
26.0" and
(L (L positive constants that do not
(2 + ((89+166.)
depend on d. Hence, we can easily obtain the following relation:
R3
(2 .3
lim inf
> 0,
(147)
d d
A2
which concludes the proof.
40

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Cupple Saddle-Point Optimization
J. Proof of Lemma G.3
Let May = max (Jay Pyn We consider a special instance of problem (I), where = = IR functions f(æ) and g(v) are defined as follows:
f(æ) = Mz | A(ei, 2), g(y) P4 |1yl1 2
(148)
2
and matrix Rdxd is defined as follows:
B where a Lay + Pays 8 = Lay - Pay-
(149)
2
a
Functions (x) and g(v) obviously satisfy Assumptions 2.3 and 2.4. Moreover, matrix B satisfies Assumption 2.5 due the following Lemma J.1, the proof is available in Appendix J.1.1. Lemma J.1. The singular values of matrix B defined in equation (149) satisfy the following inequalities:
Pry Omin (B) S m'ax (B)-
Tany-
(150)
Next, we establish the following Lemma J.2, which deseribes the solution to the problem defined above, the proof is available in Appendix J.1.2.
Lemma J.2. For all d E (2.3.... .). the instance of problem (1) defined above has unique solution (x",y") E X V
Moreover, there exist vectors x² , E pp.nn(().p.......) 10 such that the following inequality holds:
R3, (x v pd
(151)
where CR > O is some constant that possibly depends on the parameters π E 11, but does not depend on d, and p E (0, 1) satisfies the following inequality:
max
(152)
Key
In addition, the initial distance to the solution R² 5,5, (0, 0) is quadratic function of A. that is,
R²_ (0.0) = BT,dd
(153)
where Br,d > is constant that possibly depends on d 21. and the parameters x E II, and satisfies the inequality (1...., Bidd > 0.
We can express (x ()) from Lemma J.2 as follows:
xº = uzz(1, (1, P. (1,
d-1), = 1 where Uz My E R,
(154)
which implies
1 - (1 22
u
2d
||
(155)
0²
Further, fix (O....,d) d). Using the sparse structure of matrix B defined in equation (149), and using the standard arguments (Nesterov, 2013; Ibrahim et al., 2020; Zhang et al., 2022a; Scaman al., 2017; 2018; Kovalev et al., 2024), can show that the output vector (co(T).v.(T) E X x y satisfies the following implication:
span(fee....... e k 0
T S D TBk
Io(T), ())
(156)
{0)
k= 0
where a universal constant. The right-hand side of this implication implies the following:
R2,0, (xo ()()) 8 (0) x²1 + 5 (T) 111

---

On Lincar Convergence in Smooth Convex-Concave Billnearly-Couplee Saddle-Point Optimization
[o))) - 20112= + (oyllsa - - R2 (x",3))
d-1
[6 2 + +bgul)
Σ
R2 R,,0 (x)
j=k
12h
pdd
(6 + k5
R R2200 (x", .20)
1
p²
82h
p2d
5(6 11 + 5y (13)
R Ro,, 8, (x ,y4)
p2d
2 (+R3 b, (0, 3 (3. ,30²)
p²h p2d
R2 (x),,(()
1 p2d
2h p2d
R3 R5 (0,0) (1+
1 p²d
R2 R2,0, (x),9²)
4(1 p2a)
2(1 p2d)
2² ad
Bn Bn,dA? -(1 1+
2h 2d
Cx-AP p2
4(1 p2d)
2(1 2(1 - p2d)
where (a) and (c) use Young's inequality; (b) uses equation (156) and the expression for (x ) in equation (154); (d) uses Bidd to ensure the initial distance R2 5,
Lemma J.2. Furthermore, we can choose A R/ BBrd following:
(0, 0) It3 and obtain the
1 1d
1 12h -p2d
R2 (oo(T),)(()) = 4(1 Pd
B A2
2(1 - p2d)
2k pd
1 + p2h pdd
C CRR p2d
R²
4(1 2
2(1 p2d)
Bad
26 pdd
12h p²d
C²R²pa pd
R²
4(1 p2d)
2(1 p2d)
e B
1 - (2
1 + 12 - -2dd
(xp
2 R²
4(1 p2d)
2(1 p2d)
m Bx,dd
1 2R22RR² R²
where (a) uses the choice of A above; (b) uses the inequalities Bi.dd 2 min Br,d/ > 0 implied by Lemma J.2; (c) is implied by choosing a large enough value of E (1,
Next, we consider the case S It? Choosing kt as follows:
k: log (5 R /c)
(157)
log (1/p)
implies R2,0,, (Ho(T)))o(7)) 2 c. Therefore, by contraposition, from implication (156), obtain the following:
R3 (0,0) <e T> D T.kk
(158)
The night-hand side of this implication implies the following lower bound on the execution time 7:
D TBk
log (1 R2//
D
2 2og (1/p)
log ( R2 (2//c) 2 log (1/p)
2 D. TB
2 (1/p) log Rt/ /R2 - 2 log (5/4)
D TB
2 log (1/p)
42

---

On Lincar Convergence in Smooth Convex-Concave Cilincarly-Coupled Saddle-Point Optimization
D
log
[G /e)
125
B
log (1/p)
log (116 R2/e)
TB
2
(1/p
1)
D
TBP
log
16R 125c
P
5v2
D
TB y Kazy
log
16R
125c
Ω TB / Key log
16R 125c
where (a) uses the definition of in equation (157); (b) and (d) use Lemma J.2; (c) uses the concavity of the logarithm,
which concludes the proof in the case S 5 _8 In the remaining case 1R2, we have log lower bound holds due to the fact that 2 O, which concludes the proof.
16R
Hence, the latter
125c
J.1. Proofs of Auxiliary Lemmas
J.1.1. PROOF OF LEMMA J.1
We can write matrix B B as follows:
a²
-a3
a.
2 +
-3
B
4
0
a² +
-a3
-ag
a² + 82
aB
03
Taaa - 33
-03
20
-0
(a-
+
2003
00
(a 13)2
033
2aB3
Therefore, we can obtain the following matrix inequalities:
B z min((a - TT
(159)
B B B = max ((a- 3)2 44 -3) + 2a Ia = I La.
which conclude the proof.
J.1.2. PROOF OF LEMMA J.2
The first-order optimality conditions (7) imply that the unique solution the problem (x*,0") X x )/ is defined by the following linear system:
(Matyla + B B)x² Ae
(160)
Pny Bx =0
Hence, we can express the initial distance R3 R3 (0,0) follows:
R3 (0, 0) = 8z || + 6, 11y
8z | 11 la + +B TB) B)B -1 La + (J BB
A Br.ds
where (a) uses the linear system (160) and the fact that the matrix (Lulllaa + B B) invertible, which is implied by the matrix inequality (PzPyIa B BB) Z (Mally P La and Assumption 2.6, and where B is defined as follows:
Brd 51103 BJB effl - 5, B( BBBB BB)
(161)
43

---

On Linear Convergence in Smooth Convex-Concave Billncarly-Couplcc Saddle-Point Optimization
We also lower-bound Badd . as follows:
B = (1a + B B) +
| B / + B B "B
@ dapl + 0 Fy (b)
>
(Nally 12 )2
where (a) uses Lemma J.1 and the fact that |ei| | 1; (b) uses Assumption 2.6 and the assumption My >> 0. Therefore, obtain the desired inequality minde(1.2...) Bx,dd 0.
Furthermore, the first equation in equation (160) can be written as follows:
(72 2 8
a
-1 1
4pp A
x²
d ag Ci;
(162)
-1
7
1
-1
722
where 72 is defined as follows:
2 + 18 + 4paly
2(g 2(9 +1
72
(163)
a3
(1 -
where > is defined as follows:
12 + Pall
q
(164)
Pry Pzfl
where the denominator is always positive due to Assumption 2.6. Let (x", 1/) E X' y be defined as follows:
A
2A
x
( (..,,...,,)), y
B (..p".....pp
(165)
Bla - 3p)
where p 1) is defined as follows:
1
p / +1
(166)
One can verify that (a", y) satisfies the following linear system:
(a + B B)x² Ay + ap
Myg Br = 2ptt1 Bp My Ae
(167)
- 3p Ay
which, together with equation (160), implies
ap
(HotyLaa +B Bx BB -x"= a - 3p My Ae
(168)
2p
B(x Myly -²)
x²) -Bx
a - 3p MyAA
Hence, we can upper-bound -| x²1 as follows:
||000 x"1 Cxpy Ap
-
3p
Ofly Ap
(Nufll + 12 -pp)
44

---

On Lincar Convergence in Smooth Convex-Concave Billncarly-Couplce Saddle-Point Optimization
where (a) uses the linear system (160) and the fact that the matrix (Ui + B B is invertible, which is implied by the matrix inequality (dz/ly B B) = (Hullf Bay L and Assumption 2.6; (b) uses the fact that Ha La B B =
(uaty + Pey La and ||e|| = Furthermore, we can upper-bound ||y² =2' as follows:
2p
11y2
v-1
(
B(x
-2')
3p My MyAc
14y
IA3
2Ap
[B xx']l a 3p |108|
B4
Luy ||00 - 1=11 2Ap
Myy
Bp
AlTayAph
2Ap
(Wally + Play -3p) --3p -p
aLooy
Aput1
+
Malty
Pay
a 3p"
where (a) uses the linear system above; (b) uses the triangle inequality; (c) uses the fact that ||]]| S Lay and ||e (d) uses the previously obtained upper bound on ||20 x²1l Combining the upper bounds on | x*1 and I1y y"1 gives the desired inequality:
R5 (x',)²) 8z f11 x11 + + - -2-12 A2
(169)
remains lower-bound p as follows:
2
2
(c)
2
p
/ +Q+1
1/ +Me
182 max (R2 max
Malyy H
+
Pay Hu
Pay PPP
2
2
4
2
21
(182 max (px,
Pay taPPy
+ +1+1
188 (189-1) 1)
2
11+1
5
where (a) uses the definition of p in equation (166); (b) uses the definition of q equation (164); (c) uses Assumption 2.7. In addition, we can lower-bound p as follows:
2
(b)
(
(
V8
2
V
+
L2, truly
L
VKzy
P2y teep
2p
where (a) uses the definition of in equation (166); (b) uses the definition of q in equation (164); (c) uses the assumption Mally 2 max(f2 }; (d) uses the definition of Kry in equation (6) and the definitions of 6 and by in equation (4), which concludes the proof.
45

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Copplel Saddle-Point Optimization
K. Proof of Theorem 4.5
Without loss generality, we can assume P = It,- Otherwise, we can simply make variable change - p1/22, That is, we can replace functions pz(2) and operators (2) with (P-1122) and P (-11/2,(-P11/2
We start with the following Lemmas K.1, K.2 and K.3 that describe the basic properties of functions Rutarr (z) and
dkita.... (2). (2), and operators (z(z). The proofs of these lemmas is a trivial utilization of the definitions of functions Pj Ait bitt (z) and Pi t (z) on lines 17 and 22 of Algorithm I, and the definitions of constants L i M Mo
and H, Hettiaae on lines 18, 19 and 20 of Algorithm We omit these proofs due to their simplicity.
Lemma K.1. For all S i, function P. p. - (2) is L - smooth. -mmoohhh
Lemma K.2. For all k 2 i, function Pi
intionat 2k (2) is H. bibindd -stronlyy convex.
Lemma K.3. For all S i S n, operator Qi(z) is M -Lpscchiz.
Next, we establish the key Lemma K.4 that describes the convergence properties Algorithm 1. The proof is available in Appendix K.1.1.
Lemma K.4. For all S k and & E Cz, the following inequality holds:
H kith k (2) + F
0
Ay (2t (e
oo +1/2 - 2|1²
(170)
stat1
Dite
where function Jesi Au (2): 2 + R is defined as follows:
(z. (2)).
i> k i isk'
x
kett de (2) = p: kch . (2) +
(171)
0
constans H 2 O is defined as follows:
H = Σ
H. H stiitt
(172)
1=1
and Diitii.. Gt
2 defined as follows:
kstt..... T8= a M
Ti=b+1 OT,
Dit
1..0....0 12..0...1....0...0
211
(173)
2
Now, we are ready to prove Theorem 4.5. Using the initialization steps on lines and of Algorithm 1, the definition the output Zomt E on line of Algorithm 1, and the arguments that are identical to the proof of Lemma K.4, we obtain the following simplified version of equation (170) for the case ks O:
L. II af 1
M, II =1 QT,-1
Σ (Zo()) - (2))
|
-11
(174)
2
Furthermore, we prove the following Lemma K.5 in Appendix K.1.2.
Lemma K.5. The output Zom of Algorithm satisfies the inclusion Zou Cz.
It remains upper-bound ar First, we lower-bound a, follows:
(0) 1
o 2.... 2
(b) (1 2),
where (a) and (b) use the definition of a; in equation (20). This lower bound a; implies the following upper bound on 0T-11
2
QT < T+1
(175)
which concludes the proof.
46

---

On Linear Convergence in Smooth Convex-Concave Couplee Saddle-Point Optimization
K.1. Proofs of Auxiliary Lemmas
K.1.1. PROOF LEMMA K.4
We prove this lemma by induction for k n, .........
Base (k: n). Using lines 12 and 24 of Algorithm 1, we get the following relation:
th bo 1 + 1/2
arg min =EC, 1=1
Riti ou (z).
(176)
Moreover, function Σi=1 P; puiti (z) is -tronngy convex due to Lemma K.2 and the definition of H5 in equation (172).
Hence, using the fact that 2 C2 and the fact that
P. pita pitarmal (2) Mittumann (E),
(177)
which is implied by equation (171), we obtain the following inequality:
H
(E 1.bn +1/22) +
2 t 1,6+1/22 - 2||
(178)
which is nothing else but the desired equation (170) in the case k: = n.
Induction step (l: k 1). We assume that equation (170) holds for 2 s k S n, which implies the following:
H
( - Dkite.....)) +
2 11.... 1,1411/2 2|1
2
t= 1
Aata (2tt (#t1,.. 14u -r, kst Aitiimate (3)
@
Dhiftrnnte Diite...))) + Ela+1
H
11 111,111121 2112
2
i=++1
Σ
Lhitt kk t1
kit m (3)
+
Σ
(Q,(2, * t 2)
i=++1
H1 kifliinc
H kitt
| +1/2
2
k
t 11
2
2
+
L
2, A kitl m
H 2
b
Σ
- Distt mot
2112
1=++1
Σ
kit kktt mn (1)
Σ (Q)(2), 2 41....00-11,447772 2)
+
Ps
(2
+
11
#=++1
H Hiitiiime
k +
1. 1e..
2, Vp
kit ket Sestitat
(ak
(= 4
2
2 1.6 +1/ Ax
Ax. 11?
+ A
Vignon 1.44 2, Q2 (e(ttin.)t)))
18 -
*
2
24
H
+
21
2
11....4-1. 2112
2
1=
Pr
( ( - Aostimntt (2) + Σ
(Qi(2), A
ff -
1=1
1=
H. kitte...kk
L bit
H
11?
||
2
ck
24. 1|2
2
2
47

---

On Linear Convergence in Smooth Convex-Concave Bilincarly-Couplee Saddle-Point Optimization
1oo-de-1144177 Piudtee- (
Q,Q (+
n
H
D
Ditte Disti...tth)
+
2 ||
1.4+1/22 - 2|1
Pi
(=h
de - Pi
pisthmmat (2)
+
Σ
(Qi(3),
44.,1/12 -2)
i
H
Li
H Hhitimmt
||
2 C2....e ex 11?
1|
t 2.... 0x. 112
2
12k
2, 11
A killmibee
Qx
(0)
n
D
Ditz
+
11
11.2200-11 =21
*
2
Pi
(2t (3
Pi
bx (2) + Σ (1)(3,,
(1../10-1.44///2 8)
H khifii..n
kitt. Li
H Hetti...
12
22....tta
1/ 113
2
2 2q......4 112
2
M1 1.. 2, A
k
kid bi
Qu
H
Σ
Dliternee - mitte Gittt
)
+
|
* 1,/+1122 =11?
istu
2
km
bodk (2 ( - Ps
kal ()))
(2)) + + ()) *
t 1/f411/1 2)
t=
H Hhitt
H
H
t 112
1
zk q......
tg 112
2
2
H kifloonk f
|/
11.. + (H (Hittt... -1 A kitt
- =112
2
Q
H kill..... 4
|1 P1imin-11 - =112
|
k: kils 112 Qx
2
2H
k: # d2
H
+
|
41....4-11.441117 - 2112
silk
2
1=++
Aistinnt ( (2h (1ttt/) - P.
(2) + Σ (Q)(2), *
41...de-11.44117 - 2)
1=1
i=
H kiti....
Li
11 a 1122
112 e1.
1| -= ".......e
do 112
2
2
H kift.....
1
1 - 2112
112b(2
-
2
2H 2
to....
(b)
H
+
||
-212
2
1=
Astematt k
(2 (Ftemiete 1/24112) - Pr Aitimmtt (2) + Σ (Q)(3), *
f 1.44+1/2 - 2)
1=k
L bits.. Hkit
z
2....tt 112
2H k.tii.....tt to
H 1
H t
||
tu 1|2
lok P Samoot--iia 1.4+1 -11
2
2
2
48

---

On Linear Convergence in Smooth Convex-Concave cellineaarl-Couppie Saddle-Point Optimization
n
H
Ditk
(lite...ll) )
+
11
1 211
2
i=++1
(2t Pe - Ps
Joth (l)ttmatt(())
+ Σ
(2)(3), fe...fe-r..441/2 - 2)
Pi
i=
H kittion
H Hi
11?
11++1 211?
2
2
where (a) uses the definition of functions r3 A::ts....fE (2) in equation (171) and the definition of functions Pi E (z) on line 22 of Algorithm 1; (b) uses the definition of A kuti on line 21 of Algorithm 1; (c) uses the convexity and L Ret smoothness of function Pk sb:tf.....ff (=f (f ) where the smoothness property is implied by Lemma K.I: (d) uses the definition of A ff on line 26 of Algorithm 1: (c) uses the monotonicity of operator Qx (f) uses the parallclogram rule of 1 |b]]; (g) uses line 27 of Algorithm 1, the definition of H in equation (172), la + b/ell² |||a|* 2c
Qx
the form (a, b)
and the definition of A kifa....f on line 26 of Algorithm I; (h) uses the M f of operator Qx(2), which implied by Lemma K.3; (i) uses the definition of H H on line 20 of Algorithm Furthermore, we obtain the following:
H H
Ailiiin - Docte...le)) + Gdx+1
1 1
211
2
1=++1
k- --1ifi....k ( (f - Ps Pi
k- I:t1.... 133)
k- 2-1:81 Sk-1 (atts 28 ... 14 12 + (1 aity )
Pi
Ottk
1
k- 1: 16-1 (o0t 2 + (1
Σ (Qe(3), k to -t 1/2
Pi
City
i=k
H
H
Hkite....e
11 - k
112
( lo 1. 2112
2
2
Hk-1
(Dhitimants
m1tt1
sile
+
2
2
(1.., - -211
(=N (= 1/2+112)
k- 1: An (3)
Pi
Pi
k- 1i
(z
1 1 -a12
k- 1:41 -x 11-1 (Z Pi
Pi
Otk
atty
i=
i=
Pi
1:6
(2) + Σ (Q)(2), L
t tu 1// - 2))
i=
Hkith
H
H
1| - k
k
2
I 11:6 -2112
2
2
n
Hh-1
(
D
Diiti
Diit.....e)
+
2
11
1 1
Fx +1 - (1 att, )0 -1ak - -112
Ft2
k- --ltt...ssk 1 '(a7 2 (1 - are 11
12k
2tx)
E(Q(()) at o
1z - - (1 - -o0 )ar -1 z/z - 2)
km
49

---

On Lincar Convergence in Smooth Convex-Concave Sitinnarrl-Couplle Saddle-Point Optimization
R- &e
1
Ofty
k Au ((
T1
k pi (()
P
P
Pi
Ott k=
i=
H sphifiiond
H
||2 2t 2
11
P2..... 1 2|1
2
A Bl+t1
site
(=++1
1
H
1
|
211 + Σ (Qi(2), 2 -
at2
2
1-as
atk
H
1zt/ - -11 + Σ (Q)(3), z 8)
Otty
i=
1
k- 1:41 1-1:81 fu-1 (zt
1 Chiy
k 1:61 50-1 (2t))
k 1:41
f6-1
Pi
Pi
Pi
011
H
H
k
tall 11?
Pe 1d64 -21?
2
1
H
1
2x++1
2112
+
h- lite
(2 k 1 (())
ate
2
i=1
H 1
Oxix
| -112 +
k- 1-13f2 1 (zt ri A- litunttt 1 (2))
aisx
H "iiit
11
kitt
1|
k
11
2 1:441 211
2
ビ-++1
where (a) uses the previous inequality and the definition of function p. tett (2) on line 17 of Algorithm 1; (b) uses the definition of +1 1 line 25 of Algorithm I and the convexity of functions P. Ist {2); (c) uses the definition of
z +1 on line 25 of Algorithm 1; (d) uses the convexity of function p; 1i- (2) and I1-11?: (e) uses the definition of functions r, -- 1:41 14-1 (z) in equation (171). Next, we divide both sides of the inequality by are and obtain the following:
1
H 2
|
2
n
k- 1: 1: Au-1 (z)++1) -r, k- &-1:11 1: (2)
2
1 atk
H
1
211 +
k- 1-11:11..nt
1 (=th)) )
ri k- 1st Ist 1(3)
ai
2
Hhittrmnt
H tiit
1|2
# 28
11
| 1 - 2112
201z
200
Diiteemet iitt1
Kita
Ole
k=
(4)
1
H
2112 +
A- Is-istanttt 1sz (=/++1) r, k- lst1 1 (2)
2
+1
1 - ats
H 1
- 211 + Σ
1:
((x
r3 k- litertatte (3)
2
1k + Masti Au
I. kstt asstitttt + M m
11
||2 +
ta 1. 2112
2000
201t.
50

---

On Lincar Convergence in Smooth Convex-Concave Bilincarly-Couplee Saddle-Point Optimization
n
Diitimn.t lift+1
D.ile.....k)) 8i8k
ait
1=++1
(b)
1
11-11
2
1c+1 - -112 Σ
k- -i- (=(+1)) - (2)
2
2
1=1
1
Oly
22
-
2112 +
1: -- (x(2) (2))) - 73 1:11 1x- (2)
Of
2
Li
k- 1if2nmtt-1
te - =112- - - 11...14 - -211²)
2
Mb-
11-1
|1
8|12 - || - =11(²)
18x41 11xx-
20
Detts....e)) kibk
C'se
i=+1
where (a) uses the definition of H H on line 20 of Algorithm 1; (b) uses the definitions _x
kitiinn and M M on
lines 18 and 19 of Algorithm 1. Using the definition of D D Riti in equation (173), not depend on fg. Moreover, using the definition of at, equation (20), one can verify that au = 1 and t 2 1. Hence, we can do the telescoping and obtain for arbitrary ta E (O..... Ta - 1} the following:
verify that
D kitiittt
does
are 1-at
for
al
of alg-
0
1
H
21
211
1:61 12-
(2
(
-T
x-- (8)
2
TN
i=1
k:
E112 - |1 1g.... 11 - ==11²)
+
2
M k
+
k
E|1 || f 12 2112)
20 -1
(Diitemadee
D
+
Ott
After multiplying both sides of the inequality by - we obtain for arbitrary to E {O....,
Th .......1
1} the following:
H
Pi
k 1:6
(z+,))
r3 k- 1- (a-1
|
211
2
1--
1:h1
+
||
2/12 - -1124 -1, -2113)
2
+
M2
A
1h- aT--l
(1==
(1=6gnnntesIITT. =112 || - 12-1. - =113
2
a
2
D (litk
+
400
aie
i=++1
Hk-1
1:t1 (x)1 (2t,) - -r, k-
k- -11 (zt,))
+ 2
|ス 211
k- 1obpernke
a7,-1
(1 - 2112 - 11 -2112)
2
M
an-1
(1
-212 || 1t.....a-1.1 - 211)
2
51

---

On Lincar Convergence in Smooth Convex-Concave Billncarly-Coupter Saddle-Point Optimization
o M,
Mithiid Is==41 OT, 11
+
0
T1
11 ta 1.Th.0...0 2//
Cxtz
2
i=++1
T
2
/= a7,
+ M
j=k+1 ar2y-1
|| 4- 1.0...0 - 2112
Ot1
2
i=k+1
1
(0)
b-- Ioten
(27)))
R- 1: -()) +
|
21
2
k-
+
(12t 11
2112 - 11 - 1.- =21²))
2
M
1ith 11-1
-on-11
(124 (1 2|1 || 1 11 -2112)
+
2
a
k-
liti... 1 I[]==k a7 TT-1 -1 + *, 1l:t-......t "[T>=k ar;
+
|| 11 TT.... - -21/2
i=++1
k- 1:
jk 03 + +M 1:41 -M
Ti OT, -1
1|
1.0...0 1 -
k=+1
H k-1
k- (
(z1e)
r;
k- lits (el
21/ - E1
k- lifimmte-
1i== 04,-1
+
M₁.
1k- I[ OT, -1
dx 2 1+1,0.00 - -2ll
2
k- Lifimntt-
11i 07 . + M,,"
R- 18t1 Ah-
I[ QT, -1
1.0...0 1.0...0- =112
H k-1
(2)) ri
1--1: ii le-1 (8) (8))
| 211
2
D & -1-id
114-1+1
13t8-1
k- --1:
k-1 2
k- -k-idinmaaa--1 (8)
Pi
ri
H + 5
21 211
k-1
12
D (
iste-1
where (a) and (d) use the definition of D Dis in equation (173); (b) uses the definitions of L Iitttt... and Mithi,...s lines 18 and 19 of Algorithm I; (c) uses line 29 of Algorithm 1; (e) uses lines 24 and 32 of Algorithm 1. The latter inequality is nothing else but the desired equation (170) for k 1, which concludes the proof.
52

---

On Lincar Convergence in Smooth Convex-Concave Bilincarly-Couple Saddle-Point Optimization
K. 1.1.2. PROOF OF LEMMA K.5
We prove by induction that for all n,, the following inclusion holds:
Ci 1. E C...
(179)
Indeed, in the base case A n, equation (179) holds due lines 12 and 24 of Algorithm 1. Next, we assume the inclusion (179) for fixed satisfying 1 S S n. We have 전 = .h.....--1.112 C2 due the definition on line 25 of Algorithm 1 and the fact that ag 1, which is implied by equation (20). Furthermore, for t 1, we have 2 2t,+1 E C2 due to the definition on line 25 of Algorithm 1 and the inclusions z,,- 2 -1 1. +1/2 E C.. and ate E (0, 1). Hence, we obtain क C.. This, together with lines 24 and 32 of Algorithm 1, implies equation (179) for k 1, if & 2 2, Sum E C.. if k 1, which concludes the proof.
L. Proof of Corollary 4.6
Without loss of generality, we can assume that
Moni/e max M max { M./.1) for all i [1, (I....,. 13.
(180)
Otherwise, we can simply reshuffle the pairs (p;(=),Qi())) To ensure the desired inequality (22), it is sufficient to choose (T as follows:
Ti max Wi/e Sin/,,M//// Mi/e,
T:+1 = 2. max
(181)
for ie (1,...,n-11. 1}.
max (VTa/e, M./c.1
Indeed, we can lower-bound IT/= Tj as follows:
i-1 2 max { (VLota/eM
i
II T, = Ti 11 2 2 max M//.1
II max {VTsse,MM/ls)}
j=2
= 2' max { (/e.11
which, together with equation (21), implics equation (22). Similarly, we can upper-bound IT)= T3 as follows:
T, T II T
j=1
j=2
mmax
(Istt//,,M
$ (2 max VLi }
II
+1
max
max / M1st//,, II
3 max LLite,
(VLs/c.M//c.))
j=1
max
= 3 max (Viele,M//e.))
< 3" max Mi/ee.
Finally, is easy verify that Algorithm performs II; T3 computations of the gradient Vp.(2) on line 21 and 2 -IT T3 computations of operator (2(2) on lines 21 and 26, which concludes the proof.
53

---

On Linear Convergence in Smooth Convex-Concave Billncarly-Couplee Saddle-Point Optimization
Let = (x, y) E X y and x'' =x' 6 x V Then we can upper-bound [Vpi Vpi(=')] as M. Proof of Theorem 4.7
follows:
(2)
@ 5/1 [V Vf((')I (b) S 6 1/2 L | x'
(
L d
| x
1|p
Ki ||
x |lp
where (a) uses the definition of function (z) in equation (26) and the definition of matrix in equation (24); (b) uses the smoothness property in Assumption 2.3; (c) uses the definition of matrix P in equation (24); (d) uses the definition of fi in equation (6). Hence, we can choose L1 Ru, and similarly, we can choose L2 = Kiy. In addition, we can upper-bound
[[) (ps(=')||p- follows:
82
3 BB (y 8')l2
VPs(2>) Vps(2')lpp
B
B(x
22)
82
5y
IA@
L2L4 ay
13I
||
r/112
11 5/1
82
6y
Br ky
2y
112 2'Ilp
max
8y
6y
Kayy
max
(3.0y: 8yd
||I 1 P
8n
|| 2 ||P
Kay
maxx
4Toy"
4T.
1
1
||2 - z'11p
Kwy
max
4xzz
4kyy
1 Kayy || - 2'|IP: 7
where (a) the definition of function p=(z) in equation (26) and the definition of matrix P in equation (24); (b) uses Assumption 2.5; (c) uses the definition of matrix P in equation (24); (d) uses the definition of Kay in equation (6); (c) uses the definitions of 3, and 3y in equation (27); (f) uses the definitions of K2 and Ky in equation (6); (g) uses the fact that Kiz Ky 2 1, which is implied by Assumption 2.7. Hence, we can choose Ly = Kzz- Furthermore, we can upper-bound [[Qa(z) (a(2') p- as follows:
(1)(() Qs(2')lle
@
Oa. B
B
Od,
1V
OF | (y
5, |B
IA3
L2 byy 1/112 +
L2
|| x/11
8y
8y
18
Kay 8yllg 1/12 + Key || x'11
11
Mayll || 2'11p-
where (a) uses the definition of operator Qs(z) in equation (25); (b) and (e) use the definition of matrix P in equa-
tion (24); (c) uses Assumption 2.5; (d) uses the definition of Kzy in equation (6). Hence, we can choose M3 /aay.
Next, we can obtain the following:
1B (4)
en| sm
p( =um) p(=*)= + (Q(2*), =um -2")
(b)
(Fouu) - f(x') + g(moa) - g(v")) + (B y" Fral - x²)- -()- Yout y²)
54

---

On Lincar Convergence in Smooth Convex-Concave
Bilincarly-Coupled Saddle-Point Optimization
8
Bg 2
+
Bu Vg((mn)]1
yout + ([((z))
2
Bx
By
|Bx" Vg(Mnn))1
B
y (rin))
2
2
2 (Ioo)) - f(x²) + ((
- gly + [ y aoou - x²) (Bx", Your v²)
Br
By
+
[B x²)) x²111 +
B (you y²)
4
4
Bz |Bx - (i((in)l1 By B T y + V (f(in))
(
Dy (Tom, x²) ) + Dy(Uout 10 )) +
Bz
[B - -x x²1 + By "[ (Yout - y²)l
4
3x1VV(("") - vg(um)l By
I [x=) V(((s)))
By 4
2 (I x²) (Hout, 2²) +
B - x21
B (Yout y²)
4
23, Do (Vim: y 2,3 L y (fim;
9
Br
B [ =²)12+ By
2 (Fout x²) D (Hout y¹) +
T (Yout y²)
Dy (Ti: x²) - 2 (Um: y²),
where (a) uses Corollary 4.6; (b) the definitions of functions pz()) and operators Qi(z) in equations (25) and (26); (c) uses Young's s inequality; (d) uses the optimality conditions (7); (e) uses the smoothness properties in Assumptions 2.3 and 2.4; (f) uses the definitions of B. and By in equation (27).
Using the definitions of functions p=( and operators Q+(=) in equations (25) and (26), Assumptions 2.5 and 2.6, and Lemma 2.8, we can conclude that projg(Zin) projs(Zou)) (Zom). Hence, we get the following:
Be B B(
x= =²2 + By (you v²)l 2 Bz Brp Fou x x=1 + By Blyout v²1??.
(182)
which implies the following:
enl|>in
x= 21 2 Dy (Iont x²) + D 1²) HD, (zin: x²) (yin. 8²)
+ 1 x x1122 + By || - y²11
2 1 y (Fout: x²)+ + "D (Nour, 3²) - 2 ( x²) - DD (2 11)) 2
+
8 fx Bu || x x=112 + (syly + 1 |1 3/ 112
$ D (Fout x²) DD 8²) - ) (Zin; x²) - 1 ( y*) (=im
16 8x Tour - -x²1/ + 1 Syllooou 121
Dy (Foout x²) + Dy (yours 8²) - DD x²) - 1D (2m. v")
+
1 Zour - =1
16
where (a) uses the strong convexity properties in Assumptions 2.3 and 2.4;
(b) uses the definitions of 3r and By in equation (27) and the definitions of 6n and 6, in equation (4); (c) uses the definition of P in equation (24). Furthermore, we 5, (Iin yim) and lout - 2" I = R2,5s, (Iout: Your) due to the definition of =*. Hence, we obtain the
have 2mm - 2 11 = R3_s,
following inequality:
R3,8, (Xouts Mlour + 12D (J our: x²) 12D 11")
(183)
< 1GenR2, (Nim, Mim) + 8D (dtn; x" + 8D (yin
Choosing 1 concludes the proof.
24n 72
55

---

On Lincar Convergence in Smooth Convex-Concave Bilincarly-Cuppled Saddle-Point Optimization
N. Proof of Corollary 4.8
We use restarted version of Algorithm 1. That is, we apply Algorithm times and use the output at each run as the input for the next rum. Formally, by 2/1 (if M and zqu (z You) we denote the input and the output of Algorithm I at t-th run, where {0, ...,. 13. Then we have z 0 and 2 %om for all {O...., , 13. Hence, we can
upper-bound R 6,6, (I Vin follows:
8, (o Vin
I V
iin
T
(G)
T V ((
(3)
T
(R (i vin) + ( x²) + 12D, (2hn wn))
2 (2) T
(Re (+ vnn) + 12 x=112 + 12 y 113)
(3) T (1+ 12Kx + ( R2 (2 k()
T cR²
where (a) the definition of V (2) in equation (29); (b) uses Theorem 4.7; (c) use the definition of (T) in equation (29), where (x" ,²""""" projs (= (d) uses the smoothness properties in Assumptions 2.3 and 2.4; (e) uses the definitions of Ki
and Ky in equation (6) and the definition of R2 6,
in equation (9); (f) uses the definitions z/p = 0, R² R2 (0, 0) and
c = + 12kz + 12ky. Next, we choose 7 as follows:
log( (og(cR2/e)
T
(184)
1og(3/2)
which implies R3,5, (Ith v S e. Note that T' 2 0 due to the fact that S R²2 and c 2 1. In addition, we can upper-bound T as follows:
(m) Σ
log(cR2) /c)
+1
log(3/2)
log(cH?/) /e)
log(3/2)
log(cHt /e) 1
I/
log(cl? /e)
log(3/2)
log(c)
1|e
log(cR)) /c)
log(3/2)
log(1 + 12kg + 12rr,) 1
IAS
log(cR?/ /c)
1og(3/2)
log(25)
cR²
log
where (a) uses the properties of [1; (b) uses the assumption S R2; (c) uses the definition 1 + 12kg + 12kry (d) uses the fact that Rz, Ky 2 1, which is implied by Assumption 2.7.
remains to combine equation (28) in Theorem 4.7 and multiply T by the appropriate number of computations of the gradients (2)(2) and operators (z),, which are provided by Corollary 4.6. Note that the computation the gradients Vpi (2) and Vpz(2) (2) equivalent to the computation of the gradients Vf(x) and Vg(y), respectively. The computation of the gradient Vys(z) and operator Qa(z) requires O(1) matrix-vector multiplications with the matrices B and B as well as a single computation of the gradients V (x and Vg((m) at the beginning of the algorithm, which concludes the proof.
56


Reviews:
[{"review_id": "8EN0M3RxYa", "reviewer": "Reviewer_1jnp", "summary": "This work studied smooth (strongly)-convex-(strongly)-concave bilinearly-coupled saddle-point problem, and provided lower complexity bounds in terms of the computation time, and achieved the separation of complexities. And they further proposed an optimal algorithm which matches with the lower bound.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the high evaluation of our work and the useful references. We provide our answers to the questions below.\n\n1. Thank you for pointing this out. The statement \"to the best of our knowledge, there are no lower complexity bounds that would cover these cases\" is indeed a bit inaccurate. Our point was that there are no *linear* lower bounds, i.e., lower bounds for the linear convergence setting. On the other hand, [1, Theorem 2] provides a *sublinear* lower bound. We will fix the inaccuracy and cite [1] in the revised version of the paper.\n2. As far as we understand, the main limitation of [2] is that it can achieve the linear SOTA rate $\\tilde{\\mathcal{O}}\\left(\\sqrt{\\frac{L_x}{\\mu_x}+\\frac{L_y}{\\mu_y} + \\frac{L_{xy}}{\\mu_x\\mu_y}}\\right)$ in the SCSC regime only for quadratic problems. On the other hand, [2] achieves SOTA rates for general min-max problems without bilinear coupling. We will discuss this in the revised version of the paper.\n3. Thank you for the suggestion. This is an interesting question to consider for future work. In particular, we think that it is possible to remove the terms $\\sqrt{\\kappa_x}$ and/or $\\sqrt{\\kappa_y}$ from the lower and upper complexity bounds by assuming access to proximal mappings associated with functions $f(x)$ and $g(y)$, respectively.", "claims_and_evidence": "The results are supported by convincing evidence, generally I am satisfied with the results. Here are some questions:\n\n1. Missing literature. Line 83, you mentioned for strongly-convex-concave case, \"To the best of our knowledge, there are no lower complexity bounds that would cover these cases\", I think the work [1] should have solved it, check Theorem 2 therein.\n2. Another missing literature should be [2], whose upper bound result is different from your Table 1.\n3. Echo on [1], they also extended the oracle class to proximal mapping, which is broader than your setting, which may be an extension that you can consider.\n\n[1] Xie, Guangzeng, et al. \"Lower complexity bounds for finite-sum convex-concave minimax optimization problems.\" ICML 2020.\n\n[2] Wang, Yuanhao, and Jian Li. \"Improved algorithms for convex-concave minimax optimization.\" NeurIPS 2020", "methods_and_evaluation_criteria": "/", "theoretical_claims": "/", "experimental_designs_or_analyses": "/", "relation_to_broader_scientific_literature": "This work advanced the understanding of optimal complexities for bilinear min-max optimization problems.", "essential_references_not_discussed": "See above", "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": "VWRsIh7glV", "reviewer": "Reviewer_ydoA", "summary": "This paper develops tight lower complexity bounds and matching optimal algorithms for smooth saddle-point problems with bilinear coupling. The work unifies existing results in different regimes (strongly-convex-strongly-concave, bilinear saddle-point, strongly convex with affine constraints) as well as gives new results in the convex-concave setting.\n\n---\n ## Update after rebuttal\n\nThe authors have addressed my concerns regarding the proof of Theorem 3.3 in their rebuttal. I keep my current evaluation of the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments, valueable feedback, and high evaluation of our work. Below, we provide our detailed response to the review.\n\n### Question about the proof of Theorem 3.3 in the case $\\\\mu_x = 0$ or $\\\\mu_y = 0$\n\nThank you for the question! This indeed may need additional explanation. This question is related to cases **(i)**, **(ii.b)**, and **(iii.b)**. For instance, consider case **(i)** (other cases are similar). It is easy to observe that if the function $g(y)$ is $\\\\mu_y$-strongly convex with $\\\\mu_y > 0$, then it is also $0$-strongly convex or simply convex (see Definition 2.1 and Assumption 2.4). Hence, the class of problems (1) satisfying Assumptions 2.3-2.5 with parameters $\\\\pi = (\\\\ldots,\\\\mu_y,\\\\ldots) \\\\in \\\\Pi$ is contained in the class of problems (1) satisfying Assumptions 2.3-2.5 with parameters $\\\\pi = (\\\\ldots,0,\\\\ldots) \\\\in \\\\Pi$. Thus, for case **(i)**, we can choose our hard instance of problem (1) with a $\\\\mu_y$-strongly convex function $g(y)$ with an arbitrary $0 < \\\\mu_y < L_y/4$. In particular, we choose the hard problem instance according to Lemma G.2, which gives the following lower bound:\n$$\n\\\\tilde{\\\\Omega}\\\\left(\\\\frac{L_{xy}\\\\sqrt{L_y}}{\\\\mu_{xy}\\\\sqrt{\\\\mu_y + \\\\mu_{yx}^2/L_x}}\\\\right).\n$$\nWe can choose $\\\\mu_y =  \\\\mu_{yx}^2/L_x$ and obtain\n$$\n\\\\tilde{\\\\Omega}\\\\left(\\\\frac{L_{xy}\\\\sqrt{L_xL_y}}{\\\\mu_{xy}^2}\\\\right),\n$$\nwhich is the desired lower bound for case **(i)**.\n\n### Intuition behind the numerical constants\n\n- There is no particular intuition behind the actual values of the numerical constants in Assumption 2.7 (4 and 18), except that we chose these constants to simplify our calculations in the proof of Theorem 3.3 and make them less ugly. It is likely that these numerical constants can be reduced, but it would not make much sense because Assumption 2.7 is only used to avoid covering uninteresting corner cases with small, i.e., $\\\\mathcal{O}(1)$, condition numbers, as mentioned in the paper.\n- The numerical constants in the Lyapunov function in eq. (29) hold little intuition. The values of these constants are mostly driven by the proof and can likely be improved as well, but it would not make much sense as this would only result in logarithmic or additive improvements in complexity.\n\n### Intuition behind the proofs\n\nFor the intuition behind the construction and the proof of lower bounds, please refer to our response to **Reviewer PYLp**, who raised a similar question. Unfortunately, we were unable to provide a more detailed intuition behind the convergence proof beyond what we have in Section 4.2 (lines 303-345) due to the 5000 character limit (we really tried). We will include a more detailed explanation in the revised version of the paper.\n  \n### Typos and minor errors\n\nThank you for the list of typos and minor errors! We fix them all as follows:\n- (1) Fixed.\n- (2) Yes, indeed. For instance, in the definition of $\\\\mu_{xy}$, if $\\\\lambda_{\\\\min}(\\\\mathbf{B}^\\\\top \\\\mathbf{B}) > 0$, we have $\\\\mathrm{range} \\\\mathbf{B}^\\\\top = \\\\mathcal{X}$ and fall into the first option.\n- (3) Thanks for the suggestion. We have removed the references to Assumptions 2.3-2.5 and added the words \"Parameters $\\\\pi \\\\in \\\\Pi$ satisfy the inequality...\".\n- (4-5) Fixed.\n- (6) Indeed, speaking rigorously, we need to mention the transition from the lower bound on the number of iterations in Nesterov's book to the lower bound on $\\\\tau$, even though it is straightforward. We will add an appropriate comment to the proof in the revised version of the paper.\n- (7) Added reference to Lan (2020, proof of Theorem 3.3).\n- (8-15) Fixed.\n- (16) Indeed, lines 732-740 are worded inaccurately because we cannot choose $L_x=L_y=0$ due to Assumption 2.7. This is also discussed on lines 741-745 (\"Note that strictly speaking...\"). We will rewrite line 732 and eq. (37) in a more accurate way, i.e., something like \"the class of bilinear saddle-point optimization problems falls under Assumptions 2.3-2.5 with parameters...\"\n- (17) Indeed, the case $\\\\mu_x  > 0$ is trivial. The case $\\\\mu_x = 0$ implies $\\\\mu_{xy} > 0$ due to Assumption 2.6, and $\\\\nabla f(x) \\\\in \\\\mathrm{range}\\\\mathbf{B}^\\\\top = (\\\\ker \\\\mathbf{B})^\\\\perp$ due to Assumption 2.5 and point #2 from your list.\n- (18-21) Fixed.\n- (22) Yes, it does. For $i = k$, it holds due to line 22 (first option). For $k > i$, we have $p\\_{i}^{k,t_1,\\\\ldots,t\\_k} \\\\equiv \\\\hat{p}\\_{i}^{k,t\\_1,\\\\ldots,t\\_k} \\\\equiv p\\_{i}^{k-1,t\\_1,\\\\ldots,t\\_{k-1}}$ due to line 22 (second option) and line 17 (second option). Hence, we can prove the desired statement by induction. \n- (23-32) Fixed.\n- (33) Yes, indeed, they could.\n- (34) Fixed.\n- (35) Yes, indeed.\n- (36) Fixed.", "claims_and_evidence": "The claims are clear and supported by convincing evidence.", "methods_and_evaluation_criteria": "The intuition behind the used methodology is lacking and could be made more clear. The evaluation criteria make sense for the problem at hand.", "theoretical_claims": "I checked the claims and proofs in all the Appendices except Appendix I. The main issue I have is in the proof of Theorem 3.3 (Appendix G), where the case $\\mu_x=\\mu_y=0$ is proved by assuming that $\\mu_y>0$. The authors should provide more explanation why this is justified.", "experimental_designs_or_analyses": "There are no experiments in this paper.", "relation_to_broader_scientific_literature": "The paper studies saddle-point problems which have applications in various fields such as economics, game theory and statistics. A comparison with existing state-of-the-art linearly-converging algorithms is given in Appendix C. Moreover, optimal algorithms and theoretical lower bounds are given, which builds further upon the work of Nesterov.", "essential_references_not_discussed": "The related publications are adequately discussed throughout the paper.", "other_strengths_and_weaknesses": "Strengths:\n- The paper is clearly written and provides tight theoretical results in the linearly-converging setting.\n- The results of the paper are relevant to numerous machine learning applications.\n\nWeaknesses:\n- There is no intuition provided for some constants such as the ones in Assumption 2.7 or the Lyapunov function.\n- Similarly, the proofs are not very enlightening, being only a series of algebraic manipulations.", "other_comments_or_suggestions": "List of typos and minor errors:\n1. The page titles are still “Submission and Formatting Instructions for ICML 2025”\n2. Line 140: would it be possible to write $0$ instead of the minimum eigenvalues in the “otherwise” cases, or is this not valid?\n3. Line 165: Assumption 2.6 is a bit poorly worded, it might give the impression that Assumptions 2.3-2.5 implies the inequality.\n4. Line 200: Equation (9): missing squares for the distances\n5. Line 233: fix first set of quotation marks around “hard”\n6. Line 245: Theorem 3.2: does not hold for any time $\\tau>0$, in Nesterov’s book there is an upper bound for the iteration number which should translate into an upper bound for $\\tau$\n7. Line 327: Footnote 5: it is better to specify the proposition/page number instead of the whole book\n8. Line 345: Theorem 4.5: should also include a reference to Algorithm 1 as well as the problem to be solved\n9. Line 402: “numbers” should be “number”\n10. Line 448: capitalisation Polyak-Łojasiewicz (also add en-dash names between instead of hyphen)\n11. Capitalisation of conference names in references is not consistent (e.g. “International Conference on Machine Learning” vs “international conference on machine learning” or “Advances in Neural Information Processing Systems” vs “Advances in neural information processing systems”\n12. Line 561: “eigenvalues of a matrix” should be “eigenvalues of a symmetric matrix” since otherwise they might not be real\n13. Line 566: “argmin” should be “min”\n14. Line 699: “symetric” should be “symmetric”\n15. Line 718: “this” should be “these”\n16. Line 738: Equation (38) does not follow from putting in the values from (37)\n17. Line 782: A reference to Assumption 2.6 in addition to Assumption 2.5 should be added. Moreover, the implication stated should be explained more thoroughly\n18. Each time a line number from Algorithm 1 is referenced, it comes out as “algorithm 1 of Algorithm 1” instead of “line x of Algorithm 1”\n19. Line 1430: “wuch” should be “such”\n20. Line 1527: $(n+i)\\times(n+i)$ should be in the superscript\n21. Line 2290: Missing an identity matrix in the upper bound\n22. Line 2430: Lemma K.2: does this hold for $k \\neq i$?\n23. Line 2460: Equation (174): missing superscript $0$ on $r_i(\\hat{z})$; the last $z$ should be $\\hat{z}$; $z^0$ should be $z_{\\rm in}$\n24. Line 2489: “which is implied by which is implied by”\n25. Line 2495: “Introduction step” should be “Induction step”\n26. Line 2495: also have to assume that it holds for $k=n$ or the induction is invalid\n27. Line 2518: $\\nabla \\hat{p}_i^k$ should be $\\nabla \\hat{p}_k^k$\n28. Line 2596: $\\hat{p}_i^k$ should be $\\hat{p}_k^k$\n29. Line 2835, 2846, 2850: subscript inside the last product should be $j$ instead of $i$ (resp. $j+1$ instead of $i+1$)\n30. Line 2880: step (c) should be an inequality and $\\|z-z’\\|_P^2$ should be $\\|z-z’\\|_P$\n31. Line 2911: Q(z) should be Q(z^*)\n32. Line 2930: The Lipschitz constants are missing\n33. Line 2983: the coefficients 12 could be 6?\n34. Line 2985: step (e) equality should be an inequality\n35. Line 3001-3009 could be removed, the statement is obvious since big O does not care about additive constants\n36. Line 3013: deifnition should be definition", "questions_for_authors": "Could you elaborate on the proof of Theorem 3.3 in the cases that $\\mu_x=\\mu_y=0$ or when one of the two strong convexity constants is $0$?", "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": "ILlZUh1qEw", "reviewer": "Reviewer_PYLp", "summary": "This paper considers deterministic convex-concave minimax optimization problems. In particular, the main focus is on the case where we can obtain linear convergence, as characterized in Assumption 2.6.\n* First, the authors establish fine-grained lower bounds by separately counting oracle calls for the gradients and the coupling matrix multiplications, and the results (1) recover [ZHZ'22] for the SCSC (strongly-convex-strongly-concave) case and (2) also cover some other cases (including strongly-convex-concave or bilinear functions).\n* Second, the authors propose Algorithm 1, which is based on the idea of solving a more general finite-sum variational inequality. An application of this to minimax optimization problems yield tight convergence upper bounds for the cases described in the lower bound results.\n\n[ZHZ'22] Zhang, J., Hong, M., and Zhang, S. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 2022.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments, valuable feedback, and high evaluation of our work. Below, we provide our detailed response to the review.\n\n### Other Comments Or Suggestions\n- Fixed.\n- Please refer to the separate paragraph below.\n- Fixed.\n\n### Questions For Authors\n- All functions $p_i^{n;t_1,\\\\ldots,t_n}(z)$ are just quadratic functions that contain previously computed gradients $\\\\nabla p_i(z)$ and operators $Q_i(z)$. This can be shown by analyzing lines 17 and 22 at recursion levels $k = 1,\\\\ldots,n$. Hence, line 12 is a simple (possibly constrained) quadratic optimization problem, which does not require any oracle calls.\n- Please refer to the separate paragraph below.\n- Indeed, the result of Zhang et al. (2022b) recovers the $\\\\sqrt{\\\\kappa_{xy}}$ part in the SCSC case. In particular, the proof of Lemma G.3 is inspired by the result of Ibrahim et al. (2020), which is a slightly generalized version of the result by Zhang et al. (2022b). Combining this with the lower bound for smooth and strongly convex optimization by Nesterov (2013), we recover the full result in the SCSC case.\n- Some results for general min-max problems beyond SCSC were developed by Kovalev et al. (2022b). However, these results are far from reaching our lower bounds. It is worth highlighting that obtaining accelerated rates is much more difficult for general min-max problems (some results were developed by Alkousa et al. (2020), [2] mentioned by **Reviewer 1jnp**, or in arXiv:2002.02417, arXiv:2205.05653). Overall, this is indeed an interesting question that we are currently starting to examine.\n\n### Lower bounds construction.\nHere, we attempt to provide an intuition behind the construction of our lower bounds. We start with the basic example of Nesterov (considering an infinite-dimensional space $\\\\ell^2$ for simplicity). Consider the following linear system:\n$$\\\\mathbf{A}x = e_1,$$\nwhere\n$$\\\\mathbf{A} = \\\\begin{bmatrix}1\\\\\\\\\\\\alpha-1&1\\\\\\\\&\\\\alpha-1&1\\\\\\\\&&&\\\\ddots\\\\end{bmatrix},$$\nand $\\\\alpha \\\\in (0,1)$. It has a unique solution $x^* = (1,1-\\\\alpha,(1-\\\\alpha)^2,\\\\ldots)$. We can construct a minimization problem with the same solution:\n$$\\\\min_x \\\\|\\\\mathbf{A}x - e_1\\\\|^2.$$\nOne can show that after $k$ computations of the gradient, no more than $\\\\mathcal{O}(k)$ coordinates of the current iterate $x^k$ are nonzero (due to the linear span assumption). Hence, the distance to the solution is lower bounded by the remainder of the geometric series $\\\\sum_{i=k+1}^\\\\infty(1-\\\\alpha)^i = \\\\frac{(1-\\\\alpha)^{k+1}}{\\\\alpha}$. Moreover, the condition number $\\\\kappa_x$ is proportional to $1/\\\\alpha^2$, which gives the lower bound $\\\\tilde{\\\\Omega}(\\\\sqrt{\\\\kappa_x})$ of Nesterov.\n\nThe minimization problem above has the following min-max reformulation:\n$$\\\\min_x\\\\max_y 2 \\\\langle y, \\\\mathbf{A}x - e_1\\\\rangle - \\\\|y\\\\|^2.$$\nHere, we have $\\\\kappa_{xy}$ proportional to $1/\\\\alpha^2$, and we can apply arguments similar to the ones above to obtain the lower bound $\\\\tilde{\\\\Omega}(\\\\sqrt{\\\\kappa_{xy}})$. We can also add a regularizer of the form $\\\\|x\\\\|^2$, which, subject to some additional details, leads to the results of Zhang et al. (2022b) and Ibrahim et al. (2020). Our Lemma G.3 can be seen as a finite-dimensional variant of the result by Ibrahim et al. (2020).\n\nNow, we discuss the most challenging case of our lower bounds, which is Lemma G.2. The starting point is the lower bounds of Scaman et al. (2018) for smooth and strongly convex decentralized minimization, which allows for the min-max reformulation of the form (1). It is based on splitting the hard function of Nesterov (see above) into two functions and placing them on the first and the last $n/3$ nodes of the path consisting of $n$ nodes (refer to Scaman et al. (2018) for details). To obtain our lower bounds, we need to make the following substantial changes:\n- We add dual regularization of the form $-\\\\mu_y \\\\|y\\\\|^2$. This allows us to obtain the desired result for $\\\\mu_y > 0$, but it makes the problem much more difficult to work with.\n- We replace the $n$-node path with an $n/3$-node path and attach two $n/3$-node star-topology networks to its ends, such that Nesterov functions are stored only on the \"leaves\" of these stars. This step introduces some sort of symmetry, which simplifies finding the solution to the problem.\n- We also introduce an extra dual variable, modify matrix $\\\\mathbf{B}$, and add an extra regularizer of the form $-L_y\\\\|y\\\\|^2$ with respect to the new variable to account for nontrivial values of $L_y \\\\gg \\\\mu_y$. Additionally, we analyze the spectral properties of matrix $\\\\mathbf{B}$ in Lemma I.1.\n\nWe apply a series of reformulations to the resulting min-max problem and obtain a simple minimization problem similar to the example above but with a different value of $\\\\alpha$. It remains to carefully analyze this value, subject to additional details which we, unfortunately, are unable to discuss here due to the 5000 character limitation.", "claims_and_evidence": "(The main results are theoretical.) I have not checked the proofs line by line, but the details seem to have no fatal errors.", "methods_and_evaluation_criteria": "The main results are theoretical.", "theoretical_claims": "I have not checked the proofs line by line, but I read the appendix, and the details seem to have no fatal errors.\n(See **Strengths & Weaknesses** and **Questions** for details.)", "experimental_designs_or_analyses": "The main results are theoretical.", "relation_to_broader_scientific_literature": "The paper can contribute to theoretical guarantees and understandings on convex-concave minimax optimization algorithms and variational inequalities.", "essential_references_not_discussed": "I am unaware of any particular closely related work that has not been cited in the paper.", "other_strengths_and_weaknesses": "**Strengths**\n* The paper is well-written (in my opinion), and I really enjoyed reading it.\n* The paper suggests both novel lower bounds and matching upper bounds that, altogether, closes the case. The proposed results make solid contributions, especially those for the new tight rates for all of the non-SCSC cases.\n* The paper also contains (upper bound) results that consider finite-sum variational inequalities of the form $(14)$.\n\n**Weaknesses**\n* See **Questions** for details.", "other_comments_or_suggestions": "* The running title says 'Submission and Formatting Instructions for ICML 2025.' (I have 3 such papers in my review batch, and I don't know why!)\n* I think it would have been better if there were more discussions on the lower bound instance constructions, which I think is one of the most interesting parts of the paper.\n* (TYPO) Table 1, Footnote (5) symetric → symmetric", "questions_for_authors": "* Can the authors elaborate on any iteration complexities or number of oracle calls induced in the $\\arg \\min$ part of Algorithm 1 in the innermost loop $k = n+1$?\n* In the lower bounds, using matrices with $1$'s in the diagonals and $-1$'s in the super-diagonals is quite standard (as in [ZHZ'22]), but I wonder what the high-level motivations of the instances in Lemmas G.2 and G.3 (for the $\\sqrt{\\kappa_{xy}}$ parts) were. Could the authors give a bit of an illustration on this, or is this just a magical lower bound?\n* I am also curious if previous results by [ZHZ'22] can recover the same results considering separate counts for the gradient and coupling matrix oracles for the SCSC case. (I am aware that [ZHZ'22] deals *only* with the SCSC case while this paper covers several more cases.)\n* This might be a bit out of scope because the proposed problem $(1)$ is already an important, classical problem, but one weakness one could point out (for the upper bound) is that everything applies only when we have the bilinear-coupled structure. Personally, I also have been curious about whether we can construct an intuitive minimax optimization algorithm for SCSC (or maybe more general cases where we can have linear convergence) *without* the bilinear coupling structure in the objective function. I know that the existence of the coupling matrix is essential for the proposed results, but have the authors ever thought of extending Algorithm 1 to the general convex-concave case by, for instance, replacing the $\\boldsymbol{B}$'s with the Hessians $\\nabla_{xy} f$, or else?", "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": {"ethical_review_concerns": "(None)"}}, {"review_id": "lVcx7xJOEz", "reviewer": "Reviewer_FzFW", "summary": "This paper studies the first-order methods for solving smooth convex-concave saddle-point problems with bilinear coupling i.e. $ \\min_x \\max_y f(x) + \\langle y, Bx \\rangle - g(y)$. It establishes the first lower bounds on the number of gradient evaluations $\\nabla f(x), \\nabla g(y)$ and matrix-vector multiplications with $B$ and $B^{\\top}$ needed for solving these saddle-point problems. Moreover, it develops algorithm which matches this lower bound.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort. Unfortunately, the development of the *optimal algorithm* for solving problem (1), which is one of the key contributions of our paper acknowledged by other reviewers, is missing from the \"strengths\" list. Moreover, the criticism of our paper is based on claims that are either **factually false** or *highly questionable*. We address these below.\n\n1. ```Kovalev et al 2022b already attains...```\n    Unfortunately, this claim is false and unjustified:\n     - *This claim is false*. The algorithm of Kovalev et al. (2022b) cannot reach the lower bounds because it does not implement *the separation of complexities*. Refer to lines 60-72 in Section 1.2 for an explanation. This also clearly follows from Table 1.\n     - *This claim is unjustified*. You should support this claim with evidence, including an explanation with references to Kovalev et al. (2022b), such as precise theorems, equations, paragraphs, etc.\n2. ```This is an unfair comparison.``` Unfortunately, *this statement is false.* The exact opposite is true: it is correct to compare $\\mathcal{R}$ with any *norm*, including the one used by Kovalev et al. (2022b, eq. (14)), due to the *norm equivalence theorem*. The cost of the transition between the norms is negligible due to linear convergence: it only results in extra *additive factors* in the complexity. Moreover:\n     - It is standard practice in the field to ignore additive constants in linear complexities. This includes *all* SOTA papers in Table 1, most of which are A*/Q1.\n     - On lines 162 and 403, we explicitly mention that we ignore additive constants. This is also acknowledged by **Reviewer ydoA**.\n3. ```No experiments.``` It is a common standard in the field that papers with strong theoretical results are not required to include any experiments, just as strong experimental papers are not required to include any theory. Our paper contains strong theoretical results, which are acknowledged by other reviewers. Hence, the absence of experiments is justified.\n4. ```Presentation is poor.``` Unfortunately, you have not provided any arguments to support this claim. On the other hand, other reviewers found our paper \"well-written\" and \"clearly written\". Regrettably, our only option is to disregard this claim.\n5. ```Authors do not provide pseudocode.``` In Section 4.3, we provide a clear and comprehensive explanation of how to apply Algorithm 1 with restarting to solve problem (1), including the definitions of functions $p_i$ and operators $Q_i$ in eqs. (25) and (26). This is more than enough for anyone with at least some expertise in mathematical optimization to use the algorithm. It is also important to highlight that, according to lines 351-367 in Section 4.2, it is necessary to reorder functions $p_i$ and operators $Q_i$, depending on the values of constants $L_i$ and $M_i$ from Theorem 4.7. This would lead to $3!=6$ explicit variants of the algorithm for each order. Hence, a practical implementation would still use Algorithm 1 in combination with separate first-order oracle implementations for functions $p_i$ and operators $Q_i$, which can be easily done in any modern programming language/framework.\n6. ```How problem 14 generalizes problem 1.``` A brief explanation is available on lines 351-255, Section 4.3. Some explanation is also available in (Lan and Ouyang, 2021; Gidel et al., 2018; Nesterov, 2007). We are strongly convinced that a more detailed explanation is unnecessary because the reduction of convex-concave saddle-point optimization problems to monotone variational inequalities is one of the most basic facts in optimization theory. For a detailed explanation, please refer to books like \"Finite-Dimensional Variational Inequalities and Complementarity Problems\".\n\n### Questions\n\n1. ```What is the number...``` It is given in Table 1 of our paper or Table 1 of Kovalev et al. (2022b).\n2. ```Assumptions 2.6...``` This is not true. Assumption 2.6 requires $\\delta_x,\\delta_y>0$, which is not implied by Assumptions 2.3-2.5. Moreover, Assumption 2.6 is the \"line\" that separates the settings of linear convergence and sublinear convergence. This is clearly mentioned numerous times in the paper, for instance, on lines 160-188 (Section 2.2), and lines 228-262 (Section 3.2). Similarly, it is easy to verify that Assumption 2.7 is not implied by Assumptions 2.3-2.5.", "claims_and_evidence": "This paper claims to develop an optimal algorithm for solving saddle point optimization problem with bilinear coupling. However, the paper doesn't provide any experiment to show it's performance and comparison to other existing algorithms in practice.", "methods_and_evaluation_criteria": "This paper provides no experiments to evaluate the performance of the proposed algorithm. The analysis is entirely theoretical, focusing on deriving lower complexity bounds and developing an optimal algorithm that matches these bounds. No empirical validation is provided to demonstrate its practical performance on real-world problems or benchmark datasets.", "theoretical_claims": "The paper claims they develop the first optimal algorithm that matches the lower bound. However, they do not provide explicit pseudocode of the algorithm for solving the saddle point problems. Moreover, the iteration complexity of this paper is given in terms of **weighted square distance** $\\mathcal{R}^2$ which is completely different from Kovalev et al 2022b. **This is an unfair comparison.**", "experimental_designs_or_analyses": "This paper provides no experiments to evaluate the performance of the proposed algorithm. Therefore, there are no experimental designs or analyses to assess for soundness or validity.", "relation_to_broader_scientific_literature": "The saddle-point optimization problem with bilinear coupling is a fundamental problem class that arises in various machine learning applications, including game theory, reinforcement learning, computer vision, robust optimization, and distributed optimization. Developing an optimal algorithm for solving such problems has the potential to significantly benefit the machine learning community.", "essential_references_not_discussed": "I think the references discussed in the paper are sufficient.", "other_strengths_and_weaknesses": "Strength:\n1. Provides lower bound for saddle point optimization problems with bilinear coupling.\n\nWeakness: \n1. This paper claims they provide the first algorithm which attains the optimal complexity for strongly convex strongly concave. To my understanding, Kovalev et al 2022b already attains the optimal complexity with respect to each of the gradient evaluations (they just didn't mention that explicitly). I think the contribution of this paper is incremental. \n2. The iteration complexity of this paper is given in terms of **weighted square distance** $\\mathcal{R}^2$ which is completely different from Kovalev et al 2022b. **This is an unfair comparison.** \n3. The paper provides no experiment to show the performance of proposed algorithm in practice. \n4. The presentation is poor. \n5. The main problem under consideration is problem (1). However, authors do not provide any pseudocode to solve this problem class. Only pseudocode is for algorithm 1, which solves problem 14.\n6. It is hard to follow how problem 14 generalizes problem 1. Authors should add a detailed discussion on this in the Appendix.", "other_comments_or_suggestions": "1. Please write down the pseudocode of the algorithm which solves the problem 1.\n2. Add a discussion on how problem 14 generalizes problem 1.", "questions_for_authors": "1. What is the number of gradient $\\nabla f(x), \\nabla g(y)$ evaluations required for the algorithm in Kovalev et al 2022b.\n2. Assumptions 2.6 and 2.7 are not really assumptions right? They follow from assumptions 2.3-2.5.", "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 paper studies bilinearly coupled saddle-point problems with general smooth (non-strongly) convex $f(x)$ and $g(y)$. The main contributions of the work include tight upper and lower complexity bounds that establish linear convergence rates. The paper is well written and provides insightful discussion into the nuances that arise in assessing optimal convergence complexity for saddle-point settings. The reviewers were overall in agreement that the paper provides important results for saddle-point optimization, and would therefore be a valuable contribution to the conference.
Decision: Accept (poster)