Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis

We thank the reviewer for their time and service.

In the presentation of section 3.2, the matrix $Q$ is defined based on a particular pair of indexes $(i,j) \in B \times N$. Are all subsequent claims hold for all $(i,j)$?

Matrix $Q$ is indeed defined with respect to a certain pair $(i,j) \in B \times N$, and all subsequent claims hold for any such $(i, j)$.

Is there a reason for the missing proof of claim C.2?

The proof of Claim C.2 is in the paragraph just before Claim C.2. We are happy to transfer the proof after the claim if the reviewer believes the current version can cause confusion.

The definition of the matrix $Q$ in Equation (5) is quite confusing as it is not worded as a definition at all. The vector $b, c$ and value $d$ also seem to come out of no where.

Those quantities are defined in Eq. (10) of the appendix. Their exact definition is not important for the purpose of the main body, but we will make sure to include Eq. (10) in the main body of the revision as we see how the current version can cause some confusion.

Let us know if we can further make the writing easier to understand.

We thank the reviewer for their time and service.

We thank the reviewer for their time and service.

The paper lacks adequate comparison with existing literature. There has been considerable research on smoothed analysis of optimization problems (see [1] for example).

We will make sure to cite and discuss [1] (and some of the references therein) in the revised version. There are many crucial differences between our results and [1].

• First, [1] focuses on certain convex quadratic problems while we examine zero-sum games.
• The perturbation model between our paper and [1] are also different, as the latter has an average-case flavor (parameterized by the concentration of eigenvalues of a certain matrix) while we work in the usual smoothed complexity model of Spielman and Teng.
• Our main result establishes an iteration complexity scaling with $\log(1/\epsilon)$, while [1] obtains a complexity polynomial in $1/\epsilon$ (unless there is strong convexity, which is not the case in our problem).
• Moreover, the algorithms considered in [1] are distinct from ours, although they are also gradient-based, and the techniques are also very different. In particular, [1] assumes (see Problem 2.1 in that paper) that the underlying randomization is independent of the optimal solution. On the other hand, as we stress throughout our paper, the fact that in our setting the equilibrium depends on the randomization is the main technical challenge.

Overall, the technical challenges we faced are very different from the ones in [1], and we believe that the papers are generally orthogonal. We will include the above discussion in the revision.

Convergence in terms of euclidean distance instead of duality gap should be less emphasized as contribution/novelty as these type of results are already known for gradient-based algorithms

The contribution/novelty of our results in terms of Euclidean distance is that they provide the first polynomial bounds in the smoothed complexity model. Many results in terms of Euclidean distance were known, as the reviewer points out and as we highlight throughout the paper, but they had to rely on exponentially large constants. We believe that this improvement–which is obtained in conjunction with those known results–is worth highlighting as an important contribution.

​​The paper abstract and possibly title should be reflective of the fact that Theorem 1.4 is the main message of the paper (instead of convergence rates) as all the other results of the paper readily follows from Theorem 1.4.

We will expand the abstract to reflect the fact that Theorem 1.4 is the main technical contribution.

An example where the constant $\kappa$ depends exponentially on $m, n$ could be helpful.

Starting from the $3 \times 3$ example of Proposition 3.1, one can make $\kappa$ to be inversely exponential in $m, n$ by suitable selecting $\gamma = \gamma(n, m)$ (and filling the rest of the matrix according to the identity matrix).

We thank the reviewer for their time and service.

We also thank the reviewer for pointing out the issues with clarity. We will make sure to incorporate the suggestions in the revision.

Could you clarify precisely how gradient based methods in the smoothed setting improve over, say interior point methods which also achieve $\log(1/\epsilon)$ iteration complexity? Probably you can claim lower space requirements, but is there anything else to say?

The two main aspects on which gradient-based algorithms, such as OGD, are more appealing than interior-point methods are the per-iteration complexity and the memory requirements. An algorithm such as OGD requires a single matrix-vector product per iteration; this is nearly linear for sparse matrices, and can be even smaller when the game-matrix is more structured (for example, low-rank). The memory requirements of OGD are also minimal, as the reviewer points out. On the other hand, interior-point methods require solving a linear system in each iteration, which can be prohibitive in large games. In those regards gradient-based algorithms are more compelling.

We thank the reviewer for their time and service.

Can the authors comment if the smoothed analysis could give insights going beyond bimatrix games, such as the performance of the algorithms studied in this paper but for convex-concave settings or for low-rank bimatrix non-zero sum games?

This is an interesting question. Beyond (two-player) matrix games, perhaps the most natural next step would concern polymatrix zero-sum games, for which we suspect that similar results should apply. For general convex-concave games, it is not clear to us how one should even define the perturbed instance, unless the underlying function is more structured. When it comes to nonzero-sum bimatrix games, even under a low-rank constraint computing Nash equilibria is hard (unless the rank is 1), and so iterative algorithms instead converge in a time-average sense to a so-called coarse correlated equilibrium (CCE). It is unclear whether the framework of smoothed complexity can lead to meaningful improvements when it comes to convergence to CCE. On the other hand, it seems plausible that our results can be extended to rank-1 games.

Some assumptions related to perturbations of the A matrix, that is in definition 4.1 could be restrictive, in that the support of the equilibrium doesn't change. Can the authors comment on whether this can be relaxed to a certain extent?

There are other natural notions of perturbation stability one could consider in the context of Section 4; for example, that the equilibrium of the perturbed game must be $\delta$-close to the equilibrium of the original game. It is not clear whether a result such as Theorem 4.2 applies to that notion, but we believe this is an interesting question for future work. One technical challenge we should point out here is that our characterization of Theorem 3.6 does not handle multiplicity of equilibria, which appears to be relevant for other notions of perturbation stability.

I think the authors could perhaps provide more justification for using smoothed analysis in this context.

Besides the usual justification for performing smoothed analysis in the context of linear programming and optimization, which applies to zero-sum games as well, we believe that in game-theoretic problems smoothed complexity is even more relevant since there is often noise/imprecision when specifying the players’ utilities. This puts into question some worst-case pathological examples, such as the one specified in Proposition 3.1. Those are the type of examples for which algorithms such as OGD perform poorly in practice.

Finally, we thank the reviewer for spotting the typo.