On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms

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.

1. Kovalev et al 2022b already attains... Unfortunately, this claim is false and unjustified:
   • 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.
   • 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.
2. 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:
   • 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.
   • On lines 162 and 403, we explicitly mention that we ignore additive constants. This is also acknowledged by Reviewer ydoA.
3. 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.
4. 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.
5. 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.
6. 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".

Questions

1. What is the number... It is given in Table 1 of our paper or Table 1 of Kovalev et al. (2022b).
2. 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.

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.

Other Comments Or Suggestions

• Fixed.
• Please refer to the separate paragraph below.
• Fixed.

Questions For Authors

• 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.
• Please refer to the separate paragraph below.
• 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.
• 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.

Lower bounds construction.

Here, 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: $\\mathbf{A}x = e_1,$ where \\mathbf{A} = \\begin{bmatrix}1\\\\\\alpha-1&1\\\\&\\alpha-1&1\\\\&&&\\ddots\\end{bmatrix}, and $\\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: $\\min_x \\|\\mathbf{A}x - e_1\\|^2.$ One 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.

The minimization problem above has the following min-max reformulation: $\\min_x\\max_y 2 \\langle y, \\mathbf{A}x - e_1\\rangle - \\|y\\|^2.$ Here, 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).

Now, 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:

• 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.
• 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.
• 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.

We 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.

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.

Question about the proof of Theorem 3.3 in the case $\\mu_x = 0$ or $\\mu_y = 0$

Thank 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:

We can choose $\\mu_y = \\mu_{yx}^2/L_x$ and obtain

which is the desired lower bound for case (i).

Intuition behind the numerical constants

• 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.
• 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.

Intuition behind the proofs

For 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.

Typos and minor errors

Thank you for the list of typos and minor errors! We fix them all as follows:

• (1) Fixed.
• (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.
• (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...".
• (4-5) Fixed.
• (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.
• (7) Added reference to Lan (2020, proof of Theorem 3.3).
• (8-15) Fixed.
• (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..."
• (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.
• (18-21) Fixed.
• (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.
• (23-32) Fixed.
• (33) Yes, indeed, they could.
• (34) Fixed.
• (35) Yes, indeed.
• (36) Fixed.

We thank the reviewer for the high evaluation of our work and the useful references. We provide our answers to the questions below.

1. 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.
2. 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.
3. 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.