Semi-Anchored Gradient Methods for Nonconvex-Nonconcave Minimax Problems

This paper focuses on nonconvex-nonconcave minimax problems. It introduces a new method called the semi-anchored (SA) gradient method, which extend the idea of PDHG to the nonlinear setting by incorperating the certain Bregman distance as a preconditioner. With a designed Legendre function, the SA-GDmax and its practical version SA-MGDA are studied with convergence result and suitable optimality measure.

The paper consider Bregman divergence based methods for weak Minty variational inequalities. They show convergence of the Bregman divergence between two consecutive iterates for the Bregman proximal point (BPP) method by expressing the scheme as a preconditioned resolvent. By applying the hyperplane projection step of Solodov & Svaiter 1999 they increase the range of $\rho$ (showing convergence in terms of the tangent residual). By modifying the preconditioner further they obtain a scheme which alternatingly computes a proximal gradient for the min-player and solves a proximal (implicit) update for the max-player. They immediately obtain convergence from the previous results. Finally they consider inexactness of the max-player for which they show convergence for the tangent residual.

This work for the first time extends the primal-dual hybrid gradient (PDHG) method from convex-concave minimax optimization problem to nonconvex-nonconcave minimax optimization problem. The 4 versions of PDHG (with/without projection and with/without max oracle) obtain the same gradient convergence rate $\mathcal{O}(1/k)$ as the existing extragradient methods, and PDHG without projection and with max oracle upper bounds Bragman distance that is larger than the squared norm measure in the convergence rate of the existing extragradient methods, which yields faster empirical convergence of PDHG without projection and with max over extragradient methods as shown in the experiments.

The paper proposed semi-anchored gradient methods to a structured nonconvex-nonconcave minimax problem under certain assumption, namely the weakly Minty variational inequality (MVI). The proposed algorithm is based on the Bregman proximal point (BPP) algorithm, also resembles the primal-dual hybrid gradient (PDHG) method. The proposed algorithm consists of u and v substeps where the authors proposed using FISTA to solve the v substep approximately. Theoretical convergence is studied for this SA-MDGD algorithm and numerical experiments were provided to show the efficacy of the proposed method.

We express our gratitude to all the reviewers for carefully reading our paper and offering valuable feedback. We acknowledge that our contributions were not clearly stated, and we made revisions to the paper to enhance the clarity of our contributions as listed below.

• We further highlighted why we consider the PDHG-type method in the first place. In particular, we added a statement, owing from (Chambolle & Pock, 2011), that the PDHG outperforms the extragradient on a bilinear problem. The SA-GDmax exactly reduces to the PDHG for a bilinear problem, so we expect that the SA-GDmax will outperform the extragradient when entered a locally bilinear problem, regardless of the worst-case rate comparison beyond bilinear setting.
• We made the theory of the inexact SA-MGDA in Theorem 5 stronger. First of all, we accidentally missed to mention that the convergence rate of the SA-MGDA in Theorem 5 is in terms of the Bregman distance (and thus in terms of the squared gradient norm), which was already shown in Theorem 7 (of Appendix D.1), a detailed version of Theorem 5. In addition, thanks to reviewer Mhw9, we realized that Theorem 5 does not even need a bounded domain assumption, by simply adopting the proof Theorem 6. (This weakens the necessity of the projection technique in this paper, but it is still useful as it allows larger $\rho$ in the weak MVI condition.)
• We have made comparison of worst-case rates, under the weak MVI, more apparent. In particular, thanks to reviewers uoZm and vygr, we modified Table 1 (and the paper), so that our advantage over EG+/CEG+ is more evident; the SA-GDmax and EG+/CEG+ have same $O(1/k)$ rate but the optimality measure (Bregman distance) for SA-GDmax upper bounds that (squared gradient norm) for EG+/CEG+. In addition, we highlighted that, when an efficient max-oracle is available, the SA-GDmax can be superior to EG+/CEG+ even in terms of the computational complexity, which is the case of our numerical experiments. Note that GDmax also has the same $O(1/k)$ rate but only under the PL condition on the max-player, which is not of our interest and does not satisfy for our numerical experiments, so we found mentioning this not necessary.

