Extra-gradient with player sampling for faster convergence in n-player games

The appendices are structured as follows: App. A presents the setting and the existing results. In particular, we start by introducing the setting of the mirror-prox algorithm in §A.1 and detail the relation between solving this problem and finding Nash equilibria in convex n-player games §A.2. We then present the proofs of our theorems in App. B. We analyze the DSEG algorithm (Alg. 1) and study its variance-reduction version. App. D presents further experimental results and details. A. Existing results A.1. Mirror-prox Mirror-prox and mirror descent are the formulation of the extra-gradient method and gradient descent for non-Euclidean (Banach) spaces. Bubeck (2015) (which is a good reference for this subsection) and Juditsky et al. ( 2011 ) study extragradient/mirror-prox in this setting. We provide an introduction to the topic for completeness. Setting and notations. We consider a Banach space E and a compact set Θ ⊂ E. We define an open convex set D such that Θ is included in its closure, that is Θ ⊆ D and D ∩ Θ = ∅. The Banach space E is characterized by a norm • . Its conjugate norm • * is defined as ξ * = max z: z 1 ξ, z . For simplicity, we assume E = R n . We assume the existence of a mirror map for Θ, which is defined as a function Φ : D → R that is differentiable and µ-strongly convex i.e. ∀x, y ∈ D, ∇Φ(x) -∇Φ(y), xy µ xy 2 . We can define the Bregman divergence in terms of the mirror map. Definition 2. Given a mirror map Φ : D → R, the Bregman divergence D : D × D → R is defined as D(x, y) Φ(x) -Φ(y) -∇Φ(y), xy . Note that D(•, •) is always non-negative. For more properties, see e.g. Nemirovsky & Yudin (1983) and references therein. Given that Θ is compact convex space, we define Ω = max x∈D∩Θ Φ(x) -Φ(x 1 ). Lastly, for z ∈ D and ξ ∈ E * , we define the prox-mapping as P z (ξ) argmin u∈D∩Θ Φ(u) + ξ -∇Φ(z), u = argmin u∈D∩Θ