B. Proof of the main theorem

Supplementary Material:

Stochastic Dual Coordinate Descent with Alternating Direction Multiplier Method

Taiji Suzuki S-TAIJI@IS.TITECH.AC.JP

Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo 152-8552, JAPAN

A. Derivation of the proximal operation for the smoothed hinge loss

By the definition of the smoothed hinge loss, we have that, for−1≤yiv≤0, f_i^∗(v) = sup

u∈R

{uv−fi(u)}= sup

u∈R

uv−1

2(1−yiu)²

= sup

u∈R

1

2(1 +yiv)²−1 2−1

2(1 +yiv−yiu)²

=1

2(1 +yiv)²−1 2, andf_i^∗(v) =∞otherwise.

Since

f_i^∗(v) C +1

2(q−v)²= ( 1

2C(1 +y_iv)²−_2C¹ +¹₂(q−v)² (−1≤y_iv≤0),

∞ (otherwise),

=





1+C 2C

v+^y_1+C^i−qC2

+^v

2(yi−qC)²

2C(1+C) +^q₂² (−1≤yiv≤0),

∞ (otherwise).

Thus by minimizing this with respect tov, we have that

prox(u|f_i^∗/C) =







Cu−yi

1+C (−1≤ ^Cuy_1+Cⁱ⁻¹ ≤0),

−yi (−1> ^Cuy_1+Cⁱ⁻¹), 0 (otherwise).

B. Proof of the main theorem

In the section, we give the proofs of the theorems in the main body. For notational simplicity, we rewrite the dual problem as follows:

x∈Xmin,y∈Y

Xn i=1

g_i(x_i) +φ(y), (S-1a)

s.t. Zx+By= 0, (S-1b)

whereZ ∈ R^p×n,B ∈ R^p×d. This is equivalent to the dual optimization problem in the main text wheng_i = f_i^∗ and φ=nψ^∗(·/n)(or equivalentlyφ^∗=nψ). We writeg(x) =Pn

i=1gi(xi).

Then we consider the following update rule:

y^(t)←arg min

y

φ(y)− hw^(t−1), Zx^(t−1)+Byi+ρ

2kZx^(t−1)+Byk²+1

2ky−y^(t−1)kQ

x^(t)_i ←arg min

xI

X

i∈I

gi(xi)− hw^(t−1), ZIxI +By^(t)i+ρ

2kZIxI+Z\Ix^(t−1)_\I +By^(t)k²+1

2kxI−x^(t−1)_I kGii

w^(t)=w^(t−1)−γρ{n(Zx^(t)+By^(t))−(n−n/K)(Zx^(t−1)+By^(t−1))}.

Assumption 1 can be interpreted as follows. There is an optimal solution(x^∗, y^∗)and corresponding Lagrange multiplier w^∗such that

∂g(x^∗)∋Z^⊤w^∗, ∂φ(y^∗)∋B^⊤w^∗.

We denote by∇f(x)an arbitrary element of the subgradient∂f(x)of a convex functionf atx. Moreover, we suppose that each (dual) loss functiongiisv-strongly convex andφish-smooth:

gi(xi)−gi(x^∗_i)≥ hz^⊤_i w^∗, xi−x^∗_ii+vkxi−x^∗_ik²

2 .

We also assume that there exithandvφsuch that, for ally, uand ally^∗ ∈ Y^∗, there exitsyb^∗ ∈ Y^∗which depends ony and we have

φ(y)−φ(y^∗)≥ hB^⊤w^∗, y−y^∗i+v^′_φ

2 kPKer(B)(y−y^∗)k², φ^∗(u)−φ^∗(B^⊤w^∗)≥ hy^∗, u−B^⊤w^∗i+h^′

2ku−B^⊤w^∗k².

Note that the primal and dual are flipped compared with the main text. Once can check that there is a correspondence betweenv_ψ, hin the main text andv_φ^′ andh^′such thatv_φ^′ =^v_n^ψ andh^′=nh.

Define

F(x, y) :=

Xn i=1

gi(xi) +φ(y)− hw^∗, Zx+Byi (=nFD(x, y)).

By the definition ofw^∗, one can easily check that

F(x, y)−F(x^∗, y^∗)≥ nv

2 kx−x^∗k²≥0.

We define

R^′(x, y, w)

=F(x, y)−F(x^∗, y^∗) +2

ρkw^(t)−w^∗k²+ρ(1−γ)

2 kZx+Byk²+1

2kx−x^∗k²_vIp+H+ 1

2Kky− Y^∗k²_Q. Here again we have that R^′ = nRD. Let nˆ = n/K, the expected cardinality of |I|, and let Diag_I(S)be a block diagonal matrix whoseIk×Ik (k = 1, . . . , K)diagonal elements are non-zero and given by(Diag(S))Ik,Ik = SIk,Ik

(k= 1, . . . , K).

Theorem 2. Suppose thatγ= _4n¹,Diag_I(G)≻2γρ(n−n)Diagˆ _I(Z^⊤Z)andB^⊤is injective. Then, under the assump- tions, the objective function converges R-linearly:

R^′(x^(t), y^(t), w^(t))≤ 1− µ

K T

R(x⁽⁰⁾, y⁽⁰⁾, w⁽⁰⁾), E[F(x^(t), y^(t))−F(x^∗, y^∗)]≤

1− µ K

T

R(x⁽⁰⁾, y⁽⁰⁾, w⁽⁰⁾), where

µ:= min (1

2

v v+σmax(H)

, h^′ρσmin(BB^⊤)

2 max{1,4h^′ρ,4h^′σmax(Q)}, Kv_φ^′

4σmax(Q), Kvσmin(BB^⊤) σmax(Q)(ρσmax(Z^⊤Z) + 4v)

) ,

In particular, we have that

E[kw^(t)−w^∗k²]≤ ρ 2

1− µ K

T

R(x⁽⁰⁾, y⁽⁰⁾, w⁽⁰⁾).

Theorem 1 in the main text can be obtained using the relationv^′_φ = ^v_n^φ,h^′ = nh, F = nF_D andR^′ = nR_D. The convergence of the primal objective is obtained by using the following fact: Sincegis strongly convex aroundx^∗, we have that

g(x)−g(x^∗)≥ hZ^⊤w^∗, x−x^∗i+vkx−x^∗k²

2 (∀x)

⇒g^∗(u)≤g^∗(Z^⊤w^∗) +hx^∗, u−Z^⊤w^∗i+ku−Z^⊤w^∗k² 2v (∀u).

where we usedZ^⊤λ^∗∈∂g(x^∗). Using this, we have that, 1

n Xn i=1

fi(z_i^⊤w^(t))−1 n

Xn i=1

fi(z_i^⊤w^∗)≤D

Zx^∗/n, w^(t)−w^∗E

+kZ^⊤(w^(t)−w^∗)k² 2nv

=D

−y^∗/n, B^⊤(w^(t)−w^∗)E

+kZ^⊤(w^(t)−w^∗)k²

2nv ,

where we used the relationZx^∗+By^∗= 0. Moreover, using the relationψ(B^⊤w)≤ψ(B^⊤w^∗) +hy^∗/n, B^⊤(w−w^∗)i+ l1kw−w^∗k+l2kw−w^∗k²and the Jensen’s inequalityE[kw^(T)−w^∗k]²≤E[kw^(T)−w^∗k²], we obtain the assertion.

Proof of Theorem 2.

Step 1(Deriving a basic inequality):

g(x^(t))−g(x^(t−1)) +φ(y^(t))−φ(y^(t−1))

=X

i∈I

gi(x^(t)_i )−X

i∈I

gi(x^(t−1)_i ) +φ(y^(t))−φ(y^(t−1))

=X

i∈I

gi(x^(t)_i )− hw^(t−1), Zx^(t)+By^(t)i+ρ

2kZx^(t)+By^(t)k²+1

2kx^(t)_I −x^(t−1)_I k²_GI,I +hw^(t−1), Zx^(t)+By^(t)i −ρ

2kZx^(t)+By^(t)k²−1

2kx^(t)_I −x^(t−1)_I k²_GI,I

−X

i∈I

gi(x^(t−1)_i ) +φ(y^(t))−φ(y^(t−1)). (S-2)

Here we define thatZ˜I = [Z\IZI]andx˜:=

"

x^(t−1)_\I xI

#

for a givenxI, and

˜

gI(xI) :=X

i∈I

gi(xi)−D

w^(t−1),Z˜Ix˜+By^(t)E +ρ

2kZ˜Ix˜+By^(t)k²+1

2kxI−x^(t−1)_I k²_GI,I.

Then by the update rule ofx^(t), we have that

˜

gI(x^(t)_I )≤g˜I(x^∗_I)−v

2kx^(t)_I −x^∗_Ik²−ρ

2kZI(x^(t)_I −x^∗_I)k²−1

2kx^(t)_I −x^∗_IkGI,I,

which implies X

i∈I

gi(x^(t)_i )−D

w^(t−1), Zx^(t)+By^(t)E +ρ

2kZx^(t)+By^(t)k²+1

2kx^(t)_I −x^(t−1)_I k²_GI,I

≤X

i∈I

gi(x^∗_i)−D

w^(t−1), ZIx^∗_I+Z\Ix^∗_\I+By^(t)E +ρ

2kZIx^∗_I +Z\Ix^(t−1)_\I +By^(t)k²+1

2kx^∗_I−x^(t−1)_I k²_GI,I

−v

2kx^(t)_I −x^∗_Ik²−ρ

2kZ_I(x^(t)_I −x^∗_I)k²−1

2kx^(t)_I −x^∗_Ik_GI,I

=X

i∈I

gi(x^∗_i)−D

w^(t−1), ZI(x^∗_I−x^(t)_I )E

−D

w^(t−1), Zx^(t)+By^(t)E +ρ

2kZIx^∗_I+Z\Ix^(t−1)_\I +By^(t)k²−ρ

2kZx^(t)+By^(t)k²+ρ

2kZx^(t)+By^(t)k²+1

2kx^∗_I−x^(t−1)_I k²_GI,I

−v

2kx^(t)_I −x^∗_Ik²−ρ

2kZI(x^(t)_I −x^∗_I)k²−1

2kx^(t)_I −x^∗_IkGI,I

=X

i∈I

gi(x^∗_i)−D

w^(t−1), ZI(x^∗_I−x^(t)_I )E

−v

2kx^(t)_I −x^∗_Ik²−ρ

2kZI(x^(t)_I −x^∗_I)k²−1

2kx^(t)_I −x^∗_IkGI,I

−ρhZ\Ix^(t)_\I +By^(t), ZI(x^(t)_I −x^∗_I)i+ρ

2kZIx^∗_Ik²−ρ

2kZIx^(t)_I k²+1

2kx^∗_I−x^(t−1)_I k²_GI,I

−D

w^(t−1), Zx^(t)+By^(t)E +ρ

2kZx^(t−1)+By^(t)k². Using this, the RHS of Eq. (S-2) can be further bounded by

(RHS)≤X

i∈I

gi(x^∗_i)−X

i∈I

gi(x^(t−1)_i )− hw^(t−1), ZI(x^∗_I −x^(t)_I )i

−v

2kx^(t)_I −x^∗_Ik²−ρ

2kZI(x^(t)_I −x^∗_I)k²−1

2kx^(t)_I −x^∗_IkGI,I

−ρhZ\Ix^(t)_\I +By^(t), ZI(x^(t)_I −x^∗_I)i+ρ

2kZIx^∗_Ik²−ρ

2kZIx^(t)_I k² +1

2kx^∗_I −x^(t−1)_I k²_GI,I−1

2kx^(t)_I −x^(t−1)_I k²_GI,I

+φ(y^(t))−φ(y^(t−1)). (S-3)

Here, we bound the term

−ρhZ\ix^(t)_\i +By^(t), ZI(x^(t)_I −x^∗_I)i+ρ

2kZIx^∗_Ik²−ρ

2kZIx^(t)_I k². By Lemma 3, the expectation of this term is equivalent to

Eh

−ρ

nhZx^(t−1)+By^(t), Z(nx^(t)−(n−ˆn)x^(t−1)−nxˆ ^∗)ii + ρ

2Kkx^(t−1)−x^∗k²_Diag

I(Z^⊤Z)−ρ 2Eh

kx^(t)−x^(t−1)k²_Diag

I(Z^⊤Z)

i.

Note that, for any block diagonal matrixSwhich satisfiesSIk,Ik′ = (Si,j)(i,j)∈I_k×I_k′ =O(∀k6=k^′), we have that E[kx^(t)_I −x^∗_Ik²_SI,I] = E[kx^(t)_I −x^(t−1)_I +x^(t−1)_I −x^∗_Ik²_SI,I]

= E[kx^(t)_I −x^(t−1)_I k²_SI,I] + E[2hx^(t)_I −x^(t−1)_I , x^(t−1)_I −x^∗_IiSI,I] + E[kx^(t−1)_I −x^∗_Ik²_SI,I]

= E[kx^(t)−x^(t−1)k²_S] + E[2hx^(t)−x^(t−1), x^(t−1)−x^∗iS] + 1

Kkx^(t−1)−x^∗k²_S

= E[kx^(t)−x^∗k²_S]−E[kx^(t−1)−x^∗k²_S] + 1

Kkx^(t−1)−x^∗k²_S

= E[kx^(t)−x^∗k²_S]−

1− 1 K

E[kx^(t−1)−x^∗k²_S],

where the expectation is taken with respect to the choice ofI∈ {I1, . . . , IK}. Moreover, for a fixed vectorq, we have that E[hqI, x^(t)_I −x^∗_Ii]

=E[hqI, x^(t)_I −x^(t−1)_I +x^(t−1)_I −x^∗_Ii] = E[hq, x^(t)−x^(t−1)i] + E[hqI, x^(t−1)_I −x^∗_Ii]

=E[hq, x^(t)−x^(t−1)i] + E

" _K X

k=1

1[I=Ik]hqIk, x^(t−1)_Ik −x^∗_Iki

#

=E[hq, x^(t)−x^(t−1)i] + 1 K

XK k=1

1[I=I_k]hq_Ik, x^(t−1)_Ik −x^∗_Iki= E[hq, x^(t)−x^(t−1)i] + 1

Khq, x^(t−1)−x^∗i

=E

q, x^(t)−

1− 1 K

x^(t−1)− 1 Kx^∗

.

Then, by taking expectation with respect toIand multiplying both sides of the above inequality byn, we have that nE[g(x^(t)) +φ(y^(t))−g(x^(t−1))−φ(y^(t−1))]

≤g(x^∗)−g(x^(t−1)) + E[hw^(t−1), Z(nx^(t)−(n−n)xˆ ^(t−1)−nxˆ ^∗)i]

−Ehnv

2 kx^(t)−x^∗k²+nρ

2 kx^(t)−x^∗k²_Diag

I(Z^⊤Z)+n

2kx^(t)−x^∗k²_Diag

I(G)

i +(n−n)vˆ

2 kx^(t−1)−x^∗k²] + (n−ˆn)ρ

