Introduction
Generalized Nash equilibrium problems (GNEPs) model noncooperative interactions in which self-interested agents are coupled not only through their cost functions but also through shared constraints on their joint actions [11 ] . Such problems arise in a variety of engineering applications, including electricity markets and demand-side management [6 , 35 ] , charging coordination of electric vehicles [18 ] , traffic and transportation networks [8 ] , and communication systems [31 ] . In many of these settings, the shared constraints represent physical limits of a common infrastructure, such as line ratings, transformer loadings, or voltage-stability margins in power networks, and are therefore inherently nonlinear [17 ] . Moreover, the agents are typically not coordinated by a central operator and possess only local information: each agent knows its own cost and local constraints and can exchange information only with its neighbors over a communication network [22 ] .
Among the generalized Nash equilibria, a particularly relevant subclass is formed by the variational GNE (v-GNE), which correspond to solutions of a variational inequality (VI) defined by the game pseudo-gradient over the coupled feasible set [9 ] . The v-GNE are economically meaningful, as all agents face the same shadow price for the shared resources [16 ] , and, under strong monotonicity of the
T. Tatarenko is with the Technical University of Darmstadt, Darmstadt, Germany (e-mail: tatiana.tatarenko@tu-darmstadt.de). P. Latafat and A. Bemporad are with the IMT School for Advanced Studies Lucca, Lucca, Italy (e-mail: puya.latafat@imtlucca.it; alberto.bemporad@imtlucca.it).
The work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation). Project number: 528033031. This work was also funded by the European Union (ERC Advanced Research Grant COMPACT, No. 101141351). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
pseudo-gradient, a v-GNE exists and is unique [10 ] . The VI characterization suggests solving the problem by projection-type methods, such as projected gradient play or the extragradient method [2 , 14 , 15 , 23 ] . However, these methods require projections onto the coupled feasible set. When the shared constraints are nonlinear, such projections are generally not available in closed form and require solving an auxiliary optimization problem at every iteration. Furthermore, since the coupled feasible set depends on the joint action profile, these projections cannot be computed locally by the agents.
For this reason, the majority of existing GNE seeking algorithms rely on the Karush–Kuhn–Tucker (KKT) conditions of the v-GNE and operate in the lifted primal–dual space, in which the shared constraints are handled through Lagrange multipliers [28 , 32 ] . In the partial-decision information setting, where each agent maintains estimates of the actions of the others and communicates only with its neighbors [34 ] , distributed primal–dual schemes based on operator splitting have been developed [5 , 25 ] . These methods, however, require the agents to maintain, update, and reach consensus on local copies of the dual variables, which increases both the computational and the communication burden. Moreover, their convergence analysis concerns linear coupling constraints. For nonlinear shared constraints, the lifted operator is not globally Lipschitz continuous, even if the original game’s pseudo-gradient possesses this property, and, thus, constant-stepsize primal–dual methods lose their guarantees. In this case, additional mechanisms, such as adaptive or line-search stepsize rules [19 , 20 ] , are required. However, these rules are still applied to the lifted primal–dual operator and cannot be implemented in a distributed manner, as the line search requires the stepsize to be coordinated centrally among all agents.
In this paper, we take a different route and avoid dual variables altogether. We observe that the set of feasible joint actions coincides with the set of minimizers of a smooth convex penalty function defined for the constraint violation over the local action sets. As a consequence, the v-GNE problem is exactly equivalent to a hierarchical VI, in which the upper level is given by the game pseudo-gradient and the lower-level VI is given by the gradient of the penalty and involves only projections onto the local action sets. Hierarchical VIs have been studied by means of vanishing (Tikhonov-type) regularization [13 , 21 ] (see also [1 ] for minimization problems) and extragradient-type schemes [30 ] . However, all these methods are centralized procedures: they assume that the full operators of both levels are available to a single computing unit and require full information on the joint decision vector at every iteration. These works address general monotone lower-level operators and typically provide guarantees for ergodic averages or in terms of gap functions. In contrast, the nonlinear lower-level VI in our reformulation corresponds to a convex optimization problem, and we exploit this structure to obtain last-iterate convergence rates to the v-GNE. To the best of our knowledge, the hierarchical VI reformulation has not been used before to design distributed GNE seeking algorithms that operate entirely in the primal space.
The main contributions of this paper are summarized as follows.
which does not require the introduction of dual variables.
We develop a centralized hierarchical regularization scheme that performs a single projected step onto the local action sets per iteration. Under a local error bound condition on the constraint set, which holds, e.g., under Slater’s condition, we prove last-iterate squared distance convergence to the v-GNE with rate O ( 1 / t 2 / 3 ) O(1/t^{2/3}) O ( 1/ t 2/3 ) . Under a global error bound condition, which holds, e.g., for linear shared constraints and polyhedral local sets, we improve this rate to O ( 1 / t ) O(1/t) O ( 1/ t ) .
We extend the scheme to the partial-decision information setting, in which the agents communicate over a connected undirected graph and maintain local estimates of the joint action. The resulting distributed algorithm uses a constant stepsize and requires no communication of dual variables. We prove its convergence to the v-GNE with rate O ( 1 / t ) O(1/t) O ( 1/ t ) under the local error bound condition (e.g., Slater’s condition) and bounded action sets.
We illustrate the performance of the proposed algorithms on randomly generated instances of multi-agent systems with nonlinear network constraints and on distributed problems with linear shared constraints, and compare them with the corresponding KKT-based lifted primal–dual methods [5 , 15 , 19 ] .
The remainder of the paper is organized as follows. Section II formulates the problem and discusses the limitations of the projection-based and primal–dual approaches. Section III presents the hierarchical VI reformulation. The centralized and distributed hierarchical regularization schemes and their convergence analysis are presented in Sections IV and § 5 , respectively. Section VI provides the simulation results, and the proofs of auxiliary lemmas are collected in the Appendix.
Notation
We write [ N ] = { 1 , … , N } [N] = \{1,\ldots,N\} [ N ] = { 1 , … , N } and R + m \mathbb{R}_{+}^{m} R + m for the nonnegative orthant of R m \mathbb{R}^{m} R m . For vectors u 1 , … , u N u^{1},\ldots,u^{N} u 1 , … , u N of possibly different dimensions, [ u 1 , … , u N ] [u^{1},\ldots,u^{N}] [ u 1 , … , u N ] denotes the stacked column vector; a superscript i i i refers to the block associated with player i i i . For u , v ∈ R n u,v \in\mathbb{R}^{n} u , v ∈ R n , ⟨ u , v ⟩ \langle u,v\rangle ⟨ u , v ⟩ is the Euclidean inner product and ∥ u ∥ \|u\| ∥ u ∥ is the Euclidean norm; for a matrix, ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ is the induced spectral norm. We denote by 0 0 0 the zero vector, by 1 N \mathbf{1}_{N} 1 N the N N N -dimensional vector of ones, by I N I_{N} I N the N × N N \times N N × N identity matrix, by A ⊤ A^{\top} A ⊤ the transpose of a matrix A A A , and by ⊗ \otimes ⊗ the Kronecker product. For a symmetric matrix A A A , A ⪰ 0 A \succeq0 A ⪰ 0 means that A A A is positive semidefinite, and λ min ( A ) \lambda_{\min}(A) λ m i n ( A ) denotes its smallest eigenvalue. For t ∈ R t \in\mathbb{R} t ∈ R , [ t ] + = max { t , 0 } [t]_{+} = \max\{t,0\} [ t ] + = max { t , 0 } ; for vectors, [ ⋅ ] + [\cdot]_{+} [ ⋅ ] + is applied componentwise. For a differentiable function ϕ : R n → R \phi:\mathbb{R}^{n}\to\mathbb{R} ϕ : R n → R , ∇ ϕ ( a ) \nabla\phi(a) ∇ ϕ ( a ) is its gradient and ∇ i ϕ ( a ) \nabla_{i}\phi(a) ∇ i ϕ ( a ) is its partial with respect to a i a^{i} a i .
For a nonempty closed convex set X ⊆ R n X \subseteq\mathbb{R}^{n} X ⊆ R n , Π X ( u ) = argmin y ∈ X ∥ y − u ∥ \Pi_{X}(u) = \operatorname*{argmin}_{y\in X}\|y-u\| Π X ( u ) = argmin y ∈ X ∥ y − u ∥ is the Euclidean projection of u u u onto X X X , dist ( u , X ) = ∥ u − Π X ( u ) ∥ \operatorname{dist}(u,X)=\|u-\Pi_{X}(u)\| dist ( u , X ) = ∥ u − Π X ( u ) ∥ is the distance from u u u to X X X , N X ( u ) = { v : ⟨ v , y − u ⟩ ≤ 0 ∀ y ∈ X } N_{X}(u)=\{v:\langle v,y-u\rangle\leq0\ \forall y\in X\} N X ( u ) = { v : ⟨ v , y − u ⟩ ≤ 0 ∀ y ∈ X } is the normal cone to X X X at u ∈ X u\in X u ∈ X , and int X \operatorname{int}X int X and ri X \operatorname{ri}X ri X are the interior and the relative interior of X X X . Given F : X → R n F:X\to\mathbb{R}^{n} F : X → R n , VI ( X , F ) \operatorname{VI}(X,F) VI ( X , F ) is the problem of finding u ∈ X u\in X u ∈ X such that ⟨ F ( u ) , y − u ⟩ ≥ 0 \langle F(u),y-u\rangle\geq0 ⟨ F ( u ) , y − u ⟩ ≥ 0 for all y ∈ X y\in X y ∈ X , and SOL ( X , F ) \operatorname{SOL}(X,F) SOL ( X , F ) is its solution set.
A mapping F : X → R n F:X\to\mathbb{R}^{n} F : X → R n is L L L -Lipschitz continuous on X X X if ∥ F ( u ) − F ( v ) ∥ ≤ L ∥ u − v ∥ \|F(u)-F(v)\|\leq L\|u-v\| ∥ F ( u ) − F ( v ) ∥ ≤ L ∥ u − v ∥ , monotone if ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 0 \langle F(u)-F(v),u-v\rangle\geq0 ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 0 , μ \mu μ -strongly monotone if ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ μ ∥ u − v ∥ 2 \langle F(u)-F(v),u-v\rangle\geq\mu\|u-v\|^{2} ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ μ ∥ u − v ∥ 2 , and 1 L \frac{1}{L} L 1 -cocoercive if ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ 1 L ∥ F ( u ) − F ( v ) ∥ 2 \langle F(u)-F(v),u-v\rangle\geq\frac{1}{L}\|F(u)-F(v)\|^{2} ⟨ F ( u ) − F ( v ) , u − v ⟩ ≥ L 1 ∥ F ( u ) − F ( v ) ∥ 2 , for all u , v ∈ X u,v\in X u , v ∈ X . If F = ∇ ϕ F=\nabla\phi F = ∇ ϕ for a convex differentiable function ϕ \phi ϕ and F F F is L L L -Lipschitz continuous on an open convex set U U U , then F F F is 1 L \frac{1}{L} L 1 -cocoercive on U U U [26 Thm. 3.1] . For nonnegative sequences, u t = O ( v t ) u_{t}=O(v_{t}) u t = O ( v t ) means that there exists c > 0 c>0 c > 0 such that u t ≤ c v t u_{t}\leq cv_{t} u t ≤ c v t for all sufficiently large t t t .
We consider a non-cooperative game Γ \Gamma Γ between N N N players. Let player i i i , i ∈ [ N ] i\in[N] i ∈ [ N ] , choose its local action from R d i \mathbb{R}^{d_{i}} R d i and J i : R D → R \mathcal{J}^{i}:\mathbb{R}^{D}\to\mathbb{R} J i : R D → R , with D = ∑ i = 1 N d i D=\sum_{i=1}^{N}d_{i} D = ∑ i = 1 N d i , denote its cost function. We assume the existence of a local constraint set A i ⊆ R d i \mathcal{A}^{i}\subseteq\mathbb{R}^{d_{i}} A i ⊆ R d i for each player i ∈ [ N ] i\in[N] i ∈ [ N ] as well as of a shared coupling constraint set C \mathcal{C} C defined by the following system of inequalities:
C = { a ∈ R D : g ( a ) ≤ 0 } , (1) \mathcal{C}=\{a\in\mathbb{R}^{D}:g(a)\leq0\}, \tag*{(1)} C = { a ∈ R D : g ( a ) ≤ 0 } , (1)
where g ( a ) = [ g 1 ( a ) , … , g m ( a ) ] ⊤ : R D → R m g(a)=[g_{1}(a),\ldots,g_{m}(a)]^{\top}:\mathbb{R}^{D}\to\mathbb{R}^{m} g ( a ) = [ g 1 ( a ) , … , g m ( a ) ] ⊤ : R D → R m , a = [ a 1 , … , a N ] ⊤ ∈ R D a=[a^{1},\ldots,a^{N}]^{\top}\in\mathbb{R}^{D} a = [ a 1 , … , a N ] ⊤ ∈ R D , with a i = [ a i , 1 , … , a i , d i ] ⊤ a^{i}=[a^{i,1},\ldots,a^{i,d_{i}}]^{\top} a i = [ a i , 1 , … , a i , d i ] ⊤ being the action of player i i i and a − i a^{-i} a − i denoting the joint action of all players except player i i i . Thus, the feasible action set in game Γ \Gamma Γ is A ∩ C \mathcal{A}\cap\mathcal{C} A ∩ C , where A = A 1 × ⋯ × A N \mathcal{A}=\mathcal{A}^{1}\times\cdots\times\mathcal{A}^{N} A = A 1 × ⋯ × A N and the coupled action set of agent i i i is A i ∩ C i ( a − i ) \mathcal{A}^{i}\cap\mathcal{C}^{i}(a^{-i}) A i ∩ C i ( a − i ) , where C i ( a − i ) = { a i ∈ R d i : g ( a ) ≤ 0 } \mathcal{C}^{i}(a^{-i})=\{a^{i}\in\mathbb{R}^{d_{i}}:g(a)\leq0\} C i ( a − i ) = { a i ∈ R d i : g ( a ) ≤ 0 } . Throughout this work, we assume that the individual action sets A i \mathcal{A}^{i} A i , i ∈ [ N ] i\in[N] i ∈ [ N ] , possess a structure that permits efficient computation of Euclidean projections.
A generalized Nash equilibrium (GNE) in game Γ \Gamma Γ represents a joint action from which no player has any incentive to unilaterally deviate.
Definition 1: A joint action a ⋆ ∈ A ∩ C a^{\star}\in\mathcal{A}\cap\mathcal{C} a ⋆ ∈ A ∩ C in the game Γ = ( N , { A i } , { J i } , C ) \Gamma=(N,\{\mathcal{A}^{i}\},\{\mathcal{J}^{i}\},\mathcal{C}) Γ = ( N , { A i } , { J i } , C ) with the coupling constraints C \mathcal{C} C is called a generalized Nash equilibrium (GNE) if J i ( a i , ⋆ , a − i , ⋆ ) ≤ J i ( a i , a − i , ⋆ ) \mathcal{J}^{i}(a^{i,\star},a^{-i,\star})\leq\mathcal{J}^{i}(a^{i},a^{-i,\star}) J i ( a i , ⋆ , a − i , ⋆ ) ≤ J i ( a i , a − i , ⋆ ) for any i ∈ [ N ] i\in[N] i ∈ [ N ] and a i ∈ A i ∩ C i ( a − i , ⋆ ) a^{i}\in\mathcal{A}^{i}\cap\mathcal{C}^{i}(a^{-i,\star}) a i ∈ A i ∩ C i ( a − i , ⋆ ) .
We consider convex games as defined below.
Assumption 1: The game under consideration is convex. Namely, (i) for all i ∈ [ N ] i\in[N] i ∈ [ N ] the cost function J i ( a i , a − i ) \mathcal{J}^{i}(a^{i},a^{-i}) J i ( a i , a − i ) is defined on R D \mathbb{R}^{D} R D , continuously differentiable in a a a and convex in a i a^{i} a i for fixed a − i a^{-i} a − i ; (ii) the set A \mathcal{A} A is closed and convex, g j : R D → R g_{j}:\mathbb{R}^{D}\to\mathbb{R} g j : R D → R is convex and continuously differentiable for any j ∈ [ m ] j\in[m] j ∈ [ m ] , and the set A ∩ C \mathcal{A}\cap\mathcal{C} A ∩ C is nonempty.
Given the differentiability of the cost functions, we can define the game’s pseudo-gradient mapping below.
Definition 2: The mapping M = [ M 1 , … , M N ] ⊤ : R D → R D M=[M^{1},\ldots,M^{N}]^{\top}:\mathbb{R}^{D}\to\mathbb{R}^{D} M = [ M 1 , … , M N ] ⊤ : R D → R D , referred to as the pseudo-gradient of Γ = ( N , { A i } , { J i } , C ) \Gamma=(N,\{\mathcal{A}^{i}\},\{\mathcal{J}^{i}\},\mathcal{C}) Γ = ( N , { A i } , { J i } , C ) , is defined by
M i ( a ) = [ M i , 1 ( a ) , … , M i , d i ( a ) ] , M^{i}(a)=[M^{i,1}(a),\ldots,M^{i,d_{i}}(a)], M i ( a ) = [ M i , 1 ( a ) , … , M i , d i ( a )] ,
M i , j ( a ) = ∂ J i ( a ) ∂ a i , j , a ∈ R D , j ∈ [ d i ] , i ∈ [ N ] . (2) M^{i,j}(a)=\frac{\partial\mathcal{J}^{i}(a)}{\partial a^{i,j}},\quad a\in\mathbb{R}^{D},\ j\in[d_{i}],\ i\in[N]. \tag*{(2)} M i , j ( a ) = ∂ a i , j ∂ J i ( a ) , a ∈ R D , j ∈ [ d i ] , i ∈ [ N ] . (2)
In general, characterizing and computing generalized Nash equilibria (GNE) in the game Γ \Gamma Γ is challenging [9 ] . In this work, we focus on the set of variational generalized Nash equilibria (v-GNE), which can be characterized as the solution to the variational inequality defined below.
Definition 3: The set of variational generalized Nash equilibria (v-GNE) in the game Γ \Gamma Γ is defined as the set of solutions to the following variational inequality problem:
Find a ⋆ ∈ A ∩ C : ⟨ M ( a ⋆ ) , a − a ⋆ ⟩ ≥ 0 , \text{Find }a^{\star}\in\mathcal{A}\cap\mathcal{C}:\langle M(a^{\star}),a-a^{\star}\rangle\geq0, Find a ⋆ ∈ A ∩ C : ⟨ M ( a ⋆ ) , a − a ⋆ ⟩ ≥ 0 ,
for all a ∈ A ∩ C a\in\mathcal{A}\cap\mathcal{C} a ∈ A ∩ C .
{#eq:3}
The next lemma states the relation between GNE and v-GNE (see [9 ] for the proof).
Lemma 1: Under Assumption 1, the set of generalized Nash equilibria in game Γ \Gamma Γ contains the set of variational generalized Nash equilibria, i.e., v-GNE ⊆ \subseteq ⊆ GNE.
Convexity of each J i \mathcal{J}^{i} J i in its own action a i a^{i} a i , as required in Assumption 1(i), does not imply monotonicity of the pseudo-gradient M M M . Monotonicity is an additional property of the joint mapping and is central to the analysis of variational inequality problems. In this work we are interested in games with a specific structure which allows for guaranteeing existence and uniqueness of a v-GNE, and are amenable to efficient distributed solution schemes. For this reason we make the following additional strong monotonicity assumption on M M M .
Assumption 2: The pseudo-gradient M M M is L M L_M L M -Lipschitz continuous and μ \mu μ -strongly monotone over A 2 A^2 A 2 .
Strong convexity of each J i J^i J i in its own action a i a^i a i alone does not imply strong monotonicity of M M M , since the latter also depends on the coupling between players. A similar strong monotonicity and Lipschitz continuity assumption is imposed in [5 ] , against which we compare in Section VI. Taking into account that A ∩ C ⊆ A A \cap C \subseteq A A ∩ C ⊆ A and the result on existence of solutions to VI (see, for example, [9 ] ), we conclude that under Assumptions 1–2 the game Γ \Gamma Γ possesses a unique v-GNE, i.e., a solution to (3).
Remark 1: A straightforward approach for computing a v-GNE is to apply gradient-play or projected-gradient-type methods to the variational inequality (3). Such methods are particularly efficient when the feasible set A ∩ C A \cap C A ∩ C admits a projection operator that can be computed in closed form or at low computational cost. However, when the coupling constraints defining C C C are nonlinear, evaluating the projection onto A ∩ C A \cap C A ∩ C is, in general, nontrivial and may itself require solving a separate optimization problem at each iteration.
This difficulty becomes more pronounced in the generalized Nash setting, where the constraint set is coupled through the actions of all players. As a result, the projection onto A ∩ C A \cap C A ∩ C cannot be carried out locally by each agent using only its own variables; instead, it depends on the joint action profile, which is not directly available under distributed information structures. Consequently, it is unclear how to efficiently implement projection-based VI methods in a decentralized manner when agents have access only to partial information about other players’ decisions. This motivates the development of alternative approaches that avoid explicit projections onto the coupled constraint set and rely instead on more tractable, distributed-friendly mechanisms.
To address such alternative approaches, in the following analysis we will require the distance to the feasible set A ∩ C A \cap C A ∩ C to be controlled by the constraint violation, at least on bounded sets.
Assumption 3: The feasible set A ∩ C A \cap C A ∩ C admits a local error bound on A A A , i.e., for every bounded set B ⊆ R d B \subseteq\mathbb{R}^d B ⊆ R d there exist κ B > 0 \kappa_B > 0 κ B > 0 such that dist ( a , A ∩ C ) ≤ κ B ∥ [ g ( a ) ] + ∥ \operatorname{dist}(a,A \cap C) \leq\kappa_B \|[g(a)]_+\| dist ( a , A ∩ C ) ≤ κ B ∥ [ g ( a ) ] + ∥ , ∀ a ∈ B ∩ A \forall a \in B \cap A ∀ a ∈ B ∩ A .
Assumption 3 holds, in particular, under Slater’s condition, i.e., if there exists a ˉ ∈ A \bar a \in A a ˉ ∈ A such that g j ( a ˉ ) < 0 g_j(\bar a) < 0 g j ( a ˉ ) < 0 for all j ∈ [ m ] j \in[m] j ∈ [ m ] (see Lemma 8 in Appendix B). It also holds, even globally on A A A and without a Slater point, when g g g is affine and A A A is polyhedral, by Hoffman’s error bound (see Remark 4 below). Note that Assumption 3 is not implied by Assumption 1 alone: for A = R A = \mathbb{R} A = R and g ( a ) = a 2 g(a)=a^2 g ( a ) = a 2 , we have A ∩ C = { 0 } A \cap C = \{0\} A ∩ C = { 0 } and dist ( a , A ∩ C ) = ∣ a ∣ \operatorname{dist}(a,A \cap C)=|a| dist ( a , A ∩ C ) = ∣ a ∣ , which cannot be bounded by κ B [ g ( a ) ] + = κ B a 2 \kappa_B[g(a)]_+ = \kappa_B a^2 κ B [ g ( a ) ] + = κ B a 2 near a = 0 a=0 a = 0 .
Remark 2: A natural alternative to projecting onto A ∩ C A \cap C A ∩ C is to work with the KKT system of (3), which requires a constraint qualification. Slater’s condition, together with the convexity of the game in Assumption 1, allows us to formulate the following equivalent Karush–Kuhn–Tucker (KKT) conditions characterizing a v-GNE a ⋆ a^\star a ⋆ : there exists λ ⋆ ∈ R m \lambda^\star\in\mathbb{R}^m λ ⋆ ∈ R m (a common Lagrange multiplier vector) such that
0 ∈ M ( a ⋆ ) + ∇ g ( a ⋆ ) T λ ⋆ + N A ( a ⋆ ) , a ⋆ ∈ A , g ( a ⋆ ) ≤ 0 , λ ⋆ ≥ 0 , ⟨ λ ⋆ , g ( a ⋆ ) ⟩ = 0 , (3) \begin{gathered}
0 \in M(a^\star)+\nabla g(a^\star)^\mathsf{T}\lambda^\star+N_A(a^\star),\\
a^\star\in A,\qquad g(a^\star)\leq0,\\
\lambda^\star\geq0,\\
\langle\lambda^\star,g(a^\star)\rangle=0, \tag*{(3)}
\end{gathered} 0 ∈ M ( a ⋆ ) + ∇ g ( a ⋆ ) T λ ⋆ + N A ( a ⋆ ) , a ⋆ ∈ A , g ( a ⋆ ) ≤ 0 , λ ⋆ ≥ 0 , ⟨ λ ⋆ , g ( a ⋆ )⟩ = 0 , (3)
The KKT conditions (3) are equivalent to the following variational inequality on the lifted (primal–dual) space:
Find ( a ⋆ , λ ⋆ ) ∈ A × R + m (a^\star,\lambda^\star)\in A\times\mathbb{R}_+^m ( a ⋆ , λ ⋆ ) ∈ A × R + m such that ∀ ( a , λ ) ∈ A × R + m \forall(a,\lambda)\in A\times\mathbb{R}_+^m ∀ ( a , λ ) ∈ A × R + m
⟨ [ M ( a ⋆ ) + ∇ g ( a ⋆ ) T λ ⋆ − g ( a ⋆ ) ] , [ a − a ⋆ λ − λ ⋆ ] ⟩ ≥ 0. (4) \left\langle
\begin{bmatrix}
M(a^\star)+\nabla g(a^\star)^\mathsf{T}\lambda^\star\\
-g(a^\star)
\end{bmatrix},
\begin{bmatrix}
a-a^\star\\
\lambda-\lambda^\star
\end{bmatrix}
\right\rangle\geq0. \tag*{(4)} ⟨ [ M ( a ⋆ ) + ∇ g ( a ⋆ ) T λ ⋆ − g ( a ⋆ ) ] , [ a − a ⋆ λ − λ ⋆ ] ⟩ ≥ 0. (4)
It is worth noting that in the case of linear coupling constraints g ( a ) ≤ 0 g(a)\leq0 g ( a ) ≤ 0 , the KKT conditions (3) characterize the v-GNE without Slater’s condition, provided that A A A is polyhedral or if A ∩ C ≠ ∅ A \cap C\neq\varnothing A ∩ C = ∅ [29 Cor. 23.8.1] . Moreover, in this case the operator
F ( a , λ ) = [ M ( a ) + ∇ g ( a ) T λ − g ( a ) ] F(a,\lambda)=
\begin{bmatrix}
M(a)+\nabla g(a)^\mathsf{T}\lambda\\
-g(a)
\end{bmatrix} F ( a , λ ) = [ M ( a ) + ∇ g ( a ) T λ − g ( a ) ]
is monotone and Lipschitz continuous under Assumption 2. However, strong monotonicity of M M M does not provide strong monotonicity of the lifted operator. Nevertheless, mere monotonicity and Lipschitz continuity enable the use of efficient algorithms and their distributed variants for solving the monotone VI (4) ; see, e.g., [5 , 33 ] . However, such methods require working in the lifted space and performing updates of the dual variable λ \lambda λ , which may be computationally and communication-wise expensive in distributed implementations.
Furthermore, for general nonlinear coupling constraints, the mapping F F F is not globally Lipschitz continuous on A × R + m A\times\mathbb{R}_+^m A × R + m . This limitation necessitates additional central coordination or adaptive stepsize strategies, such as line-search schemes, to ensure convergence of such methods [19 ] .
In contrast to lifted-space methods that require explicit introduction and updates of the dual variables λ \lambda λ and rely on solving a variational inequality with a potentially non-Lipschitz continuous operator, in this work we develop a primal approach. Our method operates directly in the space of the primal actions a a a and does not require maintaining or updating Lagrange multipliers, thereby avoiding the computational and communication overhead associated with dual variables and lifted formulations.
Motivated by the observations made in the previous section (see Remarks 1, 2), we now derive an equivalent reformulation of the considered GNE problem that is expressed entirely in terms of the primal decision variables and thus avoids the introduction of dual variables and the associated lifted-space variational inequality formulation.
Let us define any penalty profile ψ \psi ψ from the following class.
Definition 4: A function ψ : [ 0 , ∞ ) → [ 0 , ∞ ) \psi:[0,\infty)\to[0,\infty) ψ : [ 0 , ∞ ) → [ 0 , ∞ ) is an admissible penalty profile if ψ \psi ψ is continuously differentiable with ψ ′ ( 0 ) = 0 \psi'(0)=0 ψ ′ ( 0 ) = 0 , ψ \psi ψ is convex and nondecreasing, ψ ( s ) = 0 ⟺ s = 0 \psi(s)=0\Longleftrightarrow s=0 ψ ( s ) = 0 ⟺ s = 0 , and there exist S 0 > 0 S_0>0 S 0 > 0 and c ψ > 0 c_\psi>0 c ψ > 0 such that ψ ( s ) ≥ c ψ s min ( s , S 0 ) \psi(s)\geq c_\psi s\min(s,S_0) ψ ( s ) ≥ c ψ s min ( s , S 0 ) , ∀ s ≥ 0 \forall s\geq0 ∀ s ≥ 0 , i.e., ψ \psi ψ grows at least quadratically near the origin, ψ ( s ) ≥ c ψ s 2 \psi(s)\geq c_\psi s^2 ψ ( s ) ≥ c ψ s 2 for s ≤ S 0 s\leq S_0 s ≤ S 0 , and at least linearly beyond the threshold S 0 S_0 S 0 , ψ ( s ) ≥ c ψ S 0 s \psi(s)\geq c_\psi S_0s ψ ( s ) ≥ c ψ S 0 s for s > S 0 s>S_0 s > S 0 .
Example 1 (Quadratic profile): The profile ψ ( s ) = 1 2 s 2 \psi(s)=\frac{1}{2}s^2 ψ ( s ) = 2 1 s 2 satisfies Definition 4 with c ψ = 1 2 c_\psi=\frac{1}{2} c ψ = 2 1 for every choice of S 0 > 0 S_0>0 S 0 > 0 .
Example 2 (Huber profile): For ω > 0 \omega>0 ω > 0 , the capped profile
ψ ω ( s ) = { 1 2 s 2 , 0 ≤ s ≤ ω , ω s − 1 2 ω 2 , s > ω . \psi_\omega(s)=
\begin{cases}
\frac{1}{2}s^2, & 0\leq s\leq\omega,\\
\omega s-\frac{1}{2}\omega^2, & s>\omega.
\end{cases} ψ ω ( s ) = { 2 1 s 2 , ω s − 2 1 ω 2 , 0 ≤ s ≤ ω , s > ω .
coincides with the quadratic profile on [ 0 , ω ] [0,\omega] [ 0 , ω ] and grows only linearly beyond the cap ω \omega ω .
Given an admissible penalty profile ψ \psi ψ , let us define the penalty function for the coupling constraints as follows:
Ψ ( a ) : = ∑ j = 1 m ψ ( [ g j ( a ) ] + ) , (5) \Psi(\mathbf{a}) := \sum_{j=1}^{m} \psi([g_j(\mathbf{a})]_+), \tag*{(5)} Ψ ( a ) := j = 1 ∑ m ψ ([ g j ( a ) ] + ) , (5)
together with its gradient
P ( a ) : = ∇ Ψ ( a ) , P i ( a ) : = ∇ i Ψ ( a ) . (6) P(\mathbf{a}) := \nabla\Psi(\mathbf{a}), \qquad P^i(\mathbf{a}) := \nabla_i\Psi(\mathbf{a}). \tag*{(6)} P ( a ) := ∇Ψ ( a ) , P i ( a ) := ∇ i Ψ ( a ) . (6)
The smoothness properties of P P P used in the following analysis are addressed in Appendix A A A , Lemma 7 7 7 .
Proposition 1. Let Assumption 1(ii) hold. For any admissible penalty profile ψ \psi ψ : (i) Ψ ( a ) = 0 ⟺ a ∈ C \Psi(\mathbf{a})=0 \Longleftrightarrow\mathbf{a}\in C Ψ ( a ) = 0 ⟺ a ∈ C ; (ii) Ψ \Psi Ψ is convex, so that P = ∇ Ψ P=\nabla\Psi P = ∇Ψ is monotone over A A A .
Proof. (i) By Definition 4, ψ ( s ) = 0 ⟺ s = 0 \psi(s)=0 \Longleftrightarrow s=0 ψ ( s ) = 0 ⟺ s = 0 , so Ψ ( a ) = ∑ j ψ ( [ g j ( a ) ] + ) = 0 \Psi(\mathbf{a})=\sum_j\psi([g_j(\mathbf{a})]_+)=0 Ψ ( a ) = ∑ j ψ ([ g j ( a ) ] + ) = 0 iff [ g j ( a ) ] + = 0 [g_j(\mathbf{a})]_+=0 [ g j ( a ) ] + = 0 for all j ∈ [ m ] j\in[m] j ∈ [ m ] , iff g ( a ) ≤ 0 g(\mathbf{a})\le0 g ( a ) ≤ 0 , iff a ∈ C \mathbf{a}\in C a ∈ C . (ii) Since g j g_j g j is convex over A A A for every j ∈ [ m ] j\in[m] j ∈ [ m ] (Assumption 1(ii)), [ g j ] + [g_j]_+ [ g j ] + is convex; since ψ \psi ψ is convex and nondecreasing, the composition ψ ( [ g j ( ⋅ ) ] + ) \psi([g_j(\cdot)]_+) ψ ([ g j ( ⋅ ) ] + ) is convex, and a sum of convex functions is convex, so Ψ \Psi Ψ is convex. Convexity of Ψ \Psi Ψ implies monotonicity of P = ∇ Ψ P=\nabla\Psi P = ∇Ψ over A A A .
The set A ∩ C A\cap C A ∩ C is equal to the solution set SOL ( A , P ) \operatorname{SOL}(A,P) SOL ( A , P ) of the following VI ( A , P ) \operatorname{VI}(A,P) VI ( A , P ) :
find a ∈ A such that ⟨ P ( a ) , y − a ⟩ ≥ 0 ∀ y ∈ A . \text{find }\mathbf{a}\in A\text{ such that }\langle P(\mathbf{a}),\mathbf{y}-\mathbf{a}\rangle\ge0\quad\forall\mathbf{y}\in A. find a ∈ A such that ⟨ P ( a ) , y − a ⟩ ≥ 0 ∀ y ∈ A .
Indeed, since Ψ \Psi Ψ is convex and continuously differentiable, as shown in Lemma 7, SOL ( A , P ) = arg min A Ψ \operatorname{SOL}(A,P)=\operatorname*{arg\,min}_{A}\Psi SOL ( A , P ) = arg min A Ψ . By Proposition 1, since Ψ \Psi Ψ is nonnegative and vanishes exactly on C C C and A ∩ C ≠ ∅ A\cap C\ne\varnothing A ∩ C = ∅ as in Assumption 1(ii), this set equals A ∩ C A\cap C A ∩ C . Thus, the original v-GNE problem is equivalent to the following hierarchical VI:
find a ⋆ ∈ S L such that ⟨ M ( a ⋆ ) , y − a ⋆ ⟩ ≥ 0 ∀ y ∈ S L = SOL ( A , P ) . (7) \text{find }\mathbf{a}^{\star}\in S_L\text{ such that }\langle M(\mathbf{a}^{\star}),\mathbf{y}-\mathbf{a}^{\star}\rangle\ge0
\quad\forall\mathbf{y}\in S_L=\operatorname{SOL}(A,P). \tag*{(7)} find a ⋆ ∈ S L such that ⟨ M ( a ⋆ ) , y − a ⋆ ⟩ ≥ 0 ∀ y ∈ S L = SOL ( A , P ) . (7)
Since S L = A ∩ C S_L=A\cap C S L = A ∩ C , problem (8) is exactly VI ( A ∩ C , M ) \operatorname{VI}(A\cap C,M) VI ( A ∩ C , M ) . Representing its feasible set as SOL ( A , P ) \operatorname{SOL}(A,P) SOL ( A , P ) allows us to construct methods using evaluations of P P P and projections onto A A A , without projecting onto A ∩ C A\cap C A ∩ C .
We make the following assumptions regarding the constraint set and, thus, the mapping P P P .
Assumption 4: P P P is L P L_P L P -Lipschitz continuous over an open convex set U ⊆ R D U\subseteq\mathbb{R}^{D} U ⊆ R D containing A A A , with L P > 0 L_P>0 L P > 0 .
Remark 3: Assumption 4 is standard in the literature on hierarchical and bilevel variational inequalities. In particular, convergence and complexity analyses of algorithms for hierarchical VI problems typically require the operator defining the lower-level variational inequality to be monotone and Lipschitz continuous; see, e.g., [30 ] and the references therein. In our setting, the operator P P P arises as the gradient of the smooth penalty function Ψ \Psi Ψ , and Assumption 4 can be verified directly from the regularity properties of the constraint mapping g g g , as discussed below. If ψ ′ \psi' ψ ′ is Lipschitz continuous, as for the profiles of Examples 1 and 2, Lemma 7 with X = U X=U X = U yields Assumption 4 in each of the following cases.
The set A A A is compact and g g g is twice continuously differentiable. Choose a bounded open convex neighborhood U ‾ \overline{U} U of A A A ; compactness of U ‾ \overline{U} U gives the bounds required by Lemma 7.
∇ g \nabla g ∇ g is bounded and Lipschitz continuous over an open convex neighborhood U U U of A A A , and ψ ′ \psi' ψ ′ is bounded, as for the Huber profile, for which the constant ψ ‾ \overline{\psi} ψ of Lemma 7 equals m ω \sqrt{m}\,\omega m ω .
g g g is affine, so that the constant L g L_g L g of Lemma 7 equals 0 0 0 , and we may take U = R D U=\mathbb{R}^{D} U = R D .
Table 1. Centralized hierarchical regularization scheme
a i ( t + 1 ) = Π A i [ a i ( t ) − γ P i ( a ( t ) ) − η ϵ t M i ( a ( t ) ) ] . a^i(t+1)=\Pi_{A^i}\left[a^i(t)-\gamma P^i(a(t))-\eta\epsilon_tM^i(a(t))\right]. a i ( t + 1 ) = Π A i [ a i ( t ) − γ P i ( a ( t )) − η ϵ t M i ( a ( t )) ] .
The constant L P L_P L P used in the stepsize restrictions below is the Lipschitz constant bound on U U U .
However, in contrast to the general hierarchical VI setting considered in the existing literature, the lower-level problem in our reformulation possesses a specific structure. In particular, since P = ∇ Ψ P=\nabla\Psi P = ∇Ψ , where Ψ \Psi Ψ is a convex differentiable penalty function, the lower-level variational inequality VI ( A , P ) \operatorname{VI}(A,P) VI ( A , P ) is equivalent to a convex optimization problem. As will be shown later, this additional structure can be exploited in the convergence analysis of the proposed algorithmic scheme. In particular, unlike the extragradient-based methods developed for general hierarchical VIs [30 ] , which typically provide convergence guarantees for ergodic averages, the proposed approach allows us to establish explicit convergence rate guarantees for the last iterate.
Centralized Hierarchical Regularization Scheme
Before turning to the distributed setting, we first solve the hierarchical VI (7) by a centralized scheme, i.e., one in which the mappings P P P and M M M are evaluated at the true, commonly available joint action a ( t ) a(t) a ( t ) . This scheme both serves as a performance benchmark for, and forms the basis of the derivation of, the distributed algorithm of Section V V V .
Let each player i i i start from some action a i ( 0 ) ∈ A i a^i(0)\in A^i a i ( 0 ) ∈ A i and update it using first-order information, i.e., the local gradients M i M^i M i , together with the lower-level operator P i P^i P i , as summarized in Algorithm 1. Thus, the sequence of joint actions { a ( t ) } \{a(t)\} { a ( t )} is generated by
a ( t + 1 ) = Π A [ a ( t ) − γ P ( a ( t ) ) − η ϵ t M ( a ( t ) ) ] , (8) a(t+1)=\Pi_A\left[a(t)-\gamma P(a(t))-\eta\epsilon_tM(a(t))\right], \tag*{(8)} a ( t + 1 ) = Π A [ a ( t ) − γ P ( a ( t )) − η ϵ t M ( a ( t )) ] , (8)
which can be regarded as a single gradient step towards solving the regularized VI ( A , P + τ t M ) \operatorname{VI}(A,P+\tau_tM) VI ( A , P + τ t M ) , with effective regularization parameter τ t = η γ ϵ t \tau_t=\frac{\eta}{\gamma}\epsilon_t τ t = γ η ϵ t . Unlike the distributed scheme developed in Section V V V , here every agent has access to the full joint action a ( t ) a(t) a ( t ) , so that no consensus or estimation mechanism is required; Algorithm 1 may thus be viewed as the idealized limit of the distributed Algorithm 2 introduced below, in which consensus is instantaneous, i.e., every agent’s local estimate of the joint action coincides with a ( t ) a(t) a ( t ) at every t t t .
We analyze convergence of (9) using two complementary techniques. The first, presented next, follows the classical vanishing-regularization (Tikhonov) path-of-solutions approach to hierarchical and bilevel variational inequalities [13 ] , see also [1 ] , and yields a general, if conservative, convergence rate. The second, presented in Section IV-B, exploits the error bound assumption (see Assumption 5 below) directly and yields a sharper rate.
Analysis based on regularized solutions
To analyze the algorithm (9), we use the idea of [13 ] , which perturbs the lower-level operator P P P by a vanishing multiple of the upper-level operator M M M and reformulates the two-level problem as a single-level one.
Let us fix a positive parameter ε \varepsilon ε and define F ε ( a ) : = P ( a ) + ε M ( a ) F_{\varepsilon}(a) := P(a) + \varepsilon M(a) F ε ( a ) := P ( a ) + εM ( a ) . Consider the following regularized VI ( A , F ε ) \operatorname{VI}(A,F_{\varepsilon}) VI ( A , F ε ) : find a ε ⋆ ∈ A a_{\varepsilon}^{\star} \in A a ε ⋆ ∈ A such that
⟨ F ε ( a ε ⋆ ) , y − a ε ⋆ ⟩ ≥ 0 , ∀ y ∈ A . (9) \langle F_{\varepsilon}(a_{\varepsilon}^{\star}),y-a_{\varepsilon}^{\star}\rangle\ge0,\quad\forall y\in A. \tag*{(9)} ⟨ F ε ( a ε ⋆ ) , y − a ε ⋆ ⟩ ≥ 0 , ∀ y ∈ A . (9)
The next proposition connects solutions to VI ( A , F ε ) \operatorname{VI}(A,F_{\varepsilon}) VI ( A , F ε ) with those of the hierarchical VI (7) , and thus with the v-GNE of Γ \Gamma Γ .
Proposition 2: Let Assumptions 1 and 2 hold. Then for any ε > 0 \varepsilon>0 ε > 0 the problem VI ( A , F ε ) \operatorname{VI}(A,F_{\varepsilon}) VI ( A , F ε ) has a unique solution a ε ⋆ a_{\varepsilon}^{\star} a ε ⋆ , and this solution converges to the unique v-GNE a ⋆ a^{\star} a ⋆ of Γ \Gamma Γ as ε → 0 \varepsilon\to0 ε → 0 . Moreover, for any two positive ε 1 \varepsilon_1 ε 1 and ε 2 \varepsilon_2 ε 2 ,
∥ a ε 1 ⋆ − a ε 2 ⋆ ∥ ≤ ∣ ε 2 − ε 1 ∣ ε 2 μ ∥ M ( a ε 1 ⋆ ) ∥ . \lVert a_{\varepsilon_1}^{\star}-a_{\varepsilon_2}^{\star}\rVert\le\frac{|\varepsilon_2-\varepsilon_1|}{\varepsilon_2\mu}\lVert M(a_{\varepsilon_1}^{\star})\rVert. ∥ a ε 1 ⋆ − a ε 2 ⋆ ∥ ≤ ε 2 μ ∣ ε 2 − ε 1 ∣ ∥ M ( a ε 1 ⋆ )∥ .
Proof: Since P P P is monotone and M M M is μ \mu μ -strongly monotone on A A A , the continuous operator F ε F_{\varepsilon} F ε is ε μ \varepsilon\mu ε μ -strongly monotone on A A A , so VI ( A , F ε ) \operatorname{VI}(A,F_{\varepsilon}) VI ( A , F ε ) has a unique solution [10 ] . Let z ∈ S L z\in S_L z ∈ S L . Since Ψ \Psi Ψ is convex and Ψ ( z ) = 0 \Psi(z)=0 Ψ ( z ) = 0 , we have Ψ ( a ε ⋆ ) ≤ ⟨ P ( a ε ⋆ ) , a ε ⋆ − z ⟩ \Psi(a_{\varepsilon}^{\star})\le\langle P(a_{\varepsilon}^{\star}),a_{\varepsilon}^{\star}-z\rangle Ψ ( a ε ⋆ ) ≤ ⟨ P ( a ε ⋆ ) , a ε ⋆ − z ⟩ . Combined with the VI inequality at y = z y=z y = z , this gives
0 ≤ Ψ ( a ε ⋆ ) ≤ ε ⟨ M ( a ε ⋆ ) , z − a ε ⋆ ⟩ , ∀ z ∈ S L . (10) 0\le\Psi(a_{\varepsilon}^{\star})\le\varepsilon\langle M(a_{\varepsilon}^{\star}),z-a_{\varepsilon}^{\star}\rangle,\quad\forall z\in S_L. \tag*{(10)} 0 ≤ Ψ ( a ε ⋆ ) ≤ ε ⟨ M ( a ε ⋆ ) , z − a ε ⋆ ⟩ , ∀ z ∈ S L . (10)
Taking z = a ⋆ z=a^{\star} z = a ⋆ and using μ \mu μ -strong monotonicity of M M M ,
μ ∥ a ε ⋆ − a ⋆ ∥ 2 ≤ ⟨ M ( a ε ⋆ ) − M ( a ⋆ ) , a ε ⋆ − a ⋆ ⟩ ≤ − ⟨ M ( a ⋆ ) , a ε ⋆ − a ⋆ ⟩ . (11) \mu\lVert a_{\varepsilon}^{\star}-a^{\star}\rVert^2\le\langle M(a_{\varepsilon}^{\star})-M(a^{\star}),a_{\varepsilon}^{\star}-a^{\star}\rangle
\le-\langle M(a^{\star}),a_{\varepsilon}^{\star}-a^{\star}\rangle. \tag*{(11)} μ ∥ a ε ⋆ − a ⋆ ∥ 2 ≤ ⟨ M ( a ε ⋆ ) − M ( a ⋆ ) , a ε ⋆ − a ⋆ ⟩ ≤ − ⟨ M ( a ⋆ ) , a ε ⋆ − a ⋆ ⟩ . (11)
so that ∥ a ε ⋆ − a ⋆ ∥ ≤ ∥ M ( a ⋆ ) ∥ / μ \lVert a_{\varepsilon}^{\star}-a^{\star}\rVert\le\lVert M(a^{\star})\rVert/\mu ∥ a ε ⋆ − a ⋆ ∥ ≤ ∥ M ( a ⋆ )∥ / μ for every ε > 0 \varepsilon>0 ε > 0 . In particular, { a ε ⋆ } \{a_{\varepsilon}^{\star}\} { a ε ⋆ } is bounded, so every sequence of positive numbers ε k → 0 \varepsilon_k\to0 ε k → 0 has a subsequence along which a ε k ⋆ a_{\varepsilon_k}^{\star} a ε k ⋆ converges. As M M M is Lipschitz continuous, ∥ M ( a ε ⋆ ) ∥ \lVert M(a_{\varepsilon}^{\star})\rVert ∥ M ( a ε ⋆ )∥ is bounded as well, and (10) with z = a ⋆ z=a^{\star} z = a ⋆ gives Ψ ( a ε ⋆ ) → 0 \Psi(a_{\varepsilon}^{\star})\to0 Ψ ( a ε ⋆ ) → 0 as ε → 0 \varepsilon\to0 ε → 0 . Now let a ˉ \bar a a ˉ be a cluster point of { a ε ⋆ } \{a_{\varepsilon}^{\star}\} { a ε ⋆ } as ε → 0 \varepsilon\to0 ε → 0 , that is, a ε k ⋆ → a ˉ a_{\varepsilon_k}^{\star}\to\bar a a ε k ⋆ → a ˉ for some sequence of positive numbers ε k → 0 \varepsilon_k\to0 ε k → 0 . Since A A A is closed and Ψ \Psi Ψ is continuous, a ˉ ∈ A \bar a\in A a ˉ ∈ A and Ψ ( a ˉ ) = 0 \Psi(\bar a)=0 Ψ ( a ˉ ) = 0 , so a ˉ ∈ S L \bar a\in S_L a ˉ ∈ S L by Proposition 1. Dividing (10) by ε k \varepsilon_k ε k and passing to the limit gives ⟨ M ( a ˉ ) , z − a ˉ ⟩ ≥ 0 \langle M(\bar a),z-\bar a\rangle\ge0 ⟨ M ( a ˉ ) , z − a ˉ ⟩ ≥ 0 for all z ∈ S L z\in S_L z ∈ S L , so a ˉ \bar a a ˉ solves VI ( S L , M ) \operatorname{VI}(S_L,M) VI ( S L , M ) . Since this VI has the unique solution a ⋆ a^{\star} a ⋆ , every cluster point equals a ⋆ a^{\star} a ⋆ . Hence a ε ⋆ → a ⋆ a_{\varepsilon}^{\star}\to a^{\star} a ε ⋆ → a ⋆ . Next, let a ε 1 ⋆ a_{\varepsilon_1}^{\star} a ε 1 ⋆ and a ε 2 ⋆ a_{\varepsilon_2}^{\star} a ε 2 ⋆ be the solutions to VI ( A , F ε 1 ) \operatorname{VI}(A,F_{\varepsilon_1}) VI ( A , F ε 1 ) and VI ( A , F ε 2 ) \operatorname{VI}(A,F_{\varepsilon_2}) VI ( A , F ε 2 ) , respectively. Hence,
⟨ P ( a ε 1 ⋆ ) + ε 1 M ( a ε 1 ⋆ ) , a ε 2 ⋆ − a ε 1 ⋆ ⟩ ≥ 0 , \langle P(a_{\varepsilon_1}^{\star})+\varepsilon_1M(a_{\varepsilon_1}^{\star}),a_{\varepsilon_2}^{\star}-a_{\varepsilon_1}^{\star}\rangle\ge0, ⟨ P ( a ε 1 ⋆ ) + ε 1 M ( a ε 1 ⋆ ) , a ε 2 ⋆ − a ε 1 ⋆ ⟩ ≥ 0 ,
⟨ P ( a ε 2 ⋆ ) + ε 2 M ( a ε 2 ⋆ ) , a ε 1 ⋆ − a ε 2 ⋆ ⟩ ≥ 0. \langle P(a_{\varepsilon_2}^{\star})+\varepsilon_2M(a_{\varepsilon_2}^{\star}),a_{\varepsilon_1}^{\star}-a_{\varepsilon_2}^{\star}\rangle\ge0. ⟨ P ( a ε 2 ⋆ ) + ε 2 M ( a ε 2 ⋆ ) , a ε 1 ⋆ − a ε 2 ⋆ ⟩ ≥ 0.
Summing up the inequalities above and using monotonicity of P P P and μ \mu μ -strong monotonicity of M M M (Assumption 2), we conclude that
0 ≤ ⟨ ε 1 M ( a ε 1 ⋆ ) − ε 2 M ( a ε 2 ⋆ ) , a ε 2 ⋆ − a ε 1 ⋆ ⟩ = ⟨ ε 1 M ( a ε 1 ⋆ ) − ε 2 M ( a ε 1 ⋆ ) , a ε 2 ⋆ − a ε 1 ⋆ ⟩ + ⟨ ε 2 M ( a ε 1 ⋆ ) − ε 2 M ( a ε 2 ⋆ ) , a ε 2 ⋆ − a ε 1 ⋆ ⟩ ≤ ∣ ε 1 − ε 2 ∣ ∥ M ( a ε 1 ⋆ ) ∥ ∥ a ε 2 ⋆ − a ε 1 ⋆ ∥ − ε 2 μ ∥ a ε 2 ⋆ − a ε 1 ⋆ ∥ 2 . \begin{aligned}
0&\le\langle\varepsilon_1M(a_{\varepsilon_1}^{\star})-\varepsilon_2M(a_{\varepsilon_2}^{\star}),a_{\varepsilon_2}^{\star}-a_{\varepsilon_1}^{\star}\rangle\\
&=\langle\varepsilon_1M(a_{\varepsilon_1}^{\star})-\varepsilon_2M(a_{\varepsilon_1}^{\star}),a_{\varepsilon_2}^{\star}-a_{\varepsilon_1}^{\star}\rangle\\
&\quad+\langle\varepsilon_2M(a_{\varepsilon_1}^{\star})-\varepsilon_2M(a_{\varepsilon_2}^{\star}),a_{\varepsilon_2}^{\star}-a_{\varepsilon_1}^{\star}\rangle\\
&\le|\varepsilon_1-\varepsilon_2|\lVert M(a_{\varepsilon_1}^{\star})\rVert\lVert a_{\varepsilon_2}^{\star}-a_{\varepsilon_1}^{\star}\rVert-\varepsilon_2\mu\lVert a_{\varepsilon_2}^{\star}-a_{\varepsilon_1}^{\star}\rVert^2.
\end{aligned} 0 ≤ ⟨ ε 1 M ( a ε 1 ⋆ ) − ε 2 M ( a ε 2 ⋆ ) , a ε 2 ⋆ − a ε 1 ⋆ ⟩ = ⟨ ε 1 M ( a ε 1 ⋆ ) − ε 2 M ( a ε 1 ⋆ ) , a ε 2 ⋆ − a ε 1 ⋆ ⟩ + ⟨ ε 2 M ( a ε 1 ⋆ ) − ε 2 M ( a ε 2 ⋆ ) , a ε 2 ⋆ − a ε 1 ⋆ ⟩ ≤ ∣ ε 1 − ε 2 ∣ ∥ M ( a ε 1 ⋆ )∥ ∥ a ε 2 ⋆ − a ε 1 ⋆ ∥ − ε 2 μ ∥ a ε 2 ⋆ − a ε 1 ⋆ ∥ 2 .
Thus,
∥ a ε 2 ⋆ − a ε 1 ⋆ ∥ ≤ ∣ ε 2 − ε 1 ∣ ε 2 μ ∥ M ( a ε 1 ⋆ ) ∥ . \lVert a_{\varepsilon_2}^{\star}-a_{\varepsilon_1}^{\star}\rVert\le\frac{|\varepsilon_2-\varepsilon_1|}{\varepsilon_2\mu}\lVert M(a_{\varepsilon_1}^{\star})\rVert. ∥ a ε 2 ⋆ − a ε 1 ⋆ ∥ ≤ ε 2 μ ∣ ε 2 − ε 1 ∣ ∥ M ( a ε 1 ⋆ )∥ .
The following auxiliary result is an immediate consequence of admissibility (Definition 4).
Lemma 2: Let ψ \psi ψ be an admissible penalty profile with constants S 0 , c ψ > 0 S_0,c_{\psi}>0 S 0 , c ψ > 0 as in Definition 4. If a ∈ R D a\in\mathbb{R}^{D} a ∈ R D satisfies ∥ [ g ( a ) ] + ∥ ≤ S 0 \lVert[g(a)]_{+}\rVert\le S_0 ∥[ g ( a ) ] + ∥ ≤ S 0 , then Ψ ( a ) ≥ c ψ ∥ [ g ( a ) ] + ∥ 2 \Psi(a)\ge c_{\psi}\lVert[g(a)]_{+}\rVert^2 Ψ ( a ) ≥ c ψ ∥[ g ( a ) ] + ∥ 2 .
Proof: Since ∥ [ g ( a ) ] + ∥ ≤ S 0 \lVert[g(a)]_{+}\rVert\le S_0 ∥[ g ( a ) ] + ∥ ≤ S 0 , every coordinate satisfies [ g j ( a ) ] + ≤ ∥ [ g ( a ) ] + ∥ ≤ S 0 [g_j(a)]_{+}\le\lVert[g(a)]_{+}\rVert\le S_0 [ g j ( a ) ] + ≤ ∥[ g ( a ) ] + ∥ ≤ S 0 , so Definition 4 gives ψ ( [ g j ( a ) ] + ) ≥ c ψ [ g j ( a ) ] + min ( [ g j ( a ) ] + , S 0 ) = c ψ [ g j ( a ) ] + 2 \psi([g_j(a)]_{+})\ge c_{\psi}[g_j(a)]_{+}\min([g_j(a)]_{+},S_0)=c_{\psi}[g_j(a)]_{+}^{2} ψ ([ g j ( a ) ] + ) ≥ c ψ [ g j ( a ) ] + min ([ g j ( a ) ] + , S 0 ) = c ψ [ g j ( a ) ] + 2 for every j ∈ [ m ] j\in[m] j ∈ [ m ] . Summing over j j j and recalling (5) gives the claim.
The next proposition complements Proposition 2 with a rate: it characterizes the distance between a ε ⋆ a_{\varepsilon}^{\star} a ε ⋆ (the solution to the regularized VI( A , F ε ) (A,F_{\varepsilon}) ( A , F ε ) ) and a ⋆ a^{\star} a ⋆ (the v-GNE in Γ \Gamma Γ ) under the additional Assumption 3.
Proposition 3: Let Assumptions 1, 2, and 3 hold. Then
∥ a ε ⋆ − a ⋆ ∥ = O ( ε ) as ε → 0. \lVert a_{\varepsilon}^{\star}-a^{\star}\rVert=O(\sqrt{\varepsilon})\quad\text{as }\varepsilon\to0. ∥ a ε ⋆ − a ⋆ ∥ = O ( ε ) as ε → 0.
Proof: Recall that S L = A ∩ C S_L=A\cap C S L = A ∩ C . For each ε > 0 \varepsilon>0 ε > 0 , let s ε ⋆ = Π S L ( a ε ⋆ ) s_{\varepsilon}^{\star}=\Pi_{S_L}(a_{\varepsilon}^{\star}) s ε ⋆ = Π S L ( a ε ⋆ ) and d ε = ∥ a ε ⋆ − s ε ⋆ ∥ = dist ( a ε ⋆ , S L ) d_{\varepsilon}=\lVert a_{\varepsilon}^{\star}-s_{\varepsilon}^{\star}\rVert=\operatorname{dist}(a_{\varepsilon}^{\star},S_L) d ε = ∥ a ε ⋆ − s ε ⋆ ∥ = dist ( a ε ⋆ , S L ) . By Proposition 2, a ε ⋆ → a ⋆ a_{\varepsilon}^{\star}\to a^{\star} a ε ⋆ → a ⋆ as ε → 0 \varepsilon\to0 ε → 0 , so { a ε ⋆ } \{a_{\varepsilon}^{\star}\} { a ε ⋆ } eventually lies in some fixed compact ball B ⊆ R D B\subseteq\mathbb{R}^{D} B ⊆ R D . By Assumption 3, there exists a constant κ B > 0 \kappa_B>0 κ B > 0 such that
dist ( a , S L ) ≤ κ B ∥ [ g ( a ) ] + ∥ , ∀ a ∈ B ∩ A . \operatorname{dist}(a,S_L)\le\kappa_B\lVert[g(a)]_{+}\rVert,\quad\forall a\in B\cap A. dist ( a , S L ) ≤ κ B ∥[ g ( a ) ] + ∥ , ∀ a ∈ B ∩ A .
Moreover, since g g g is continuous and g ( a ⋆ ) ≤ 0 g(a^{\star})\le0 g ( a ⋆ ) ≤ 0 (as a ⋆ ∈ S L a^{\star}\in S_L a ⋆ ∈ S L ), ∥ [ g ( a ε ⋆ ) ] + ∥ → 0 \lVert[g(a_{\varepsilon}^{\star})]_{+}\rVert\to0 ∥[ g ( a ε ⋆ ) ] + ∥ → 0 as ε → 0 \varepsilon\to0 ε → 0 . Hence, for all sufficiently small ε \varepsilon ε , a ε ⋆ ∈ B ∩ A a_{\varepsilon}^{\star}\in B\cap A a ε ⋆ ∈ B ∩ A and ∥ [ g ( a ε ⋆ ) ] + ∥ ≤ S 0 \lVert[g(a_{\varepsilon}^{\star})]_{+}\rVert\le S_0 ∥[ g ( a ε ⋆ ) ] + ∥ ≤ S 0 , so that Lemma 2 implies
Ψ ( a ε ⋆ ) = ∑ j = 1 m ψ ( [ g j ( a ε ⋆ ) ] + ) ≥ c ψ ∥ [ g ( a ε ⋆ ) ] + ∥ 2 . \Psi(a_{\varepsilon}^{\star})=\sum_{j=1}^{m}\psi([g_j(a_{\varepsilon}^{\star})]_{+})\ge c_{\psi}\lVert[g(a_{\varepsilon}^{\star})]_{+}\rVert^2. Ψ ( a ε ⋆ ) = j = 1 ∑ m ψ ([ g j ( a ε ⋆ ) ] + ) ≥ c ψ ∥[ g ( a ε ⋆ ) ] + ∥ 2 .
Combining the last inequalities above (applied at a = a ε ⋆ ∈ B ∩ A a=a_{\varepsilon}^{\star}\in B\cap A a = a ε ⋆ ∈ B ∩ A ), for all sufficiently small ε \varepsilon ε , we conclude that
Ψ ( a ε ⋆ ) ≥ c ψ κ B 2 d ε 2 . (12) \Psi(a_{\varepsilon}^{\star})\ge\frac{c_{\psi}}{\kappa_B^2}d_{\varepsilon}^{2}. \tag*{(12)} Ψ ( a ε ⋆ ) ≥ κ B 2 c ψ d ε 2 . (12)
By (10) with z = s ε ⋆ z=s_{\varepsilon}^{\star} z = s ε ⋆ ,
Ψ ( a ε ⋆ ) ≤ ε ⟨ M ( a ε ⋆ ) , s ε ⋆ − a ε ⋆ ⟩ ≤ ε ∥ M ( a ε ⋆ ) ∥ d ε . (13) \Psi(a_{\varepsilon}^{\star})\le\varepsilon\langle M(a_{\varepsilon}^{\star}),s_{\varepsilon}^{\star}-a_{\varepsilon}^{\star}\rangle\le\varepsilon\lVert M(a_{\varepsilon}^{\star})\rVert d_{\varepsilon}. \tag*{(13)} Ψ ( a ε ⋆ ) ≤ ε ⟨ M ( a ε ⋆ ) , s ε ⋆ − a ε ⋆ ⟩ ≤ ε ∥ M ( a ε ⋆ )∥ d ε . (13)
Since a ε ⋆ → a ⋆ a_{\varepsilon}^{\star}\to a^{\star} a ε ⋆ → a ⋆ (Proposition 2) and M M M is continuous, there exists M ‾ > 0 \overline M>0 M > 0 such that ∥ M ( a ε ⋆ ) ∥ ≤ M ‾ \lVert M(a_{\varepsilon}^{\star})\rVert\le\overline M ∥ M ( a ε ⋆ )∥ ≤ M for sufficiently small ε \varepsilon ε . Therefore, by (12) and (13) ,
c ψ κ B 2 d ε 2 ≤ M ‾ ε d ε . \frac{c_{\psi}}{\kappa_B^2}d_{\varepsilon}^{2}\le\overline M\varepsilon d_{\varepsilon}. κ B 2 c ψ d ε 2 ≤ M ε d ε .
Thus, d ε ≤ κ B 2 c ψ M ‾ ε d_{\varepsilon}\le\frac{\kappa_B^2}{c_{\psi}}\overline M\varepsilon d ε ≤ c ψ κ B 2 M ε , which proves dist ( a ε ⋆ , S L ) = O ( ε ) \operatorname{dist}(a_{\varepsilon}^{\star},S_L)=O(\varepsilon) dist ( a ε ⋆ , S L ) = O ( ε ) .
By (11) ,
μ ∥ a ε ⋆ − a ⋆ ∥ 2 ≤ − ⟨ M ( a ⋆ ) , a ε ⋆ − s ε ⋆ ⟩ − ⟨ M ( a ⋆ ) , s ε ⋆ − a ⋆ ⟩ . (14) \mu\lVert a_{\varepsilon}^{\star}-a^{\star}\rVert^2\le-\langle M(a^{\star}),a_{\varepsilon}^{\star}-s_{\varepsilon}^{\star}\rangle-\langle M(a^{\star}),s_{\varepsilon}^{\star}-a^{\star}\rangle. \tag*{(14)} μ ∥ a ε ⋆ − a ⋆ ∥ 2 ≤ − ⟨ M ( a ⋆ ) , a ε ⋆ − s ε ⋆ ⟩ − ⟨ M ( a ⋆ ) , s ε ⋆ − a ⋆ ⟩ . (14)
Since s ε ⋆ ∈ S L s_{\varepsilon}^{\star}\in S_L s ε ⋆ ∈ S L and a ⋆ a^{\star} a ⋆ solves VI ( S L , M ) \operatorname{VI}(S_L,M) VI ( S L , M ) , we have ⟨ M ( a ⋆ ) , s ε ⋆ − a ⋆ ⟩ ≥ 0 \langle M(a^{\star}),s_{\varepsilon}^{\star}-a^{\star}\rangle\ge0 ⟨ M ( a ⋆ ) , s ε ⋆ − a ⋆ ⟩ ≥ 0 . Therefore, from (14) ,
μ ∥ a ε ⋆ − a ⋆ ∥ 2 ≤ − ⟨ M ( a ⋆ ) , a ε ⋆ − s ε ⋆ ⟩ ≤ ∥ M ( a ⋆ ) ∥ ∥ a ε ⋆ − s ε ⋆ ∥ . \mu\lVert a_{\varepsilon}^{\star}-a^{\star}\rVert^2\le-\langle M(a^{\star}),a_{\varepsilon}^{\star}-s_{\varepsilon}^{\star}\rangle\le\lVert M(a^{\star})\rVert\lVert a_{\varepsilon}^{\star}-s_{\varepsilon}^{\star}\rVert. μ ∥ a ε ⋆ − a ⋆ ∥ 2 ≤ − ⟨ M ( a ⋆ ) , a ε ⋆ − s ε ⋆ ⟩ ≤ ∥ M ( a ⋆ )∥ ∥ a ε ⋆ − s ε ⋆ ∥ .
Hence, μ ∥ a ε ⋆ − a ⋆ ∥ 2 ≤ ∥ M ( a ⋆ ) ∥ dist ( a ε ⋆ , S L ) \mu\lVert a_{\varepsilon}^{\star}-a^{\star}\rVert^2\le\lVert M(a^{\star})\rVert\operatorname{dist}(a_{\varepsilon}^{\star},S_L) μ ∥ a ε ⋆ − a ⋆ ∥ 2 ≤ ∥ M ( a ⋆ )∥ dist ( a ε ⋆ , S L ) . Since dist ( a ε ⋆ , S L ) = O ( ε ) \operatorname{dist}(a_{\varepsilon}^{\star},S_L)=O(\varepsilon) dist ( a ε ⋆ , S L ) = O ( ε ) , we conclude that ∥ a ε ⋆ − a ⋆ ∥ = O ( ε ) \lVert a_{\varepsilon}^{\star}-a^{\star}\rVert=O(\sqrt{\varepsilon}) ∥ a ε ⋆ − a ⋆ ∥ = O ( ε ) . ■
Next we prove the following convergence result for the centralized algorithm (8) .
Theorem 1: Let Assumptions 1–4 hold. Let the stepsize γ \gamma γ satisfy 0 < γ < 2 L P 0<\gamma<\frac{2}{L_P} 0 < γ < L P 2 , let η > 0 \eta>0 η > 0 , and let the regularization parameter be set up as ε t = E ( t + 1 ) ϵ \varepsilon_t=\frac{E}{(t+1)^{\epsilon}} ε t = ( t + 1 ) ϵ E for some E > 0 E>0 E > 0 and ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) . Then the sequence generated by (8) converges to the unique v-GNE a ⋆ a^{\star} a ⋆ in Γ \Gamma Γ and
∥ a ( t ) − a ⋆ ∥ 2 = O ( 1 t min { 1 − 2 ϵ , 2 − 2 ϵ } ) . \lVert a(t)-a^{\star}\rVert^2=O\left(\frac{1}{t^{\min\{1-2\epsilon,2-2\epsilon\}}}\right). ∥ a ( t ) − a ⋆ ∥ 2 = O ( t m i n { 1 − 2 ϵ , 2 − 2 ϵ } 1 ) .
Proof: Set τ t = η γ ε t \tau_t=\frac{\eta}{\gamma}\varepsilon_t τ t = γ η ε t , and denote by a τ t ⋆ = a ε t ⋆ a_{\tau_t}^{\star}=a_{\varepsilon_t}^{\star} a τ t ⋆ = a ε t ⋆ the unique solution to VI ( A , P + τ t M ) \operatorname{VI}(A,P+\tau_tM) VI ( A , P + τ t M ) . Since τ t = η E / γ ( t + 1 ) ϵ \tau_t=\frac{\eta E/\gamma}{(t+1)^{\epsilon}} τ t = ( t + 1 ) ϵ η E / γ , Propositions 2 and 3 apply with ε \varepsilon ε replaced by τ t \tau_t τ t .
By the projection identity for VI solutions, written in the form of (8) , we have
a t ⋆ = Π A [ a τ t ⋆ − γ ( P ( a τ t ⋆ ) + τ t M ( a τ t ⋆ ) ) ] = Π A [ a t ⋆ − γ P ( a t ⋆ ) − γ η t M ( a t ⋆ ) ] . \begin{aligned}
a_t^{\star}&=\Pi_A\left[a_{\tau_t}^{\star}-\gamma\left(P(a_{\tau_t}^{\star})+\tau_tM(a_{\tau_t}^{\star})\right)\right]\\
&=\Pi_A\left[a_t^{\star}-\gamma P(a_t^{\star})-\gamma\eta_tM(a_t^{\star})\right].
\end{aligned} a t ⋆ = Π A [ a τ t ⋆ − γ ( P ( a τ t ⋆ ) + τ t M ( a τ t ⋆ ) ) ] = Π A [ a t ⋆ − γ P ( a t ⋆ ) − γ η t M ( a t ⋆ ) ] .
Define F t ( a ) = F τ t ( a ) = P ( a ) + τ t M ( a ) F_t(a)=F_{\tau_t}(a)=P(a)+\tau_tM(a) F t ( a ) = F τ t ( a ) = P ( a ) + τ t M ( a ) , so that γ F t ( a ) = γ P ( a ) + η ε t M ( a ) \gamma F_t(a)=\gamma P(a)+\eta\varepsilon_tM(a) γ F t ( a ) = γ P ( a ) + η ε t M ( a ) matches (9). Then by the nonexpansiveness of Π A \Pi_A Π A , we obtain
∥ a ( t + 1 ) − a τ t ∗ ∥ 2 ≤ ∥ a ( t ) − a τ t ∗ − γ ( F t ( a ( t ) ) − F t ( a τ t ∗ ) ) ∥ 2 = ∥ a ( t ) − a τ t ∗ ∥ 2 − 2 γ ⟨ F t ( a ( t ) ) − F t ( a τ t ∗ ) , a ( t ) − a τ t ∗ ⟩ + γ 2 ∥ F t ( a ( t ) ) − F t ( a τ t ∗ ) ∥ 2 . (15) \begin{aligned}
\|a(t+1)-a_{\tau_t}^*\|^2
&\leq\|a(t)-a_{\tau_t}^*-\gamma(F_t(a(t))-F_t(a_{\tau_t}^*))\|^2\\
&=\|a(t)-a_{\tau_t}^*\|^2-2\gamma\langle F_t(a(t))-F_t(a_{\tau_t}^*),a(t)-a_{\tau_t}^*\rangle\\
&\qquad+\gamma^2\|F_t(a(t))-F_t(a_{\tau_t}^*)\|^2. \tag*{(15)}
\end{aligned} ∥ a ( t + 1 ) − a τ t ∗ ∥ 2 ≤ ∥ a ( t ) − a τ t ∗ − γ ( F t ( a ( t )) − F t ( a τ t ∗ )) ∥ 2 = ∥ a ( t ) − a τ t ∗ ∥ 2 − 2 γ ⟨ F t ( a ( t )) − F t ( a τ t ∗ ) , a ( t ) − a τ t ∗ ⟩ + γ 2 ∥ F t ( a ( t )) − F t ( a τ t ∗ ) ∥ 2 . (15)
Using cocoercivity of P P P over A A A (which holds since Ψ \Psi Ψ is convex, P = ∇ Ψ P=\nabla\Psi P = ∇Ψ and P P P is L P L_P L P -Lipschitz on the open convex set U ⊇ A U\supseteq A U ⊇ A by Assumption 4, see [26 Thm. 3.1] ),
⟨ P ( a ( t ) ) − P ( a τ t ∗ ) , a ( t ) − a τ t ∗ ⟩ ≥ 1 L P ∥ P ( a ( t ) ) − P ( a τ t ∗ ) ∥ 2 , \langle P(a(t))-P(a_{\tau_t}^*),a(t)-a_{\tau_t}^*\rangle\geq\frac{1}{L_P}\|P(a(t))-P(a_{\tau_t}^*)\|^2, ⟨ P ( a ( t )) − P ( a τ t ∗ ) , a ( t ) − a τ t ∗ ⟩ ≥ L P 1 ∥ P ( a ( t )) − P ( a τ t ∗ ) ∥ 2 ,
together with Lipschitz continuity and μ \mu μ -strong monotonicity of M M M (Assumption 2), and the weighted Young inequality ∥ u + v ∥ 2 ≤ ( 1 + δ ) ∥ u ∥ 2 + ( 1 + δ − 1 ) ∥ v ∥ 2 \|u+v\|^2\leq(1+\delta)\|u\|^2+(1+\delta^{-1})\|v\|^2 ∥ u + v ∥ 2 ≤ ( 1 + δ ) ∥ u ∥ 2 + ( 1 + δ − 1 ) ∥ v ∥ 2 with 1 + δ = 2 γ L P 1+\delta=\frac{2}{\gamma L_P} 1 + δ = γ L P 2 (so that δ > 0 \delta>0 δ > 0 by γ < 2 L P \gamma<\frac{2}{L_P} γ < L P 2 and 1 + δ − 1 = K γ : = 2 2 − γ L P 1+\delta^{-1}=K_\gamma:=\frac{2}{2-\gamma L_P} 1 + δ − 1 = K γ := 2 − γ L P 2 ), we obtain from (15)
∥ a ( t + 1 ) − a τ t ∗ ∥ 2 ≤ ∥ a ( t ) − a τ t ∗ ∥ 2 − 2 γ τ t μ ∥ a ( t ) − a τ t ∗ ∥ 2 − 2 γ L P ∥ P ( a ( t ) ) − P ( a τ t ∗ ) ∥ 2 + K γ γ 2 τ t 2 L M 2 ∥ a ( t ) − a τ t ∗ ∥ 2 + 2 γ L P ∥ P ( a ( t ) ) − P ( a τ t ∗ ) ∥ 2 = ( 1 − 2 γ τ t μ + K γ γ 2 τ t 2 L M 2 ) ∥ a ( t ) − a τ t ∗ ∥ 2 = ( 1 − 2 η ε t μ + K γ η 2 ε t 2 L M 2 ) ∥ a ( t ) − a τ t ∗ ∥ 2 . (16) \begin{aligned}
\|a(t+1)-a_{\tau_t}^*\|^2
&\leq\|a(t)-a_{\tau_t}^*\|^2-2\gamma\tau_t\mu\|a(t)-a_{\tau_t}^*\|^2\\
&\qquad-\frac{2\gamma}{L_P}\|P(a(t))-P(a_{\tau_t}^*)\|^2
+K_\gamma\gamma^2\tau_t^2L_M^2\|a(t)-a_{\tau_t}^*\|^2\\
&\qquad+\frac{2\gamma}{L_P}\|P(a(t))-P(a_{\tau_t}^*)\|^2\\
&=(1-2\gamma\tau_t\mu+K_\gamma\gamma^2\tau_t^2L_M^2)\|a(t)-a_{\tau_t}^*\|^2\\
&=(1-2\eta\varepsilon_t\mu+K_\gamma\eta^2\varepsilon_t^2L_M^2)\|a(t)-a_{\tau_t}^*\|^2. \tag*{(16)}
\end{aligned} ∥ a ( t + 1 ) − a τ t ∗ ∥ 2 ≤ ∥ a ( t ) − a τ t ∗ ∥ 2 − 2 γ τ t μ ∥ a ( t ) − a τ t ∗ ∥ 2 − L P 2 γ ∥ P ( a ( t )) − P ( a τ t ∗ ) ∥ 2 + K γ γ 2 τ t 2 L M 2 ∥ a ( t ) − a τ t ∗ ∥ 2 + L P 2 γ ∥ P ( a ( t )) − P ( a τ t ∗ ) ∥ 2 = ( 1 − 2 γ τ t μ + K γ γ 2 τ t 2 L M 2 ) ∥ a ( t ) − a τ t ∗ ∥ 2 = ( 1 − 2 η ε t μ + K γ η 2 ε t 2 L M 2 ) ∥ a ( t ) − a τ t ∗ ∥ 2 . (16)
where we used ( 1 + δ ) γ 2 = 2 γ L P (1+\delta)\gamma^2=\frac{2\gamma}{L_P} ( 1 + δ ) γ 2 = L P 2 γ , and in the last equality we substituted γ τ t = η ε t \gamma\tau_t=\eta\varepsilon_t γ τ t = η ε t .
Next,
∥ a ( t + 1 ) − a τ t + 1 ∗ ∥ ≤ ∥ a ( t + 1 ) − a τ t ∗ ∥ + ∥ a τ t + 1 ∗ − a τ t ∗ ∥ . \|a(t+1)-a_{\tau_{t+1}}^*\|\leq\|a(t+1)-a_{\tau_t}^*\|+\|a_{\tau_{t+1}}^*-a_{\tau_t}^*\|. ∥ a ( t + 1 ) − a τ t + 1 ∗ ∥ ≤ ∥ a ( t + 1 ) − a τ t ∗ ∥ + ∥ a τ t + 1 ∗ − a τ t ∗ ∥.
By sensitivity of strongly monotone VIs (see Proposition 2, applied to the sequence τ t \tau_t τ t with ϵ 1 = τ t + 1 \epsilon_1=\tau_{t+1} ϵ 1 = τ t + 1 and ϵ 2 = τ t \epsilon_2=\tau_t ϵ 2 = τ t ), with C 0 = sup τ > 0 ∥ M ( a τ ∗ ) ∥ / μ C_0=\sup_{\tau>0}\|M(a_\tau^*)\|/\mu C 0 = sup τ > 0 ∥ M ( a τ ∗ ) ∥/ μ , which is finite by (12) and Lipschitz continuity of M M M ,
∥ a τ t + 1 ∗ − a τ t ∗ ∥ ≤ C 0 ∣ τ t + 1 − τ t ∣ τ t = C 0 ∣ ε t + 1 − ε t ∣ ε t . \|a_{\tau_{t+1}}^*-a_{\tau_t}^*\|\leq C_0\frac{|\tau_{t+1}-\tau_t|}{\tau_t}=C_0\frac{|\varepsilon_{t+1}-\varepsilon_t|}{\varepsilon_t}. ∥ a τ t + 1 ∗ − a τ t ∗ ∥ ≤ C 0 τ t ∣ τ t + 1 − τ t ∣ = C 0 ε t ∣ ε t + 1 − ε t ∣ .
Thus, taking into account the last three inequalities, we conclude that
∥ a ( t + 1 ) − a τ t + 1 ∗ ∥ ≤ ( 1 − η μ 2 ε t ) ∥ a ( t ) − a τ t ∗ ∥ + C 0 ∣ ε t + 1 − ε t ∣ ε t , \|a(t+1)-a_{\tau_{t+1}}^*\|\leq\left(1-\frac{\eta\mu}{2}\varepsilon_t\right)\|a(t)-a_{\tau_t}^*\|+C_0\frac{|\varepsilon_{t+1}-\varepsilon_t|}{\varepsilon_t}, ∥ a ( t + 1 ) − a τ t + 1 ∗ ∥ ≤ ( 1 − 2 η μ ε t ) ∥ a ( t ) − a τ t ∗ ∥ + C 0 ε t ∣ ε t + 1 − ε t ∣ ,
for all t t t large enough that ε t ≤ min { μ / ( K γ η L M 2 ) , 1 / ( η μ ) } \varepsilon_t\leq\min\{\mu/(K_\gamma\eta L_M^2),1/(\eta\mu)\} ε t ≤ min { μ / ( K γ η L M 2 ) , 1/ ( η μ )} , since then the factor in (17) is at most 1 − η μ ε t 1-\eta\mu\varepsilon_t 1 − η μ ε t and 1 − η μ ε t ≤ 1 − η μ 2 ε t \sqrt{1-\eta\mu\varepsilon_t}\leq1-\frac{\eta\mu}{2}\varepsilon_t 1 − η μ ε t ≤ 1 − 2 η μ ε t . Moreover, ∣ ε t + 1 − ε t ∣ / ε t = 1 − ( 1 − 1 t + 2 ) e ≤ e t + 2 |\varepsilon_{t+1}-\varepsilon_t|/\varepsilon_t=1-(1-\frac{1}{t+2})^e\leq\frac{e}{t+2} ∣ ε t + 1 − ε t ∣/ ε t = 1 − ( 1 − t + 2 1 ) e ≤ t + 2 e . Since ε t = E / ( t + 1 ) e \varepsilon_t=E/(t+1)^e ε t = E / ( t + 1 ) e with e ∈ ( 0 , 1 ) e\in(0,1) e ∈ ( 0 , 1 ) , Lemma 9(i) with p = e p=e p = e , q = 1 q=1 q = 1 , and a = η μ E / 2 a=\eta\mu E/2 a = η μ E /2 implies ∥ a ( t ) − a τ t ∗ ∥ = O ( 1 t 1 − e ) \|a(t)-a_{\tau_t}^*\|=O\left(\frac{1}{t^{1-e}}\right) ∥ a ( t ) − a τ t ∗ ∥ = O ( t 1 − e 1 ) . Taking into account Proposition 3 (applied to τ t \tau_t τ t , of the same order as ε t \varepsilon_t ε t ) and ∥ a ( t ) − a ∗ ∥ ≤ ∥ a ( t ) − a τ t ∗ ∥ + ∥ a τ t ∗ − a ∗ ∥ \|a(t)-a^*\|\leq\|a(t)-a_{\tau_t}^*\|+\|a_{\tau_t}^*-a^*\| ∥ a ( t ) − a ∗ ∥ ≤ ∥ a ( t ) − a τ t ∗ ∥ + ∥ a τ t ∗ − a ∗ ∥ , we conclude that ∥ a ( t ) − a ∗ ∥ = O ( 1 t min { e / 2 , 1 − e } ) \|a(t)-a^*\|=O\left(\frac{1}{t^{\min\{e/2,1-e\}}}\right) ∥ a ( t ) − a ∗ ∥ = O ( t m i n { e /2 , 1 − e } 1 ) , and squaring gives the claim.
Corollary 1: Optimizing the rate in Theorem 1 above, we obtain that under the choice e = 2 / 3 e=2/3 e = 2/3 ,
∥ a ( t ) − a ∗ ∥ 2 = O ( 1 t 2 / 3 ) . \|a(t)-a^*\|^2=O\left(\frac{1}{t^{2/3}}\right). ∥ a ( t ) − a ∗ ∥ 2 = O ( t 2/3 1 ) .
Error Bound Condition
We now show that strengthening the local error bound of Assumption 3 to the global one posed below, i.e., requiring a single constant κ \kappa κ valid on all of A A A , yields a sharper rate than Theorem 1 and Corollary 1 above: in particular, a rate of O ( 1 / t ) O(1/t) O ( 1/ t ) becomes available. To this end, we pose the following additional assumption on the constraint set.
Assumption 5: The constraint set in (8) admits an error bound on A A A , i.e., there exists κ > 0 \kappa>0 κ > 0 such that
dist ( a , S L ) ≤ κ ∥ [ g ( a ) ] + ∥ , ∀ a ∈ A . \operatorname{dist}(a,S_L)\leq\kappa\|[g(a)]_+\|,\qquad\forall a\in A. dist ( a , S L ) ≤ κ ∥ [ g ( a ) ] + ∥ , ∀ a ∈ A .
Assumption 5 is the global counterpart of Assumption 3: it implies Assumption 3 with κ B = κ \kappa_B=\kappa κ B = κ for every bounded B B B , but the converse fails in general, even under Slater’s condition. For instance, let A = R 2 A=\mathbb{R}^2 A = R 2 and g ( a ) = ∥ a ∥ − a 1 − 1 g(a)=\|a\|-a_1-1 g ( a ) = ∥ a ∥ − a 1 − 1 , so that A ∩ C = { a : a 2 2 ≤ 2 a 1 + 1 } A\cap C=\{a:a_2^2\leq2a_1+1\} A ∩ C = { a : a 2 2 ≤ 2 a 1 + 1 } and a = 0 a=0 a = 0 is a Slater point; hence Assumption 3 holds by Lemma 8. Along a = [ x , 2 x + 1 + 1 ] a=[x,\sqrt{2x+1}+1] a = [ x , 2 x + 1 + 1 ] , however, dist ( a , A ∩ C ) → 1 \operatorname{dist}(a,A\cap C)\to1 dist ( a , A ∩ C ) → 1 while ∥ [ g ( a ) ] + ∥ → 0 \|[g(a)]_+\|\to0 ∥ [ g ( a ) ] + ∥ → 0 as x → ∞ x\to\infty x → ∞ , so Assumption 5 fails.
Remark 4: Assumption 5 is satisfied, in particular, when g g g is affine and the individual action set A A A is polyhedral, namely g ( a ) = K a − k g(a)=Ka-k g ( a ) = K a − k and A = { a : H a − h ≤ 0 } A=\{a:Ha-h\leq0\} A = { a : H a − h ≤ 0 } . Indeed, by Hoffman's error bound (see, for example, [12 ] ), there exists κ > 0 \kappa>0 κ > 0 such that
dist ( a , S L ) = dist ( a , A ∩ C ) ≤ κ ( ∥ [ H a − h ] + ∥ + ∥ [ K a − k ] + ∥ ) = κ ∥ [ K a − k ] + ∥ , \operatorname{dist}(a,S_L)=\operatorname{dist}(a,A\cap C)\leq\kappa(\|[Ha-h]_+\|+\|[Ka-k]_+\|)
=\kappa\|[Ka-k]_+\|, dist ( a , S L ) = dist ( a , A ∩ C ) ≤ κ ( ∥ [ H a − h ] + ∥ + ∥ [ K a − k ] + ∥ ) = κ ∥ [ K a − k ] + ∥ ,
where we used a ∈ A a\in A a ∈ A .
Another sufficient condition for Assumption 5 is Assumption 3 together with boundedness of A A A : taking B = A B=A B = A gives Assumption 5 with κ = κ A \kappa=\kappa_A κ = κ A . In particular, this is the case under Slater’s condition with bounded A A A , where Lemma 8 gives κ = sup a ∈ A ∥ a − a ˉ ∥ / s ˉ \kappa=\sup_{a\in A}\|a-\bar a\|/\bar s κ = sup a ∈ A ∥ a − a ˉ ∥/ s ˉ , with s ˉ \bar s s ˉ as in Lemma 8.
Converting the per-coordinate growth of Definition 4 into a bound on Ψ \Psi Ψ in terms of the norm ∥ [ g ( a ) ] + ∥ \|[g(a)]_+\| ∥ [ g ( a ) ] + ∥ relies on the following elementary fact.
Lemma 3: Let s 1 , … , s m ≥ 0 s_1,\ldots,s_m\geq0 s 1 , … , s m ≥ 0 , S 0 > 0 S_0>0 S 0 > 0 , and r = ( ∑ j = 1 m s j 2 ) 1 / 2 r=(\sum_{j=1}^m s_j^2)^{1/2} r = ( ∑ j = 1 m s j 2 ) 1/2 . Then ∑ j = 1 m s j min ( s j , S 0 ) ≥ r min ( r , S 0 ) \sum_{j=1}^m s_j\min(s_j,S_0)\geq r\min(r,S_0) ∑ j = 1 m s j min ( s j , S 0 ) ≥ r min ( r , S 0 ) .
Proof: Let J 1 = { j : s j ≤ S 0 } \mathcal{J}_1=\{j:s_j\leq S_0\} J 1 = { j : s j ≤ S 0 } , J 2 = { j : s j > S 0 } \mathcal{J}_2=\{j:s_j>S_0\} J 2 = { j : s j > S 0 } , and set T 1 = ∑ J 1 s j 2 T_1=\sum_{\mathcal{J}_1}s_j^2 T 1 = ∑ J 1 s j 2 , T 2 = ∑ J 2 s j 2 T_2=\sum_{\mathcal{J}_2}s_j^2 T 2 = ∑ J 2 s j 2 (so r 2 = T 1 + T 2 r^2=T_1+T_2 r 2 = T 1 + T 2 ) and T 3 = ∑ J 2 s j T_3=\sum_{\mathcal{J}_2}s_j T 3 = ∑ J 2 s j . Then the left-hand side equals T 1 + S 0 T 3 T_1+S_0T_3 T 1 + S 0 T 3 , and T 3 ≥ T 2 T_3\geq\sqrt{T_2} T 3 ≥ T 2 since ( ∑ J 2 s j ) 2 ≥ ∑ J 2 s j 2 (\sum_{\mathcal{J}_2}s_j)^2\geq\sum_{\mathcal{J}_2}s_j^2 ( ∑ J 2 s j ) 2 ≥ ∑ J 2 s j 2 for nonnegative terms.
If r ≤ S 0 r\leq S_0 r ≤ S 0 , every s j ≤ r ≤ S 0 s_j\leq r\leq S_0 s j ≤ r ≤ S 0 , so J 2 = ∅ \mathcal{J}_2=\varnothing J 2 = ∅ and the left-hand side equals T 1 = r 2 = r min ( r , S 0 ) T_1=r^2=r\min(r,S_0) T 1 = r 2 = r min ( r , S 0 ) .
If r > S 0 r>S_0 r > S 0 , it suffices, using T 3 ≥ T 2 T_3\geq\sqrt{T_2} T 3 ≥ T 2 , to show T 1 + S 0 T 2 ≥ S 0 T 1 + T 2 T_1+S_0\sqrt{T_2}\geq S_0\sqrt{T_1+T_2} T 1 + S 0 T 2 ≥ S 0 T 1 + T 2 ; since both sides are nonnegative, this is equivalent to T 1 2 + 2 T 1 S 0 T 2 ≥ S 0 2 T 1 T_1^2+2T_1S_0\sqrt{T_2}\geq S_0^2T_1 T 1 2 + 2 T 1 S 0 T 2 ≥ S 0 2 T 1 , i.e., (for T 1 > 0 T_1>0 T 1 > 0 ) to T 1 + 2 S 0 T 2 ≥ S 0 2 T_1+2S_0\sqrt{T_2}\geq S_0^2 T 1 + 2 S 0 T 2 ≥ S 0 2 , with the case T 1 = 0 T_1=0 T 1 = 0 verified directly below. As a function of T 1 ≥ max ( 0 , S 0 2 − T 2 ) T_1\geq\max(0,S_0^2-T_2) T 1 ≥ max ( 0 , S 0 2 − T 2 ) (the constraint T 1 + T 2 ≥ S 0 2 T_1+T_2\geq S_0^2 T 1 + T 2 ≥ S 0 2 ), the left-hand side is increasing in T 1 T_1 T 1 , so it suffices to check it at T 1 = max ( 0 , S 0 2 − T 2 ) T_1=\max(0,S_0^2-T_2) T 1 = max ( 0 , S 0 2 − T 2 ) : if T 2 ≤ S 0 2 T_2\leq S_0^2 T 2 ≤ S 0 2 , this gives ( S 0 2 − T 2 ) + 2 S 0 T 2 = S 0 2 + T 2 ( 2 S 0 − T 2 ) ≥ S 0 2 (S_0^2-T_2)+2S_0\sqrt{T_2}=S_0^2+\sqrt{T_2}(2S_0-\sqrt{T_2})\geq S_0^2 ( S 0 2 − T 2 ) + 2 S 0 T 2 = S 0 2 + T 2 ( 2 S 0 − T 2 ) ≥ S 0 2 (as T 2 ≤ S 0 \sqrt{T_2}\leq S_0 T 2 ≤ S 0 ); if T 2 > S 0 2 T_2>S_0^2 T 2 > S 0 2 , this gives 2 S 0 T 2 ≥ 2 S 0 2 > S 0 2 2S_0\sqrt{T_2}\geq2S_0^2>S_0^2 2 S 0 T 2 ≥ 2 S 0 2 > S 0 2 . Either way, T 1 + 2 S 0 T 2 ≥ S 0 2 T_1+2S_0\sqrt{T_2}\geq S_0^2 T 1 + 2 S 0 T 2 ≥ S 0 2 , completing the proof.
The following lemma, which relies only on Definition 4, the convexity in Assumption 1(ii), and the error bound of Assumption 5, is the key tool used to establish this sharper convergence rate for (9).
Lemma 4: Let z ∈ S L z\in S_L z ∈ S L , let ψ \psi ψ be an admissible penalty profile with constants S 0 , c ψ > 0 S_0,c_\psi>0 S 0 , c ψ > 0 as in Definition 4, and set D 0 : = κ S 0 D_0:=\kappa S_0 D 0 := κ S 0 . Then, under Assumptions 1(ii) and 5, for any a ∈ A a\in A a ∈ A and given d = dist ( a , S L ) d=\operatorname{dist}(a,S_L) d = dist ( a , S L ) ,
⟨ P ( a ) , a − z ⟩ ≥ μ P d min ( d , D 0 ) , μ P = c ψ κ 2 . \langle P(a),a-z\rangle\geq\mu_Pd\min(d,D_0),\qquad\mu_P=\frac{c_\psi}{\kappa^2}. ⟨ P ( a ) , a − z ⟩ ≥ μ P d min ( d , D 0 ) , μ P = κ 2 c ψ .
Proof: Let r = ∥ [ g ( a ) ] + ∥ r=\lVert[g(a)]_{+}\rVert r = ∥[ g ( a ) ] + ∥ and d = dist ( a , S L ) d=\operatorname{dist}(a,S_L) d = dist ( a , S L ) . By Definition 4 applied coordinatewise and Lemma 3, recalling (6),
Ψ ( a ) = ∑ j = 1 m ψ ( [ g j ( a ) ] + ) ≥ c ψ ∑ j = 1 m [ g j ( a ) ] + min ( [ g j ( a ) ] + , S 0 ) ≥ c ψ r min ( r , S 0 ) . \begin{aligned}
\Psi(a)=\sum_{j=1}^{m}\psi([g_j(a)]_{+})\ge c_{\psi}\sum_{j=1}^{m}[g_j(a)]_{+}\min([g_j(a)]_{+},S_0) \\
&\ge c_{\psi}r\min(r,S_0).
\end{aligned} Ψ ( a ) = j = 1 ∑ m ψ ([ g j ( a ) ] + ) ≥ c ψ j = 1 ∑ m [ g j ( a ) ] + min ([ g j ( a ) ] + , S 0 ) ≥ c ψ r min ( r , S 0 ) .
By Assumption 5, r ≥ d / κ r\ge d/\kappa r ≥ d / κ , and since s ↦ s min ( s , S 0 ) s\mapsto s\min(s,S_0) s ↦ s min ( s , S 0 ) is nondecreasing on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) ,
Ψ ( a ) ≥ c ψ ⋅ d κ min ( d κ , S 0 ) = c ψ κ 2 d min ( d , κ S 0 ) = μ P d min ( d , D 0 ) . \Psi(a)\ge c_{\psi}\cdot\frac{d}{\kappa}\min\left(\frac{d}{\kappa},S_0\right)
=\frac{c_{\psi}}{\kappa^2}d\min(d,\kappa S_0)=\mu_Pd\min(d,D_0). Ψ ( a ) ≥ c ψ ⋅ κ d min ( κ d , S 0 ) = κ 2 c ψ d min ( d , κ S 0 ) = μ P d min ( d , D 0 ) .
Since Ψ \Psi Ψ is convex and Ψ ( z ) = 0 \Psi(z)=0 Ψ ( z ) = 0 for z ∈ S L z\in S_L z ∈ S L ,
0 = Ψ ( z ) ≥ Ψ ( a ) + ⟨ P ( a ) , z − a ⟩ , 0=\Psi(z)\ge\Psi(a)+\langle P(a),z-a\rangle, 0 = Ψ ( z ) ≥ Ψ ( a ) + ⟨ P ( a ) , z − a ⟩ ,
i.e., ⟨ P ( a ) , a − z ⟩ ≥ Ψ ( a ) ≥ μ P d min ( d , D 0 ) \langle P(a),a-z\rangle\ge\Psi(a)\ge\mu_Pd\min(d,D_0) ⟨ P ( a ) , a − z ⟩ ≥ Ψ ( a ) ≥ μ P d min ( d , D 0 ) .
Theorem 2. Let Assumptions 1, 2, 4, and 5 hold. Let the regularization parameter be ε t = E ( t + 1 ) e \varepsilon_t=\frac{E}{(t+1)^e} ε t = ( t + 1 ) e E for some E > 0 E>0 E > 0 , e ∈ ( 0 , 1 ] e\in(0,1] e ∈ ( 0 , 1 ] , let the stepsize satisfy γ ∈ ( 0 , 2 L P ) \gamma\in\left(0,\frac{2}{L_P}\right) γ ∈ ( 0 , L P 2 ) , and let η > 0 \eta>0 η > 0 . Then the sequence { a ( t ) } \{a(t)\} { a ( t )} generated by (9) converges to the unique v-GNE a ⋆ a^\star a ⋆ in Γ \Gamma Γ . Moreover,
∥ a ( t ) − a ⋆ ∥ 2 = { O ( 1 t e ) , if e ∈ ( 0 , 1 ) , O ( 1 t ) , if e = 1 and E > 1 η μ . \lVert a(t)-a^\star\rVert^2=
\begin{cases}
O\left(\frac{1}{t^e}\right),&\text{if }e\in(0,1),\\
O\left(\frac{1}{t}\right),&\text{if }e=1\text{ and }E>\frac{1}{\eta\mu}.
\end{cases} ∥ a ( t ) − a ⋆ ∥ 2 = { O ( t e 1 ) , O ( t 1 ) , if e ∈ ( 0 , 1 ) , if e = 1 and E > η μ 1 .
Proof: Set d t = a ( t ) − a ⋆ d_t=a(t)-a^\star d t = a ( t ) − a ⋆ . Since a ⋆ ∈ S L = SOL ( A , P ) a^\star\in S_L=\operatorname{SOL}(A,P) a ⋆ ∈ S L = SOL ( A , P ) , we have
a ⋆ = Π A [ a ⋆ − γ P ( a ⋆ ) ] . a^\star=\Pi_A[a^\star-\gamma P(a^\star)]. a ⋆ = Π A [ a ⋆ − γ P ( a ⋆ )] .
Using nonexpansiveness of the projection,
∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t − γ ( P ( a ( t ) ) − P ( a ⋆ ) ) − η ε t M ( a ( t ) ) ∥ 2 . \lVert a(t+1)-a^\star\rVert^2\le\left\lVert d_t-\gamma\big(P(a(t))-P(a^\star)\big)-\eta\varepsilon_tM(a(t))\right\rVert^2. ∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ d t − γ ( P ( a ( t )) − P ( a ⋆ ) ) − η ε t M ( a ( t )) 2 .
Let p t = P ( a ( t ) ) − P ( a ⋆ ) p_t=P(a(t))-P(a^\star) p t = P ( a ( t )) − P ( a ⋆ ) . Fix δ = 2 − γ L P 2 γ L P \delta=\frac{2-\gamma L_P}{2\gamma L_P} δ = 2 γ L P 2 − γ L P , which is positive since γ < 2 L P \gamma<\frac{2}{L_P} γ < L P 2 , and set K ˉ γ : = 1 + δ − 1 = 2 + γ L P 2 − γ L P \bar K_\gamma:=1+\delta^{-1}=\frac{2+\gamma L_P}{2-\gamma L_P} K ˉ γ := 1 + δ − 1 = 2 − γ L P 2 + γ L P . Then, since 2 γ η ε t ⟨ p t , M ( a ( t ) ) ⟩ ≤ δ γ 2 ∥ p t ∥ 2 + δ − 1 η 2 ε t 2 ∥ M ( a ( t ) ) ∥ 2 2\gamma\eta\varepsilon_t\langle p_t,M(a(t))\rangle\le\delta\gamma^2\lVert p_t\rVert^2+\delta^{-1}\eta^2\varepsilon_t^2\lVert M(a(t))\rVert^2 2 γ η ε t ⟨ p t , M ( a ( t ))⟩ ≤ δ γ 2 ∥ p t ∥ 2 + δ − 1 η 2 ε t 2 ∥ M ( a ( t )) ∥ 2 , we obtain
∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − 2 γ ⟨ p t , d t ⟩ − 2 η ε t ⟨ M ( a ( t ) ) , d t ⟩ + ( 1 + δ ) γ 2 ∥ p t ∥ 2 + K ˉ γ η 2 ε t 2 ∥ M ( a ( t ) ) ∥ 2 . (17) \lVert a(t+1)-a^\star\rVert^2\le\lVert d_t\rVert^2-2\gamma\langle p_t,d_t\rangle-2\eta\varepsilon_t\langle M(a(t)),d_t\rangle
+(1+\delta)\gamma^2\lVert p_t\rVert^2+\bar K_\gamma\eta^2\varepsilon_t^2\lVert M(a(t))\rVert^2. \tag*{(17)} ∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − 2 γ ⟨ p t , d t ⟩ − 2 η ε t ⟨ M ( a ( t )) , d t ⟩ + ( 1 + δ ) γ 2 ∥ p t ∥ 2 + K ˉ γ η 2 ε t 2 ∥ M ( a ( t )) ∥ 2 . (17)
Since P = ∇ Ψ P=\nabla\Psi P = ∇Ψ is the gradient of a convex function with an L P L_P L P -Lipschitz gradient on the open convex set U ⊇ A U\supseteq A U ⊇ A (Assumption 4), it is cocoercive on A A A by [26 Thm. 3.1] , i.e., ∥ p t ∥ 2 ≤ L P ⟨ p t , d t ⟩ \lVert p_t\rVert^2\le L_P\langle p_t,d_t\rangle ∥ p t ∥ 2 ≤ L P ⟨ p t , d t ⟩ . Thus, since ( 1 + δ ) L P γ 2 = γ ( 2 + γ L P ) 2 (1+\delta)L_P\gamma^2=\frac{\gamma(2+\gamma L_P)}{2} ( 1 + δ ) L P γ 2 = 2 γ ( 2 + γ L P ) , setting γ ˉ : = γ ( 2 − γ L P ) 2 > 0 \bar\gamma:=\frac{\gamma(2-\gamma L_P)}{2}>0 γ ˉ := 2 γ ( 2 − γ L P ) > 0 gives
− 2 γ ⟨ p t , d t ⟩ + ( 1 + δ ) γ 2 ∥ p t ∥ 2 ≤ − 2 γ ⟨ p t , d t ⟩ + ( 1 + δ ) L P γ 2 ⟨ p t , d t ⟩ = − γ ˉ ⟨ p t , d t ⟩ . -2\gamma\langle p_t,d_t\rangle+(1+\delta)\gamma^2\lVert p_t\rVert^2
\le-2\gamma\langle p_t,d_t\rangle+(1+\delta)L_P\gamma^2\langle p_t,d_t\rangle
=-\bar\gamma\langle p_t,d_t\rangle. − 2 γ ⟨ p t , d t ⟩ + ( 1 + δ ) γ 2 ∥ p t ∥ 2 ≤ − 2 γ ⟨ p t , d t ⟩ + ( 1 + δ ) L P γ 2 ⟨ p t , d t ⟩ = − γ ˉ ⟨ p t , d t ⟩ .
Thus, (18) implies
∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − γ ˉ ⟨ p t , d t ⟩ − 2 η ε t ⟨ M ( a ( t ) ) , d t ⟩ + K ˉ γ η 2 ε t 2 ∥ M ( a ( t ) ) ∥ 2 . (18) \lVert a(t+1)-a^\star\rVert^2\le\lVert d_t\rVert^2-\bar\gamma\langle p_t,d_t\rangle-2\eta\varepsilon_t\langle M(a(t)),d_t\rangle
+\bar K_\gamma\eta^2\varepsilon_t^2\lVert M(a(t))\rVert^2. \tag*{(18)} ∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − γ ˉ ⟨ p t , d t ⟩ − 2 η ε t ⟨ M ( a ( t )) , d t ⟩ + K ˉ γ η 2 ε t 2 ∥ M ( a ( t )) ∥ 2 . (18)
Let d t = dist ( a ( t ) , S L ) d_t=\operatorname{dist}(a(t),S_L) d t = dist ( a ( t ) , S L ) . As a ⋆ ∈ S L a^\star\in S_L a ⋆ ∈ S L , P ( a ⋆ ) = 0 P(a^\star)=0 P ( a ⋆ ) = 0 . Then Lemma 4 implies ⟨ p t , d t ⟩ = ⟨ P ( a ( t ) ) , a ( t ) − a ⋆ ⟩ ≥ μ P d t min ( d t , D 0 ) \langle p_t,d_t\rangle=\langle P(a(t)),a(t)-a^\star\rangle\ge\mu_Pd_t\min(d_t,D_0) ⟨ p t , d t ⟩ = ⟨ P ( a ( t )) , a ( t ) − a ⋆ ⟩ ≥ μ P d t min ( d t , D 0 ) , so that
− γ ˉ ⟨ p t , d t ⟩ ≤ − γ ˉ μ P d t min ( d t , D 0 ) . (19) -\bar\gamma\langle p_t,d_t\rangle\le-\bar\gamma\mu_Pd_t\min(d_t,D_0). \tag*{(19)} − γ ˉ ⟨ p t , d t ⟩ ≤ − γ ˉ μ P d t min ( d t , D 0 ) . (19)
Next decompose
⟨ M ( a ( t ) ) , d t ⟩ = ⟨ M ( a ( t ) ) − M ( a ⋆ ) , d t ⟩ + ⟨ M ( a ⋆ ) , d t ⟩ . \langle M(a(t)),d_t\rangle=\langle M(a(t))-M(a^\star),d_t\rangle+\langle M(a^\star),d_t\rangle. ⟨ M ( a ( t )) , d t ⟩ = ⟨ M ( a ( t )) − M ( a ⋆ ) , d t ⟩ + ⟨ M ( a ⋆ ) , d t ⟩ .
By μ \mu μ -strong monotonicity of M M M (Assumption 2),
⟨ M ( a ( t ) ) − M ( a ⋆ ) , d t ⟩ ≥ μ ∥ d t ∥ 2 . \langle M(a(t))-M(a^\star),d_t\rangle\ge\mu\lVert d_t\rVert^2. ⟨ M ( a ( t )) − M ( a ⋆ ) , d t ⟩ ≥ μ ∥ d t ∥ 2 .
Since a ⋆ a^\star a ⋆ solves VI ( S L , M ) \operatorname{VI}(S_L,M) VI ( S L , M ) , ⟨ M ( a ⋆ ) , Π S L ( a ( t ) ) − a ⋆ ⟩ ≥ 0 \langle M(a^\star),\Pi_{S_L}(a(t))-a^\star\rangle\ge0 ⟨ M ( a ⋆ ) , Π S L ( a ( t )) − a ⋆ ⟩ ≥ 0 . Therefore,
⟨ M ( a ⋆ ) , d t ⟩ = ⟨ M ( a ⋆ ) , a ( t ) − Π S L ( a ( t ) ) ⟩ + ⟨ M ( a ⋆ ) , Π S L ( a ( t ) ) − a ⋆ ⟩ ≥ − ∥ M ( a ⋆ ) ∥ d t . \langle M(a^\star),d_t\rangle
=\langle M(a^\star),a(t)-\Pi_{S_L}(a(t))\rangle
+\langle M(a^\star),\Pi_{S_L}(a(t))-a^\star\rangle
\ge-\lVert M(a^\star)\rVert d_t. ⟨ M ( a ⋆ ) , d t ⟩ = ⟨ M ( a ⋆ ) , a ( t ) − Π S L ( a ( t ))⟩ + ⟨ M ( a ⋆ ) , Π S L ( a ( t )) − a ⋆ ⟩ ≥ − ∥ M ( a ⋆ )∥ d t .
Thus,
⟨ M ( a ( t ) ) , d t ⟩ ≥ μ ∥ d t ∥ 2 − ∥ M ( a ⋆ ) ∥ d t . (20) \langle M(a(t)),d_t\rangle\ge\mu\lVert d_t\rVert^2-\lVert M(a^\star)\rVert d_t. \tag*{(20)} ⟨ M ( a ( t )) , d t ⟩ ≥ μ ∥ d t ∥ 2 − ∥ M ( a ⋆ )∥ d t . (20)
Combining (20) and (21) in (19) yields
∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − γ ˉ μ P d t min ( d t , D 0 ) − 2 η μ ε t ∥ d t ∥ 2 + 2 η ε t ∥ M ( a ⋆ ) ∥ d t + K ˉ γ η 2 ε t 2 ∥ M ( a ( t ) ) ∥ 2 . (21) \lVert a(t+1)-a^\star\rVert^2\le\lVert d_t\rVert^2-\bar\gamma\mu_Pd_t\min(d_t,D_0)
-2\eta\mu\varepsilon_t\lVert d_t\rVert^2
+2\eta\varepsilon_t\lVert M(a^\star)\rVert d_t
+\bar K_\gamma\eta^2\varepsilon_t^2\lVert M(a(t))\rVert^2. \tag*{(21)} ∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − γ ˉ μ P d t min ( d t , D 0 ) − 2 η μ ε t ∥ d t ∥ 2 + 2 η ε t ∥ M ( a ⋆ )∥ d t + K ˉ γ η 2 ε t 2 ∥ M ( a ( t )) ∥ 2 . (21)
We bound the two d t d_t d t -dependent terms in (22) jointly. Let ε ˉ = γ ˉ μ P D 0 4 η ∥ M ( a ⋆ ) ∥ \bar\varepsilon=\frac{\bar\gamma\mu_PD_0}{4\eta\lVert M(a^\star)\rVert} ε ˉ = 4 η ∥ M ( a ⋆ )∥ γ ˉ μ P D 0 and C 3 = 2 η 2 γ ˉ μ P ∥ M ( a ⋆ ) ∥ 2 C_3=\frac{2\eta^2}{\bar\gamma\mu_P}\lVert M(a^\star)\rVert^2 C 3 = γ ˉ μ P 2 η 2 ∥ M ( a ⋆ ) ∥ 2 . Then for all t t t with ε t ≤ ε ˉ \varepsilon_t\le\bar\varepsilon ε t ≤ ε ˉ ,
− γ ˉ μ P d t min ( d t , D 0 ) + 2 η ε t ∥ M ( a ⋆ ) ∥ d t ≤ C 3 ε t 2 . (22) -\bar\gamma\mu_Pd_t\min(d_t,D_0)+2\eta\varepsilon_t\lVert M(a^\star)\rVert d_t\le C_3\varepsilon_t^2. \tag*{(22)} − γ ˉ μ P d t min ( d t , D 0 ) + 2 η ε t ∥ M ( a ⋆ )∥ d t ≤ C 3 ε t 2 . (22)
Indeed, if d t ≤ D 0 d_t\le D_0 d t ≤ D 0 , then min ( d t , D 0 ) = d t \min(d_t,D_0)=d_t min ( d t , D 0 ) = d t and (23) is the standard Young's inequality bound 2 η ε t ∥ M ( a ⋆ ) ∥ d t ≤ C 3 ε t 2 + γ ˉ μ P 2 d t 2 2\eta\varepsilon_t\lVert M(a^\star)\rVert d_t\le C_3\varepsilon_t^2+\frac{\bar\gamma\mu_P}{2}d_t^2 2 η ε t ∥ M ( a ⋆ )∥ d t ≤ C 3 ε t 2 + 2 γ ˉ μ P d t 2 , obtained by completing the square in d t d_t d t . If d t > D 0 d_t>D_0 d t > D 0 , then min ( d t , D 0 ) = D 0 \min(d_t,D_0)=D_0 min ( d t , D 0 ) = D 0 and, since ε t ≤ ε ˉ \varepsilon_t\le\bar\varepsilon ε t ≤ ε ˉ gives 2 η ε t ∥ M ( a ⋆ ) ∥ ≤ γ ˉ μ P D 0 2 2\eta\varepsilon_t\lVert M(a^\star)\rVert\le\frac{\bar\gamma\mu_PD_0}{2} 2 η ε t ∥ M ( a ⋆ )∥ ≤ 2 γ ˉ μ P D 0 , the left-hand side of (23) equals
d t ( 2 η ε t ∥ M ( a ⋆ ) ∥ − γ ˉ μ P D 0 ) ≤ d t ( γ ˉ μ P D 0 2 − γ ˉ μ P D 0 ) = − γ ˉ μ P D 0 2 d t ≤ 0 ≤ C 3 ε t 2 . d_t\left(2\eta\varepsilon_t\lVert M(a^\star)\rVert-\bar\gamma\mu_PD_0\right)
\le d_t\left(\frac{\bar\gamma\mu_PD_0}{2}-\bar\gamma\mu_PD_0\right)
=-\frac{\bar\gamma\mu_PD_0}{2}d_t\le0\le C_3\varepsilon_t^2. d t ( 2 η ε t ∥ M ( a ⋆ )∥ − γ ˉ μ P D 0 ) ≤ d t ( 2 γ ˉ μ P D 0 − γ ˉ μ P D 0 ) = − 2 γ ˉ μ P D 0 d t ≤ 0 ≤ C 3 ε t 2 .
Since ε t → 0 \varepsilon_t\to0 ε t → 0 , ε t ≤ ε ˉ \varepsilon_t\le\bar\varepsilon ε t ≤ ε ˉ for all sufficiently large t t t . Combining (22) with (23) then gives, for such t t t ,
∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − 2 η μ ε t ∥ d t ∥ 2 + K ˉ γ η 2 ε t 2 ∥ M ( a ( t ) ) ∥ 2 + C 3 ε t 2 . (23) \lVert a(t+1)-a^\star\rVert^2\le\lVert d_t\rVert^2-2\eta\mu\varepsilon_t\lVert d_t\rVert^2
+\bar K_\gamma\eta^2\varepsilon_t^2\lVert M(a(t))\rVert^2+C_3\varepsilon_t^2. \tag*{(23)} ∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − 2 η μ ε t ∥ d t ∥ 2 + K ˉ γ η 2 ε t 2 ∥ M ( a ( t )) ∥ 2 + C 3 ε t 2 . (23)
Since M M M is Lipschitz continuous (Assumption 2),
K ˉ γ ∥ M ( a ( t ) ) ∥ 2 ≤ C 1 ∥ d t ∥ 2 + C 2 , \bar K_\gamma\lVert M(a(t))\rVert^2\le C_1\lVert d_t\rVert^2+C_2, K ˉ γ ∥ M ( a ( t )) ∥ 2 ≤ C 1 ∥ d t ∥ 2 + C 2 ,
where C 1 = 2 K ˉ γ L M 2 C_1=2\bar K_\gamma L_M^2 C 1 = 2 K ˉ γ L M 2 and C 2 = 2 K ˉ γ ∥ M ( a ⋆ ) ∥ 2 C_2=2\bar K_\gamma\lVert M(a^\star)\rVert^2 C 2 = 2 K ˉ γ ∥ M ( a ⋆ ) ∥ 2 . Hence, inserting the last inequality into (24) gives, for all sufficiently large t t t ,
∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ( 1 − 2 η μ ε t + η 2 C 1 ε t 2 ) ∥ a ( t ) − a ⋆ ∥ 2 + ( C 3 + η 2 C 2 ) ε t 2 . \lVert a(t+1)-a^\star\rVert^2
\le(1-2\eta\mu\varepsilon_t+\eta^2C_1\varepsilon_t^2)\lVert a(t)-a^\star\rVert^2
+(C_3+\eta^2C_2)\varepsilon_t^2. ∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ( 1 − 2 η μ ε t + η 2 C 1 ε t 2 ) ∥ a ( t ) − a ⋆ ∥ 2 + ( C 3 + η 2 C 2 ) ε t 2 .
Due to the choice of ε t \varepsilon_t ε t , for all sufficiently large t t t , 2 η μ ε t − η 2 C 1 ε t 2 ≥ η μ ε t 2\eta\mu\varepsilon_t-\eta^2C_1\varepsilon_t^2\ge\eta\mu\varepsilon_t 2 η μ ε t − η 2 C 1 ε t 2 ≥ η μ ε t , so that, for such t t t ,
∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ( 1 − η μ ε t ) ∥ a ( t ) − a ⋆ ∥ 2 + ( C 3 + η 2 C 2 ) ε t 2 . \lVert a(t+1)-a^\star\rVert^2
\le(1-\eta\mu\varepsilon_t)\lVert a(t)-a^\star\rVert^2
+(C_3+\eta^2C_2)\varepsilon_t^2. ∥ a ( t + 1 ) − a ⋆ ∥ 2 ≤ ( 1 − η μ ε t ) ∥ a ( t ) − a ⋆ ∥ 2 + ( C 3 + η 2 C 2 ) ε t 2 .
By Lemma 9 with p = e p=e p = e , q = 2 e q=2e q = 2 e , and a = η μ E a=\eta\mu E a = η μ E , we obtain convergence, by item (iii) if e = 1 e=1 e = 1 and η μ E ≤ 1 \eta\mu E\le1 η μ E ≤ 1 , and
∥ a ( t ) − a ⋆ ∥ 2 = { O ( 1 t e ) , if e ∈ ( 0 , 1 ) , O ( 1 t ) , if e = 1 and E > 1 η μ . \lVert a(t)-a^\star\rVert^2=
\begin{cases}
O\left(\frac{1}{t^e}\right),&\text{if }e\in(0,1),\\
O\left(\frac{1}{t}\right),&\text{if }e=1\text{ and }E>\frac{1}{\eta\mu}.
\end{cases} ∥ a ( t ) − a ⋆ ∥ 2 = { O ( t e 1 ) , O ( t 1 ) , if e ∈ ( 0 , 1 ) , if e = 1 and E > η μ 1 .
Distributed Hierarchical Regularization Scheme
In this section, we develop a distributed algorithmic framework for solving the hierarchical variational inequality (7) . Since the mappings M M M and P P P depend on the global action profile, the centralized scheme of Section Section IV would generally require global information, namely, access of every agent to the full joint action a ( t ) a(t) a ( t ) . To overcome this limitation, we adopt a consensus-based distributed approach in which each agent maintains local estimates of the actions of all other agents and communicates only with its neighbors over a communication network.
Specifically, each agent i i i stores a local estimate of the global action profile a = [ a 1 , … , a N ] a = [a^{1},\ldots,a^{N}] a = [ a 1 , … , a N ] which is denoted by
x i = [ x i 1 , … , x i N ] ∈ R D . x_i = [x_i^{1},\ldots,x_i^{N}] \in\mathbb{R}^{D}. x i = [ x i 1 , … , x i N ] ∈ R D .
Here, x i j x_i^{j} x i j represents agent i i i ’s estimate of the action of agent j j j . In particular, x i i = a i x_i^{i}=a^{i} x i i = a i . Stacking all local estimates yields
x = [ x 1 , … , x N ] ∈ R N D . x=[x_1,\ldots,x_N]\in\mathbb{R}^{ND}. x = [ x 1 , … , x N ] ∈ R N D .
The agents communicate over an undirected graph G = ( [ N ] , E ) \mathcal{G}=([N],\mathcal{E}) G = ([ N ] , E ) , where ( i , j ) ∈ E (i,j)\in\mathcal{E} ( i , j ) ∈ E if agents i i i and j j j can exchange information. For each agent i ∈ [ N ] i\in[N] i ∈ [ N ] , we denote by N i = { j ∈ [ N ] ∣ ( i , j ) ∈ E } \mathcal{N}_i=\{j\in[N]\mid(i,j)\in\mathcal{E}\} N i = { j ∈ [ N ] ∣ ( i , j ) ∈ E } the set of its neighbors. We assume that i ∈ N i i\in\mathcal{N}_i i ∈ N i , that is, each agent is considered a neighbor of itself. Throughout the paper, we impose the following standard assumption [24 ] .
Assumption 6: The communication graph G \mathcal{G} G is connected. Moreover, the associated mixing matrix W = [ w i j ] i , j = 1 N W=[w_{ij}]_{i,j=1}^{N} W = [ w ij ] i , j = 1 N defines the weights on the undirected arcs such that w i j > 0 w_{ij}>0 w ij > 0 if and only if the agents i i i and j j j can exchange information (are neighbors). W W W is symmetric and doubly stochastic, i.e., W = W T W=W^{\mathsf{T}} W = W T , W 1 N = 1 N W1_N=1_N W 1 N = 1 N , and 1 N T W = 1 N T 1_N^{\mathsf{T}}W=1_N^{\mathsf{T}} 1 N T W = 1 N T .
The assumption above implies, in particular, that the second largest singular value of W W W satisfies
σ = ∥ W − J ˉ ∥ ∈ [ 0 , 1 ) , J ˉ = 1 N 1 N 1 N T . (24) \sigma=\lVert W-\bar{J}\rVert\in[0,1),\qquad\bar{J}=\frac{1}{N}1_N1_N^{\mathsf{T}}. \tag*{(24)} σ = ∥ W − J ˉ ∥ ∈ [ 0 , 1 ) , J ˉ = N 1 1 N 1 N T . (24)
Assumption 6 guarantees that repeated applications of the mixing matrix asymptotically drive the agents’ local estimates to consensus. The parameter σ \sigma σ quantifies the connectivity of the communication graph and determines the rate of consensus formation [24 ] . For the current analysis, we assume the following condition regarding the feasible sets and smoothness of the operators.
Assumption 7: Each set A i A^{i} A i , i ∈ [ N ] i\in[N] i ∈ [ N ] , is bounded. Fix a compact box
Q i ⊇ A i , i ∈ [ N ] , Q : = Q 1 × ⋯ × Q N ⊇ A , Q^{i}\supseteq A^{i},\qquad i\in[N],\qquad Q:=Q^{1}\times\cdots\times Q^{N}\supseteq A, Q i ⊇ A i , i ∈ [ N ] , Q := Q 1 × ⋯ × Q N ⊇ A , known to all agents (e.g., Q i = [ − ρ , ρ ] d i Q^{i}=[-\rho,\rho]^{d_i} Q i = [ − ρ , ρ ] d i for ρ > 0 \rho>0 ρ > 0 large enough that A i ⊆ Q i A^{i}\subseteq Q^{i} A i ⊆ Q i ). Moreover, P P P and M M M are Lipschitz continuous over Q Q Q with constants L P Q , L M Q > 0 L_{P}^{Q},L_{M}^{Q}>0 L P Q , L M Q > 0 , respectively:
∥ P ( a ) − P ( b ) ∥ ≤ L P Q ∥ a − b ∥ , \lVert P(a)-P(b)\rVert\le L_{P}^{Q}\lVert a-b\rVert, ∥ P ( a ) − P ( b )∥ ≤ L P Q ∥ a − b ∥ , ∥ M ( a ) − M ( b ) ∥ ≤ L M Q ∥ a − b ∥ , ∀ a , b ∈ Q . \lVert M(a)-M(b)\rVert\le L_{M}^{Q}\lVert a-b\rVert,\qquad\forall a,b\in Q. ∥ M ( a ) − M ( b )∥ ≤ L M Q ∥ a − b ∥ , ∀ a , b ∈ Q .
Using the notation above, we define the steps of the distributed procedure in Algorithm 2. The algorithm consists of three main steps. First, each agent i i i exchanges its current estimates with its neighbors and computes a local weighted average z i z_i z i using the corresponding row of the mixing matrix W W W . Second, each agent i i i performs a projected gradient step with respect to the local coordinate of the regularized operator, where the lower-level part P P P is calculated at the local weighted average z i z_i z i , whereas the upper-level part M i M^{i} M i is calculated at the joint action estimate x i x_i x i and influences only the agent’s own action update. Finally, the resulting iterate of the local action update is projected onto the local feasible set A i A^{i} A i for the owned coordinate, and onto the shared public box Q j Q^{j} Q j (see Assumption 7) for every other, non-owned coordinate j ≠ i j\ne i j = i . Importantly, the proposed algorithm operates entirely in the primal space and therefore does not require introducing, communicating, or updating dual variables; the boxes Q j Q^{j} Q j are common knowledge and disclose no private information about the sets A j A^{j} A j .
Algorithm 2 Distributed hierarchical regularization scheme
Initialization: Each agent chooses x i ( 0 ) ∈ Ω i = Q 1 × ⋯ × Q i − 1 × A i × Q i + 1 × ⋯ × Q N x_i(0)\in\Omega^{i}=Q^{1}\times\cdots\times Q^{i-1}\times A^{i}\times Q^{i+1}\times\cdots\times Q^{N} x i ( 0 ) ∈ Ω i = Q 1 × ⋯ × Q i − 1 × A i × Q i + 1 × ⋯ × Q N . The stepsizes γ , η \gamma,\eta γ , η and the regularization sequence { ϵ t } ⊂ ( 0 , ∞ ) \{\epsilon_t\}\subset(0,\infty) { ϵ t } ⊂ ( 0 , ∞ ) are common to all agents.
For t = 0 , 1 , 2 , … t=0,1,2,\ldots t = 0 , 1 , 2 , … do
Each agent i ∈ [ N ] i\in[N] i ∈ [ N ] obtains the estimates x j ( t ) x_j(t) x j ( t ) from all neighbors j ∈ N i j\in\mathcal{N}_i j ∈ N i and computes
z i ( t ) = ∑ j = 1 N w i j x j ( t ) . z_i(t)=\sum_{j=1}^{N}w_{ij}x_j(t). z i ( t ) = j = 1 ∑ N w ij x j ( t ) . Each agent i ∈ [ N ] i\in[N] i ∈ [ N ] updates its local estimate as
x i i ( t + 1 ) = Π A i [ z i i ( t ) − γ P i ( z i ( t ) ) − η ϵ t M i ( x i ( t ) ) ] , x_i^{i}(t+1)=\Pi_{A^{i}}\left[z_i^{i}(t)-\gamma P^{i}(z_i(t))-\eta\epsilon_tM^{i}(x_i(t))\right], x i i ( t + 1 ) = Π A i [ z i i ( t ) − γ P i ( z i ( t )) − η ϵ t M i ( x i ( t )) ] , x i j ( t + 1 ) = Π Q j [ z i j ( t ) − γ P j ( z i ( t ) ) ] , j ≠ i . x_i^{j}(t+1)=\Pi_{Q^{j}}\left[z_i^{j}(t)-\gamma P^{j}(z_i(t))\right],\qquad j\ne i. x i j ( t + 1 ) = Π Q j [ z i j ( t ) − γ P j ( z i ( t )) ] , j = i .
Remark 5: Assumption 7 is of exactly the same nature as Assumption 4, only stated on the compact set Q ⊇ A Q\supseteq A Q ⊇ A instead of the open neighborhood U U U of A A A , and is satisfied under the sufficient conditions listed after Assumption 4 with U U U replaced by an open convex neighborhood of Q Q Q throughout. Since Q Q Q is a box with nonempty interior, cocoercivity of P P P on int Q Q Q follows from [26, Thm. 3.1 and extends to Q Q Q by continuity of P P P . Assumption 7 imposes no control whatsoever on P P P or M M M outside the fixed, bounded, and explicitly constructed set Q Q Q . Agent i i i need not know the private set A j A^{j} A j of any other agent j j j . Assumption 7 allows for keeping z i ( t ) z_i(t) z i ( t ) inside a fixed, compact, and explicitly known set on which P P P is well controlled.
For each agent i i i , let us define the selection matrix R i ∈ R d i × D R_i\in\mathbb{R}^{d_i\times D} R i ∈ R d i × D :
R i = [ 0 d i × d 1 ⋯ 0 d i × d i − 1 I d i 0 d i × d i + 1 ⋯ 0 d i × d N ] . (25) R_i=[0_{d_i\times d_1}\ \cdots\ 0_{d_i\times d_{i-1}}\ I_{d_i}\ 0_{d_i\times d_{i+1}}\ \cdots\ 0_{d_i\times d_N}]. \tag*{(25)} R i = [ 0 d i × d 1 ⋯ 0 d i × d i − 1 I d i 0 d i × d i + 1 ⋯ 0 d i × d N ] . (25)
where, as before, D = ∑ i = 1 N d i D=\sum_{i=1}^{N}d_i D = ∑ i = 1 N d i .
We further define the sets of local joint action estimates:
Ω i = Q 1 × ⋯ × Q i − 1 × A i × Q i + 1 × ⋯ × Q N \Omega^{i}=Q^{1}\times\cdots\times Q^{i-1}\times A^{i}\times Q^{i+1}\times\cdots\times Q^{N} Ω i = Q 1 × ⋯ × Q i − 1 × A i × Q i + 1 × ⋯ × Q N
and Ω = ∏ i = 1 N Ω i \Omega=\prod_{i=1}^{N}\Omega^{i} Ω = ∏ i = 1 N Ω i . Next, for x = [ x 1 , … , x N ] ∈ R N D x=[x_1,\ldots,x_N]\in\mathbb{R}^{ND} x = [ x 1 , … , x N ] ∈ R N D , we define, with a slight abuse of notation,
P ( x ) = [ P ( x 1 ) , … , P ( x N ) ] (26) P(x)=[P(x_1),\ldots,P(x_N)] \tag*{(26)} P ( x ) = [ P ( x 1 ) , … , P ( x N )] (26)
and
M R ( x ) = [ R 1 T M 1 ( x 1 ) , … , R N T M N ( x N ) ] . M_R(x)=[R_1^{\mathsf{T}}M^{1}(x_1),\ldots,R_N^{\mathsf{T}}M^{N}(x_N)]. M R ( x ) = [ R 1 T M 1 ( x 1 ) , … , R N T M N ( x N )] .
Moreover, define W = W ⊗ I D W=W\otimes I_D W = W ⊗ I D . Then the compact form of the distributed hierarchical regularization scheme is given by
z ( t ) = W x ( t ) , z(t)=Wx(t), z ( t ) = W x ( t ) ,
x ( t + 1 ) = Π Ω [ z ( t ) − γ P ( z ( t ) ) − η ϵ t M R ( x ( t ) ) ] . (27) x(t+1)=\Pi_{\Omega}\left[z(t)-\gamma P(z(t))-\eta\epsilon_tM_R(x(t))\right]. \tag*{(27)} x ( t + 1 ) = Π Ω [ z ( t ) − γ P ( z ( t )) − η ϵ t M R ( x ( t )) ] . (27)
Convergence Analysis
We first formulate two auxiliary results (Lemmas 5 and 6) that are used to conduct the convergence analysis of Algorithm 2. Their proofs are deferred to the Appendix.
Next, for x = [ x 1 , … , x N ] ∈ R N D \boldsymbol{x}=[x_1,\ldots,x_N]\in\mathbb{R}^{ND} x = [ x 1 , … , x N ] ∈ R N D , we define the owned-action vector
a ( x ) = [ R 1 x 1 , … , R N x N ] , a(\boldsymbol{x})=[R_1x_1,\ldots,R_Nx_N], a ( x ) = [ R 1 x 1 , … , R N x N ] ,
where R i R_i R i , i ∈ [ N ] i\in[N] i ∈ [ N ] , is defined in (25) . Notice that, if x ∈ Ω \boldsymbol{x}\in\Omega x ∈ Ω , then a ( x ) ∈ A a(\boldsymbol{x})\in A a ( x ) ∈ A . Moreover, we define
Π ⊥ = ( I N − J ˉ ) ⊗ I D , x ⊥ = Π ⊥ x , \Pi_{\perp}=(I_N-\bar{J})\otimes I_D,\qquad\boldsymbol{x}^{\perp}=\Pi_{\perp}\boldsymbol{x}, Π ⊥ = ( I N − J ˉ ) ⊗ I D , x ⊥ = Π ⊥ x ,
as well as the consensual lower-level solution set:
S L = { 1 N ⊗ a : a ∈ S L } . S_L=\{\boldsymbol{1}_N\otimes a:a\in S_L\}. S L = { 1 N ⊗ a : a ∈ S L } .
Lemma 5. For every x ∈ R N D \boldsymbol{x}\in\mathbb{R}^{ND} x ∈ R N D , ∥ x − 1 N ⊗ a ( x ) ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 \|\boldsymbol{x}-\boldsymbol{1}_N\otimes a(\boldsymbol{x})\|^2\leq(N+1)\|\boldsymbol{x}^{\perp}\|^2 ∥ x − 1 N ⊗ a ( x ) ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 .
Lemma 6. Let ψ \psi ψ be an admissible penalty profile as in Definition 4. Under Assumptions 1(ii), 3, 6, and 7, define, for x ∈ Ω \boldsymbol{x}\in\Omega x ∈ Ω , z = W x \boldsymbol{z}=W\boldsymbol{x} z = W x and R ( x ) = ∥ x ⊥ ∥ 2 + ∥ P ( z ) ∥ 2 \mathcal{R}(\boldsymbol{x})=\|\boldsymbol{x}^{\perp}\|^2+\|P(\boldsymbol{z})\|^2 R ( x ) = ∥ x ⊥ ∥ 2 + ∥ P ( z ) ∥ 2 .
Then there exists C R > 0 C_R>0 C R > 0 , independent of x \boldsymbol{x} x , such that
dist ( x , S L ) 2 ≤ C R R ( x ) , ∀ x ∈ Ω . \operatorname{dist}(\boldsymbol{x},S_L)^2\leq C_R\mathcal{R}(\boldsymbol{x}),\qquad\forall\boldsymbol{x}\in\Omega. dist ( x , S L ) 2 ≤ C R R ( x ) , ∀ x ∈ Ω. Moreover, there exist constants K R , K a > 0 K_R,K_a>0 K R , K a > 0 , independent of x \boldsymbol{x} x and s s s , such that
∥ x − 1 N ⊗ s ∥ 2 ≤ K R R ( x ) + K a ∥ a ( x ) − s ∥ 2 , \|\boldsymbol{x}-\boldsymbol{1}_N\otimes s\|^2\leq K_R\mathcal{R}(\boldsymbol{x})+K_a\|a(\boldsymbol{x})-s\|^2, ∥ x − 1 N ⊗ s ∥ 2 ≤ K R R ( x ) + K a ∥ a ( x ) − s ∥ 2 , ∀ x ∈ Ω , ∀ s ∈ S L \forall\boldsymbol{x}\in\Omega,\ \forall s\in S_L ∀ x ∈ Ω , ∀ s ∈ S L .
With the results of Lemmas 5 and 6 in hand, we are now ready to present the main convergence result for Algorithm 2. Throughout the remainder of this section, the regularization parameter in Algorithm 2 is taken to be of the form
ε t = E ( t + 1 ) e , E > 0 , e ∈ ( 0 , 1 ] . \varepsilon_t=\frac{E}{(t+1)^e},\qquad E>0,\qquad e\in(0,1]. ε t = ( t + 1 ) e E , E > 0 , e ∈ ( 0 , 1 ] .
Theorem 3. Let Assumptions 1, 2, 3, 6, and 7 hold. Let a ⋆ a^\star a ⋆ be the unique solution of VI ( S L , M ) \operatorname{VI}(S_L,M) VI ( S L , M ) , and define x ⋆ = 1 N ⊗ a ⋆ \boldsymbol{x}^\star=\boldsymbol{1}_N\otimes a^\star x ⋆ = 1 N ⊗ a ⋆ . Then, for any γ ∈ ( 0 , 2 L P Q ) \gamma\in\left(0,\frac{2}{L_P^Q}\right) γ ∈ ( 0 , L P Q 2 ) and any η > 0 \eta>0 η > 0 , the sequence generated by (27) satisfies x ( t ) → x ⋆ \boldsymbol{x}(t)\to\boldsymbol{x}^\star x ( t ) → x ⋆ as t → ∞ t\to\infty t → ∞ . Moreover,
∥ x ( t ) − x ⋆ ∥ 2 = { O ( 1 t e ) , if e ∈ ( 0 , 1 ) , O ( 1 t ) , if e = 1 and E > 1 c . \|\boldsymbol{x}(t)-\boldsymbol{x}^\star\|^2=
\begin{cases}
O\left(\frac{1}{t^e}\right), & \text{if }e\in(0,1),\\
O\left(\frac{1}{t}\right), & \text{if }e=1\text{ and }E>\frac{1}{c}.
\end{cases} ∥ x ( t ) − x ⋆ ∥ 2 = { O ( t e 1 ) , O ( t 1 ) , if e ∈ ( 0 , 1 ) , if e = 1 and E > c 1 . where c > 0 c>0 c > 0 is a constant, given explicitly in the proof, that depends only on the problem and the algorithm parameters.
Proof. For the sake of brevity, set x t = x ( t ) \boldsymbol{x}_t=\boldsymbol{x}(t) x t = x ( t ) with blocks x i , t = x i ( t ) x_{i,t}=x_i(t) x i , t = x i ( t ) , z t = z ( t ) \boldsymbol{z}_t=\boldsymbol{z}(t) z t = z ( t ) , d t = x t − x ⋆ \boldsymbol{d}_t=\boldsymbol{x}_t-\boldsymbol{x}^\star d t = x t − x ⋆ , and a t = a ( x t ) a_t=a(\boldsymbol{x}_t) a t = a ( x t ) . Define
R t = ∥ x t ⊥ ∥ 2 + ∥ P ( z t ) ∥ 2 . (28) \mathcal{R}_t=\|\boldsymbol{x}_t^{\perp}\|^2+\|P(\boldsymbol{z}_t)\|^2. \tag*{(28)} R t = ∥ x t ⊥ ∥ 2 + ∥ P ( z t ) ∥ 2 . (28)
Since a ⋆ ∈ S L a^\star\in S_L a ⋆ ∈ S L , P ( a ⋆ ) = 0 P(a^\star)=0 P ( a ⋆ ) = 0 . Therefore, P ( x ⋆ ) = 0 P(\boldsymbol{x}^\star)=0 P ( x ⋆ ) = 0 . Define
u t = z t − x ⋆ − γ P ( z t ) . \boldsymbol{u}_t=\boldsymbol{z}_t-\boldsymbol{x}^\star-\gamma P(\boldsymbol{z}_t). u t = z t − x ⋆ − γ P ( z t ) .
Since x t ∈ Ω \boldsymbol{x}_t\in\Omega x t ∈ Ω , we have z i , t ∈ Q z_{i,t}\in Q z i , t ∈ Q for all i ∈ [ N ] i\in[N] i ∈ [ N ] (due to double stochasticity of W W W ) and x ⋆ = 1 N ⊗ a ⋆ ∈ Q × ⋯ × Q \boldsymbol{x}^\star=\boldsymbol{1}_N\otimes a^\star\in Q\times\cdots\times Q x ⋆ = 1 N ⊗ a ⋆ ∈ Q × ⋯ × Q (as a ⋆ ∈ S L ⊆ A ⊆ Q a^\star\in S_L\subseteq A\subseteq Q a ⋆ ∈ S L ⊆ A ⊆ Q ). Thus the cocoercivity inequality implied by Assumption 7 and [26 Thm. 3.1] on int Q \operatorname{int}Q int Q , extended to Q Q Q by continuity of P P P , applies to the pair ( z t , x ⋆ ) (\boldsymbol{z}_t,\boldsymbol{x}^\star) ( z t , x ⋆ ) , resulting in
⟨ P ( z t ) , z t − x ⋆ ⟩ = ⟨ P ( z t ) − P ( x ⋆ ) , z t − x ⋆ ⟩ ≥ 1 L P Q ∥ P ( z t ) − P ( x ⋆ ) ∥ 2 = 1 L P Q ∥ P ( z t ) ∥ 2 . \langle P(\boldsymbol{z}_t),\boldsymbol{z}_t-\boldsymbol{x}^\star\rangle=\langle P(\boldsymbol{z}_t)-P(\boldsymbol{x}^\star),\boldsymbol{z}_t-\boldsymbol{x}^\star\rangle\geq\frac{1}{L_P^Q}\|P(\boldsymbol{z}_t)-P(\boldsymbol{x}^\star)\|^2=\frac{1}{L_P^Q}\|P(\boldsymbol{z}_t)\|^2. ⟨ P ( z t ) , z t − x ⋆ ⟩ = ⟨ P ( z t ) − P ( x ⋆ ) , z t − x ⋆ ⟩ ≥ L P Q 1 ∥ P ( z t ) − P ( x ⋆ ) ∥ 2 = L P Q 1 ∥ P ( z t ) ∥ 2 .
Hence,
∥ u t ∥ 2 = ∥ z t − x ⋆ ∥ 2 − 2 γ ⟨ P ( z t ) , z t − x ⋆ ⟩ + γ 2 ∥ P ( z t ) ∥ 2 ≤ ∥ z t − x ⋆ ∥ 2 − γ ( 2 L P Q − γ ) ∥ P ( z t ) ∥ 2 . (29) \|\boldsymbol{u}_t\|^2=\|\boldsymbol{z}_t-\boldsymbol{x}^\star\|^2-2\gamma\langle P(\boldsymbol{z}_t),\boldsymbol{z}_t-\boldsymbol{x}^\star\rangle+\gamma^2\|P(\boldsymbol{z}_t)\|^2
\leq\|\boldsymbol{z}_t-\boldsymbol{x}^\star\|^2-\gamma\left(\frac{2}{L_P^Q}-\gamma\right)\|P(\boldsymbol{z}_t)\|^2. \tag*{(29)} ∥ u t ∥ 2 = ∥ z t − x ⋆ ∥ 2 − 2 γ ⟨ P ( z t ) , z t − x ⋆ ⟩ + γ 2 ∥ P ( z t ) ∥ 2 ≤ ∥ z t − x ⋆ ∥ 2 − γ ( L P Q 2 − γ ) ∥ P ( z t ) ∥ 2 . (29)
Moreover, since x ⋆ = 1 N ⊗ a ⋆ \boldsymbol{x}^\star=\boldsymbol{1}_N\otimes a^\star x ⋆ = 1 N ⊗ a ⋆ is already consensual, Π ⊥ x ⋆ = 0 \Pi_{\perp}\boldsymbol{x}^\star=0 Π ⊥ x ⋆ = 0 , and therefore Π ⊥ d t = Π ⊥ x t = x t ⊥ \Pi_{\perp}\boldsymbol{d}_t=\Pi_{\perp}\boldsymbol{x}_t=\boldsymbol{x}_t^{\perp} Π ⊥ d t = Π ⊥ x t = x t ⊥ . Recall J ˉ = 1 N 1 N 1 N T \bar{J}=\frac{1}{N}\boldsymbol{1}_N\boldsymbol{1}_N^\mathsf{T} J ˉ = N 1 1 N 1 N T . By double stochasticity of W W W (Assumption 6), one has W J ˉ = J ˉ W = J ˉ W\bar{J}=\bar{J}W=\bar{J} W J ˉ = J ˉ W = J ˉ , so that W ( J ˉ ⊗ I D ) = J ˉ ⊗ I D W(\bar{J}\otimes I_D)=\bar{J}\otimes I_D W ( J ˉ ⊗ I D ) = J ˉ ⊗ I D , W Π ⊥ = ( W − J ˉ ) ⊗ I D W\Pi_{\perp}=(W-\bar{J})\otimes I_D W Π ⊥ = ( W − J ˉ ) ⊗ I D , and W x ⋆ = x ⋆ W\boldsymbol{x}^\star=\boldsymbol{x}^\star W x ⋆ = x ⋆ . Consequently,
z t − x ⋆ = W d t = ( J ˉ ⊗ I D ) d t + ( ( W − J ˉ ) ⊗ I D ) x t ⊥ . \boldsymbol{z}_t-\boldsymbol{x}^\star=W\boldsymbol{d}_t=(\bar{J}\otimes I_D)\boldsymbol{d}_t+((W-\bar{J})\otimes I_D)\boldsymbol{x}_t^{\perp}. z t − x ⋆ = W d t = ( J ˉ ⊗ I D ) d t + (( W − J ˉ ) ⊗ I D ) x t ⊥ .
The two terms on the right are orthogonal, because J ˉ ( W − J ˉ ) = J ˉ W − J ˉ 2 = J ˉ − J ˉ = 0 \bar{J}(W-\bar{J})=\bar{J}W-\bar{J}^2=\bar{J}-\bar{J}=0 J ˉ ( W − J ˉ ) = J ˉ W − J ˉ 2 = J ˉ − J ˉ = 0 . Moreover, since J ˉ ⊗ I D \bar{J}\otimes I_D J ˉ ⊗ I D and Π ⊥ \Pi_{\perp} Π ⊥ are complementary orthogonal projections, ∥ d t ∥ 2 = ∥ ( J ˉ ⊗ I D ) d t ∥ 2 + ∥ x t ⊥ ∥ 2 \|\boldsymbol{d}_t\|^2=\|(\bar{J}\otimes I_D)\boldsymbol{d}_t\|^2+\|\boldsymbol{x}_t^{\perp}\|^2 ∥ d t ∥ 2 = ∥ ( J ˉ ⊗ I D ) d t ∥ 2 + ∥ x t ⊥ ∥ 2 . Combining these relations with the spectral bound ∥ W − J ˉ ∥ = σ ∈ [ 0 , 1 ) \|W-\bar{J}\|=\sigma\in[0,1) ∥ W − J ˉ ∥ = σ ∈ [ 0 , 1 ) furnished by Assumption 6 (see (24) ) gives
∥ z t − x ⋆ ∥ 2 = ∥ ( J ˉ ⊗ I D ) d t ∥ 2 + ∥ ( ( W − J ˉ ) ⊗ I D ) x t ⊥ ∥ 2 ≤ ∥ d t ∥ 2 − ( 1 − σ 2 ) ∥ x t ⊥ ∥ 2 . \|\boldsymbol{z}_t-\boldsymbol{x}^\star\|^2=\|(\bar{J}\otimes I_D)\boldsymbol{d}_t\|^2+\|((W-\bar{J})\otimes I_D)\boldsymbol{x}_t^{\perp}\|^2
\leq\|\boldsymbol{d}_t\|^2-(1-\sigma^2)\|\boldsymbol{x}_t^{\perp}\|^2. ∥ z t − x ⋆ ∥ 2 = ∥ ( J ˉ ⊗ I D ) d t ∥ 2 + ∥ (( W − J ˉ ) ⊗ I D ) x t ⊥ ∥ 2 ≤ ∥ d t ∥ 2 − ( 1 − σ 2 ) ∥ x t ⊥ ∥ 2 .
Hence, (29) and the preceding inequalities yield (see also (28) )
∥ u t ∥ 2 ≤ ∥ d t ∥ 2 − c L R t , (30) \|\boldsymbol{u}_t\|^2\leq\|\boldsymbol{d}_t\|^2-c_L\mathcal{R}_t, \tag*{(30)} ∥ u t ∥ 2 ≤ ∥ d t ∥ 2 − c L R t , (30)
where c L = min { 1 − σ 2 , γ ( 2 L P Q − γ ) } > 0 c_L=\min\left\{1-\sigma^2,\gamma\left(\frac{2}{L_P^Q}-\gamma\right)\right\}>0 c L = min { 1 − σ 2 , γ ( L P Q 2 − γ ) } > 0 , which is strictly positive precisely because 0 < γ < 2 / L P Q 0<\gamma<2/L_P^Q 0 < γ < 2/ L P Q .
Since x ⋆ ∈ Ω \boldsymbol{x}^\star\in\Omega x ⋆ ∈ Ω , nonexpansiveness of the projection in (27) gives
∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ u t − η ε t M R ( x t ) ∥ 2 = ∥ u t ∥ 2 − 2 η ε t ⟨ M R ( x t ) , u t ⟩ + η 2 ε t 2 ∥ M R ( x t ) ∥ 2 . (31) \|\boldsymbol{x}_{t+1}-\boldsymbol{x}^\star\|^2\leq\|\boldsymbol{u}_t-\eta\varepsilon_t M_R(\boldsymbol{x}_t)\|^2
=\|\boldsymbol{u}_t\|^2-2\eta\varepsilon_t\langle M_R(\boldsymbol{x}_t),\boldsymbol{u}_t\rangle+\eta^2\varepsilon_t^2\|M_R(\boldsymbol{x}_t)\|^2. \tag*{(31)} ∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ u t − η ε t M R ( x t ) ∥ 2 = ∥ u t ∥ 2 − 2 η ε t ⟨ M R ( x t ) , u t ⟩ + η 2 ε t 2 ∥ M R ( x t ) ∥ 2 . (31)
We now bound the middle and last terms of this expansion. The constants, obtained from the compactness furnished by Assumption 7, will be used throughout. Since A A A is compact, the diameter Δ = sup a , b ∈ A ∥ a − b ∥ \Delta=\sup_{a,b\in A}\|a-b\| Δ = sup a , b ∈ A ∥ a − b ∥ is finite. Moreover, the maximum M max = max a ∈ A ∥ M ( a ) ∥ M_{\max}=\max_{a\in A}\|M(a)\| M m a x = max a ∈ A ∥ M ( a ) ∥ is attained and finite. Because x i , t ∈ Q x_{i,t}\in Q x i , t ∈ Q for every t t t , we have a t , a ⋆ ∈ A a_t,a^\star\in A a t , a ⋆ ∈ A and x i , t ∈ Q x_{i,t}\in Q x i , t ∈ Q for every i i i , so that, throughout the proof, ∥ a t − a ⋆ ∥ ≤ Δ \|a_t-a^\star\|\leq\Delta ∥ a t − a ⋆ ∥ ≤ Δ and ∥ M i ( x i , t ) ∥ ≤ ∥ M ( x i , t ) ∥ ≤ M max \|M^i(x_{i,t})\|\leq\|M(x_{i,t})\|\leq M_{\max} ∥ M i ( x i , t ) ∥ ≤ ∥ M ( x i , t ) ∥ ≤ M m a x for all i ∈ [ N ] i\in[N] i ∈ [ N ] and all t t t .
Estimate of the middle term ⟨ M R ( x t ) , u t ⟩ \langle M_R(\boldsymbol{x}_t),\boldsymbol{u}_t\rangle ⟨ M R ( x t ) , u t ⟩ . Since
u t = d t + ( z t − x t ) − γ P ( z t ) , \boldsymbol{u}_t=\boldsymbol{d}_t+(\boldsymbol{z}_t-\boldsymbol{x}_t)-\gamma P(\boldsymbol{z}_t), u t = d t + ( z t − x t ) − γ P ( z t ) ,
we have
⟨ M R ( x t ) , u t ⟩ = ⟨ M R ( x t ) , d t ⟩ ⏟ ( a ) + ⟨ M R ( x t ) , z t − x t ⟩ − γ ⟨ M R ( x t ) , P ( z t ) ⟩ ⏟ ( b ) . \langle M_R(\boldsymbol{x}_t),\boldsymbol{u}_t\rangle
=\underbrace{\langle M_R(\boldsymbol{x}_t),\boldsymbol{d}_t\rangle}_{(a)}
+\underbrace{\langle M_R(\boldsymbol{x}_t),\boldsymbol{z}_t-\boldsymbol{x}_t\rangle-\gamma\langle M_R(\boldsymbol{x}_t),P(\boldsymbol{z}_t)\rangle}_{(b)}. ⟨ M R ( x t ) , u t ⟩ = ( a ) ⟨ M R ( x t ) , d t ⟩ + ( b ) ⟨ M R ( x t ) , z t − x t ⟩ − γ ⟨ M R ( x t ) , P ( z t )⟩ .
Term (a). By definition of M R M_R M R and of the selection matrices R i R_i R i ,
⟨ M R ( x t ) , d t ⟩ = ⟨ M ( a t ) , a t − a ⋆ ⟩ + ζ t , (32) \langle M_R(\boldsymbol{x}_t),\boldsymbol{d}_t\rangle=\langle M(a_t),a_t-a^\star\rangle+\zeta_t, \tag*{(32)} ⟨ M R ( x t ) , d t ⟩ = ⟨ M ( a t ) , a t − a ⋆ ⟩ + ζ t , (32)
with ζ t = ∑ i = 1 N ⟨ M i ( x i , t ) − M i ( a t ) , a t i − a ⋆ i ⟩ \zeta_t=\sum_{i=1}^N\langle M^i(x_{i,t})-M^i(a_t),a_t^i-a^{\star i}\rangle ζ t = ∑ i = 1 N ⟨ M i ( x i , t ) − M i ( a t ) , a t i − a ⋆ i ⟩ , where a t i = R i x i , t a_t^i=R_ix_{i,t} a t i = R i x i , t and a ⋆ i = R i a ⋆ a^{\star i}=R_ia^\star a ⋆ i = R i a ⋆ denote the i i i -th blocks of a t = a ( x t ) a_t=a(\boldsymbol{x}_t) a t = a ( x t ) and a ⋆ a^\star a ⋆ . By the Cauchy–Schwarz inequality, using ∑ i = 1 N ∥ a t i − a ⋆ i ∥ 2 = ∥ a t − a ⋆ ∥ 2 ≤ Δ 2 \sum_{i=1}^N\|a_t^i-a^{\star i}\|^2=\|a_t-a^\star\|^2\leq\Delta^2 ∑ i = 1 N ∥ a t i − a ⋆ i ∥ 2 = ∥ a t − a ⋆ ∥ 2 ≤ Δ 2 ,
∣ ζ t ∣ ≤ Δ ( ∑ i = 1 N ∥ M i ( x i , t ) − M i ( a t ) ∥ 2 ) 1 / 2 . |\zeta_t|\leq\Delta\left(\sum_{i=1}^N\|M^i(x_{i,t})-M^i(a_t)\|^2\right)^{1/2}. ∣ ζ t ∣ ≤ Δ ( i = 1 ∑ N ∥ M i ( x i , t ) − M i ( a t ) ∥ 2 ) 1/2 .
Since x i , t , a t ∈ Q x_{i,t},a_t\in Q x i , t , a t ∈ Q , Assumption 7 gives ∥ M i ( x i , t ) − M i ( a t ) ∥ ≤ L M Q ∥ x i , t − a t ∥ \|M^i(x_{i,t})-M^i(a_t)\|\leq L_M^Q\|x_{i,t}-a_t\| ∥ M i ( x i , t ) − M i ( a t ) ∥ ≤ L M Q ∥ x i , t − a t ∥ for every i i i . Thus,
( ∑ i = 1 N ∥ M i ( x i , t ) − M i ( a t ) ∥ 2 ) 1 / 2 ≤ L M Q ∥ x t − 1 N ⊗ a t ∥ ≤ L M Q N + 1 ∥ x t ⊥ ∥ . \left(\sum_{i=1}^N\|M^i(x_{i,t})-M^i(a_t)\|^2\right)^{1/2}
\leq L_M^Q\|\boldsymbol{x}_t-\boldsymbol{1}_N\otimes a_t\|
\leq L_M^Q\sqrt{N+1}\|\boldsymbol{x}_t^{\perp}\|. ( i = 1 ∑ N ∥ M i ( x i , t ) − M i ( a t ) ∥ 2 ) 1/2 ≤ L M Q ∥ x t − 1 N ⊗ a t ∥ ≤ L M Q N + 1 ∥ x t ⊥ ∥.
where in the last inequality we used Lemma 5. Combining the last two relations and using ∥ x t ∥ ≤ R t \lVert x_t\rVert\le\sqrt{R_t} ∥ x t ∥ ≤ R t (see again (28) ), we conclude that
∣ ζ t ∣ ≤ Δ L M Q N + 1 R t . (33) |\zeta_t| \le\Delta L_M^Q\sqrt{N+1}\sqrt{R_t}. \tag*{(33)} ∣ ζ t ∣ ≤ Δ L M Q N + 1 R t . (33)
For the remaining term, strong monotonicity of M M M (Assumption 2) together with the variational-inequality optimality of a ⋆ a^\star a ⋆ for VI ( S L , M ) \operatorname{VI}(S_L,M) VI ( S L , M ) , applied at s t = Π S L ( a t ) s_t=\Pi_{S_L}(a_t) s t = Π S L ( a t ) , i.e., ⟨ M ( a ⋆ ) , s t − a ⋆ ⟩ ≥ 0 \langle M(a^\star),s_t-a^\star\rangle\ge0 ⟨ M ( a ⋆ ) , s t − a ⋆ ⟩ ≥ 0 , gives
⟨ M ( a t ) , a t − a ⋆ ⟩ = ⟨ M ( a t ) − M ( a ⋆ ) , a t − a ⋆ ⟩ + ⟨ M ( a ⋆ ) , a t − a ⋆ ⟩ ≥ μ ∥ a t − a ⋆ ∥ 2 − M max d ˉ t , (34) \begin{aligned}
\langle M(a_t),a_t-a^\star\rangle
&=\langle M(a_t)-M(a^\star),a_t-a^\star\rangle\\
&\quad+\langle M(a^\star),a_t-a^\star\rangle\\
&\ge\mu\lVert a_t-a^\star\rVert^2-M_{\max}\bar d_t, \tag*{(34)}
\end{aligned} ⟨ M ( a t ) , a t − a ⋆ ⟩ = ⟨ M ( a t ) − M ( a ⋆ ) , a t − a ⋆ ⟩ + ⟨ M ( a ⋆ ) , a t − a ⋆ ⟩ ≥ μ ∥ a t − a ⋆ ∥ 2 − M m a x d ˉ t , (34)
where d ˉ t = dist ( x t , S L ) \bar d_t=\operatorname{dist}(x_t,S_L) d ˉ t = dist ( x t , S L ) , we used ∥ M ( a ⋆ ) ∥ ≤ M max \lVert M(a^\star)\rVert\le M_{\max} ∥ M ( a ⋆ )∥ ≤ M m a x , and the last inequality uses ∥ a t − s t ∥ = dist ( a t , S L ) ≤ d ˉ t \lVert a_t-s_t\rVert=\operatorname{dist}(a_t,S_L)\le\bar d_t ∥ a t − s t ∥ = dist ( a t , S L ) ≤ d ˉ t (since 1 N ⊗ s t ∈ S L \mathbf{1}_N\otimes s_t\in S_L 1 N ⊗ s t ∈ S L and ∥ a t − s t ∥ ≤ ∥ x t − 1 N ⊗ s t ∥ \lVert a_t-s_t\rVert\le\lVert x_t-\mathbf{1}_N\otimes s_t\rVert ∥ a t − s t ∥ ≤ ∥ x t − 1 N ⊗ s t ∥ ). By Lemma 6, d ˉ t ≤ C R R t \bar d_t\le\sqrt{C_R}\sqrt{R_t} d ˉ t ≤ C R R t . Combining this last inequality with (33) and (34) and inserting it into (32) , we obtain
⟨ M R ( x t ) , d t ⟩ ≥ μ ∥ a t − a ⋆ ∥ 2 − C a R t , \langle M_R(x_t),d_t\rangle\ge\mu\lVert a_t-a^\star\rVert^2-C_a\sqrt{R_t}, ⟨ M R ( x t ) , d t ⟩ ≥ μ ∥ a t − a ⋆ ∥ 2 − C a R t ,
where C a = M max C R + Δ L M Q N + 1 C_a=M_{\max}\sqrt{C_R}+\Delta L_M^Q\sqrt{N+1} C a = M m a x C R + Δ L M Q N + 1 .
Term (b). Since z t − x t = ( W − I N D ) x t = ( ( W − I N ) ⊗ I D ) x t ⊥ z_t-x_t=(W-I_{ND})x_t=((W-I_N)\otimes I_D)x_t^\perp z t − x t = ( W − I N D ) x t = (( W − I N ) ⊗ I D ) x t ⊥ , we have
∥ z t − x t ∥ ≤ C W R t , C W = ∥ W − I N ∥ . \lVert z_t-x_t\rVert\le C_W\sqrt{R_t},\qquad C_W=\lVert W-I_N\rVert. ∥ z t − x t ∥ ≤ C W R t , C W = ∥ W − I N ∥ .
Moreover, since M R ( x t ) = [ R 1 ⊤ M 1 ( x 1 , t ) , … , R N ⊤ M N ( x N , t ) ] M_R(x_t)=[R_1^\top M^1(x_{1,t}),\ldots,R_N^\top M^N(x_{N,t})] M R ( x t ) = [ R 1 ⊤ M 1 ( x 1 , t ) , … , R N ⊤ M N ( x N , t )] , we have ∥ M R ( x t ) ∥ 2 = ∑ i = 1 N ∥ M i ( x i , t ) ∥ 2 ≤ N M max 2 \lVert M_R(x_t)\rVert^2=\sum_{i=1}^N\lVert M^i(x_{i,t})\rVert^2\le NM_{\max}^2 ∥ M R ( x t ) ∥ 2 = ∑ i = 1 N ∥ M i ( x i , t ) ∥ 2 ≤ N M m a x 2 and, thus, the uniform bound ∥ M R ( x t ) ∥ ≤ M ˉ R = N M max \lVert M_R(x_t)\rVert\le\bar M_R=\sqrt{N}M_{\max} ∥ M R ( x t )∥ ≤ M ˉ R = N M m a x . By the Cauchy–Schwarz inequality,
∣ ( b ) ∣ ≤ ∥ M R ( x t ) ∥ ( ∥ z t − x t ∥ + γ ∥ P ( z t ) ∥ ) ≤ C b R t , |(b)|\le\lVert M_R(x_t)\rVert(\lVert z_t-x_t\rVert+\gamma\lVert P(z_t)\rVert)\le C_b\sqrt{R_t}, ∣ ( b ) ∣ ≤ ∥ M R ( x t )∥ (∥ z t − x t ∥ + γ ∥ P ( z t )∥) ≤ C b R t ,
where C b = M ˉ R ( C W + γ ) C_b=\bar M_R(C_W+\gamma) C b = M ˉ R ( C W + γ ) .
Combined estimate. Adding the bounds for (a) and (b), with C ⋆ = C a + C b C_\star=C_a+C_b C ⋆ = C a + C b ,
⟨ M R ( x t ) , u t ⟩ ≥ μ ∥ a t − a ⋆ ∥ 2 − C ⋆ R t . (35) \langle M_R(x_t),u_t\rangle\ge\mu\lVert a_t-a^\star\rVert^2-C_\star\sqrt{R_t}. \tag*{(35)} ⟨ M R ( x t ) , u t ⟩ ≥ μ ∥ a t − a ⋆ ∥ 2 − C ⋆ R t . (35)
Substituting (30) , (35) , and ∥ M R ( x t ) ∥ 2 ≤ M ˉ R 2 \lVert M_R(x_t)\rVert^2\le\bar M_R^2 ∥ M R ( x t ) ∥ 2 ≤ M ˉ R 2 into the estimate (31) gives
∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − c L R t − 2 η μ ε t ∥ a t − a ⋆ ∥ 2 + 2 η C ⋆ ε t R t + η 2 M ˉ R 2 ε t 2 . \lVert x_{t+1}-x^\star\rVert^2\le\lVert d_t\rVert^2-c_LR_t-2\eta\mu\varepsilon_t\lVert a_t-a^\star\rVert^2+2\eta C_\star\varepsilon_t\sqrt{R_t}+\eta^2\bar M_R^2\varepsilon_t^2. ∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − c L R t − 2 η μ ε t ∥ a t − a ⋆ ∥ 2 + 2 η C ⋆ ε t R t + η 2 M ˉ R 2 ε t 2 .
By Young’s inequality, 2 η C ⋆ ε t R t ≤ c L 2 R t + 2 η 2 C ⋆ 2 c L ε t 2 2\eta C_\star\varepsilon_t\sqrt{R_t}\le\frac{c_L}{2}R_t+\frac{2\eta^2C_\star^2}{c_L}\varepsilon_t^2 2 η C ⋆ ε t R t ≤ 2 c L R t + c L 2 η 2 C ⋆ 2 ε t 2 , so that, for every t ≥ 0 t\ge0 t ≥ 0 ,
∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − c L 2 R t − 2 η μ ε t ∥ a t − a ⋆ ∥ 2 + C 4 ε t 2 (36) \lVert x_{t+1}-x^\star\rVert^2\le\lVert d_t\rVert^2-\frac{c_L}{2}R_t-2\eta\mu\varepsilon_t\lVert a_t-a^\star\rVert^2+C_4\varepsilon_t^2 \tag*{(36)} ∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ d t ∥ 2 − 2 c L R t − 2 η μ ε t ∥ a t − a ⋆ ∥ 2 + C 4 ε t 2 (36)
where C 4 = 2 η 2 C ⋆ 2 c L + η 2 M ˉ R 2 C_4=\frac{2\eta^2C_\star^2}{c_L}+\eta^2\bar M_R^2 C 4 = c L 2 η 2 C ⋆ 2 + η 2 M ˉ R 2 .
By Lemma 6, ∥ d t ∥ 2 ≤ K R R t + K a ∥ a t − a ⋆ ∥ 2 \lVert d_t\rVert^2\le K_RR_t+K_a\lVert a_t-a^\star\rVert^2 ∥ d t ∥ 2 ≤ K R R t + K a ∥ a t − a ⋆ ∥ 2 for all t ≥ 0 t\ge0 t ≥ 0 . Since ε t = E / ( t + 1 ) e ≤ E \varepsilon_t=E/(t+1)^e\le E ε t = E / ( t + 1 ) e ≤ E for every sufficiently large t ≥ 0 t\ge0 t ≥ 0 , setting c = min { c L 2 K R E , 2 η μ K a } c=\min\left\{\frac{c_L}{2K_RE},\frac{2\eta\mu}{K_a}\right\} c = min { 2 K R E c L , K a 2 η μ } ensures c ε t K R ≤ c L / 2 c\varepsilon_tK_R\le c_L/2 c ε t K R ≤ c L /2 and c K a ≤ 2 η μ cK_a\le2\eta\mu c K a ≤ 2 η μ for every t ≥ 0 t\ge0 t ≥ 0 , and therefore
c ε t ∥ d t ∥ 2 ≤ c ε t K R R t + c ε t K a ∥ a t − a ⋆ ∥ 2 ≤ c L 2 R t + 2 η μ ε t ∥ a t − a ⋆ ∥ 2 , c\varepsilon_t\lVert d_t\rVert^2\le c\varepsilon_tK_RR_t+c\varepsilon_tK_a\lVert a_t-a^\star\rVert^2\le\frac{c_L}{2}R_t+2\eta\mu\varepsilon_t\lVert a_t-a^\star\rVert^2, c ε t ∥ d t ∥ 2 ≤ c ε t K R R t + c ε t K a ∥ a t − a ⋆ ∥ 2 ≤ 2 c L R t + 2 η μ ε t ∥ a t − a ⋆ ∥ 2 ,
implying − c L 2 R t ≤ − c ε t ∥ d t ∥ 2 + 2 η μ ε t ∥ a t − a ⋆ ∥ 2 -\frac{c_L}{2}R_t\le-c\varepsilon_t\lVert d_t\rVert^2+2\eta\mu\varepsilon_t\lVert a_t-a^\star\rVert^2 − 2 c L R t ≤ − c ε t ∥ d t ∥ 2 + 2 η μ ε t ∥ a t − a ⋆ ∥ 2 . Consequently, (36) implies, for every sufficiently large t ≥ 0 t\ge0 t ≥ 0 ,
∥ x t + 1 − x ⋆ ∥ 2 ≤ ( 1 − c ε t ) ∥ x t − x ⋆ ∥ 2 + C 4 ε t 2 . \lVert x_{t+1}-x^\star\rVert^2\le(1-c\varepsilon_t)\lVert x_t-x^\star\rVert^2+C_4\varepsilon_t^2. ∥ x t + 1 − x ⋆ ∥ 2 ≤ ( 1 − c ε t ) ∥ x t − x ⋆ ∥ 2 + C 4 ε t 2 .
Lemma 9 with p = e p=e p = e , q = 2 e q=2e q = 2 e , and a = c E a=cE a = c E , applied to the scalar recursion above, gives ∥ x t − x ⋆ ∥ 2 → 0 \lVert x_t-x^\star\rVert^2\to0 ∥ x t − x ⋆ ∥ 2 → 0 , and moreover ∥ x t − x ⋆ ∥ 2 = O ( ε t ) = O ( 1 / t e ) \lVert x_t-x^\star\rVert^2=O(\varepsilon_t)=O(1/t^e) ∥ x t − x ⋆ ∥ 2 = O ( ε t ) = O ( 1/ t e ) whenever e ∈ ( 0 , 1 ) e\in(0,1) e ∈ ( 0 , 1 ) , while for e = 1 e=1 e = 1 one obtains the faster rate ∥ x t − x ⋆ ∥ 2 = O ( 1 / t ) \lVert x_t-x^\star\rVert^2=O(1/t) ∥ x t − x ⋆ ∥ 2 = O ( 1/ t ) provided c E > 1 cE>1 c E > 1 . This proves the convergence and rate claims of the theorem.
Simulation Results
We evaluate the proposed hierarchical VI reformulation and its centralized and distributed algorithms (Sections IV and V) on randomly generated strongly monotone GNEP instances constructed so that a ground-truth v-GNE ( a ⋆ , λ ⋆ ) (a^\star,\lambda^\star) ( a ⋆ , λ ⋆ ) satisfying the KKT conditions (3) is known by construction, which allows us to directly measure the distance ∥ a ( t ) − a ⋆ ∥ \lVert a(t)-a^\star\rVert ∥ a ( t ) − a ⋆ ∥ to the true equilibrium. We consider three settings: centralized GNE seeking with nonlinear shared constraints, and distributed GNE seeking with nonlinear and with linear shared constraints, respectively. In each setting, we report results averaged over 20 random instances of problems of the same size, with strong monotonicity constant μ = 0.1 \mu=0.1 μ = 0.1 . All tests were run on a MacBook Pro with an Apple M5 Max chip.
Centralized, nonlinear shared constraints
The test instances are obtained by drawing a target equilibrium a ⋆ ∈ R D a^\star\in\mathbb{R}^D a ⋆ ∈ R D with i.i.d. standard Gaussian entries and then constructing the GNEP around this target equilibrium with convex quadratic costs, local box constraints, and nonlinear shared constraints. Following the construction suggested in [4 ] , each player i ∈ [ N ] i\in[N] i ∈ [ N ] has the cost
J i ( a ) = 1 2 a ⊤ H i a + ( c i ) ⊤ a i (37) J^i(a)=\frac{1}{2}a^\top H^ia+(c^i)^\top a^i \tag*{(37)} J i ( a ) = 2 1 a ⊤ H i a + ( c i ) ⊤ a i (37)
where c i ∈ R d i c^i\in\mathbb{R}^{d_i} c i ∈ R d i and the symmetric matrix H i H^i H i has ( i , j ) (i,j) ( i , j ) block G i j G_{ij} G ij and ( j , i ) (j,i) ( j , i ) block G i j ⊤ G_{ij}^\top G ij ⊤ for all j ∈ [ N ] j\in[N] j ∈ [ N ] , and zero blocks elsewhere, with G i j ∈ R d i × d j G_{ij}\in\mathbb{R}^{d_i\times d_j} G ij ∈ R d i × d j the blocks of the matrix
G = V ⊤ V + S − S ⊤ + ( μ − λ min ( V ⊤ V ) ) I D . G=V^\top V+S-S^\top+(\mu-\lambda_{\min}(V^\top V))I_D. G = V ⊤ V + S − S ⊤ + ( μ − λ m i n ( V ⊤ V )) I D .
Here V ∈ R D × D V\in\mathbb{R}^{D\times D} V ∈ R D × D is upper triangular and S ∈ R D × D S\in\mathbb{R}^{D\times D} S ∈ R D × D is strictly lower block triangular with respect to the partition of a a a into a 1 , … , a N a^1,\ldots,a^N a 1 , … , a N , both with i.i.d. standard Gaussian nonzero entries. By construction, the pseudo-gradient is the affine mapping M ( a ) = G a + c M(a)=Ga+c M ( a ) = G a + c , with c = [ c 1 , … , c N ] c=[c^1,\ldots,c^N] c = [ c 1 , … , c N ] , and since 1 2 ( G + G ⊤ ) = V ⊤ V + ( μ − λ min ( V ⊤ V ) ) I \frac{1}{2}(G+G^\top)=V^\top V+(\mu-\lambda_{\min}(V^\top V))I 2 1 ( G + G ⊤ ) = V ⊤ V + ( μ − λ m i n ( V ⊤ V )) I has minimum eigenvalue equal to μ \mu μ , M M M is μ \mu μ -strongly monotone and ∥ G ∥ \lVert G\rVert ∥ G ∥ -Lipschitz continuous, as required by Assumption 2. The players are coupled through m = n e + n q m=n_e+n_q m = n e + n q shared constraints g ( a ) ≤ 0 g(a)\le0 g ( a ) ≤ 0 , namely n e n_e n e log-sum-exp and n q n_q n q convex quadratic constraints
g s ( a ) = log ∑ k = 1 2 exp ( α s , k ⊤ a + β s , k ) − r s ≤ 0 s ∈ [ n e ] g_s(a)=\log\sum_{k=1}^{2}\exp(\alpha_{s,k}^\top a+\beta_{s,k})-r_s\le0\qquad s\in[n_e] g s ( a ) = log k = 1 ∑ 2 exp ( α s , k ⊤ a + β s , k ) − r s ≤ 0 s ∈ [ n e ]
g n e + s ( a ) = a ⊤ P s a + p s ⊤ a − r n e + s ≤ 0 s ∈ [ n q ] . (38) g_{n_e+s}(a)=a^\top P_sa+p_s^\top a-r_{n_e+s}\le0\qquad s\in[n_q]. \tag*{(38)} g n e + s ( a ) = a ⊤ P s a + p s ⊤ a − r n e + s ≤ 0 s ∈ [ n q ] . (38)
where α s , k , p s ∈ R D \alpha_{s,k},p_s\in\mathbb{R}^D α s , k , p s ∈ R D and β s , k ∈ R \beta_{s,k}\in\mathbb{R} β s , k ∈ R have i.i.d. Gaussian entries (with variance 1 / D 1/D 1/ D for α s , k \alpha_{s,k} α s , k and p s p_s p s ), and P s = B s ⊤ B s ⪰ 0 P_s=B_s^\top B_s\succeq0 P s = B s ⊤ B s ⪰ 0 , with B s ∈ R D × D B_s\in\mathbb{R}^{D\times D} B s ∈ R D × D having Gaussian entries with variance 1 / D 1/D 1/ D . A subset J a ⊆ [ m ] \mathcal{J}_a\subseteq[m] J a ⊆ [ m ] of m a m_a m a constraints is selected at random to be active at a ⋆ a^\star a ⋆ : the offsets r j r_j r j are chosen such that g j ( a ⋆ ) = 0 g_j(a^\star)=0 g j ( a ⋆ ) = 0 for j ∈ J a j\in\mathcal{J}_a j ∈ J a and g j ( a ⋆ ) = − δ j g_j(a^\star)=-\delta_j g j ( a ⋆ ) = − δ j for j ∉ J a j\notin\mathcal{J}_a j ∈ / J a , with slack δ j \delta_j δ j uniformly distributed in [ 0.5 , 1.5 ] [0.5,1.5] [ 0.5 , 1.5 ] . The local activation set on the box constraints are A i = { a i : a ‾ i ≤ a i ≤ a ‾ i } \mathcal{A}^i=\{a^i:\underline a^i\le a^i\le\overline a^i\} A i = { a i : a i ≤ a i ≤ a i } , whose bounds are obtained by subtracting from and adding to each entry of a ⋆ , i a^{\star,i} a ⋆ , i numbers uniformly distributed in [ 0.5 , 1.5 ] [0.5,1.5] [ 0.5 , 1.5 ] , so that a ⋆ a^\star a ⋆ lies in the interior of A \mathcal{A} A and N A ( a ⋆ ) = { 0 } \mathcal{N}_{\mathcal{A}}(a^\star)=\{0\} N A ( a ⋆ ) = { 0 } . The multipliers are set to λ j ⋆ \lambda_j^\star λ j ⋆ uniformly distributed in [ 0.5 , 1.5 ] [0.5,1.5] [ 0.5 , 1.5 ] for j ∈ J a j \in\mathcal{J}_a j ∈ J a and λ j ⋆ = 0 \lambda_j^\star= 0 λ j ⋆ = 0 otherwise. Finally, the linear cost terms are chosen as
c = − G a ⋆ − ∇ g ( a ⋆ ) T λ ⋆ c=-Ga^\star-\nabla g(a^\star)^{\mathsf T}\lambda^\star c = − G a ⋆ − ∇ g ( a ⋆ ) T λ ⋆
so that the KKT conditions (3) hold at ( a ⋆ , λ ⋆ ) (a^\star,\lambda^\star) ( a ⋆ , λ ⋆ ) with strict complementarity. Since the game is strongly monotone with continuous costs over the defined compact, convex, nonempty constraint set, a ⋆ a^\star a ⋆ is the unique v-GNE of the generated game. Such a random problem construction is implemented in NashOpt [3 ] .
We test the centralized algorithm of Section IV using N = 10 N=10 N = 10 players with d i = 3 d_i=3 d i = 3 , i = 1 , … , N i=1,\ldots,N i = 1 , … , N (i.e., 30 variables in total), coupled through 500 nonlinear shared constraints of the form (38) , 3 of which are active at the v-GNE. We use the Huber profile of Example 2 with ω = 0.03 \omega=0.03 ω = 0.03 , ε t = 0.01 / ( t + 1 ) 2 / 3 \varepsilon_t=0.01/(t+1)^{2/3} ε t = 0.01/ ( t + 1 ) 2/3 , η = 10 γ \eta=10\gamma η = 10 γ , and γ = 2 / L ^ P \gamma=2/\widehat{L}_P γ = 2/ L P , where L ^ P \widehat{L}_P L P is a numerical estimate of the Lipschitz constant of P P P . This stepsize sits at the boundary of the admissible range ( 0 , 2 / L P ) (0,2/L_P) ( 0 , 2/ L P ) of Theorems 1 and 2. On this family we compare the proposed algorithm against the Golden Ratio Algorithm (GRAAL) [19 ] on the lifted primal–dual VI (4) , and Operator Extrapolation [15 ] using projection steps onto the nonlinear feasible set at each iteration and applied directly to the non-lifted variational GNE problem. As shown in Figure 1 , the proposed hierarchical VI algorithm attains the smallest distance to the v-GNE. Note that, while our algorithm requires only projections onto local box constraints, Operator Extrapolation solves an auxiliary optimization problem to project onto the nonlinear coupled feasible set at every iteration, and GRAAL operates in the lifted primal–dual space of dimension 30 + 500 = 530 30+500=530 30 + 500 = 530 .
Figure 1. Centralized GNE seeking, nonlinear constraints: Distance to the true v-GNE a ⋆ a^\star a ⋆ as a function of CPU time.
Distributed, nonlinear shared constraints
We next test the distributed hierarchical VI algorithm (Algorithm 2) on instances generated as described above with N = 10 N=10 N = 10 agents with scalar actions, i.e., d i = 1 d_i=1 d i = 1 , i ∈ [ N ] i\in[N] i ∈ [ N ] , no linear shared constraints, and m ∈ { 4 , 8 , 12 } m\in\{4,8,12\} m ∈ { 4 , 8 , 12 } nonlinear shared constraints split evenly between log-sum-exp and quadratic terms, m a = 4 m_a=4 m a = 4 of which are active at the v-GNE a ⋆ a^\star a ⋆ . The agents communicate over a fixed random connected graph with 22 out of 45 possible edges, using Metropolis–Hastings weights w i j = 1 / max { ∣ N i ∣ , ∣ N j ∣ } w_{ij}=1/\max\{|\mathcal{N}_i|,|\mathcal{N}_j|\} w ij = 1/ max { ∣ N i ∣ , ∣ N j ∣ } for j ∈ N i ∖ { i } j\in\mathcal{N}_i\setminus\{i\} j ∈ N i ∖ { i } and w i i = 1 − ∑ j ≠ i w i j w_{ii}=1-\sum_{j\ne i}w_{ij} w ii = 1 − ∑ j = i w ij , which gives σ ≈ 0.78 \sigma\approx0.78 σ ≈ 0.78 in (24) . We use the Huber profile of Example 2 with ω = 0.03 \omega=0.03 ω = 0.03 , ε t = 0.01 / ( t + 1 ) 2 / 3 \varepsilon_t=0.01/(t+1)^{2/3} ε t = 0.01/ ( t + 1 ) 2/3 , γ = 2 ⋅ 0.9999 / L ^ P \gamma=2\cdot0.9999/\widehat{L}_P γ = 2 ⋅ 0.9999/ L P , where L ^ P \widehat{L}_P L P is a numerical estimate of the Lipschitz constant of P P P , so that γ \gamma γ lies just inside the admissible range ( 0 , 2 / L P Q ) (0,2/L_P^Q) ( 0 , 2/ L P Q ) of Theorem 3 , η = 10 γ \eta=10\gamma η = 10 γ , Q j = A j Q^j=A^j Q j = A j , and x i ( 0 ) = 0 x_i(0)=0 x i ( 0 ) = 0 for all i ∈ [ N ] i\in[N] i ∈ [ N ] . Figure 2 reports the distance ∥ a ( t ) − a ⋆ ∥ \|a(t)-a^\star\| ∥ a ( t ) − a ⋆ ∥ of the agents’ actions a ( t ) = [ x 1 1 ( t ) , … , x 1 N ( t ) ] a(t)=[x_1^1(t),\ldots,x_1^N(t)] a ( t ) = [ x 1 1 ( t ) , … , x 1 N ( t )] to the v-GNE, averaged over 20 random instances.
Figure 2. Distributed GNE seeking, nonlinear constraints: Average distance to the true v-GNE for a varying number of shared nonlinear constraints.
Distributed, linear shared constraints
To compare against the distributed preconditioned proximal-point algorithm (PPPA) of [5 ] and its accelerated (over-relaxed) version (PPPA, acc), in which each agent maintains, besides its estimates of the joint action, a local copy of the dual variable λ ∈ R m \lambda\in\mathbb{R}^m λ ∈ R m that is driven to consensus over the unweighted path graph, we finally consider games with linear shared constraints g ( a ) = A a − b ≤ 0 g(a)=Aa-b\leq0 g ( a ) = A a − b ≤ 0 . The GNEPs are generated as described in Section VI-A with A A A having i.i.d. standard Gaussian entries and with large row-wise local bounds A i A^i A i , whose bounds are obtained by subtracting from and adding to each entry of a ⋆ , i a^{\star,i} a ⋆ , i numbers uniformly distributed in [ 10 , 20 ] [10,20] [ 10 , 20 ] . Each cost J i \mathcal{J}^i J i is linear-quadratic in the joint action a a a . We consider N = 5 N=5 N = 5 agents with d i = 20 d_i=20 d i = 20 , i ∈ [ N ] i\in[N] i ∈ [ N ] (i.e., 100 variables in total), coupled through m = 300 m=300 m = 300 linear shared constraints, 100 of which are active at the v-GNE.
The agents communicate over a path graph, the sparsest connected topology. The distributed hierarchical VI algorithm uses Metropolis–Hastings weights, which give σ ≈ 0.87 \sigma\approx0.87 σ ≈ 0.87 in (24) , the Huber profile of Example 2 with ω = 0.3 \omega=0.3 ω = 0.3 , ε t = 1 / ( t + 1 ) 2 / 3 \varepsilon_t=1/(t+1)^{2/3} ε t = 1/ ( t + 1 ) 2/3 , γ = 2 ⋅ 0.9999 / ∥ A ∥ 2 \gamma=2\cdot0.9999/\|A\|^2 γ = 2 ⋅ 0.9999/∥ A ∥ 2 (note that L P ≤ ∥ A ∥ 2 L_P\leq\|A\|^2 L P ≤ ∥ A ∥ 2 ), η = 10 γ \eta=10\gamma η = 10 γ , and x i ( 0 ) = 0 x_i(0)=0 x i ( 0 ) = 0 . The PPPA stepsizes τ i \tau_i τ i , δ i \delta_i δ i , and ν \nu ν are set to 0.9999 0.9999 0.9999 times the upper bounds given by the sufficient conditions in [5 Lemma 5] , so that these conditions hold strictly, while α \alpha α is set to 0.9999 0.9999 0.9999 times the bound in [5 Lemma 3] , which we multiplied by the boost factor 10 6 10^6 1 0 6 to overcome the large conservativeness of such a theoretical bound (hence convergence of PPPA is not formally guaranteed in this setting). As shown in Figure 3 , which reports the average distance to the v-GNE over 20 instances against the average execution time, the distributed hierarchical VI algorithm outperforms both versions of PPPA. This behavior is due to the fact that, in PPPA, each agent has to maintain and reach consensus on a local copy of the 300-dimensional dual variable in addition to its estimates of the joint action, and this consensus is slow over the path graph. In contrast, the proposed algorithm exchanges only the estimates of the joint action and involves no dual variables.
Figure 3. Distributed GNE seeking, linear constraints: Distance to the true v-GNE as a function of CPU time.
Conclusion
We addressed the computation of variational GNE in games with strongly monotone pseudo-gradients and nonlinear convex shared constraints. We showed that the v-GNE problem is exactly equivalent to a hierarchical VI, whose lower level is defined by the gradient of a smooth convex penalty of the constraint violation over the local action sets. This reformulation removes the need for projections onto the coupled feasible set and for dual variables. Building on it, we proposed a centralized hierarchical regularization scheme that requires only one projection onto the local action sets per iteration, and proved its last-iterate convergence to the v-GNE with rate O ( 1 / t 2 / 3 ) O(1/t^{2/3}) O ( 1/ t 2/3 ) under a local error bound condition (implied, e.g., by Slater’s condition) and O ( 1 / t ) O(1/t) O ( 1/ t ) under a global error bound condition. We then extended the scheme to the partial-decision information setting and obtained a distributed algorithm with constant stepsize, in which the agents exchange only local estimates of the joint action with their neighbors, and proved its convergence to the v-GNE with rate O ( 1 / t ) O(1/t) O ( 1/ t ) . The numerical experiments showed that the proposed methods reach a higher accuracy than the projection-based and lifted primal–dual methods for the same computational time.
Future research directions include the extension of the approach to merely monotone games, to time-varying and directed communication graphs, and to settings with stochastic or payoff-based information on the agents’ costs.
Appendix
Properties of the Penalty Function
This appendix collects the regularity properties of the penalty function Ψ \Psi Ψ defined in (6) and of its gradient P = ∇ Ψ P = \nabla\Psi P = ∇Ψ in (7).
Lemma 7. Let Assumption 1(ii) hold and let ψ \psi ψ be an admissible penalty profile, with ψ ′ \psi' ψ ′ and [ ⋅ ] + [\cdot]_{+} [ ⋅ ] + acting componentwise on vectors.
(i) The function Ψ \Psi Ψ is continuously differentiable and
P ( a ) = ∇ g ( a ) T ψ ′ ( [ g ( a ) ] + ) . P(a) = \nabla g(a)^{\mathsf T}\psi'([g(a)]_{+}). P ( a ) = ∇ g ( a ) T ψ ′ ([ g ( a ) ] + ) .
(ii) Let X ⊆ R D X \subseteq\mathbb{R}^{D} X ⊆ R D be convex and let ψ ′ \psi' ψ ′ be L ψ ′ L_{\psi'} L ψ ′ -Lipschitz continuous. Suppose that for all a , b ∈ X a,b \in X a , b ∈ X
∥ ∇ g ( a ) ∥ ≤ G g , ∥ ψ ′ ( [ g ( a ) ] + ) ∥ ≤ ψ ˉ , \lVert\nabla g(a)\rVert\le G_g,\qquad\lVert\psi'([g(a)]_{+})\rVert\le\bar{\psi}, ∥ ∇ g ( a )∥ ≤ G g , ∥ ψ ′ ([ g ( a ) ] + )∥ ≤ ψ ˉ ,
∥ ∇ g ( a ) − ∇ g ( b ) ∥ ≤ L g ∥ a − b ∥ . \lVert\nabla g(a)-\nabla g(b)\rVert\le L_g\lVert a-b\rVert. ∥ ∇ g ( a ) − ∇ g ( b )∥ ≤ L g ∥ a − b ∥ .
Then P P P is L P L_P L P -Lipschitz continuous on X X X with L P = L ψ ′ G g 2 + ψ ˉ L g L_P = L_{\psi'}G_g^2+\bar{\psi}L_g L P = L ψ ′ G g 2 + ψ ˉ L g . If g g g is affine, then L g = 0 L_g=0 L g = 0 and the bound ψ ˉ \bar{\psi} ψ ˉ is not needed.
Proof. (i) Let θ ( s ) : = ψ ( [ s ] + ) \theta(s):=\psi([s]_{+}) θ ( s ) := ψ ([ s ] + ) . Then θ ′ ( s ) = ψ ′ ( [ s ] + ) \theta'(s)=\psi'([s]_{+}) θ ′ ( s ) = ψ ′ ([ s ] + ) for s ≠ 0 s\ne0 s = 0 . Since ψ ′ \psi' ψ ′ is nondecreasing (ψ \psi ψ being convex), the mean value theorem yields, for s ≠ 0 s\ne0 s = 0 ,
∣ θ ( s ) − θ ( 0 ) − 0 ⋅ s ∣ ∣ s ∣ = ψ ( [ s ] + ) ∣ s ∣ ≤ ψ ′ ( [ s ] + ) [ s ] + ∣ s ∣ ≤ ψ ′ ( [ s ] + ) , \frac{|\theta(s)-\theta(0)-0\cdot s|}{|s|}
=\frac{\psi([s]_{+})}{|s|}
\le\frac{\psi'([s]_{+})[s]_{+}}{|s|}
\le\psi'([s]_{+}), ∣ s ∣ ∣ θ ( s ) − θ ( 0 ) − 0 ⋅ s ∣ = ∣ s ∣ ψ ([ s ] + ) ≤ ∣ s ∣ ψ ′ ([ s ] + ) [ s ] + ≤ ψ ′ ([ s ] + ) ,
which vanishes as s → 0 s\to0 s → 0 owing to continuity of ψ ′ \psi' ψ ′ and ψ ′ ( 0 ) = 0 \psi'(0)=0 ψ ′ ( 0 ) = 0 . Hence θ \theta θ is continuously differentiable with θ ′ ( s ) = ψ ′ ( [ s ] + ) \theta'(s)=\psi'([s]_{+}) θ ′ ( s ) = ψ ′ ([ s ] + ) , and the expression for P P P follows from the chain rule applied to Ψ ( a ) = ∑ j = 1 m θ ( g j ( a ) ) \Psi(a)=\sum_{j=1}^{m}\theta(g_j(a)) Ψ ( a ) = ∑ j = 1 m θ ( g j ( a )) .
(ii) For a , b ∈ X a,b\in X a , b ∈ X we have
∥ P ( a ) − P ( b ) ∥ ≤ ∥ ∇ g ( a ) T ( ψ ′ ( [ g ( a ) ] + ) − ψ ′ ( [ g ( b ) ] + ) ) ∥ + ∥ ( ∇ g ( a ) − ∇ g ( b ) ) T ψ ′ ( [ g ( b ) ] + ) ∥ ≤ L ψ ′ G g ∥ g ( a ) − g ( b ) ∥ + ψ ˉ L g ∥ a − b ∥ ≤ ( L ψ ′ G g 2 + ψ ˉ L g ) ∥ a − b ∥ , \begin{aligned}
\lVert P(a)-P(b)\rVert
&\le\lVert\nabla g(a)^{\mathsf T}\bigl(\psi'([g(a)]_{+})-\psi'([g(b)]_{+})\bigr)\rVert\\
&\quad+\lVert(\nabla g(a)-\nabla g(b))^{\mathsf T}\psi'([g(b)]_{+})\rVert\\
&\le L_{\psi'}G_g\lVert g(a)-g(b)\rVert+\bar{\psi}L_g\lVert a-b\rVert\\
&\le(L_{\psi'}G_g^2+\bar{\psi}L_g)\lVert a-b\rVert,
\end{aligned} ∥ P ( a ) − P ( b )∥ ≤ ∥ ∇ g ( a ) T ( ψ ′ ([ g ( a ) ] + ) − ψ ′ ([ g ( b ) ] + ) ) ∥ + ∥( ∇ g ( a ) − ∇ g ( b ) ) T ψ ′ ([ g ( b ) ] + )∥ ≤ L ψ ′ G g ∥ g ( a ) − g ( b )∥ + ψ ˉ L g ∥ a − b ∥ ≤ ( L ψ ′ G g 2 + ψ ˉ L g ) ∥ a − b ∥ ,
where the second inequality uses ∥ [ u ] + − [ v ] + ∥ ≤ ∥ u − v ∥ \lVert[u]_{+}-[v]_{+}\rVert\le\lVert u-v\rVert ∥[ u ] + − [ v ] + ∥ ≤ ∥ u − v ∥ , and the last one follows from the mean value inequality on the segment [ a , b ] ⊆ X [a,b]\subseteq X [ a , b ] ⊆ X .
An Error Bound under Slater’s Condition
Lemma 8. Let Assumption 1(ii) hold, let a ˉ ∈ A \bar{a}\in A a ˉ ∈ A satisfy Slater’s condition, i.e., g j ( a ˉ ) < 0 g_j(\bar{a})<0 g j ( a ˉ ) < 0 for all j ∈ [ m ] j\in[m] j ∈ [ m ] , and let s ˉ = min j ∈ [ m ] ( − g j ( a ˉ ) ) > 0 \bar{s}=\min_{j\in[m]}(-g_j(\bar{a}))>0 s ˉ = min j ∈ [ m ] ( − g j ( a ˉ )) > 0 . Then
dist ( a , A ∩ C ) ≤ ∥ a − a ˉ ∥ s ˉ ∥ [ g ( a ) ] + ∥ , ∀ a ∈ A . \operatorname{dist}(a,A\cap C)\le\frac{\lVert a-\bar{a}\rVert}{\bar{s}}\lVert[g(a)]_{+}\rVert,\qquad\forall a\in A. dist ( a , A ∩ C ) ≤ s ˉ ∥ a − a ˉ ∥ ∥[ g ( a ) ] + ∥ , ∀ a ∈ A .
In particular, Assumption 3 holds: for every bounded set B ⊆ R D B\subseteq\mathbb{R}^{D} B ⊆ R D there exists κ B > 0 \kappa_B>0 κ B > 0 such that dist ( a , A ∩ C ) ≤ κ B ∥ [ g ( a ) ] + ∥ \operatorname{dist}(a,A\cap C)\le\kappa_B\lVert[g(a)]_{+}\rVert dist ( a , A ∩ C ) ≤ κ B ∥[ g ( a ) ] + ∥ for all a ∈ B ∩ A a\in B\cap A a ∈ B ∩ A .
Proof. Let a ∈ A a\in A a ∈ A and r = max j ∈ [ m ] [ g j ( a ) ] + r=\max_{j\in[m]}[g_j(a)]_{+} r = max j ∈ [ m ] [ g j ( a ) ] + . If r = 0 r=0 r = 0 , then a ∈ A ∩ C a\in A\cap C a ∈ A ∩ C and claim holds. Otherwise, let λ = s ˉ / ( s ˉ + r ) ∈ ( 0 , 1 ) \lambda=\bar{s}/(\bar{s}+r)\in(0,1) λ = s ˉ / ( s ˉ + r ) ∈ ( 0 , 1 ) and y = λ a + ( 1 − λ ) a ˉ y=\lambda a+(1-\lambda)\bar{a} y = λa + ( 1 − λ ) a ˉ . Then y ∈ A y\in A y ∈ A by convexity of A A A , and convexity of g j g_j g j gives g j ( y ) ≤ λ r − ( 1 − λ ) s ˉ = 0 g_j(y)\le\lambda r-(1-\lambda)\bar{s}=0 g j ( y ) ≤ λ r − ( 1 − λ ) s ˉ = 0 for all j ∈ [ m ] j\in[m] j ∈ [ m ] , so that y ∈ A ∩ C y\in A\cap C y ∈ A ∩ C . Hence
dist ( a , A ∩ C ) ≤ ∥ a − y ∥ = r s ˉ + r ∥ a − a ˉ ∥ ≤ ∥ a − a ˉ ∥ s ˉ r , \operatorname{dist}(a,A\cap C)\le\lVert a-y\rVert=\frac{r}{\bar{s}+r}\lVert a-\bar{a}\rVert\le\frac{\lVert a-\bar{a}\rVert}{\bar{s}}r, dist ( a , A ∩ C ) ≤ ∥ a − y ∥ = s ˉ + r r ∥ a − a ˉ ∥ ≤ s ˉ ∥ a − a ˉ ∥ r ,
and r ≤ ∥ [ g ( a ) ] + ∥ r\le\lVert[g(a)]_{+}\rVert r ≤ ∥[ g ( a ) ] + ∥ . The second claim follows with κ B = sup a ∈ B ∥ a − a ˉ ∥ / s ˉ \kappa_B=\sup_{a\in B}\lVert a-\bar{a}\rVert/\bar{s} κ B = sup a ∈ B ∥ a − a ˉ ∥ / s ˉ .
A Chung-Type Lemma
The following lemma is a version of Chung’s lemma [7 ] (see also [27 Ch. 2] ). We include a short proof for completeness.
Lemma 9. Let { u t } \{u_t\} { u t } satisfy
u t + 1 ≤ ( 1 − a ( t + 1 ) p ) u t + b ( t + 1 ) q , ∀ t ≥ T , u_{t+1}\le\left(1-\frac{a}{(t+1)^p}\right)u_t+\frac{b}{(t+1)^q},\qquad\forall t\ge T, u t + 1 ≤ ( 1 − ( t + 1 ) p a ) u t + ( t + 1 ) q b , ∀ t ≥ T ,
where a , b > 0 a,b>0 a , b > 0 , p ∈ ( 0 , 1 ] p\in(0,1] p ∈ ( 0 , 1 ] , and p < q ≤ p + 1 p<q\le p+1 p < q ≤ p + 1 . Then the following hold.
(i) If p < 1 p<1 p < 1 , then u t = O ( t − ( q − p ) ) u_t=O(t^{-(q-p)}) u t = O ( t − ( q − p ) ) .
(ii) If p = 1 p=1 p = 1 and a > q − 1 a>q-1 a > q − 1 , then u t = O ( t − ( q − 1 ) ) u_t=O(t^{-(q-1)}) u t = O ( t − ( q − 1 ) ) .
(iii) If p = 1 p=1 p = 1 , then u t → 0 u_t\to0 u t → 0 .
Proof. Let x t = 1 / ( t + 1 ) ∈ ( 0 , 1 ] x_t=1/(t+1)\in(0,1] x t = 1/ ( t + 1 ) ∈ ( 0 , 1 ] , and let s = q − p s=q-p s = q − p in case (i), s = q − 1 s=q-1 s = q − 1 in case (ii), and s = min { a , q − 1 } / 2 s=\min\{a,q-1\}/2 s = min { a , q − 1 } /2 in case (iii). In each case 0 < s ≤ q − p ≤ 1 0<s\le q-p\le1 0 < s ≤ q − p ≤ 1 , and s < a s<a s < a if p = 1 p=1 p = 1 . We show that v t = ( t + 1 ) s u t v_t=(t+1)^su_t v t = ( t + 1 ) s u t is bounded, which gives u t = O ( t − s ) u_t=O(t^{-s}) u t = O ( t − s ) and proves all three claims.
Since ( t + 2 ) / ( t + 1 ) = 1 + x t (t+2)/(t+1)=1+x_t ( t + 2 ) / ( t + 1 ) = 1 + x t , multiplying the recursion by ( t + 2 ) s (t+2)^s ( t + 2 ) s gives
v t + 1 ≤ ( 1 + x t ) s ( 1 − a x t p ) v t + b ( 1 + x t ) s x t q − s . v_{t+1}\le(1+x_t)^s(1-ax_t^p)v_t+b(1+x_t)^s x_t^{q-s}. v t + 1 ≤ ( 1 + x t ) s ( 1 − a x t p ) v t + b ( 1 + x t ) s x t q − s .
Since s ≤ 1 s\le1 s ≤ 1 , we have ( 1 + x t ) s ≤ 1 + s x t ≤ 2 (1+x_t)^s\le1+sx_t\le2 ( 1 + x t ) s ≤ 1 + s x t ≤ 2 , and since q − s ≥ p q-s\ge p q − s ≥ p , we have x t q − s ≤ x t p x_t^{q-s}\le x_t^p x t q − s ≤ x t p . Hence, for all t t t large enough that a x t p ≤ 1 ax_t^p\le1 a x t p ≤ 1 ,
v t + 1 ≤ ( 1 + s x t − a x t p ) v t + 2 b x t p . v_{t+1}\le(1+sx_t-ax_t^p)v_t+2b x_t^p. v t + 1 ≤ ( 1 + s x t − a x t p ) v t + 2 b x t p .
Let a ′ = a / 2 a' = a/2 a ′ = a /2 if p < 1 p < 1 p < 1 and a ′ = a − s a' = a - s a ′ = a − s if p = 1 p = 1 p = 1 . Then s x t p − a x t ≤ − a ′ x t p sx_t^p - ax_t \le-a'x_t^p s x t p − a x t ≤ − a ′ x t p for all large t t t . For p < 1 p < 1 p < 1 this holds because x t 1 − p → 0 x_t^{1-p} \to0 x t 1 − p → 0 , and for p = 1 p = 1 p = 1 it holds with equality. With θ t = a ′ x t p ∈ ( 0 , 1 ] \theta_t = a'x_t^p \in(0,1] θ t = a ′ x t p ∈ ( 0 , 1 ] and K = 2 b / a ′ K = 2b/a' K = 2 b / a ′ , we thus have, for all t ≥ T ′ t \ge T' t ≥ T ′ and some T ′ ≥ T T' \ge T T ′ ≥ T ,
v t + 1 ≤ ( 1 − θ t ) v t + θ t K . v_{t+1} \le(1-\theta_t)v_t+\theta_t K. v t + 1 ≤ ( 1 − θ t ) v t + θ t K .
The right-hand side is a convex combination of v t v_t v t and K K K , so v t + 1 ≤ max { v t , K } v_{t+1} \le\max\{v_t,K\} v t + 1 ≤ max { v t , K } . By induction, v t ≤ max { v T ′ , K } v_t \le\max\{v_{T'},K\} v t ≤ max { v T ′ , K } for all t ≥ T ′ t \ge T' t ≥ T ′ . ■
Proof of Lemma 5
Let a = a ( x ) a=a(x) a = a ( x ) , x ˉ = 1 N ∑ i = 1 N x i \bar{x}=\frac{1}{N}\sum_{i=1}^{N}x_i x ˉ = N 1 ∑ i = 1 N x i . For every block k ∈ [ N ] k\in[N] k ∈ [ N ] , define
x ˉ k = 1 N ∑ i = 1 N x i k . \bar{x}^{k}=\frac{1}{N}\sum_{i=1}^{N}x_i^k. x ˉ k = N 1 i = 1 ∑ N x i k .
Since a k = x k k a^k=x_k^k a k = x k k , we obtain
∑ i = 1 N ∥ x i k − a k ∥ 2 = ∑ i = 1 N ∥ x i k − x k k ∥ 2 = ∑ i = 1 N ∥ ( x i k − x ˉ k ) − ( x k k − x ˉ k ) ∥ 2 = ∑ i = 1 N ∥ x i k − x ˉ k ∥ 2 + N ∥ x k k − x ˉ k ∥ 2 ≤ ( N + 1 ) ∑ i = 1 N ∥ x i k − x ˉ k ∥ 2 . \begin{aligned}
\sum_{i=1}^{N}\lVert x_i^k-a^k\rVert^2
&=\sum_{i=1}^{N}\lVert x_i^k-x_k^k\rVert^2\\
&=\sum_{i=1}^{N}\lVert(x_i^k-\bar{x}^k)-(x_k^k-\bar{x}^k)\rVert^2\\
&=\sum_{i=1}^{N}\lVert x_i^k-\bar{x}^k\rVert^2+N\lVert x_k^k-\bar{x}^k\rVert^2\\
&\le(N+1)\sum_{i=1}^{N}\lVert x_i^k-\bar{x}^k\rVert^2.
\end{aligned} i = 1 ∑ N ∥ x i k − a k ∥ 2 = i = 1 ∑ N ∥ x i k − x k k ∥ 2 = i = 1 ∑ N ∥( x i k − x ˉ k ) − ( x k k − x ˉ k ) ∥ 2 = i = 1 ∑ N ∥ x i k − x ˉ k ∥ 2 + N ∥ x k k − x ˉ k ∥ 2 ≤ ( N + 1 ) i = 1 ∑ N ∥ x i k − x ˉ k ∥ 2 .
Summing over k ∈ [ N ] k\in[N] k ∈ [ N ] proves
∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x − 1 N ⊗ x ˉ ∥ 2 . \lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x-\mathbf{1}_N\otimes\bar{x}\rVert^2. ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x − 1 N ⊗ x ˉ ∥ 2 .
Since x − 1 N ⊗ x ˉ = x ⊥ x-\mathbf{1}_N\otimes\bar{x}=x^\perp x − 1 N ⊗ x ˉ = x ⊥ , the claim follows.
An Auxiliary Gradient-Dominance Bound
The following lemma is used only internally, in the proof of Lemma 6 below.
Lemma 10. Let ψ \psi ψ be an admissible penalty profile with constants S 0 , c ψ > 0 S_0,c_\psi>0 S 0 , c ψ > 0 as in Definition 4. Under Assumptions 1(ii), 3, and 7, let κ A \kappa_A κ A be the constant of Assumption 3 for B = A B=A B = A . Then there exists c ′ > 0 c'>0 c ′ > 0 , depending only on ψ \psi ψ and on A A A , such that
Ψ ( a ) ≤ κ A 4 ( c ′ ) 2 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . \Psi(a)\le\kappa_A^4(c')^2\lVert P(a)\rVert^2,\qquad\forall a\in A. Ψ ( a ) ≤ κ A 4 ( c ′ ) 2 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . Consequently,
dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . \operatorname{dist}(a,S_L)^2\le\kappa_A^4(c')^4\lVert P(a)\rVert^2,\qquad\forall a\in A. dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 , ∀ a ∈ A .
Proof. Since A A A is bounded (Assumption 7), Assumption 3 with B = A B=A B = A gives dist ( a , S L ) ≤ κ A ∥ [ g ( a ) ] + ∥ \operatorname{dist}(a,S_L)\le\kappa_A\lVert[g(a)]_+\rVert dist ( a , S L ) ≤ κ A ∥[ g ( a ) ] + ∥ for every a ∈ A . S i n c e a\in A. Since a ∈ A . S in ce A$ is closed (Assumption 1(ii)) and bounded (Assumption 7), it is compact, so Ψ max = max a ∈ A Ψ ( a ) < ∞ \Psi_{\max}=\max_{a\in A}\Psi(a)<\infty Ψ m a x = max a ∈ A Ψ ( a ) < ∞ is attained (Ψ \Psi Ψ being continuous). Set
c ′ = max ( 1 c ψ , Ψ max c ψ S 0 ) . c'=\max\left(\frac{1}{\sqrt{c_\psi}},\frac{\sqrt{\Psi_{\max}}}{c_\psi S_0}\right). c ′ = max ( c ψ 1 , c ψ S 0 Ψ m a x ) .
Let a ∈ A a\in A a ∈ A and write r = ∥ [ g ( a ) ] + ∥ r=\lVert[g(a)]_+\rVert r = ∥[ g ( a ) ] + ∥ . By Definition 4 applied coordinatewise and Lemma 3, recalling (6), Ψ ( a ) ≥ c ψ r min ( r , S 0 ) \Psi(a)\ge c_\psi r\min(r,S_0) Ψ ( a ) ≥ c ψ r min ( r , S 0 ) ; since s ↦ s min ( s , S 0 ) s\mapsto s\min(s,S_0) s ↦ s min ( s , S 0 ) is increasing, this inverts to
r ≤ max ( Ψ ( a ) c ψ , Ψ ( a ) c ψ S 0 ) . r\le\max\left(\sqrt{\frac{\Psi(a)}{c_\psi}},\frac{\Psi(a)}{c_\psi S_0}\right). r ≤ max ( c ψ Ψ ( a ) , c ψ S 0 Ψ ( a ) ) .
As Ψ ( a ) ≤ Ψ max \Psi(a)\le\Psi_{\max} Ψ ( a ) ≤ Ψ m a x , the second term satisfies
Ψ ( a ) c ψ S 0 ≤ Ψ max c ψ S 0 Ψ ( a ) , \frac{\Psi(a)}{c_\psi S_0}\le\frac{\sqrt{\Psi_{\max}}}{c_\psi S_0}\sqrt{\Psi(a)}, c ψ S 0 Ψ ( a ) ≤ c ψ S 0 Ψ m a x Ψ ( a ) ,
so that, combined with the first term Ψ ( a ) / c ψ = 1 c ψ Ψ ( a ) \sqrt{\Psi(a)/c_\psi}=\frac{1}{\sqrt{c_\psi}}\sqrt{\Psi(a)} Ψ ( a ) / c ψ = c ψ 1 Ψ ( a ) ,
∥ [ g ( a ) ] + ∥ = r ≤ c ′ Ψ ( a ) . (39) \lVert[g(a)]_+\rVert=r\le c'\sqrt{\Psi(a)}. \tag*{(39)} ∥[ g ( a ) ] + ∥ = r ≤ c ′ Ψ ( a ) . (39)
Let s = Π S L ( a ) s=\Pi_{S_L}(a) s = Π S L ( a ) . Since Ψ ( s ) = 0 \Psi(s)=0 Ψ ( s ) = 0 , convexity of Ψ \Psi Ψ implies
0 = Ψ ( s ) ≥ Ψ ( a ) + ⟨ P ( a ) , s − a ⟩ , 0=\Psi(s)\ge\Psi(a)+\langle P(a),s-a\rangle, 0 = Ψ ( s ) ≥ Ψ ( a ) + ⟨ P ( a ) , s − a ⟩ ,
so that
Ψ ( a ) ≤ ∥ P ( a ) ∥ dist ( a , S L ) . \Psi(a)\le\lVert P(a)\rVert\operatorname{dist}(a,S_L). Ψ ( a ) ≤ ∥ P ( a )∥ dist ( a , S L ) .
By the error bound established above and (40),
dist ( a , S L ) ≤ κ A ∥ [ g ( a ) ] + ∥ ≤ κ A c ′ Ψ ( a ) . (40) \operatorname{dist}(a,S_L)\le\kappa_A\lVert[g(a)]_+\rVert\le\kappa_Ac'\sqrt{\Psi(a)}. \tag*{(40)} dist ( a , S L ) ≤ κ A ∥[ g ( a ) ] + ∥ ≤ κ A c ′ Ψ ( a ) . (40)
Combining the relations above, we obtain
Ψ ( a ) ≤ κ A c ′ ∥ P ( a ) ∥ Ψ ( a ) . \Psi(a)\le\kappa_Ac'\lVert P(a)\rVert\sqrt{\Psi(a)}. Ψ ( a ) ≤ κ A c ′ ∥ P ( a )∥ Ψ ( a ) .
If Ψ ( a ) = 0 \Psi(a)=0 Ψ ( a ) = 0 , the claims hold. Otherwise, division by Ψ ( a ) \sqrt{\Psi(a)} Ψ ( a ) and squaring yield
Ψ ( a ) ≤ κ A 2 ( c ′ ) 2 ∥ P ( a ) ∥ 2 . \Psi(a)\le\kappa_A^2(c')^2\lVert P(a)\rVert^2. Ψ ( a ) ≤ κ A 2 ( c ′ ) 2 ∥ P ( a ) ∥ 2 .
Finally, using (41), we conclude
dist ( a , S L ) 2 ≤ κ A 2 ( c ′ ) 2 Ψ ( a ) ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 . \operatorname{dist}(a,S_L)^2\le\kappa_A^2(c')^2\Psi(a)\le\kappa_A^4(c')^4\lVert P(a)\rVert^2. dist ( a , S L ) 2 ≤ κ A 2 ( c ′ ) 2 Ψ ( a ) ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 .
■
Proof of Lemma 6
Set a = a ( x ) ∈ A ⊆ Q a=a(x)\in A\subseteq Q a = a ( x ) ∈ A ⊆ Q . By Lemma 5 ,
∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . \lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2. ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 .
Since W 1 N = 1 N W\mathbf{1}_N=\mathbf{1}_N W 1 N = 1 N (Assumption 6), we have W ( 1 N ⊗ a ) = ( W ⊗ I D ) ( 1 N ⊗ a ) = ( W 1 N ) ⊗ a = 1 N ⊗ a W(\mathbf{1}_N\otimes a)=(W\otimes I_D)(\mathbf{1}_N\otimes a)=(W\mathbf{1}_N)\otimes a=\mathbf{1}_N\otimes a W ( 1 N ⊗ a ) = ( W ⊗ I D ) ( 1 N ⊗ a ) = ( W 1 N ) ⊗ a = 1 N ⊗ a , so that
z − 1 N ⊗ a = W x − W ( 1 N ⊗ a ) = W ( x − 1 N ⊗ a ) . z-\mathbf{1}_N\otimes a=Wx-W(\mathbf{1}_N\otimes a)=W(x-\mathbf{1}_N\otimes a). z − 1 N ⊗ a = W x − W ( 1 N ⊗ a ) = W ( x − 1 N ⊗ a ) .
Moreover, W W W , being symmetric and doubly stochastic, has eigenvalues in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , so ∥ W ∥ = ∥ W ⊗ I D ∥ = ∥ W ∥ ≤ 1 \lVert W\rVert=\lVert W\otimes I_D\rVert=\lVert W\rVert\le1 ∥ W ∥ = ∥ W ⊗ I D ∥ = ∥ W ∥ ≤ 1 . Combining this inequality with the previous equality, we obtain
∥ z − 1 N ⊗ a ∥ 2 ≤ ∥ W ∥ 2 ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . (41) \lVert z-\mathbf{1}_N\otimes a\rVert^2\le\lVert W\rVert^2\lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2. \tag*{(41)} ∥ z − 1 N ⊗ a ∥ 2 ≤ ∥ W ∥ 2 ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . (41)
As x ∈ Ω x\in\Omega x ∈ Ω , we have z i ∈ Q z_i\in Q z i ∈ Q for every i ∈ [ N ] i\in[N] i ∈ [ N ] . Since also a ∈ Q a\in Q a ∈ Q , Assumption 7 implies, for every i ∈ [ N ] i\in[N] i ∈ [ N ] ,
∥ P ( a ) ∥ ≤ ∥ P ( z i ) ∥ + L P Q ∥ z i − a ∥ . \lVert P(a)\rVert\le\lVert P(z_i)\rVert+L_P^Q\lVert z_i-a\rVert. ∥ P ( a )∥ ≤ ∥ P ( z i )∥ + L P Q ∥ z i − a ∥ .
Squaring via ( u + v ) 2 ≤ 2 u 2 + 2 v 2 (u+v)^2\le2u^2+2v^2 ( u + v ) 2 ≤ 2 u 2 + 2 v 2 , summing over i ∈ [ N ] i\in[N] i ∈ [ N ] , and dividing by N N N gives
∥ P ( a ) ∥ 2 ≤ 2 N ∑ i = 1 N ∥ P ( z i ) ∥ 2 + 2 ( L P Q ) 2 N ∑ i = 1 N ∥ z i − a ∥ 2 = 2 N ∥ P ( z ) ∥ 2 + 2 ( L P Q ) 2 N ∥ z − 1 N ⊗ a ∥ 2 , \begin{aligned}
\lVert P(a)\rVert^2
&\le\frac{2}{N}\sum_{i=1}^{N}\lVert P(z_i)\rVert^2+\frac{2(L_P^Q)^2}{N}\sum_{i=1}^{N}\lVert z_i-a\rVert^2\\
&=\frac{2}{N}\lVert P(z)\rVert^2+\frac{2(L_P^Q)^2}{N}\lVert z-\mathbf{1}_N\otimes a\rVert^2,
\end{aligned} ∥ P ( a ) ∥ 2 ≤ N 2 i = 1 ∑ N ∥ P ( z i ) ∥ 2 + N 2 ( L P Q ) 2 i = 1 ∑ N ∥ z i − a ∥ 2 = N 2 ∥ P ( z ) ∥ 2 + N 2 ( L P Q ) 2 ∥ z − 1 N ⊗ a ∥ 2 ,
where we used P ( z ) = [ P ( z 1 ) , … , P ( z N ) ] P(z)=[P(z_1),\ldots,P(z_N)] P ( z ) = [ P ( z 1 ) , … , P ( z N )] and ∥ z − 1 N ⊗ a ∥ 2 = ∑ i = 1 N ∥ z i − a ∥ 2 \lVert z-\mathbf{1}_N\otimes a\rVert^2=\sum_{i=1}^{N}\lVert z_i-a\rVert^2 ∥ z − 1 N ⊗ a ∥ 2 = ∑ i = 1 N ∥ z i − a ∥ 2 . Substituting ∥ z − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 \lVert z-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2 ∥ z − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 from (42) and using ∥ x ∥ 2 = R ( x ) \lVert x\rVert^2=\mathcal{R}(x) ∥ x ∥ 2 = R ( x ) , ∥ P ( z ) ∥ 2 = R ( x ) = ∥ x ⊥ ∥ 2 + ∥ P ( z ) ∥ 2 \lVert P(z)\rVert^2=\mathcal{R}(x)=\lVert x^\perp\rVert^2+\lVert P(z)\rVert^2 ∥ P ( z ) ∥ 2 = R ( x ) = ∥ x ⊥ ∥ 2 + ∥ P ( z ) ∥ 2 , we obtain
∥ P ( a ) ∥ 2 ≤ 2 N ∥ P ( z ) ∥ 2 + 2 ( L P Q ) 2 ( N + 1 ) N ∥ x ⊥ ∥ 2 ≤ C P R ( x ) , \lVert P(a)\rVert^2\le\frac{2}{N}\lVert P(z)\rVert^2+\frac{2(L_P^Q)^2(N+1)}{N}\lVert x^\perp\rVert^2\le C_P\mathcal{R}(x), ∥ P ( a ) ∥ 2 ≤ N 2 ∥ P ( z ) ∥ 2 + N 2 ( L P Q ) 2 ( N + 1 ) ∥ x ⊥ ∥ 2 ≤ C P R ( x ) ,
where C P = 2 max ( 1 , ( L P Q ) 2 ( N + 1 ) / N ) C_P=2\max(1,(L_P^Q)^2(N+1)/N) C P = 2 max ( 1 , ( L P Q ) 2 ( N + 1 ) / N ) . Thus, Lemma 10 together with the inequality above gives
dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 C P R ( x ) . (42) \operatorname{dist}(a,S_L)^2\le\kappa_A^4(c')^4C_P\mathcal{R}(x). \tag*{(42)} dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 C P R ( x ) . (42)
Next, for every s ∈ S L s\in S_L s ∈ S L ,
∥ x − 1 N ⊗ s ∥ ≤ ∥ x − 1 N ⊗ a ∥ + ∥ 1 N ⊗ a − 1 N ⊗ s ∥ = ∥ x − 1 N ⊗ a ∥ + N ∥ a − s ∥ , \lVert x-\mathbf{1}_N\otimes s\rVert\le\lVert x-\mathbf{1}_N\otimes a\rVert+\lVert\mathbf{1}_N\otimes a-\mathbf{1}_N\otimes s\rVert
=\lVert x-\mathbf{1}_N\otimes a\rVert+\sqrt{N}\lVert a-s\rVert, ∥ x − 1 N ⊗ s ∥ ≤ ∥ x − 1 N ⊗ a ∥ + ∥ 1 N ⊗ a − 1 N ⊗ s ∥ = ∥ x − 1 N ⊗ a ∥ + N ∥ a − s ∥ ,
@page 13/14 starts_mid=1 ends_mid=1 Let a ′ = a / 2 a' = a/2 a ′ = a /2 if p < 1 p < 1 p < 1 and a ′ = a − s a' = a - s a ′ = a − s if p = 1 p = 1 p = 1 . Then s x t p − a x t ≤ − a ′ x t p sx_t^p - ax_t \le-a'x_t^p s x t p − a x t ≤ − a ′ x t p for all large t t t . For p < 1 p < 1 p < 1 this holds because x t 1 − p → 0 x_t^{1-p} \to0 x t 1 − p → 0 , and for p = 1 p = 1 p = 1 it holds with equality. With θ t = a ′ x t p ∈ ( 0 , 1 ] \theta_t = a'x_t^p \in(0,1] θ t = a ′ x t p ∈ ( 0 , 1 ] and K = 2 b / a ′ K = 2b/a' K = 2 b / a ′ , we thus have, for all t ≥ T ′ t \ge T' t ≥ T ′ and some T ′ ≥ T T' \ge T T ′ ≥ T ,
v t + 1 ≤ ( 1 − θ t ) v t + θ t K . v_{t+1} \le(1-\theta_t)v_t+\theta_t K. v t + 1 ≤ ( 1 − θ t ) v t + θ t K .
The right-hand side is a convex combination of v t v_t v t and K K K , so v t + 1 ≤ max { v t , K } v_{t+1} \le\max\{v_t,K\} v t + 1 ≤ max { v t , K } . By induction, v t ≤ max { v T ′ , K } v_t \le\max\{v_{T'},K\} v t ≤ max { v T ′ , K } for all t ≥ T ′ t \ge T' t ≥ T ′ . ■
Proof of Lemma 5
Let a = a ( x ) a=a(x) a = a ( x ) , x ˉ = 1 N ∑ i = 1 N x i \bar{x}=\frac{1}{N}\sum_{i=1}^{N}x_i x ˉ = N 1 ∑ i = 1 N x i . For every block k ∈ [ N ] k\in[N] k ∈ [ N ] , define
x ˉ k = 1 N ∑ i = 1 N x i k . \bar{x}^{k}=\frac{1}{N}\sum_{i=1}^{N}x_i^k. x ˉ k = N 1 i = 1 ∑ N x i k .
Since a k = x k k a^k=x_k^k a k = x k k , we obtain
∑ i = 1 N ∥ x i k − a k ∥ 2 = ∑ i = 1 N ∥ x i k − x k k ∥ 2 = ∑ i = 1 N ∥ ( x i k − x ˉ k ) − ( x k k − x ˉ k ) ∥ 2 = ∑ i = 1 N ∥ x i k − x ˉ k ∥ 2 + N ∥ x k k − x ˉ k ∥ 2 ≤ ( N + 1 ) ∑ i = 1 N ∥ x i k − x ˉ k ∥ 2 . \begin{aligned}
\sum_{i=1}^{N}\lVert x_i^k-a^k\rVert^2
&=\sum_{i=1}^{N}\lVert x_i^k-x_k^k\rVert^2\\
&=\sum_{i=1}^{N}\lVert(x_i^k-\bar{x}^k)-(x_k^k-\bar{x}^k)\rVert^2\\
&=\sum_{i=1}^{N}\lVert x_i^k-\bar{x}^k\rVert^2+N\lVert x_k^k-\bar{x}^k\rVert^2\\
&\le(N+1)\sum_{i=1}^{N}\lVert x_i^k-\bar{x}^k\rVert^2.
\end{aligned} i = 1 ∑ N ∥ x i k − a k ∥ 2 = i = 1 ∑ N ∥ x i k − x k k ∥ 2 = i = 1 ∑ N ∥( x i k − x ˉ k ) − ( x k k − x ˉ k ) ∥ 2 = i = 1 ∑ N ∥ x i k − x ˉ k ∥ 2 + N ∥ x k k − x ˉ k ∥ 2 ≤ ( N + 1 ) i = 1 ∑ N ∥ x i k − x ˉ k ∥ 2 .
Summing over k ∈ [ N ] k\in[N] k ∈ [ N ] proves
∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x − 1 N ⊗ x ˉ ∥ 2 . \lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x-\mathbf{1}_N\otimes\bar{x}\rVert^2. ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x − 1 N ⊗ x ˉ ∥ 2 .
Since x − 1 N ⊗ x ˉ = x ⊥ x-\mathbf{1}_N\otimes\bar{x}=x^\perp x − 1 N ⊗ x ˉ = x ⊥ , the claim follows.
An Auxiliary Gradient-Dominance Bound
The following lemma is used only internally, in the proof of Lemma 6 below.
Lemma 10. Let ψ \psi ψ be an admissible penalty profile with constants S 0 , c ψ > 0 S_0,c_\psi>0 S 0 , c ψ > 0 as in Definition 4. Under Assumptions 1(ii), 3, and 7, let κ A \kappa_A κ A be the constant of Assumption 3 for B = A B=A B = A . Then there exists c ′ > 0 c'>0 c ′ > 0 , depending only on ψ \psi ψ and on A A A , such that
Ψ ( a ) ≤ κ A 4 ( c ′ ) 2 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . \Psi(a)\le\kappa_A^4(c')^2\lVert P(a)\rVert^2,\qquad\forall a\in A. Ψ ( a ) ≤ κ A 4 ( c ′ ) 2 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . Consequently,
dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . \operatorname{dist}(a,S_L)^2\le\kappa_A^4(c')^4\lVert P(a)\rVert^2,\qquad\forall a\in A. dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 , ∀ a ∈ A .
Proof. Since A A A is bounded (Assumption 7), Assumption 3 with B = A B=A B = A gives dist ( a , S L ) ≤ κ A ∥ [ g ( a ) ] + ∥ \operatorname{dist}(a,S_L)\le\kappa_A\lVert[g(a)]_+\rVert dist ( a , S L ) ≤ κ A ∥[ g ( a ) ] + ∥ for every a ∈ A . S i n c e a\in A. Since a ∈ A . S in ce A$ is closed (Assumption 1(ii)) and bounded (Assumption 7), it is compact, so Ψ max = max a ∈ A Ψ ( a ) < ∞ \Psi_{\max}=\max_{a\in A}\Psi(a)<\infty Ψ m a x = max a ∈ A Ψ ( a ) < ∞ is attained (Ψ \Psi Ψ being continuous). Set
c ′ = max ( 1 c ψ , Ψ max c ψ S 0 ) . c'=\max\left(\frac{1}{\sqrt{c_\psi}},\frac{\sqrt{\Psi_{\max}}}{c_\psi S_0}\right). c ′ = max ( c ψ 1 , c ψ S 0 Ψ m a x ) .
Let a ∈ A a\in A a ∈ A and write r = ∥ [ g ( a ) ] + ∥ r=\lVert[g(a)]_+\rVert r = ∥[ g ( a ) ] + ∥ . By Definition 4 applied coordinatewise and Lemma 3, recalling (6), Ψ ( a ) ≥ c ψ r min ( r , S 0 ) \Psi(a)\ge c_\psi r\min(r,S_0) Ψ ( a ) ≥ c ψ r min ( r , S 0 ) ; since s ↦ s min ( s , S 0 ) s\mapsto s\min(s,S_0) s ↦ s min ( s , S 0 ) is increasing, this inverts to
r ≤ max ( Ψ ( a ) c ψ , Ψ ( a ) c ψ S 0 ) . r\le\max\left(\sqrt{\frac{\Psi(a)}{c_\psi}},\frac{\Psi(a)}{c_\psi S_0}\right). r ≤ max ( c ψ Ψ ( a ) , c ψ S 0 Ψ ( a ) ) .
As Ψ ( a ) ≤ Ψ max \Psi(a)\le\Psi_{\max} Ψ ( a ) ≤ Ψ m a x , the second term satisfies
Ψ ( a ) c ψ S 0 ≤ Ψ max c ψ S 0 Ψ ( a ) , \frac{\Psi(a)}{c_\psi S_0}\le\frac{\sqrt{\Psi_{\max}}}{c_\psi S_0}\sqrt{\Psi(a)}, c ψ S 0 Ψ ( a ) ≤ c ψ S 0 Ψ m a x Ψ ( a ) ,
so that, combined with the first term Ψ ( a ) / c ψ = 1 c ψ Ψ ( a ) \sqrt{\Psi(a)/c_\psi}=\frac{1}{\sqrt{c_\psi}}\sqrt{\Psi(a)} Ψ ( a ) / c ψ = c ψ 1 Ψ ( a ) ,
∥ [ g ( a ) ] + ∥ = r ≤ c ′ Ψ ( a ) . (43) \lVert[g(a)]_+\rVert=r\le c'\sqrt{\Psi(a)}. \tag*{(43)} ∥[ g ( a ) ] + ∥ = r ≤ c ′ Ψ ( a ) . (43)
Let s = Π S L ( a ) s=\Pi_{S_L}(a) s = Π S L ( a ) . Since Ψ ( s ) = 0 \Psi(s)=0 Ψ ( s ) = 0 , convexity of Ψ \Psi Ψ implies
0 = Ψ ( s ) ≥ Ψ ( a ) + ⟨ P ( a ) , s − a ⟩ , 0=\Psi(s)\ge\Psi(a)+\langle P(a),s-a\rangle, 0 = Ψ ( s ) ≥ Ψ ( a ) + ⟨ P ( a ) , s − a ⟩ ,
so that
Ψ ( a ) ≤ ∥ P ( a ) ∥ dist ( a , S L ) . \Psi(a)\le\lVert P(a)\rVert\operatorname{dist}(a,S_L). Ψ ( a ) ≤ ∥ P ( a )∥ dist ( a , S L ) .
By the error bound established above and (40),
dist ( a , S L ) ≤ κ A ∥ [ g ( a ) ] + ∥ ≤ κ A c ′ Ψ ( a ) . (44) \operatorname{dist}(a,S_L)\le\kappa_A\lVert[g(a)]_+\rVert\le\kappa_Ac'\sqrt{\Psi(a)}. \tag*{(44)} dist ( a , S L ) ≤ κ A ∥[ g ( a ) ] + ∥ ≤ κ A c ′ Ψ ( a ) . (44)
Combining the relations above, we obtain
Ψ ( a ) ≤ κ A c ′ ∥ P ( a ) ∥ Ψ ( a ) . \Psi(a)\le\kappa_Ac'\lVert P(a)\rVert\sqrt{\Psi(a)}. Ψ ( a ) ≤ κ A c ′ ∥ P ( a )∥ Ψ ( a ) .
If Ψ ( a ) = 0 \Psi(a)=0 Ψ ( a ) = 0 , the claims hold. Otherwise, division by Ψ ( a ) \sqrt{\Psi(a)} Ψ ( a ) and squaring yield
Ψ ( a ) ≤ κ A 2 ( c ′ ) 2 ∥ P ( a ) ∥ 2 . \Psi(a)\le\kappa_A^2(c')^2\lVert P(a)\rVert^2. Ψ ( a ) ≤ κ A 2 ( c ′ ) 2 ∥ P ( a ) ∥ 2 .
Finally, using (41), we conclude
dist ( a , S L ) 2 ≤ κ A 2 ( c ′ ) 2 Ψ ( a ) ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 . \operatorname{dist}(a,S_L)^2\le\kappa_A^2(c')^2\Psi(a)\le\kappa_A^4(c')^4\lVert P(a)\rVert^2. dist ( a , S L ) 2 ≤ κ A 2 ( c ′ ) 2 Ψ ( a ) ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 .
■
Proof of Lemma 6
Set a = a ( x ) ∈ A ⊆ Q a=a(x)\in A\subseteq Q a = a ( x ) ∈ A ⊆ Q . By Lemma 5 ,
∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . \lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2. ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 .
Since W 1 N = 1 N W\mathbf{1}_N=\mathbf{1}_N W 1 N = 1 N (Assumption 6), we have W ( 1 N ⊗ a ) = ( W ⊗ I D ) ( 1 N ⊗ a ) = ( W 1 N ) ⊗ a = 1 N ⊗ a W(\mathbf{1}_N\otimes a)=(W\otimes I_D)(\mathbf{1}_N\otimes a)=(W\mathbf{1}_N)\otimes a=\mathbf{1}_N\otimes a W ( 1 N ⊗ a ) = ( W ⊗ I D ) ( 1 N ⊗ a ) = ( W 1 N ) ⊗ a = 1 N ⊗ a , so that
z − 1 N ⊗ a = W x − W ( 1 N ⊗ a ) = W ( x − 1 N ⊗ a ) . z-\mathbf{1}_N\otimes a=Wx-W(\mathbf{1}_N\otimes a)=W(x-\mathbf{1}_N\otimes a). z − 1 N ⊗ a = W x − W ( 1 N ⊗ a ) = W ( x − 1 N ⊗ a ) .
Moreover, W W W , being symmetric and doubly stochastic, has eigenvalues in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , so ∥ W ∥ = ∥ W ⊗ I D ∥ = ∥ W ∥ ≤ 1 \lVert W\rVert=\lVert W\otimes I_D\rVert=\lVert W\rVert\le1 ∥ W ∥ = ∥ W ⊗ I D ∥ = ∥ W ∥ ≤ 1 . Combining this inequality with the previous equality, we obtain
∥ z − 1 N ⊗ a ∥ 2 ≤ ∥ W ∥ 2 ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . (45) \lVert z-\mathbf{1}_N\otimes a\rVert^2\le\lVert W\rVert^2\lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2. \tag*{(45)} ∥ z − 1 N ⊗ a ∥ 2 ≤ ∥ W ∥ 2 ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . (45)
As x ∈ Ω x\in\Omega x ∈ Ω , we have z i ∈ Q z_i\in Q z i ∈ Q for every i ∈ [ N ] i\in[N] i ∈ [ N ] . Since also a ∈ Q a\in Q a ∈ Q , Assumption 7 implies, for every i ∈ [ N ] i\in[N] i ∈ [ N ] ,
∥ P ( a ) ∥ ≤ ∥ P ( z i ) ∥ + L P Q ∥ z i − a ∥ . \lVert P(a)\rVert\le\lVert P(z_i)\rVert+L_P^Q\lVert z_i-a\rVert. ∥ P ( a )∥ ≤ ∥ P ( z i )∥ + L P Q ∥ z i − a ∥ .
Squaring via ( u + v ) 2 ≤ 2 u 2 + 2 v 2 (u+v)^2\le2u^2+2v^2 ( u + v ) 2 ≤ 2 u 2 + 2 v 2 , summing over i ∈ [ N ] i\in[N] i ∈ [ N ] , and dividing by N N N gives
∥ P ( a ) ∥ 2 ≤ 2 N ∑ i = 1 N ∥ P ( z i ) ∥ 2 + 2 ( L P Q ) 2 N ∑ i = 1 N ∥ z i − a ∥ 2 = 2 N ∥ P ( z ) ∥ 2 + 2 ( L P Q ) 2 N ∥ z − 1 N ⊗ a ∥ 2 , \begin{aligned}
\lVert P(a)\rVert^2
&\le\frac{2}{N}\sum_{i=1}^{N}\lVert P(z_i)\rVert^2+\frac{2(L_P^Q)^2}{N}\sum_{i=1}^{N}\lVert z_i-a\rVert^2\\
&=\frac{2}{N}\lVert P(z)\rVert^2+\frac{2(L_P^Q)^2}{N}\lVert z-\mathbf{1}_N\otimes a\rVert^2,
\end{aligned} ∥ P ( a ) ∥ 2 ≤ N 2 i = 1 ∑ N ∥ P ( z i ) ∥ 2 + N 2 ( L P Q ) 2 i = 1 ∑ N ∥ z i − a ∥ 2 = N 2 ∥ P ( z ) ∥ 2 + N 2 ( L P Q ) 2 ∥ z − 1 N ⊗ a ∥ 2 ,
where we used P ( z ) = [ P ( z 1 ) , … , P ( z N ) ] P(z)=[P(z_1),\ldots,P(z_N)] P ( z ) = [ P ( z 1 ) , … , P ( z N )] and ∥ z − 1 N ⊗ a ∥ 2 = ∑ i = 1 N ∥ z i − a ∥ 2 \lVert z-\mathbf{1}_N\otimes a\rVert^2=\sum_{i=1}^{N}\lVert z_i-a\rVert^2 ∥ z − 1 N ⊗ a ∥ 2 = ∑ i = 1 N ∥ z i − a ∥ 2 . Substituting ∥ z − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 \lVert z-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2 ∥ z − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 from (42) and using ∥ x ∥ 2 = R ( x ) \lVert x\rVert^2=\mathcal{R}(x) ∥ x ∥ 2 = R ( x ) , ∥ P ( z ) ∥ 2 = R ( x ) = ∥ x ⊥ ∥ 2 + ∥ P ( z ) ∥ 2 \lVert P(z)\rVert^2=\mathcal{R}(x)=\lVert x^\perp\rVert^2+\lVert P(z)\rVert^2 ∥ P ( z ) ∥ 2 = R ( x ) = ∥ x ⊥ ∥ 2 + ∥ P ( z ) ∥ 2 , we obtain
∥ P ( a ) ∥ 2 ≤ 2 N ∥ P ( z ) ∥ 2 + 2 ( L P Q ) 2 ( N + 1 ) N ∥ x ⊥ ∥ 2 ≤ C P R ( x ) , \lVert P(a)\rVert^2\le\frac{2}{N}\lVert P(z)\rVert^2+\frac{2(L_P^Q)^2(N+1)}{N}\lVert x^\perp\rVert^2\le C_P\mathcal{R}(x), ∥ P ( a ) ∥ 2 ≤ N 2 ∥ P ( z ) ∥ 2 + N 2 ( L P Q ) 2 ( N + 1 ) ∥ x ⊥ ∥ 2 ≤ C P R ( x ) ,
where C P = 2 max ( 1 , ( L P Q ) 2 ( N + 1 ) / N ) C_P=2\max(1,(L_P^Q)^2(N+1)/N) C P = 2 max ( 1 , ( L P Q ) 2 ( N + 1 ) / N ) . Thus, Lemma 10 together with the inequality above gives
dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 C P R ( x ) . (46) \operatorname{dist}(a,S_L)^2\le\kappa_A^4(c')^4C_P\mathcal{R}(x). \tag*{(46)} dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 C P R ( x ) . (46)
Next, for every s ∈ S L s\in S_L s ∈ S L ,
∥ x − 1 N ⊗ s ∥ ≤ ∥ x − 1 N ⊗ a ∥ + ∥ 1 N ⊗ a − 1 N ⊗ s ∥ = ∥ x − 1 N ⊗ a ∥ + N ∥ a − s ∥ , \lVert x-\mathbf{1}_N\otimes s\rVert\le\lVert x-\mathbf{1}_N\otimes a\rVert+\lVert\mathbf{1}_N\otimes a-\mathbf{1}_N\otimes s\rVert
=\lVert x-\mathbf{1}_N\otimes a\rVert+\sqrt{N}\lVert a-s\rVert, ∥ x − 1 N ⊗ s ∥ ≤ ∥ x − 1 N ⊗ a ∥ + ∥ 1 N ⊗ a − 1 N ⊗ s ∥ = ∥ x − 1 N ⊗ a ∥ + N ∥ a − s ∥ ,
@page 13/14 starts_mid=1 ends_mid=1 Let a ′ = a / 2 a' = a/2 a ′ = a /2 if p < 1 p < 1 p < 1 and a ′ = a − s a' = a - s a ′ = a − s if p = 1 p = 1 p = 1 . Then s x t p − a x t ≤ − a ′ x t p sx_t^p - ax_t \le-a'x_t^p s x t p − a x t ≤ − a ′ x t p for all large t t t . For p < 1 p < 1 p < 1 this holds because x t 1 − p → 0 x_t^{1-p} \to0 x t 1 − p → 0 , and for p = 1 p = 1 p = 1 it holds with equality. With θ t = a ′ x t p ∈ ( 0 , 1 ] \theta_t = a'x_t^p \in(0,1] θ t = a ′ x t p ∈ ( 0 , 1 ] and K = 2 b / a ′ K = 2b/a' K = 2 b / a ′ , we thus have, for all t ≥ T ′ t \ge T' t ≥ T ′ and some T ′ ≥ T T' \ge T T ′ ≥ T ,
v t + 1 ≤ ( 1 − θ t ) v t + θ t K . v_{t+1} \le(1-\theta_t)v_t+\theta_t K. v t + 1 ≤ ( 1 − θ t ) v t + θ t K .
The right-hand side is a convex combination of v t v_t v t and K K K , so v t + 1 ≤ max { v t , K } v_{t+1} \le\max\{v_t,K\} v t + 1 ≤ max { v t , K } . By induction, v t ≤ max { v T ′ , K } v_t \le\max\{v_{T'},K\} v t ≤ max { v T ′ , K } for all t ≥ T ′ t \ge T' t ≥ T ′ . ■
Proof of Lemma 5
Let a = a ( x ) a=a(x) a = a ( x ) , x ˉ = 1 N ∑ i = 1 N x i \bar{x}=\frac{1}{N}\sum_{i=1}^{N}x_i x ˉ = N 1 ∑ i = 1 N x i . For every block k ∈ [ N ] k\in[N] k ∈ [ N ] , define
x ˉ k = 1 N ∑ i = 1 N x i k . \bar{x}^{k}=\frac{1}{N}\sum_{i=1}^{N}x_i^k. x ˉ k = N 1 i = 1 ∑ N x i k .
Since a k = x k k a^k=x_k^k a k = x k k , we obtain
∑ i = 1 N ∥ x i k − a k ∥ 2 = ∑ i = 1 N ∥ x i k − x k k ∥ 2 = ∑ i = 1 N ∥ ( x i k − x ˉ k ) − ( x k k − x ˉ k ) ∥ 2 = ∑ i = 1 N ∥ x i k − x ˉ k ∥ 2 + N ∥ x k k − x ˉ k ∥ 2 ≤ ( N + 1 ) ∑ i = 1 N ∥ x i k − x ˉ k ∥ 2 . \begin{aligned}
\sum_{i=1}^{N}\lVert x_i^k-a^k\rVert^2
&=\sum_{i=1}^{N}\lVert x_i^k-x_k^k\rVert^2\\
&=\sum_{i=1}^{N}\lVert(x_i^k-\bar{x}^k)-(x_k^k-\bar{x}^k)\rVert^2\\
&=\sum_{i=1}^{N}\lVert x_i^k-\bar{x}^k\rVert^2+N\lVert x_k^k-\bar{x}^k\rVert^2\\
&\le(N+1)\sum_{i=1}^{N}\lVert x_i^k-\bar{x}^k\rVert^2.
\end{aligned} i = 1 ∑ N ∥ x i k − a k ∥ 2 = i = 1 ∑ N ∥ x i k − x k k ∥ 2 = i = 1 ∑ N ∥( x i k − x ˉ k ) − ( x k k − x ˉ k ) ∥ 2 = i = 1 ∑ N ∥ x i k − x ˉ k ∥ 2 + N ∥ x k k − x ˉ k ∥ 2 ≤ ( N + 1 ) i = 1 ∑ N ∥ x i k − x ˉ k ∥ 2 .
Summing over k ∈ [ N ] k\in[N] k ∈ [ N ] proves
∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x − 1 N ⊗ x ˉ ∥ 2 . \lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x-\mathbf{1}_N\otimes\bar{x}\rVert^2. ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x − 1 N ⊗ x ˉ ∥ 2 .
Since x − 1 N ⊗ x ˉ = x ⊥ x-\mathbf{1}_N\otimes\bar{x}=x^\perp x − 1 N ⊗ x ˉ = x ⊥ , the claim follows.
An Auxiliary Gradient-Dominance Bound
The following lemma is used only internally, in the proof of Lemma 6 below.
Lemma 10. Let ψ \psi ψ be an admissible penalty profile with constants S 0 , c ψ > 0 S_0,c_\psi>0 S 0 , c ψ > 0 as in Definition 4. Under Assumptions 1(ii), 3, and 7, let κ A \kappa_A κ A be the constant of Assumption 3 for B = A B=A B = A . Then there exists c ′ > 0 c'>0 c ′ > 0 , depending only on ψ \psi ψ and on A A A , such that
Ψ ( a ) ≤ κ A 4 ( c ′ ) 2 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . \Psi(a)\le\kappa_A^4(c')^2\lVert P(a)\rVert^2,\qquad\forall a\in A. Ψ ( a ) ≤ κ A 4 ( c ′ ) 2 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . Consequently,
dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 , ∀ a ∈ A . \operatorname{dist}(a,S_L)^2\le\kappa_A^4(c')^4\lVert P(a)\rVert^2,\qquad\forall a\in A. dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 , ∀ a ∈ A .
Proof. Since A A A is bounded (Assumption 7), Assumption 3 with B = A B=A B = A gives dist ( a , S L ) ≤ κ A ∥ [ g ( a ) ] + ∥ \operatorname{dist}(a,S_L)\le\kappa_A\lVert[g(a)]_+\rVert dist ( a , S L ) ≤ κ A ∥[ g ( a ) ] + ∥ for every a ∈ A . S i n c e a\in A. Since a ∈ A . S in ce A$ is closed (Assumption 1(ii)) and bounded (Assumption 7), it is compact, so Ψ max = max a ∈ A Ψ ( a ) < ∞ \Psi_{\max}=\max_{a\in A}\Psi(a)<\infty Ψ m a x = max a ∈ A Ψ ( a ) < ∞ is attained (Ψ \Psi Ψ being continuous). Set
c ′ = max ( 1 c ψ , Ψ max c ψ S 0 ) . c'=\max\left(\frac{1}{\sqrt{c_\psi}},\frac{\sqrt{\Psi_{\max}}}{c_\psi S_0}\right). c ′ = max ( c ψ 1 , c ψ S 0 Ψ m a x ) .
Let a ∈ A a\in A a ∈ A and write r = ∥ [ g ( a ) ] + ∥ r=\lVert[g(a)]_+\rVert r = ∥[ g ( a ) ] + ∥ . By Definition 4 applied coordinatewise and Lemma 3, recalling (6), Ψ ( a ) ≥ c ψ r min ( r , S 0 ) \Psi(a)\ge c_\psi r\min(r,S_0) Ψ ( a ) ≥ c ψ r min ( r , S 0 ) ; since s ↦ s min ( s , S 0 ) s\mapsto s\min(s,S_0) s ↦ s min ( s , S 0 ) is increasing, this inverts to
r ≤ max ( Ψ ( a ) c ψ , Ψ ( a ) c ψ S 0 ) . r\le\max\left(\sqrt{\frac{\Psi(a)}{c_\psi}},\frac{\Psi(a)}{c_\psi S_0}\right). r ≤ max ( c ψ Ψ ( a ) , c ψ S 0 Ψ ( a ) ) .
As Ψ ( a ) ≤ Ψ max \Psi(a)\le\Psi_{\max} Ψ ( a ) ≤ Ψ m a x , the second term satisfies
Ψ ( a ) c ψ S 0 ≤ Ψ max c ψ S 0 Ψ ( a ) , \frac{\Psi(a)}{c_\psi S_0}\le\frac{\sqrt{\Psi_{\max}}}{c_\psi S_0}\sqrt{\Psi(a)}, c ψ S 0 Ψ ( a ) ≤ c ψ S 0 Ψ m a x Ψ ( a ) ,
so that, combined with the first term Ψ ( a ) / c ψ = 1 c ψ Ψ ( a ) \sqrt{\Psi(a)/c_\psi}=\frac{1}{\sqrt{c_\psi}}\sqrt{\Psi(a)} Ψ ( a ) / c ψ = c ψ 1 Ψ ( a ) ,
∥ [ g ( a ) ] + ∥ = r ≤ c ′ Ψ ( a ) . (47) \lVert[g(a)]_+\rVert=r\le c'\sqrt{\Psi(a)}. \tag*{(47)} ∥[ g ( a ) ] + ∥ = r ≤ c ′ Ψ ( a ) . (47)
Let s = Π S L ( a ) s=\Pi_{S_L}(a) s = Π S L ( a ) . Since Ψ ( s ) = 0 \Psi(s)=0 Ψ ( s ) = 0 , convexity of Ψ \Psi Ψ implies
0 = Ψ ( s ) ≥ Ψ ( a ) + ⟨ P ( a ) , s − a ⟩ , 0=\Psi(s)\ge\Psi(a)+\langle P(a),s-a\rangle, 0 = Ψ ( s ) ≥ Ψ ( a ) + ⟨ P ( a ) , s − a ⟩ ,
so that
Ψ ( a ) ≤ ∥ P ( a ) ∥ dist ( a , S L ) . \Psi(a)\le\lVert P(a)\rVert\operatorname{dist}(a,S_L). Ψ ( a ) ≤ ∥ P ( a )∥ dist ( a , S L ) .
By the error bound established above and (40),
dist ( a , S L ) ≤ κ A ∥ [ g ( a ) ] + ∥ ≤ κ A c ′ Ψ ( a ) . (48) \operatorname{dist}(a,S_L)\le\kappa_A\lVert[g(a)]_+\rVert\le\kappa_Ac'\sqrt{\Psi(a)}. \tag*{(48)} dist ( a , S L ) ≤ κ A ∥[ g ( a ) ] + ∥ ≤ κ A c ′ Ψ ( a ) . (48)
Combining the relations above, we obtain
Ψ ( a ) ≤ κ A c ′ ∥ P ( a ) ∥ Ψ ( a ) . \Psi(a)\le\kappa_Ac'\lVert P(a)\rVert\sqrt{\Psi(a)}. Ψ ( a ) ≤ κ A c ′ ∥ P ( a )∥ Ψ ( a ) .
If Ψ ( a ) = 0 \Psi(a)=0 Ψ ( a ) = 0 , the claims hold. Otherwise, division by Ψ ( a ) \sqrt{\Psi(a)} Ψ ( a ) and squaring yield
Ψ ( a ) ≤ κ A 2 ( c ′ ) 2 ∥ P ( a ) ∥ 2 . \Psi(a)\le\kappa_A^2(c')^2\lVert P(a)\rVert^2. Ψ ( a ) ≤ κ A 2 ( c ′ ) 2 ∥ P ( a ) ∥ 2 .
Finally, using (41), we conclude
dist ( a , S L ) 2 ≤ κ A 2 ( c ′ ) 2 Ψ ( a ) ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 . \operatorname{dist}(a,S_L)^2\le\kappa_A^2(c')^2\Psi(a)\le\kappa_A^4(c')^4\lVert P(a)\rVert^2. dist ( a , S L ) 2 ≤ κ A 2 ( c ′ ) 2 Ψ ( a ) ≤ κ A 4 ( c ′ ) 4 ∥ P ( a ) ∥ 2 .
■
Proof of Lemma 6
Set a = a ( x ) ∈ A ⊆ Q a=a(x)\in A\subseteq Q a = a ( x ) ∈ A ⊆ Q . By Lemma 5 ,
∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . \lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2. ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 .
Since W 1 N = 1 N W\mathbf{1}_N=\mathbf{1}_N W 1 N = 1 N (Assumption 6), we have W ( 1 N ⊗ a ) = ( W ⊗ I D ) ( 1 N ⊗ a ) = ( W 1 N ) ⊗ a = 1 N ⊗ a W(\mathbf{1}_N\otimes a)=(W\otimes I_D)(\mathbf{1}_N\otimes a)=(W\mathbf{1}_N)\otimes a=\mathbf{1}_N\otimes a W ( 1 N ⊗ a ) = ( W ⊗ I D ) ( 1 N ⊗ a ) = ( W 1 N ) ⊗ a = 1 N ⊗ a , so that
z − 1 N ⊗ a = W x − W ( 1 N ⊗ a ) = W ( x − 1 N ⊗ a ) . z-\mathbf{1}_N\otimes a=Wx-W(\mathbf{1}_N\otimes a)=W(x-\mathbf{1}_N\otimes a). z − 1 N ⊗ a = W x − W ( 1 N ⊗ a ) = W ( x − 1 N ⊗ a ) .
Moreover, W W W , being symmetric and doubly stochastic, has eigenvalues in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , so ∥ W ∥ = ∥ W ⊗ I D ∥ = ∥ W ∥ ≤ 1 \lVert W\rVert=\lVert W\otimes I_D\rVert=\lVert W\rVert\le1 ∥ W ∥ = ∥ W ⊗ I D ∥ = ∥ W ∥ ≤ 1 . Combining this inequality with the previous equality, we obtain
∥ z − 1 N ⊗ a ∥ 2 ≤ ∥ W ∥ 2 ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . (49) \lVert z-\mathbf{1}_N\otimes a\rVert^2\le\lVert W\rVert^2\lVert x-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2. \tag*{(49)} ∥ z − 1 N ⊗ a ∥ 2 ≤ ∥ W ∥ 2 ∥ x − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 . (49)
As x ∈ Ω x\in\Omega x ∈ Ω , we have z i ∈ Q z_i\in Q z i ∈ Q for every i ∈ [ N ] i\in[N] i ∈ [ N ] . Since also a ∈ Q a\in Q a ∈ Q , Assumption 7 implies, for every i ∈ [ N ] i\in[N] i ∈ [ N ] ,
∥ P ( a ) ∥ ≤ ∥ P ( z i ) ∥ + L P Q ∥ z i − a ∥ . \lVert P(a)\rVert\le\lVert P(z_i)\rVert+L_P^Q\lVert z_i-a\rVert. ∥ P ( a )∥ ≤ ∥ P ( z i )∥ + L P Q ∥ z i − a ∥ .
Squaring via ( u + v ) 2 ≤ 2 u 2 + 2 v 2 (u+v)^2\le2u^2+2v^2 ( u + v ) 2 ≤ 2 u 2 + 2 v 2 , summing over i ∈ [ N ] i\in[N] i ∈ [ N ] , and dividing by N N N gives
∥ P ( a ) ∥ 2 ≤ 2 N ∑ i = 1 N ∥ P ( z i ) ∥ 2 + 2 ( L P Q ) 2 N ∑ i = 1 N ∥ z i − a ∥ 2 = 2 N ∥ P ( z ) ∥ 2 + 2 ( L P Q ) 2 N ∥ z − 1 N ⊗ a ∥ 2 , \begin{aligned}
\lVert P(a)\rVert^2
&\le\frac{2}{N}\sum_{i=1}^{N}\lVert P(z_i)\rVert^2+\frac{2(L_P^Q)^2}{N}\sum_{i=1}^{N}\lVert z_i-a\rVert^2\\
&=\frac{2}{N}\lVert P(z)\rVert^2+\frac{2(L_P^Q)^2}{N}\lVert z-\mathbf{1}_N\otimes a\rVert^2,
\end{aligned} ∥ P ( a ) ∥ 2 ≤ N 2 i = 1 ∑ N ∥ P ( z i ) ∥ 2 + N 2 ( L P Q ) 2 i = 1 ∑ N ∥ z i − a ∥ 2 = N 2 ∥ P ( z ) ∥ 2 + N 2 ( L P Q ) 2 ∥ z − 1 N ⊗ a ∥ 2 ,
where we used P ( z ) = [ P ( z 1 ) , … , P ( z N ) ] P(z)=[P(z_1),\ldots,P(z_N)] P ( z ) = [ P ( z 1 ) , … , P ( z N )] and ∥ z − 1 N ⊗ a ∥ 2 = ∑ i = 1 N ∥ z i − a ∥ 2 \lVert z-\mathbf{1}_N\otimes a\rVert^2=\sum_{i=1}^{N}\lVert z_i-a\rVert^2 ∥ z − 1 N ⊗ a ∥ 2 = ∑ i = 1 N ∥ z i − a ∥ 2 . Substituting ∥ z − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 \lVert z-\mathbf{1}_N\otimes a\rVert^2\le(N+1)\lVert x^\perp\rVert^2 ∥ z − 1 N ⊗ a ∥ 2 ≤ ( N + 1 ) ∥ x ⊥ ∥ 2 from (42) and using ∥ x ∥ 2 = R ( x ) \lVert x\rVert^2=\mathcal{R}(x) ∥ x ∥ 2 = R ( x ) , ∥ P ( z ) ∥ 2 = R ( x ) = ∥ x ⊥ ∥ 2 + ∥ P ( z ) ∥ 2 \lVert P(z)\rVert^2=\mathcal{R}(x)=\lVert x^\perp\rVert^2+\lVert P(z)\rVert^2 ∥ P ( z ) ∥ 2 = R ( x ) = ∥ x ⊥ ∥ 2 + ∥ P ( z ) ∥ 2 , we obtain
∥ P ( a ) ∥ 2 ≤ 2 N ∥ P ( z ) ∥ 2 + 2 ( L P Q ) 2 ( N + 1 ) N ∥ x ⊥ ∥ 2 ≤ C P R ( x ) , \lVert P(a)\rVert^2\le\frac{2}{N}\lVert P(z)\rVert^2+\frac{2(L_P^Q)^2(N+1)}{N}\lVert x^\perp\rVert^2\le C_P\mathcal{R}(x), ∥ P ( a ) ∥ 2 ≤ N 2 ∥ P ( z ) ∥ 2 + N 2 ( L P Q ) 2 ( N + 1 ) ∥ x ⊥ ∥ 2 ≤ C P R ( x ) ,
where C P = 2 max ( 1 , ( L P Q ) 2 ( N + 1 ) / N ) C_P=2\max(1,(L_P^Q)^2(N+1)/N) C P = 2 max ( 1 , ( L P Q ) 2 ( N + 1 ) / N ) . Thus, Lemma 10 together with the inequality above gives
dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 C P R ( x ) . (50) \operatorname{dist}(a,S_L)^2\le\kappa_A^4(c')^4C_P\mathcal{R}(x). \tag*{(50)} dist ( a , S L ) 2 ≤ κ A 4 ( c ′ ) 4 C P R ( x ) . (50)
Next, for every s ∈ S L s\in S_L s ∈ S L ,
∥ x − 1 N ⊗ s ∥ ≤ ∥ x − 1 N ⊗ a ∥ + ∥ 1 N ⊗ a − 1 N ⊗ s ∥ = ∥ x − 1 N ⊗ a ∥ + N ∥ a − s ∥ , \lVert x-\mathbf{1}_N\otimes s\rVert\le\lVert x-\mathbf{1}_N\otimes a\rVert+\lVert\mathbf{1}_N\otimes a-\mathbf{1}_N\otimes s\rVert
=\lVert x-\mathbf{1}_N\otimes a\rVert+\sqrt{N}\lVert a-s\rVert, ∥ x − 1 N ⊗ s ∥ ≤ ∥ x − 1 N ⊗ a ∥ + ∥ 1 N ⊗ a − 1 N ⊗ s ∥ = ∥ x − 1 N ⊗ a ∥ + N ∥ a − s ∥ ,
where we used ∥ 1 N ⊗ v ∥ 2 = N ∥ v ∥ 2 \lVert\mathbf{1}_N \otimes v \rVert^2 = N\lVert v\rVert^2 ∥ 1 N ⊗ v ∥ 2 = N ∥ v ∥ 2 for v = a − s v=a-s v = a − s . Since S L = { 1 N ⊗ s : s ∈ S L } S_L=\{\mathbf{1}_N\otimes s:s\in S_L\} S L = { 1 N ⊗ s : s ∈ S L } , taking the infimum over s ∈ S L s\in S_L s ∈ S L on both sides gives
dist ( x , S L ) ≤ ∥ x − 1 N ⊗ a ∥ + N dist ( a , S L ) . \operatorname{dist}(x,S_L)\leq\lVert x-\mathbf{1}_N\otimes a\rVert+\sqrt{N}\operatorname{dist}(a,S_L). dist ( x , S L ) ≤ ∥ x − 1 N ⊗ a ∥ + N dist ( a , S L ) .
Squaring via ( u + v ) 2 ≤ 2 u 2 + 2 v 2 (u+v)^2\leq2u^2+2v^2 ( u + v ) 2 ≤ 2 u 2 + 2 v 2 , we obtain
dist ( x , S L ) 2 ≤ 2 ∥ x − 1 N ⊗ a ∥ 2 + 2 N dist ( a , S L ) 2 ≤ 2 ( N + 1 ) ∥ x ⊥ ∥ 2 + 2 N κ A 4 ( c ′ ) 4 C P R ( x ) ≤ [ 2 ( N + 1 ) + 2 N κ A 4 ( c ′ ) 4 C P ] R ( x ) . \begin{aligned}
\operatorname{dist}(x,S_L)^2
&\leq2\lVert x-\mathbf{1}_N\otimes a\rVert^2+2N\operatorname{dist}(a,S_L)^2\\
&\leq2(N+1)\lVert x^{\perp}\rVert^2+2N\kappa_A^4(c')^4C_P R(x)\\
&\leq\left[2(N+1)+2N\kappa_A^4(c')^4C_P\right]R(x).
\end{aligned} dist ( x , S L ) 2 ≤ 2 ∥ x − 1 N ⊗ a ∥ 2 + 2 N dist ( a , S L ) 2 ≤ 2 ( N + 1 ) ∥ x ⊥ ∥ 2 + 2 N κ A 4 ( c ′ ) 4 C P R ( x ) ≤ [ 2 ( N + 1 ) + 2 N κ A 4 ( c ′ ) 4 C P ] R ( x ) .
where in the first inequality we used Lemma 5 and (43), and in the last inequality we used ∥ x ⊥ ∥ 2 ≤ R ( x ) \lVert x^{\perp}\rVert^2\leq R(x) ∥ x ⊥ ∥ 2 ≤ R ( x ) . Thus,
dist ( x , S L ) 2 ≤ C R R ( x ) , \operatorname{dist}(x,S_L)^2\leq C_RR(x), dist ( x , S L ) 2 ≤ C R R ( x ) ,
where C R = 2 ( N + 1 ) + 2 N κ A 4 ( c ′ ) 4 C P C_R=2(N+1)+2N\kappa_A^4(c')^4C_P C R = 2 ( N + 1 ) + 2 N κ A 4 ( c ′ ) 4 C P . Finally,
∥ x − 1 N ⊗ s ∥ 2 ≤ 2 ∥ x − 1 N ⊗ a ∥ 2 + 2 N ∥ a − s ∥ 2 \lVert x-\mathbf{1}_N\otimes s\rVert^2\leq2\lVert x-\mathbf{1}_N\otimes a\rVert^2+2N\lVert a-s\rVert^2 ∥ x − 1 N ⊗ s ∥ 2 ≤ 2 ∥ x − 1 N ⊗ a ∥ 2 + 2 N ∥ a − s ∥ 2
≤ 2 ( N + 1 ) ∥ x ⊥ ∥ 2 + 2 N ∥ a − s ∥ 2 . \leq2(N+1)\lVert x^{\perp}\rVert^2+2N\lVert a-s\rVert^2. ≤ 2 ( N + 1 ) ∥ x ⊥ ∥ 2 + 2 N ∥ a − s ∥ 2 .
Thus one may take K R = 2 ( N + 1 ) K_R=2(N+1) K R = 2 ( N + 1 ) , and K a = 2 N K_a=2N K a = 2 N .
References