The paper studies min-max optimization problems in structured nonconvex-nonconcave primal-dual (PD) settings and proposes new algorithms based on the Bregman proximal point (PP) method. Nonconvex-nonconcave min-max optimization settings are known to be computationally challenging, thus the paper studies them under the "weak MVI" condition proposed in the recent literature. The results in the paper extend the range of the parameter of the weak MVI condition (thus showing that a larger class of nonconvex-nonconcave problems can be addressed algorithmically in poly-time), at the cost of a more expensive oracle access to a problem (Bregman prox for either the entire operator associated with the problem or with the "max" part of the problem). Importantly, it is possible to use an approximate version of the oracle (under additional "smoothness" assumptions for the "max" part function $g$) at a $\log(1/\epsilon)$ cost.

The paper has multiple interesting contributions, but the positioning of the paper seems misplaced. I had trouble understanding this from the author-reviewer discussion, so I read the paper to see what was happening. The main motivations of the paper and its primary "selling points" are: (1) using a PD method in place of extragradient (EG)-type methods, because "they are faster in practice" and (2) introducing a new convergence criterion, which is simply a Bregman divergence between successive iterates. If the paper were to be considered based on these two contributions, then I would agree with the reviewers that this would be incremental and not particularly interesting, for the following reasons. First, the claim about PD methods being "faster in practice" than EG methods is ill-defined and not supported by evidence. The two classes of methods are not directly comparable, because EG applies to a much broader classes of problems (variational inequalities) and assumes only oracle access to evaluations of the operator associated with the problem (plus possibly a projection oracle for the feasible set or its close variant). PD methods apply to more specialized problem classes and usually assume availability of a prox-oracle for the (primal-dual) separable components of the objective. To make a fair comparison, one would need to consider variants of EG specialized to the considered problem class and the available oracle(s). It is known that in terms of the (theoretical) convergence rate, there is no difference between the two classes of methods; one could primarily gain in PD setups from better balancing of the dependence on the problem parameters when the primal and the dual side have substantially different Lipschitz constants and diameters of the feasible set. If EG were to be used in these setups, one would use different step sizes for the primal and the dual portion and that's not hard to handle in its analysis. In any case, if the main motivation is that PD methods are faster in practice, then one would expect to see extensive numerical experiments in place of a single toy experiment in the present paper. Second, Bregman distance between successive iterates is not a surprising measure of convergence for prox-type methods and, more importantly, it is not a good measure of convergence as it is algorithm-specific. One could have a trivial algorithm that always outputs the same point. For such an algorithm, this measure of convergence would be zero (convergence in one iteration!), even though the algorithm is clearly not doing anything useful. Additionally, even the standard analysis of the Mirror-Prox method from Nemirovski's '04 paper bounds an upper bound on the "useful" gap but it is the result for the gap that is stated in the theorems because it is an interpretable condition.

Additionally, it should be clarified very early on in the paper that even though the paper considers Bregman PP method, it does not address more general normed spaces than previous work.

That all said, the paper does have good contributions, but it needs to be repositioned. The most interesting ones, from my perspective, come down to extending the range of the weak MVI condition at the cost of a more expensive oracle. Even if the oracle costs $\log(1/\epsilon)$ (or even poly$(1/\epsilon)$), the point is that we get to solve more nonconvex-nonconcave problems (which are computationally challenging in general) than we did before. That should be highlighted better. Second, the paper would benefit from providing clear remarks after the theorem statements explaining by how much we can extend this range by translating its algorithm parameters into problem parameters. Finally, the result for the quasi-Bregman firm nonexpansiveness of the (Bregman) resolvent under the weak MVI condition appears new to me -- this should be highlighted as well.

There were at least two experts evaluating this paper and understanding its contributions took quite a bit of effort. That begs the question: who is this paper for?

Reject