凸对策中无导数博弈的改进率_Improved rates for derivative free play in convex
版权申诉
167 浏览量
2022-01-19
18:44:09
上传
评论
收藏 146KB PDF 举报
arXiv:2111.09456v2 [cs.GT] 22 Nov 2021
Improved rates for derivative free play in convex games
Dmitriy Drusvyatskiy
∗
Lillian J. Ratliff
†
Abstract
The influential work of Bravo et al. (2018) shows that derivative free play in strongly monotone games
has complexity O(d
2
/ε
3
), where ε is the target accuracy on the expected squared distance to the solution.
This note shows that the efficiency estimate is actually O(d
2
/ε
2
), which reduces to the kn own efficiency
guarantee for the method in unconstrained optimization. The argument we present is elementary, simply
interpreting the method as stochastic gradient play on a slightly perturbed strongly monotone game.
1 Introduction and main result
In this paper, we consider an N-player game defined by cost functions f
i
: X
i
→ R and sets of strategies
X
i
⊂ R
d
i
. Thus each player i ∈ {1, . . . , N} seeks to solve the problem
min
x
i
∈X
i
f
i
(x
i
, x
−i
),
where x
−i
denotes the actions of all the players excluding player i. A vector of strategies x
∗
= (x
∗
1
, . . . , x
∗
N
)
is a Nash equilibrium if each player i has no ince ntive to unilaterally change their strategy, that is
x
∗
i
∈ argmin
x
i
∈X
i
f
i
(x
i
, x
∗
−i
).
Throughout, we impose the following convexity and smoothness assumptions; items 1-2 and 4-5 are identical
to those in Bravo et al. (2018). In contrast, item 3 is not assumed in Bravo e t al. (2018), but will b e
important in what follows. We note that when applied to the single player setting N = 1, none of our
results require item 3 and it may be dropped entirely. Throughout, the symbol ∇
i
will de note the partial
derivative with respect to x
i
, we set d =
P
d
i=1
d
i
, and let S
i
and B
i
denote the unit s phere and unit ball in
R
d
i
, respectively.
Assumption 1 (Standing). There exist constants α, β ≥ 0 such that fo r each i ∈ [N ], the following hold:
1. The set X
i
⊂ R
d
i
is closed and convex, and there exist constants r, R > 0 satisfying rB ⊆ X ⊆ RB.
2. The function f
i
(x
i
, x
−i
) is convex and C
1
-smooth in x
i
and the gradient ∇
i
f
i
(x) is β-Lipschitz con-
tinuous in x.
3. The Jacobian of the map ∇
i
f
i
(x) is L-Lipschitz continuous meaning:
k∇(∇f
i
)(x) −∇(∇
i
f
i
)(x
′
)k
op
≤ L kx − x
′
k ∀x, x
′
∈ X.
4. The gradient map g(x) := (∇
1
f
1
(x), ∇
2
f
2
(x), . . . , ∇
N
f
N
(x)) is α-strongly monotone on X, meaning
hg(x) − g(x
′
), x − x
′
i ≥ αkx − x
′
k
2
∀x, x
′
∈ X.
5. For each i ∈ [N ] and x ∈ X, the function f
i
satisfies |f
i
(x)| < ∞ and we set F
∗
:= max
x∈X
|f
i
(x)|
2
.
∗
Department of Mathematics, University of Washington, Seattle
†
Department of Electrical and Computer Engineering, University of Washington, Seattle
1
资源评论