2 kx^(t−1)−x^∗k²_Diag

I(Z^⊤Z)+n−nˆ

2 kx^(t−1)−x^∗k²_Diag

I(G)

+ Eh

−ρhZx^(t−1)+By^(t), Z(nx^(t)−(n−n)xˆ ^(t−1)−ˆnx^∗)ii +ρˆn

2 kx^(t−1)−x^∗k²_Diag

I(Z^⊤Z)−nρ 2 Eh

kx^(t)−x^(t−1)k²_Diag

I(Z^⊤Z)

i +nˆ

2kx^(t−1)−x^∗k²_Diag

I(G)−n

2E[kx^(t)−x^(t−1)k²_Diag

I(G)]

+nφ(y^(t))−nφ(y^(t−1)). (S-4)

Here, note that the last two termnφ(y^(t))−nφ(y^(t−1))is bounded as nφ(y^(t))−nφ(y^(t−1))

=ˆn(φ(y^(t))−φ(y^(t−1))) + (n−n)(φ(yˆ ^(t))−φ(y^(t−1)))

≤ˆn(φ(y^∗)−φ(y^(t−1))) +D

∇φ(y^(t)),(n−n)(yˆ ^(t)−y^(t−1)) + ˆn(y^(t)−y^∗)E

−nhˆ ^′

2 kB^⊤w^∗− ∇φ(y^(t))k².

for arbitraryy^∗∈ Y^∗where we used Lemma 4 in the last line. Define

˜

w^(t):=w^(t−1)−ρ(Zx^(t−1)+By^(t)).

Note thatB^⊤w˜^(t)−Q(y^(t)−y^(t−1))∈∂φ(y^(t)).

Next, addingE[nhw^∗, Z(x^(t−1)−x^(t)) +B(y^(t−1)−y^(t))i]to the both sides of Eq. (S-4), we have that nE[F(x^(t), y^(t))−F(x^(t−1), y^(t−1))]

≤ˆn(F(x^∗, y^∗)−F(x^(t−1), y^(t−1)))

+ E[hw^(t−1)−w^∗, Z(nx^(t)−(n−ˆn)x^(t−1)−nxˆ ^∗)i]

+ E[hw˜^(t)−w^∗, B(ny^(t)−(n−n)yˆ ^(t−1)−nyˆ ^∗)i]

− hQ(y^(t)−y^(t−1)), ny^(t)−(n−n)yˆ ^(t−1)−nyˆ ^∗i

−Ehnv

2 kx^(t)−x^∗k²+n

2kx^(t)−x^∗k²_Hi

+(n−n)vˆ

2 kx^(t−1)−x^∗k²+n

2kx^(t−1)−x^∗k²_H + Eh

−ρhZx^(t−1)+By^(t), Z(nx^(t)−(n−ˆn)x^(t−1)−nxˆ ^∗)ii

−n 2Eh

kx^(t)−x^(t−1)k²_Hi

−ˆnh^′

2 kB^⊤w^∗− ∇φ(y^(t))k². (S-5) Step 2(Rearranging cross terms between(x^(t), y^(t), w^(t))and(x^(t−1), y^(t−1), w^(t−1))):

Now, we definexˆ^(t):=nx^(t)−(n−n)xˆ ^(t−1)andyˆ^(t):=ny^(t)−(n−n)yˆ ^(t−1). Then by the update rule ofw^(t), we have thatw^(t)=w^(t−1)−γρ(Zxˆ^(t)+Byˆ^(t)). We evaluate the termE[hw^(t−1)−w^∗, Z(ˆx^(t)−ˆnx^∗)i] + E[hw˜^(t)−w^∗, B(ˆy^(t)− ˆ

ny^∗)i]:

hw^(t−1)−w^∗, Z(ˆx^(t)−ˆnx^∗)i+hw˜^(t)−w^∗, B(ˆy^(t)−nyˆ ^∗)i

=hw^(t−1)−w^∗, Z(ˆx^(t)−ˆnx^∗)i+hw^(t−1)−ρ(Zx^(t−1)+By^(t))−w^∗, B(ˆy^(t)−nyˆ ^∗)i

=hw^(t)+γρ(Zxˆ^(t)+Byˆ^(t))−w^∗, Z(ˆx^(t)−ˆnx^∗)i

+hw^(t)+γρ(Zxˆ^(t)+Byˆ^(t))−ρ(Zx^(t−1)+By^(t))−w^∗, B(ˆy^(t)−nyˆ ^∗)i

=− 1

γρhw^(t)−w^∗, w^(t)−w^(t−1)i

+γρkZxˆ^(t)+Byˆ^(t)k²−ρhZx^(t−1)+By^(t), B(ˆy^(t)−nyˆ ^∗)i

=− 1 2γρ

kw^(t)−w^∗k²+kw^(t)−w^(t−1)k²− kw^(t−1)−w^∗k² +γρkZxˆ^(t)+Byˆ^(t)k²−ρhZx^(t−1)+By^(t), B(ˆy^(t)−nyˆ ^∗)i

= 1 2γρ

−kw^(t)−w^∗k²+kw^(t−1)−w^∗k² +γρ

2 kZxˆ^(t)+Byˆ^(t)k²

−ρhZx^(t−1)+By^(t), B(ˆy^(t)−nyˆ ^∗)i.

Therefore,

hw^(t−1)−w^∗, Z(ˆx^(t)−nxˆ ^∗) +hw˜^(t)−w^∗, B(ˆy^(t)−nyˆ ^∗)i

−ρhZx^(t−1)+By^(t), Z(nx^(t)−(n−n)xˆ ^(t−1)−ˆnx^∗)i

= 1 2γρ

−kw^(t)−w^∗k²+kw^(t−1)−w^∗k² +γρ

2 kZˆx^(t)+Byˆ^(t)k²

−ρhZx^(t−1)+By^(t), Zxˆ^(t)+Byˆ^(t)i

= 1 2γρ

−kw^(t)−w^∗k²+kw^(t−1)−w^∗k² +γρ

2 n²kZx^(t)+By^(t)k²+γρ

2 (n−n)ˆ ²kZx^(t−1)+By^(t−1)k²

−γρn(n−n)hZxˆ ^(t)+By^(t), Zx^(t−1)+By^(t−1)i

−ρhZx^(t−1)+By^(t), Z(nx^(t)−(n−n)xˆ ^(t−1)) +B(ny^(t)−(n−n)yˆ ^(t−1))i.

Next, we expand the non-squared term:

−γρn(n−n)hZxˆ ^(t)+By^(t), Zx^(t−1)+By^(t−1)i

−ρhZx^(t−1)+By^(t), Z(nx^(t)−(n−n)xˆ ^(t−1)) +B(ny^(t)−(n−n)yˆ ^(t−1))i

=−γρn(n−n)hZxˆ ^(t)−Zx^∗, Zx^(t−1)−Zx^∗i

−γρn(n−n)hByˆ ^(t)−By^∗, By^(t−1)−By^∗i

−γρn(n−n)hZxˆ ^(t)−Zx^∗, By^(t−1)−By^∗i

−γρn(n−n)hByˆ ^(t)−By^∗, Zx^(t−1)−Zx^∗i

−nρhZx^(t−1)−Zx^∗, Z(x^(t)−x^∗)i+ (n−ˆn)ρkZx^(t−1)−Zx^∗k² + (n−n)ρhByˆ ^(t)−By^∗, B(y^(t−1)−y^∗)i −nρkBy^(t)−By^∗k²

−ρhZx^(t−1)−Zx^∗, B(ny^(t)−(n−n)yˆ ^(t−1)−nyˆ ^∗)i

−ρhB(y^(t)−y^∗), Z(nx^(t)−(n−n)xˆ ^(t−1)−nxˆ ^∗)i

=−(γρn(n−n) +ˆ nρ)hZx^(t)−Zx^∗, Zx^(t−1)−Zx^∗i

−(γρn(n−n)ˆ −(n−n)ρ)hByˆ ^(t)−By^∗, By^(t−1)−By^∗i

−γρn(n−n)hZxˆ ^(t)−Zx^∗, By^(t−1)−By^∗i

−(γρn(n−n) +ˆ nρ−(n−n)ρ)hByˆ ^(t)−By^∗, Zx^(t−1)−Zx^∗i + (n−n)ρkZxˆ ^(t−1)−Zx^∗k²−nρkBy^(t)−By^∗k²

−ρ(n−ˆn)hZx^(t−1)−Zx^∗, B(y^∗−y^(t−1))i

−ρnhB(y^(t)−y^∗), Z(x^(t)−x^∗)i. (S-6)

Using the relation

hZx^(t)−Zx^∗, By^(t−1)−By^∗i=hZ(x^(t)−x^∗), B(y^(t)−y^∗)i+hZ(x^(t)−x^∗), B(y^(t−1)−y^(t))i, hBy^(t)−By^∗, Zx^(t−1)−Zx^∗i=hB(y^(t)−y^(t−1)), Z(x^(t−1)−x^∗)i+hB(y^(t−1)−y^∗), Z(x^(t−1)−x^∗)i, the RHS of Eq. (S-6) is equivalent to

−(γρn(n−n) +ˆ nρ)hZx^(t)−Zx^∗, Zx^(t−1)−Zx^∗i

−(γρn(n−n)ˆ −(n−n)ρ)hByˆ ^(t)−By^∗, By^(t−1)−By^∗i + (n−n)ρkZxˆ ^(t−1)−Zx^∗k²−nρkBy^(t)−By^∗k²

+{−(γρn(n−n) +ˆ ρˆn) +ρ(n−n)}hZxˆ ^(t−1)−Zx^∗, B(y^(t−1)−y^∗)i

−(γρn(n−n) +ˆ ρn)hB(y^(t)−y^∗), Z(x^(t)−x^∗)i

−γρn(n−n)hZ(xˆ ^(t)−x^∗), B(y^(t−1)−y^(t))i

−(γρn(n−n) +ˆ ρˆn)hBy^(t)−By^(t−1), Zx^(t−1)−Zx^∗i.

The last two terms are transformed to

−γρn(n−n)hZˆ (x^(t)−x^∗), B(y^(t−1)−y^(t))i

−(γρn(n−ˆn) +ρˆn)hBy^(t)−By^(t−1), Zx^(t−1)−Zx^∗i

=γρn(n−ˆn)hZ(x^(t)−x^(t−1)), B(y^(t)−y^(t−1))i

−ρˆnhBy^(t)−By^∗, Zx^(t−1)−Zx^∗i+ρˆnhBy^(t−1)−By^∗, Zx^(t−1)−Zx^∗i.

Thus, the RHS of Eq. (S-6) is further transformed to

−(γρn(n−n) +ˆ nρ)hZx^(t)−Zx^∗, Zx^(t−1)−Zx^∗i

−(γρn(n−n)ˆ −(n−ˆn)ρ)hBy^(t)−By^∗, By^(t−1)−By^∗i + (n−n)ρkZxˆ ^(t−1)−Zx^∗k²−nρkBy^(t)−By^∗k²

+{−γρn(n−n) +ˆ ρ(n−ˆn)}hZx^(t−1)−Zx^∗, B(y^(t−1)−y^∗)i

−(γρn(n−n) +ˆ ρn)hB(y^(t)−y^∗), Z(x^(t)−x^∗)i +γρn(n−ˆn)hZ(x^(t)−x^(t−1)), B(y^(t)−y^(t−1))i

−ρˆnhBy^(t)−By^∗, Zx^(t−1)−Zx^∗i.

By Lemma 5 andZx^∗=−By^∗, this is equivalent to

−1

2(γρn(n−n) +ˆ nρ){kZx^(t)−Zx^∗k²+kZx^(t−1)−Zx^∗k²− kZx^(t)−Zx^(t−1)k²}

−1

2(γρn(n−n)ˆ −(n−ˆn)ρ){kBy^(t)−By^∗k²+kBy^(t−1)−By^∗k²− kBy^(t)−By^(t−1)k²} + (n−n)ρkZxˆ ^(t−1)−Zx^∗k²−nρkBy^(t)−By^∗k²

−1

2{−γρn(n−n) +ˆ ρ(n−ˆn)}(kZx^(t−1)−Zx^∗k²+kB(y^(t−1)−y^∗)k²− kZx^(t−1)+By^(t−1)k²) +1

2(γρn(n−n) +ˆ ρn)(kZx^(t)−Zx^∗k²+kB(y^(t)−y^∗)k²− kZx^(t)+By^(t)k²) +γρn(n−ˆn)hZ(x^(t)−x^(t−1)), B(y^(t)−y^(t−1))i

−ρˆnhBy^(t)−By^∗, Zx^(t−1)−Zx^∗i

=−ρˆn

2 kZx^(t−1)−Zx^∗k²+1

2(γρn(n−n) +ˆ nρ)kZx^(t)−Zx^(t−1)k²

−ρˆn

2 kBy^(t)−By^∗k²+1

2(γρn(n−n)ˆ −(n−n)ρ)kByˆ ^(t)−By^(t−1)k²

−1

2{γρn(n−n)ˆ −ρ(n−n)}kZxˆ ^(t−1)+By^(t−1)k²

−1

2{γρn(n−n) +ˆ ρn}kZx^(t)+By^(t)k²

+γρn(n−ˆn)hZ(x^(t)−x^(t−1)), B(y^(t)−y^(t−1))i

−nρhByˆ ^(t)−By^∗, Zx^(t−1)−Zx^∗i

=−nρˆ

2 kZx^(t−1)+By^(t)k² +1

2(γρn(n−n) +ˆ nρ)kZx^(t)−Zx^(t−1)k² +1

2(γρn(n−n)ˆ −(n−ˆn)ρ)kBy^(t)−By^(t−1)k²

−1

2{γρn(n−n)ˆ −ρ(n−n)}kZxˆ ^(t−1)+By^(t−1)k²

−1

2{γρn(n−n) +ˆ ρn}kZx^(t)+By^(t)k²

+γρn(n−ˆn)hZ(x^(t)−x^(t−1)), B(y^(t)−y^(t−1))i. (S-7) Since

γρn(n−ˆn)hZ(x^(t)−x^(t−1)), B(y^(t)−y^(t−1))i

≤γρn(n−n)ˆ

2 {kZ(x^(t)−x^(t−1))k²+kB(y^(t)−y^(t−1))k²}, the RHS of Eq. (S-7) is bounded by

−ˆnρ

2 kZx^(t−1)+By^(t)k² +1

2(2γρn(n−ˆn) +nρ)kZx^(t)−Zx^(t−1)k² +1

2(2γρn(n−ˆn)−(n−ˆn)ρ)kBy^(t)−By^(t−1)k²

−1

2{γρn(n−n)ˆ −ρ(n−ˆn)}kZx^(t−1)+By^(t−1)k²−1

2{γρn(n−n) +ˆ ρn}kZx^(t)+By^(t)k². Combining this and Eq. (S-5), and noticingkZx^(t)−Zx^(t−1)k=kZI(x^(t)_I −x^(t−1)_I )k=kx^(t)−x^(t−1)k_Diag

I(Z^⊤Z), we

obtain

nE[F(x^(t), y^(t))−F(x^(t−1), y^(t−1))]

≤ˆn(F(x^∗, y^∗)−F(x^(t−1), y^(t−1))) + 1

2γρ

−kw^(t)−w^∗k²+kw^(t−1)−w^∗k²

−nρˆ

2 kZx^(t−1)+By^(t)k² +1

2{γρn²−γρn(n−ˆn)−ρn}kZx^(t)+By^(t)k² +1

2{γρ(n−n)ˆ ²−γρn(n−n) +ˆ ρ(n−n)}kZxˆ ^(t−1)+By^(t−1)k²

−Ehnv

2 kx^(t)−x^∗k²+n

2kx^(t)−x^∗k²_Hi +(n−n)vˆ

2 kx^(t−1)−x^∗k²+n

2kx^(t−1)−x^∗k²_H +γρn(n−n)Eˆ h

kx^(t)−x^(t−1)k²_Diag

I(Z^⊤Z)

i−n

2E[kx^(t)−x^(t−1)k²_Diag

I(G)] + (γρn(n−ˆn)−(n−n)ρˆ

2 )kB(y^(t)−y^(t−1))k²

− hQ(y^(t)−y^(t−1)), ny^(t)−(n−ˆn)y^(t−1)−nyˆ ^∗i

−nhˆ ^′

2 kB^⊤w^∗− ∇φ(y^(t))k².

Since we have assumedDiag_I(G)≻2γρ(n−n)Diagˆ _I(Z^⊤Z), it holds that γρn(n−n)Eˆ h

kx^(t)−x^(t−1)k²_Diag

I(Z^⊤Z)

i

−n

2E[kx^(t)−x^(t−1)k²_Diag

I(G)]≤0.

Moreover, we have that

− hQ(y^(t)−y^(t−1)), ny^(t)−(n−n)yˆ ^(t−1)−nyˆ ^∗i

=−nky^(t)−y^(t−1)k²_Q+1

2{ky^(t)−y^(t−1)k²_Q+ky^(t−1)−y^∗k²_Q− ky^(t)−y^∗k²_Q}

=−

n−nˆ 2

ky^(t)−y^(t−1)k²_Q+nˆ

2ky^(t−1)−y^∗k²_Q−ˆn

2ky^(t)−y^∗k²_Q. Finally, we achieve

nE[F(x^(t), y^(t))−F(x^(t−1), y^(t−1))]

≤ˆn(F(x^∗, y^∗)−F(x^(t−1), y^(t−1))) + 1

2γρ

−kw^(t)−w^∗k²+kw^(t−1)−w^∗k²

−ρn(1−γ)

2 kZx^(t)+By^(t)k²+ρ(n−n)(1 +ˆ γ)

2 kZx^(t−1)+By^(t−1)k²

−Ehnv

2 kx^(t)−x^∗k²+n

2kx^(t)−x^∗k²_Hi +(n−n)vˆ

2 kx^(t−1)−x^∗k²+n

2kx^(t−1)−x^∗k²_H +γρn(n−n)Eˆ h

kx^(t)−x^(t−1)k²_Diag

I(Z^⊤Z)

i−n

2E[kx^(t)−x^(t−1)k²_Diag

I(G)]

−nρˆ

2 kZx^(t−1)+By^(t)k² + (γρn(n−ˆn)−(n−n)ρˆ

2 )kB(y^(t)−y^(t−1))k²

−

n−ˆn 2

ky^(t)−y^(t−1)k²_Q+nˆ

2ky^(t−1)−y^∗k²_Q−nˆ

2ky^(t)−y^∗k²_Q

−nhˆ ^′

2 kB^⊤w^∗− ∇φ(y^(t))k². (S-8)

Note that Eq. (S-8) holds for arbitraryy^∗∈ Y^∗. Step 3:(Deriving the assertion)

(i) Now, since we can take∇φ(y^(t)) =B^⊤w^(t−1)−ρ(Zx^(t−1)+By^(t))−Q(y^(t)−y^(t−1)), it holds that kB^⊤w^∗− ∇φ(y^(t))k²=kB^⊤(w^∗−w^(t−1))−ρ(Zx^(t−1)+By^(t))−Q(y^(t)−y^(t−1))k². SinceB^⊤is injective, this gives that

−h^′

2kB^⊤w^∗− ∇φ(y^(t))k²

≤ −h^′σmin(BB^⊤)kw^∗−w^(t−1)k²+ 2h^′ρ²kZx^(t−1)+By^(t)k²+ 2h^′kQ(y^(t)−y^(t−1))k²

≤ −h^′σmin(BB^⊤)kw^∗−w^(t−1)k²+ 2h^′ρ²kZx^(t−1)+By^(t)k²+ 2h^′σmax(Q)ky^(t)−y^(t−1)k²_Q. Now, dividing both sides bymax{1,4h^′ρ,4h^′σmax(Q)}(≥1), we have

−nhˆ ^′

2 kB^⊤w^∗− ∇φ(y^(t))k²

≤ − nhˆ ^′σmin(BB^⊤)

max{1,4h^′ρ,4h^′σmax(Q)}kw^∗−w^(t−1)k²+ˆnρ

2 kZx^(t−1)+By^(t)k²+nˆ

2ky^(t)−y^(t−1)k²_Q. (S-9) (ii) Next, it holds that, for someyb^∗∈ Y^∗,

1 2

F(x^∗, y^∗)−F(x^(t−1), y^(t−1))

≤ −v^′_φ

4 kPKer(B)(y^(t−1)−yb^∗)k². (S-10) On the other hand, for arbitrarya >0, it follows that

−ρ

8kZx^(t−1)+By^(t−1)k²

≤ −1

8(1−a)kZ(x^(t−1)−x^∗)k²−1

8(1−a⁻¹)kB(y^(t−1)−by^∗)k². Thus, settinga= 1 +_ρσmax^2v_(Z⊤Z), we have that

−ρ

8kZx^(t−1)+By^(t−1)k²

≤ρ 8

2v

ρσmax(Z^⊤Z)σmax(Z^⊤Z)kx^(t−1)−x^∗k²

−ρ 8

2vρ

ρσmax(Z^⊤Z) + 4vσmin(BB^⊤)kP_Ker(B)^⊥ (y^(t−1)−yb^∗)k²

=v

4kx^(t−1)−x^∗k²− vρσmin(BB^⊤)

4(ρσmax(Z^⊤Z) + 4v)kP_Ker(B)^⊥ (y^(t−1)−yb^∗)k². (S-11) Combining Eqs. (S-10), (S-11), we have that

ˆ n 2

F(x^∗, y^∗)−F(x^(t−1), y^(t−1))

−nρˆ

8nkZx^(t−1)+By^(t−1)k²

≤nvˆ

4 kx^(t−1)−x^∗k²−ˆn nmin

nv^′_φ, nρvσmin(BB^⊤) ρσmax(Z^⊤Z) + 4v

ky^(t−1)−by^∗k²_Q 4σmax(Q)

≤nvˆ

4 kx^(t−1)−x^∗k²−ˆn nmin

nv^′_φ, nρvσmin(BB^⊤) ρσmax(Z^⊤Z) + 4v

ky^(t−1)− Y^∗k²_Q

4σmax(Q) . (S-12)

(iii) By the assumptionDiag_I(G)≻2γρ(n−n)Diagˆ _I(Z^⊤Z), it holds that γρn(n−n)Eˆ h

kx^(t)−x^(t−1)k²_Diag

I(Z^⊤Z)

i−n

2E[kx^(t)−x^(t−1)k²_Diag

I(G)]≤0. (S-13) (iv) Therefore, ifγ= _4n¹ , applying Eq. (S-9), Eq. (S-12) and Eq. (S-13) to Eq. (S-8), for

ν =nˆ nmin

(1 4

v v+σmax(H)

, h^′ρσmin(BB^⊤)

2 max{1,4h^′ρ,4h^′σmax(Q)}, nv_φ^′/ˆn

4σmax(Q), nvσmin(BB^⊤)/nˆ 4σmax(Q)(ρσmax(Z^⊤Z) + 4v)

) ,

we have that

Eh

F(x^(t), y^(t))−F(x^∗, y^∗) + 1

2nγρkw^(t)−w^∗k² +ρ(1−γ)

2 kZx^(t)+By^(t)k²+1

2kx^(t)−x^∗k²_vIp+H+ nˆ

2nky^(t)−y^∗k²_Qi

≤(1−ν) (

F(x^(t−1), y^(t−1))−F(x^∗, y^∗) + 1

2nγρkw^(t−1)−w^∗k² +ρ(1−γ)

2 kZx^(t−1)+By^(t−1)k²+1

2kx^(t−1)−x^∗k²_vIp+H+ nˆ

2nky^(t−1)−y^∗k²_Q )

.

Settingµ:=nν/ˆn, this gives the assertion.

Lemma 3.

Eh

−ρhZ\ix^(t)_\i +By^(t), ZI(x^(t)_I −x^∗_I)i+ρ

2kZIx^∗_Ik²−ρ

2kZIx^(t)_I k²i

≤Eh

−ρ

nhZx^(t−1)+By^(t), Z(nx^(t)−(n−ˆn)x^(t−1)−x^∗)ii + ρ

2nkx^(t−1)−x^∗k²_Diag

I(Z^⊤Z)−ρ 2Eh

kx^(t)−x^(t−1)k²_Diag

I(Z^⊤Z)

i .

Proof.

ρhZ\Ix^(t−1)_\I , ZI(x^∗_I−x^(t)_I )i+ρhBy^(t), ZI(x^∗_I−x^(t)_I )i+ρ

2kZIx^∗_Ik²−ρ

2kZIx^(t)_I k²

=ρhZx^(t−1), ZI(x^∗_I−x^(t)_I )i+ρhBy^(t), ZI(x^∗_I−x^(t)_I )i+ρ

2kZIx^∗_Ik²−ρ

2kZIx^(t)_I k²

−ρhZIx^(t−1)_i , ZI(x^∗_I−x^(t)_I )i

=ρhZx^(t−1), ZI(x^∗_I−x^(t−1)_I +x^(t−1)_I −x^(t)_I )i+ρhBy^(t), ZI(x^∗_I −x^(t−1)_I +x^(t−1)_I −x^(t)_I )i +ρ

2kZIx^∗_Ik²−ρ

2kZIx^(t)_I k²−ρhZIx^(t−1)_I , ZI(x^∗_I−x^(t)_I )i

=ρhZx^(t−1)+By^(t), ZI(x^∗_I −x^(t−1)_I )i +ρ

2kZI(x^(t−1)_I −x^∗_I)k²−ρ

2kZI(x^(t)_I −x^(t−1)_I )k² +ρhZx^(t−1)+By^(t), Z(x^(t−1)−x^(t))i.