STay-ON-the-Ridge Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games Constantinos DaskalakisNoah GolowichStratis Skoulakis

2025-05-03 0 0 3.23MB 43 页 10玖币

侵权投诉

STay-ON-the-Ridge: Guaranteed Convergence to Local

Minimax Equilibrium in Nonconvex-Nonconcave Games

Constantinos DaskalakisNoah GolowichStratis Skoulakis†

Manolis Zampetakis?

Massachusetts Institute of Technology

École Polytechnique Fédérale de Lausanne†

University of California, Berkeley?

October 19, 2022

Abstract

Min-max optimization problems involving nonconvex-nonconcave objectives have found

important applications in adversarial training and other multi-agent learning settings. Yet,

no known gradient descent-based method is guaranteed to converge to (even local notions

of) min-max equilibrium in the nonconvex-nonconcave setting. For all known methods,

there exist relatively simple objectives for which they cycle or exhibit other undesirable

behavior different from converging to a point, let alone to some game-theoretically meaningful

one [

VGFP19

HMC21

]. The only known convergence guarantees hold under the strong

assumption that the initialization is very close to a local min-max equilibrium [

WZB19

Moreover, the afore-described challenges are not just theoretical curiosities. All known methods

are unstable in practice, even in simple settings.

We propose the ﬁrst method that is guaranteed to converge to a local min-max equilibrium

for smooth nonconvex-nonconcave objectives. Our method is second-order and provably

escapes limit cycles as long as it is initialized at an easy-to-ﬁnd initial point. Both the deﬁnition

of our method and its convergence analysis are motivated by the topological nature of the

problem. In particular, our method is not designed to decrease some potential function, such

as the distance of its iterate from the set of local min-max equilibria or the projected gradient

of the objective, but is designed to satisfy a topological property that guarantees the avoidance

of cycles and implies its convergence.

arXiv:2210.09769v1 [cs.LG] 18 Oct 2022

1 Introduction

Min-max optimization lies at the foundations of Game Theory [

vN28b

], Convex Optimiza-

tion [

Dan51a

Adl13

] and Online Learning [

Bla56

Han57

CBL06

], and has found many ap-

plications in theoretical and applied ﬁelds including, more recently, in adversarial training and

other multi-agent learning problems [

GPM+14

MMS+18

ZYB19

]. In its general form, it can be

written as

min

θ∈Θmax

ω∈Ωf(θ,ω), (1)

where Θand Ωare convex subsets of the Euclidean space, and fis continuous.

Eq.

(1)

can be viewed as a model of a sequential-move game wherein a player who is interested

in minimizing

chooses

ﬁrst, and then a player who is interested in maximizing

chooses

after seeing

. A solution to

(1)

corresponds to a Nash equilibrium of this sequential-move game.

We may also study the simultaneous-move game with the same objective

wherein the mini-

mizing player and the maximizing player choose

and

simultaneously. The Nash equilibrium

of the simultaneous-move game, also called a min-max equilibrium, is a pair

(θ?

ω?)∈Θ×Ω

such

that

f(θ?,ω?)≤f(θ,ω?), for all θ∈Θand f(θ?,ω?)≥f(θ?,ω), for all ω∈Ω. (2)

It is easy to see that a Nash equilibrium of the simultaneous-move game also constitutes a

Nash equilibrium of the sequential-move game, but the converse need not be true. Here, we focus

on solving the (harder) simultaneous-move game. In particular, we study the existence of dynamics

which converge to solutions of the simultaneous-move game, namely the existence of methods

that make incremental updates to a pair

(θt

ωt)

so as the sequence

(θt

ωt)

converges, as

t→∞

to some (θ∗,ω∗)satisfying (2) or some relaxation of it.

This problem has been extensively studied in the special case where

and

Ω

are convex and

compact and

is convex-concave — i.e. convex in

for all

and concave in

for all

. In this case,

the set of Nash equilibria of the simultaneous-move game is equal to the set of Nash equilibria

of the sequential-move game, and these sets are non-empty and convex [

vN28b

]. Even in this

simple setting, however, many natural dynamics surprisingly fail to converge: gradient descent-

ascent, as well as various continuous-time versions of follow-the-regularized-leader, not only fail to

converge to a min-max equilibrium, even for very simple objectives, but may even exhibit chaotic

behavior [

MPP18

VGFP19

HMC21

]. In order to circumvent these negative results, an extensive

line of work has introduced other algorithms, such as extragradient [

Kor76

] and optimistic gradient

descent [

Pop80

], which exhibit last-iterate convergence to the set of min-max equilibria in this

setting; see e.g. [

DISZ18

DP18

MR18

RLLY18

HA18

ADLH19

DP19

LS19

GHP+19

MOP19

ALW19

GPDO20

GPD20

]. Alternatively, one may take advantage of the convexity of the problem,

which implies that several no-regret learning procedures, such as online gradient descent, exhibit

average-iterate convergence to the set of min-max equilibria [

CBL06

SS12

BCB12

SSBD14

Haz16

Moreover, [

LJJ20

KM21

OLR21

] show that convexity with respect to one of the two players is

enough to design algorithms that exhibit average-iterate convergence to min-max equilibria.

Our focus in this paper is on the more general case where

is not assumed to be convex-

concave, i.e. it may fail to be convex in

for all

, or may fail to be concave in

for all

, or

both. We call this general setting where neither convexity with respect to

nor concavity with

respect to

is assumed, the nonconvex-nonconcave setting. This setting presents some substantial

challenges. First, min-max equilibria are not guaranteed to exist, i.e. for general objectives there

may be no

(θ?

ω?)

satisfying

(2)

; this happens even in very simple cases, e.g. when

Θ=Ω= [

0, 1

]

and

f(θ

ω) = (θ−ω)2

. Second, it is

-hard to determine whether a min-max equilibrium

exists [

DSZ21

] and, as is easy to see, it is also

-hard to compute Nash equilibria of the sequential-

move game (which do exist under compactness of the constraint sets). For these reasons, the

optimization literature has targeted the computation of local and/or approximate solutions in

this setting [

DP18

MR18

JNJ19

WZB19

DSZ21

MV21

]. This is the approach we also take in this

paper, targeting the computation of

(ε

δ)

-local min-max equilibria, which were proposed in [

DSZ21

These are approximate and local Nash equilibria of the simultaneous-move game, deﬁned as

feasible points (θ?,ω?)which satisfy a relaxed and local version of (2), namely:

f(θ?,ω?)<f(θ,ω?) + ε, for all θ∈Θsuch that kθ−θ?k ≤ δ; (3)

f(θ?,ω?)>f(θ?,ω)−ε, for all ω∈Ωsuch that kω−ω?k ≤ δ. (4)

Besides being a natural concept of local, approximate min-max equilibrium, an attractive feature

(ε

δ)

-local min-max equilibria is that they are guaranteed to exist when

-smooth and the

locality parameter,

, is chosen small enough in terms of the smoothness,

, and the approximation

parameter,

, namely whenever

δ≤q2ε

. Indeed, in this regime of parameters the

(ε

δ)

-local

min-max equilibria are in correspondence with the approximate ﬁxed points of the Projected

Gradient Descent/Ascent dynamics. Thus, the existence of the former can be established by invoking

Brouwer’s ﬁxed point theorem to establish the existence of the latter. (Theorem 5.1 of [DSZ20]).

There are a number of existing approaches which would be natural to use to ﬁnd a solution

(θ?

ω?)

satisfying

(3)

and

(4)

, but all run into signiﬁcant obstacles. First, the idea of averaging,

which can be leveraged in the convex-concave setting to obtain provable guarantees for otherwise

chaotic algorithms, such as online gradient descent, no longer works, as it critically uses Jensen’s

inequality which needs convexity/concavity. On the other hand, negative results abound for

last-iterate convergence: [

HMC21

] show that a variety of zeroth, ﬁrst, and second order methods

may converge to a limit cycle, even in simple settings. [

VGFP19

] study a particular class of

nonconvex-nonconcave games and show that continuous-time gradient descent-ascent (GDA)

exhibits recurrent behavior. Furthermore, common variants of gradient descent-ascent, such as

optmistic GDA (OGDA) or extra-gradient (EG), may be unstable even in the proximity of local

min-max equilibria, or converge to ﬁxed points that are not local min-max equilibria [

DP18

JNJ19

While there do exist algorithms, such as Follow-The-Ridge proposed by [

WZB19

], which provably

exhibit local convergence to a (relaxation of) local min-max equilibrium, these algorithms do not

enjoy global convergence guarantees, and no algorithm is known with guaranteed convergence to

a local min-max equilibrium.

These negative theoretical results are consistent with the practical experience with min-

maximization of nonconvex-nonconcave objectives, which is rife with frustration as well. A

common experience is that the training dynamics of ﬁrst-order methods are unstable, oscillatory

or divergent, and the quality of the points encountered in the course of training can be poor; see

e.g. [

Goo16

MPPSD16

DISZ18

MGN18

DP18

MR18

MPP18

ADLH19

]. In light of the failure of

essentially all known algorithms to guarantee convergence, even asymptotically, to local min-max

convex-concave nonconvex-concave nonconvex-

nonconcave

existence yes [vN28a]no†no†

complexity poly-time

e.g. [

Dan51b

FS97

SS12

]

NP-hard?NP-hard [DSZ21]

Nash Eq.

convergent

dynamics

many

e.g. [FS97,CBL06,SS12]not applicable not applicable

existence same as above yes yes [DSZ21]

complexity same as above poly-time

[LJJ20,KM21,OLR21]PPAD-hard [DSZ21]

Local Nash Eq.

convergent

dynamics same as above many

[LJJ20,KM21,OLR21]This paper

Table 1: Summary of known results for equilibrium existence, equilibrium complexity, and

existence of dynamics converging to equilibrium for simultaneous zero-sum games with differing

complexity in their objective function.

(†)

For example, the zero-sum game with objective function

f(θ

ω) = −(θ−ω)2

, where the minimizing player chooses

θ∈[−1, 1]and the maximizing player chooses ω∈[−1, 1], does not have any Nash Equilibrium.

(?)Although it is not explicitly stated in [DSZ21], this is a consequence of the proof of Theorem 10.1 in [DSZ20].

equilibria, we ask the following question: Is there an algorithm which is guaranteed to converge to a

local min-max equilibrium in the nonconvex-nonconcave setting [WZB19]?

1.1 Our Contribution

In this work we answer the above question in the afﬁrmative:

we propose a second-order method

that is guaranteed to converge to a local min-max equilibrium (Theorem 1)

. Our algorithm,

called STay-ON-the-Ridge or STON’R, has some similarity to Follow-The-Ridge or FTR, which

only converges locally and to a relaxed notion of min-max equilibrium. Both the structure of

our algorithm and its global convergence analysis are motivated by the topological nature of

the problem, as established by [

DSZ21

] who showed that the problem is computationally (and

mathematically) equivalent to Brouwer ﬁxed point computation. In particular, the structure and

analysis of STON’R are not based on a potential function argument but on a parity argument (see

Section 4), akin to the combinatorial argument used to prove the existence of Brouwer ﬁxed points.

Table 1shows our contributions in the context of what was known prior to our work about

equilibrium existence, equilibrium complexity, and existence of dynamics with guaranteed conver-

gence to equilibrium in zero-sum games with objectives of differing complexity.

1.2 Simulated Experiments

As a warm-up we present some simulated experiments to compare the performance of our

algorithm with the widely used algorithms for min-max optimization. More precisely, we compare:

Gradient Descent Ascent (GDA; Figure 1), Extra-Gradient (EG; Figure 2), Follow-the-Ridge (FtR;

Figure 3), and STay-ON-the-Ridge (STON’R; Figure 4) in the following 2-D examples:

min

θ∈[−1,1]max

ω∈[−1,1]f1(θ,ω):= (4θ2−(ω−3θ+θ3

20)2−ω4

10 )exp(−θ2+ω2

100 ), and

min

θ∈[−1,1]max

ω∈[−1,1]f2(θ,ω):=−θω −1

20 ·ω2+2

20 ·Sθ2+ω2

2·ω2

where Sis the smooth-step function S(θ) = 









0, θ≤0

3θ2−2θ3,θ∈[0, 1]

1, θ≥1

We do not provide separate plots for Optimistic Gradient Descent Ascent (OGDA) because its

behavior is almost identical with the behavior of EG in these examples and hence all our comments

about EG transfer to OGDA as well. In all the following ﬁgures the different colors represent

trajectories with different initialization. The initialization of every trajectory is represented by a

dot and the line represent the path that the algorithm follows starting from the dot.

Observe that all the known methods either get trapped on a limit cycle, or they only converge

when initialized very close to the solution. Our algorithm (Figure 4) is the only one that converges

in both of these examples when initialized in (−1, −1)which is far away from the solution.

(a) f1(θ,ω). (b) f2(θ,ω).

Figure 1: (Algorithm: GDA)

(a)

We observe that for any initial condition the algorithm converges

to the same limit cycle. The only exception is when the algorithm is initialized exactly on

(

0, 0

)

where the gradients are 0 and hence it does not move. So in this example, unless initialized on the

equilibrium, the algorithm converges to a speciﬁc limit cycle.

(b)

In this example, if the algorithm

is initialized far away from the equilibrium, which is

(

0, 0

)

, then it diverges, i.e., it moves towards

the boundary. On the other hand, if the algorithm is initialized close enough to the equilibrium

then it slowly converges to the equilibrium point with a very slow rate.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

STay-ON-the-Ridge:GuaranteedConvergencetoLocalMinimaxEquilibriuminNonconvex-NonconcaveGamesConstantinosDaskalakisNoahGolowichStratisSkoulakisManolisZampetakis?MassachusettsInstituteofTechnologyÉcolePolytechniqueFédéraledeLausanneUniversityofCalifornia,Berkeley?October19,2022AbstractMin-maxoptim...

展开>> 收起<<

STay-ON-the-Ridge Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games Constantinos DaskalakisNoah GolowichStratis Skoulakis.pdf

共43页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

STay-ON-the-Ridge Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games Constantinos DaskalakisNoah GolowichStratis Skoulakis

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: