# A Stochastic Variance Reduction Algorithm with Bregman Distances for
Structured Composite Problems

Nguyen Van Dung1 and B$\grave{\text{\u{a}}}$ng Công Vũ2

1 Department of Mathematics, University of Transport and Communications,
3 Cau Giay Street, Hanoi, Vietnam
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We develop a novel stochastic primal dual splitting method with Bregman
distances for solving a structured composite problems involving infimal
convolutions in non-Euclidean spaces. The sublinear convergence in expectation
of the primal-dual gap is proved under mild conditions on stepsize for the
general case. The linear convergence rate is obtained under additional
condition like the strong convexity relative to Bregman functions.

Keywords: stochastic optimization, variance reduction, Bregman distance,
splitting, reflected method, duality, primal-dual algorithm, ergodic
convergence, linear convergence.

Mathematics Subject Classifications (2010): 49M29, 65K10, 65Y20, 90C25.

##  1 Introduction

The stochastic gradient method is one of the most popular algorithm in machine
learning. This method was introduced over 60 years ago. The main advantage of
this type of method is the low computational cost per iteration. However,
stochastic gradient algorithm converges slowly and achieves only the sublinear
convergence rates even when the underlying problem is strongly convex. To
accelerate the convergence of the stochastic gradient algorithms, one of the
popular approach is to use the variance reduction techniques. As a result,
various variance-reduced stochastic gradient algorithms have been proposed in
the literature; see [23, 39, 31, 40] and the references therein. Recently,
variance reduced methods are also investigated extensively for solving saddle
point problems [3, 19, 16, 24, 36]. In this paper, we focus on the following
stochastic optimization problem in non-Euclidean spaces.

###### Problem 1.1

Let $d$ and $p$ be strictly positive integer. Let $\mathcal{X}$ be
$(\mathbb{R}^{d},\|\cdot\|_{\mathcal{X}})$, let $\mathcal{Y}$ be
$(\mathbb{R}^{p},\|\cdot\|_{\mathcal{Y}})$. Let $f\in\Gamma_{0}(\mathcal{X})$,
$g\in\Gamma_{0}(\mathcal{Y})$ and $h\colon\mathcal{X}\to\mathbb{R}$;
$\ell\colon\mathcal{Y}^{*}\to\mathbb{R}$ be convex differentiable functions.
Let $K\colon\mathcal{X}\to\mathcal{Y}$ be a bounded linear operator. The
primal problem is to

$\displaystyle\underset{x\in\mathcal{X}}{\text{minimize}}\;h(x)+(\ell^{*}\mbox{\footnotesize$\square$}g)(Kx)+f(x),$
(1.1)

and the dual problem is to

$\displaystyle\underset{v\in\mathcal{Y}^{*}}{\text{minimize}}\;(h+f)^{*}(-K^{*}v)+g^{*}(v)+\ell(v),$
(1.2)

where $h$ and $\ell$ are given by finite sums. Here the symbol $\square$
denotes the infimal convolution:

$\ell^{*}\mbox{\footnotesize$\square$}g\colon
x\mapsto\inf_{y\in\mathcal{Y}}(\ell^{*}(y)+g(x-y)).$ (1.3)

This framework covers various problem formulations in image processing,
machine learning, statistical learning, game theory, reinforcement learning,
portfiolo optimization, [23, 39, 31, 40, 3, 19, 16, 24, 36, 13].

When $\mathcal{X}$ and $\mathcal{Y}$ are Euclidean spaces, this typical
primal-dual framework was first investigated in [13] and then in [38, 8, 4, 5,
35] for instances. In these works, various deterministic primal-dual splitting
methods were proposed where the proximity operators of $f$, $g$ are often used
in the backward steps, the gradient of $h$, $\ell^{*}$ and $K,K^{*}$ are often
used in the forward steps. In other words, they are full-splitting. The
stochastic counterparts of some primal-dual splitting methods were also
investigated in the literature; see [33, 21, 14, 34] for instances.

When $\mathcal{X}$ and $\mathcal{Y}$ are non-Euclidean spaces, finding the
closed-form expression of proximity operators is quite a challenge.
Alternatively, the notion of the Bregman proximity operator appeared naturally
and based on Bregman distance [7]. This concept plays an important role in
various field of applied mathematics and information theory. Numerical
optimization methods with Bregman proximity operator are investigated widely
in the literature; see [11, 2, 9, 17, 20, 26, 28, 30, 37, 22, 32] for
instances. In particular, the stochastic numerical methods with Bregman
distance for saddle point problems are of great interest; see [3, 30, 36, 12]
and the references therein.

The objective of this paper is to develop a new stochastic primal-dual
splitting method, for solving Problem 1.1, which incorporates the following
features: (i) Using the the Bregman proximity operators which allows us the
implement the proposed algorithm easily in non-Euclidan spaces; (ii) Using the
acceleration technique in term of variance reduced to obtain a faster
convergence rate; (iii) The proposed algorithm is full splitting. To the best
of our knowledge, there exists no method in the literature for solving Problem
1.1 with non-trivial $\ell$, which has simultaneously these features.

The paper is organized as follows. In Section 2, we recall the basic notions
in convex analysis and we precisely state our assumptions which will be used
in the proof of the convergence of the proposed method. Subsequently, in
Section 3, we present the proposed methods. Then, we derive the linear
convergence in expectation of the primal-dual gap for the strong convex case,
and the sublinear convergence for the general case.

Notations. Throughout this paper, we use the notation $\|\cdot\|$ for any norm
in the spaces $\mathcal{X},\mathcal{Y}$ as well as their dual spaces
$\mathcal{X}^{*},\mathcal{Y}^{*}$. The conjugate of the operator $K$ is
denoted by $K^{*}$. The interior and closure of a subset $X$ is denoted by
$\operatorname{int}(X)$ and $\overline{X}$, respectively. The domain of a
function $f\colon\mathcal{X}\to\left]0,+\infty\right]$ is
$\operatorname{dom}(f)=\big{\\{}{x\in\mathcal{X}}\;|\;{f(x)<+\infty}\big{\\}}$.
This function is proper if $\operatorname{dom}(f)\not={\varnothing}$. We
denote $\Gamma_{0}(\mathcal{X})$ the class of all proper lower semicontinous
functions $f$ from $\mathcal{X}$ to $\left]0,+\infty\right]$. Let $A$ be a
set-valued operator on $\mathcal{X}$, the inverse of $A$ is $A^{-1}\colon
x\mapsto\big{\\{}{u\in\mathcal{X}}\;|\;{x\in Au}\big{\\}}$. The expectation of
a random variable $x$ is denoted by $\mathsf{E}\left[x\right]$.

##  2 Preliminaries

###  2.1 Bregman distance

We first recall the following definitions.

###### Definition 2.1

[1, 2] Let $\phi\in\Gamma_{0}(\mathcal{X})$. Its conjutate is
$\phi^{*}\colon\mathcal{X}^{*}\to\,\left]-\infty,+\infty\right]\colon
x^{*}\mapsto\sup_{x\in\mathcal{X}}({\langle{{x},{x^{*}}}\rangle}-\phi(x))$ and
its Moreau subdifferential [29] is

$\partial\phi\colon\mathcal{X}\to 2^{\mathcal{X}^{*}}\colon
x\mapsto\big{\\{}{x^{*}\in\mathcal{X}^{*}}\;|\;{(\forall
y\in\mathcal{X})\,{\big{\langle}{{y-x},{x^{*}}}\big{\rangle}}+\phi(x)\leq\phi(y)}\big{\\}}.$
(2.1)

Recall that $\phi$ is a Legendre function if it is essentially smooth in the
sense that $\partial\phi$ is both locally bounded and single-valued on its
domain, and essentially strictly convex in the sense that $\partial\phi^{*}$
is locally bounded on its domain and $\phi$ is strictly convex on every convex
subset of $\operatorname{dom}\partial\phi$. Moreover, $\phi$ is Gâteaux
differentiable on $\operatorname{int}\operatorname{dom}\phi\neq{\varnothing}$
and the associated _Bregman distance_ is defined by

$\displaystyle D_{\phi}\colon\mathcal{X}\times\mathcal{X}$
$\displaystyle\to\,[0,+\infty]$ (2.2) $\displaystyle(x,y)$
$\displaystyle\mapsto\begin{cases}\phi(x)-\phi(y)-{\big{\langle}{{x-y},{\nabla\phi(y)}}\big{\rangle}},&\text{if}\;\;y\in\operatorname{int}\operatorname{dom}\phi;\\\
+\infty,&\text{otherwise},\end{cases}$

and the Bregman proximity operator of $g\in\Gamma_{0}(\mathcal{X})$ with
respect to $\phi$ is

$\operatorname{prox}_{g}^{\phi}\colon\mathcal{X}\to 2^{\mathcal{X}}\colon
x\mapsto\arg\min_{y\in\mathcal{X}}g(y)+D_{\phi}(y,x).$ (2.3)

Note that $\operatorname{prox}_{g}^{\phi}$ is well-defined and single valued,

$\operatorname{prox}_{g}^{\phi}=(\nabla\phi+\partial
g)^{-1}\circ\nabla\phi\colon\operatorname{int}\operatorname{dom}\phi\to\operatorname{int}\operatorname{dom}\phi.$

Let us recall the following lemma play a key role in the analysis of Bregman-
based methods.

###### Lemma 2.2

Let $x\in\mathcal{X}$ and let
$(z,p)\in(\operatorname{int}\operatorname{dom}\phi)^{2}$. The following hold.

  1. (i)

${\big{\langle}{{x-p},{\nabla\phi(z)-\nabla\phi(p)}}\big{\rangle}}=D(x,p)+D(p,z)-D(x,z)$.

  2. (ii)

${\big{\langle}{{z-p},{\nabla\phi(z)-\nabla\phi(p)}}\big{\rangle}}=D(z,p)+D(p,z)$.

  3. (iii)

Suppose that $p=\operatorname{prox}_{g}^{\phi}z$ and $g$ is $\alpha$-strongly
convex relative to $\phi$, then

$g(p)+D(p,z)\leq g(x)+D(x,z)-(1+\alpha)D(x,p).$ (2.4)

Proof. (i)&(ii): [2, Proposition 2.3].

(iii): By definition,

$\nabla\phi(z)-\nabla\phi(p)\in\partial g(p),$ (2.5)

and hence (2.1) yields

$\alpha
D(x,p)+g(p)+{\big{\langle}{{x-p},{\nabla\phi(z)-\nabla\phi(p)}}\big{\rangle}}\leq
g(x).$ (2.6)

Consequently, the assertion follows from (i).

###  2.2 Assumptions

We state several additional assumptions to Problem 1.1 which will be used in
the next section.

###### Assumption 2.3

There exists a point
$(x^{\star},v^{\star})\in\mathcal{X}\times\mathcal{Y}^{*}$ such that the
primal-dual gap function defined by

$\displaystyle G:$
$\displaystyle\mathcal{X}\times\mathcal{Y}^{*}\to\mathbb{R}\cup\\{-\infty,+\infty\\}$
$\displaystyle(x,v)\mapsto h(x)+f(x)+\langle Kx,v\rangle-g^{*}(v)-\ell(v)$
(2.7)

verifies the following condition:

$\displaystyle\big{(}\forall x\in\mathcal{X}\big{)}\big{(}\forall
v\in\mathcal{Y}^{*}\big{)}\;G(x^{\star},v)\leq G(x^{\star},v^{\star})\leq
G(x,v^{\star}),$ (2.8)

We denote $\mathcal{S}$ the set of all point $(x^{*},v^{*})$ such that (2.8)
is satisfied.

###### Assumption 2.4

The following conditions will be used.

  1. (B0)

$\varphi$ and $\psi$ are $1$-strong convex, Gâteaux differentiable on
$\operatorname{int}\operatorname{dom}\varphi\neq{\varnothing}$ and
$\operatorname{int}\operatorname{dom}\psi\neq{\varnothing}$, , _Legendre
functions_ on $\mathcal{X}$ and $\mathcal{Y}^{*}$, respectively. Moreover,
$\operatorname{dom}(f)\subset\operatorname{int}\operatorname{dom}(\varphi)$
and
$\operatorname{dom}(g^{*})\subset\operatorname{int}\operatorname{dom}(\psi)$.

  2. (B1)

$h=\dfrac{1}{n}\sum\limits_{i=1}^{n}h_{i}$ and
$\ell=\dfrac{1}{n^{\prime}}\sum\limits_{i=1}^{n^{\prime}}\ell_{i}$, where
$h_{i}$ and $\ell_{i}$ are differentiable with $\mu_{i}$ and
$\nu_{i}$-Lipschitz continuous, respectively:

$\|\nabla h_{i}(x)-\nabla
h_{i}(y)\|\leq\mu_{i}\|x-y\|\;\text{and}\;\|\nabla\ell_{i}(u)-\nabla\ell_{i}(v)\|\leq\nu_{i}\|u-v\|.$

Hence,

$\|\nabla h(x)-\nabla h(y)\|\leq\mu\|x-y\|,\text{ where
$\mu=(1/n)\sum\limits_{i=1}^{n}\mu_{i},$}$

and

$\|\nabla\ell(u)-\nabla\ell(v)\|\leq\nu\|u-v\|,\;\text{where
$\nu=(1/n^{\prime})\sum\limits_{j=1}^{n^{\prime}}\nu_{j}$.}$

###### Assumption 2.5

The functions $f$ and $g^{*}$ are $\alpha$-strongly convex relative to
$\varphi$ and $\psi$, respectively, i.e.,

$\begin{cases}(\forall x,\ y\in\operatorname{int}\operatorname{dom}(\varphi))\
(\forall p\in\partial f(y))\;f(x)\geq f(y)+{\langle{{p},{x-y}}\rangle}+\alpha
D_{\varphi}(x,y),\\\ (\forall u,\
v\in\operatorname{int}\operatorname{dom}(\psi))\ (\forall q\in\partial
g^{*}(v))\ g^{*}(u)\geq g^{*}(v)+{\langle{{q},{u-v}}\rangle}+\alpha
D_{\psi}(u,v).\end{cases}$ (2.9)

###### Remark 2.6

Assumption 2.3 and Assumption 2.4 are very popular in the literature. While,
many of functions, for which Assumption 2.5 can be verified, can be found in
[20, 36, 22].

##  3 Main results

We propose the following primal dual splitting method for solving Problem 1.1
which incorporates the variance reduction technique as the Bregman proximity
operators at each iteration.

###### Algorithm 3.1

Let
$(\bar{x}_{0},\bar{v}_{0})\in\operatorname{int}(\operatorname{dom}(\varphi))\times\operatorname{int}(\operatorname{dom}(\psi))$,
let $\gamma>0,\ \theta\in\\{0;1\\}$ and $m$ is a strictly positive integer.
Let $(\omega_{k})_{k\in\mathbb{N}}$ be a strictly positive sequence in
$\mathbb{R}$. Let $Q=\\{q_{1},\ldots,q_{n}\\}$ and
$Q^{\prime}=\\{q^{\prime}_{1},\ldots,q^{\prime}_{n^{\prime}}\\}$ be the
probabilites on $\\{1,\ldots,n\\}$ and $\\{1,\ldots,n^{\prime}\\}$,
respectively.
Set $x^{0}_{0}=x^{0}_{-1}=\bar{x}_{0},\ v^{0}_{0}=v^{0}_{-1}=\bar{v}_{0}.$
Iterate: for $s=0,1,2,\ldots$

$\displaystyle\bar{x}=\bar{x}_{s},\bar{v}=\bar{v}_{s}$ $\displaystyle
x_{0}=x_{0}^{s},\ x_{-1}=x_{-1}^{s}$ $\displaystyle v_{0}=v_{0}^{s},\
v_{-1}=v_{-1}^{s}$ $\displaystyle{\bf iterate:}\ \text{for}\ k=0,1,\ldots,m-1$
$\displaystyle\hskip 28.45274pt\text{pick}\ i_{k}\in\\{1,\ldots,n\\}\
\text{and}\ \ j_{k}\in\\{1,\ldots,n^{\prime}\\}\ \text{randomly according to
$Q$ and $Q^{\prime}$, respectively}$ $\displaystyle\hskip
28.45274pt\begin{cases}y_{k}&=x_{k}+\theta(x_{k}-x_{k-1})\\\
z_{k}&=\dfrac{\nabla h_{i_{k}}(y_{k})-\nabla
h_{i_{k}}(\bar{x})}{q_{i_{k}}n}+\nabla h(\bar{x})\\\
u_{k}&=v_{k}+\theta(v_{k}-v_{k-1})\\\
t_{k}&=\dfrac{\nabla\ell_{j_{k}}(u_{k})-\nabla\ell_{j_{k}}(\bar{v})}{q^{\prime}_{j_{k}}n^{\prime}}+\nabla\ell(\bar{v})\\\
x_{k+1}&=(\nabla\varphi+\gamma\partial f)^{-1}(\nabla\varphi(x_{k})-\gamma
z_{k}-\gamma K^{*}u_{k})\\\ v_{k+1}&=(\nabla\psi+\gamma\partial
g^{*})^{-1}(\nabla\psi(v_{k})-\gamma t_{k}+\gamma Ky_{k}),\end{cases}$ end
$\displaystyle\text{set}\
\bar{x}_{s+1}=\sum_{k=1}^{m}\omega_{k}x_{k}\;\text{and}\;\bar{v}_{s+1}=\sum_{k=1}^{m}\omega_{k}v_{k}.$
$\displaystyle x^{s+1}_{0}=x_{m},\ x^{s+1}_{-1}=x_{m-1},\ v^{s+1}_{0}=v_{m},\
v^{s+1}_{-1}=v_{m-1}.$

end

###### Remark 3.2

Here are some remarks.

  1. (i)

Algorithm 3.1 is an extension of the one in [21] which is restricted to
Hilbert spaces setting with the Euclidean norm and $\theta=1$ and without
variance reduction. Further connections to existing work [15] can be found in
[21]. In particular, we use the variance reduction technique as in [39, 36].
When $\theta\not=0$, the proposed algorithm is different from the inertial
stochastic primal-dual splitting method in [33].

  2. (ii)

Recently, there appeared several stochastic variance reduction algorithms in
[3, 30, 36, 12] which can be used to solve Problem 1.1. However, the resulting
algorithms are not full-splitting and they are different from our proposed
algorithm here.

Before stating our main convergence results of Algorithm 3.1, we first prove
several auxiliary results which are natural extension of [39, Lemma 1,
Corollary 3] from primal framework to our primal-dual framework.

###### Lemma 3.3

Suppose the Assumption 2.4 $(B1)$ and Assumption 2.3 are satisfied. Then, for
all $(x,v)\in\operatorname{dom}(f)\times\operatorname{dom}(g^{*})$ and for all
$(x^{*},v^{*})\in\mathcal{S}$, we have

$\dfrac{1}{n}\sum\limits_{i=1}^{n}\dfrac{1}{nq_{i}}\|\nabla h_{i}(x)-\nabla
h_{i}(x^{\star})\|^{2}\leq 2L_{Q}[G(x,v^{\star})-G(x^{\star},v^{\star})],$
(3.1)

and

$\dfrac{1}{n^{\prime}}\sum\limits_{j=1}^{n^{\prime}}\dfrac{1}{n^{\prime}q^{\prime}_{j}}\|\nabla\ell_{j}(v)-\nabla\ell_{j}(v^{\star})\|^{2}\leq
2L_{Q^{\prime}}[G(x^{\star},v^{\star})-G(x^{\star},v)],$ (3.2)

where $L_{Q}=\max_{i}\mu_{i}/(q_{i}n),\
L_{Q^{\prime}}=\max_{j}\nu_{j}/(q_{j}^{\prime}n^{\prime}).$

Proof. It follows from [36, Lemma 2] that

$\dfrac{1}{n}\sum\limits_{i=1}^{n}\dfrac{1}{nq_{i}}\|\nabla h_{i}(x)-\nabla
h_{i}(x^{\star})\|^{2}\leq
2L_{Q}[h(x)-h(x^{\star})-{\langle{{x-x^{\star}},{\nabla
h(x^{\star})}}\rangle}.$

Since $(x^{*},v^{*})\in\mathcal{S}$, we have

$x^{\star}=\underset{x}{\operatorname{argmin}}\
G(x,v^{\star})=\underset{x}{\operatorname{argmin}}\ \\{h(x)+R(x)\\},$

where
$R(x)=f(x)+{\langle{{Kx},{v^{\star}}}\rangle}-g^{*}(v^{\star})-\ell(v^{\star}).$
By the optimality of $x^{\star}$, there exists $\xi^{\star}\in\partial
R(x^{\star})$ such that $\nabla h(x^{\star})+\xi^{\star}=0.$ Therefore

$\displaystyle h(x)-h(x^{\star})-{\langle{{x-x^{\star}},{\nabla
h(x^{\star})}}\rangle}$
$\displaystyle=h(x)-h(x^{\star})+{\langle{{x-x^{\star}},{\xi^{\star}}}\rangle}$
$\displaystyle\leq h(x)-h(x^{\star})+R(x)-R(x^{\star})$
$\displaystyle=G(x,v^{\star})-G(x^{\star},v^{\star}),$

where the second inequality follows from the convexity of $R$. Hence, (3.1) is
proved. The estimation (3.2) is proved by the same fashion.

###### Corollary 3.4

Under the same assumptions as in Lemma 3.3. Let
$(x_{k})_{k\in\mathbb{N}},(y_{k})_{k\in\mathbb{N}},$
$(u_{k})_{k\in\mathbb{N}},(v_{k})_{k\in\mathbb{N}}$,
$(z_{k})_{k\in\mathbb{N}}$ $(t_{k})_{k\in\mathbb{N}}$ be sequences generated
by Algorithm 3.1. Let $\mathsf{E}_{i_{k}}$ and $\mathsf{E}_{j_{k}}$ be the
conditional expectation with respect to the history
$\\{(i_{0},j_{0}),\ldots,(i_{k-1},j_{k-1})\\}$. Then, we have

$(\forall k\in\mathbb{N})\;\mathsf{E}_{i_{k}}\left[z_{k}\right]=\nabla
h(y_{k})\quad\text{and}\quad\mathsf{E}_{j_{k}}\left[t_{k}\right]=\nabla\ell(u_{k}).$
(3.3)

Moreover, set $L_{1}=\max\\{L_{Q},\ L_{Q^{\prime}}\\},\
L_{2}=\max\\{\mu_{i}^{2}/(q_{i}n),\
\nu_{j}^{2}/(q_{j}^{\prime}n^{\prime})\\}$. If $\theta=0$ then

$\begin{cases}\mathsf{E}_{i_{k}}\|z_{k}-\nabla h(y_{k})\|^{2}&\leq
4L_{1}\big{(}[G(x_{k},v^{\star})-G(x^{\star},v^{\star})]+G(\bar{x},v^{\star})-G(x^{\star},v^{\star})\big{)}\\\
\mathsf{E}_{j_{k}}\|t_{k}-\nabla\ell(u_{k})\|^{2}&\leq
4L_{1}\big{(}[G(x^{\star},v^{\star})-G(x^{\star},v_{k})]+G(x^{\star},v^{\star})-G(x^{\star},\bar{v})\big{)}.\end{cases}$
(3.4)

If $\theta=1$ then

$\begin{cases}\mathsf{E}_{i_{k}}\|z_{k}-\nabla h(y_{k})\|^{2}&\leq
4L_{2}\|x_{k}-x_{k-1}\|^{2}+8L_{1}[G(x_{k},v^{\star})-G(x^{\star},v^{\star})]\\\
&\ \ +4L_{1}[G(\bar{x},v^{\star})-G(x^{\star},v^{\star}))\\\
\mathsf{E}_{j_{k}}\|t_{k}-\nabla\ell(u_{k})\|^{2}&\leq
4L_{2}\|v_{k}-v_{k-1}\|^{2}+8L_{1}[G(x^{\star},v^{\star})-G(x^{\star},v_{k})]\\\
&\ \ +4L_{1}[G(x^{\star},v^{\star})-G(x^{\star},\bar{v})).\end{cases}$ (3.5)

Proof. We take expectation with respect to $i_{k}$ to obtain

$\mathsf{E}_{i_{k}}\big{[}\dfrac{1}{nq_{i_{k}}}\nabla
h_{i_{k}}(y_{k})\big{]}=\sum_{i=1}^{n}\dfrac{q_{i}}{nq_{i}}\nabla
h_{i}(y_{k})=\sum_{i=1}^{n}\dfrac{1}{n}\nabla h_{i}(y_{k})=\nabla h(y_{k}).$

Similarly, we have $\mathsf{E}_{i_{k}}[(1/(nq_{i_{k}}))\nabla
h_{i_{k}}(\bar{x})]=\nabla h(\bar{x})$. Therefore

$\mathsf{E}_{i_{k}}\left[z_{k}\right]=\mathsf{E}_{i_{k}}\big{[}\dfrac{\nabla
h_{i_{k}}(y_{k})-\nabla h_{i_{k}}(\bar{x})}{q_{i_{k}}n}+\nabla
h(\bar{x})\big{]}=\nabla h(y_{k}).$

Using the same argument, we also obtain
$\mathsf{E}_{j_{k}}\left[t_{k}\right]=\nabla\ell(u_{k}).$ Hence, (3.3) is
proved. We next bound the variance, we have

$\displaystyle\mathsf{E}_{i_{k}}\left[\|z_{k}-\nabla h(y_{k})\|^{2}\right]$
$\displaystyle=\mathsf{E}_{i_{k}}\left[\big{\|}\dfrac{1}{nq_{i_{k}}}\big{(}\nabla
h_{i_{k}}(y_{k})-\nabla h_{i_{k}}(\bar{x})\big{)}+\nabla h(\bar{x})-\nabla
h(y_{k})\big{\|}^{2}\right]$
$\displaystyle=\mathsf{E}_{i_{k}}\left[\dfrac{1}{(nq_{i_{k}})^{2}}\|\nabla
h_{i_{k}}(y_{k})-\nabla h_{i_{k}}(\bar{x})\|^{2}-\|\nabla h(y_{k})-\nabla
h(\bar{x})\|^{2}\right]$
$\displaystyle\leq\mathsf{E}_{i_{k}}\left[\dfrac{1}{(nq_{i_{k}})^{2}}\|\nabla
h_{i_{k}}(y_{k})-\nabla h_{i_{k}}(\bar{x})\|^{2}\right]$
$\displaystyle=\dfrac{1}{n}\sum_{i=1}^{n}\dfrac{1}{nq_{i}}\|\nabla
h_{i}(y_{k})-\nabla h_{i}(\bar{x})\|^{2}$
$\displaystyle\leq\dfrac{2}{n}\sum_{i=1}^{n}\dfrac{1}{nq_{i}}\big{(}\|\nabla
h_{i}(y_{k})-\nabla h_{i}(x^{\star})\|^{2}+\|\nabla h_{i}(\bar{x})-\nabla
h_{i}(x^{\star})\|^{2}\big{)}.$

If $\theta=0$ then $y_{k}=x_{k}$. Using Lemma 3.3, we derive that

$\displaystyle\mathsf{E}_{i_{k}}\left[\|z_{k}-\nabla h(y_{k})\|^{2}\right]$
$\displaystyle\leq\dfrac{2}{n}\sum_{i=1}^{n}\dfrac{1}{nq_{i}}\big{(}\|\nabla
h_{i}(x_{k})-\nabla h_{i}(x^{\star})\|^{2}+\|\nabla h_{i}(\bar{x})-\nabla
h_{i}(x^{\star})\|^{2}\big{)}$ $\displaystyle\leq
4L_{1}\big{(}[G(x_{k},v^{\star})-G(x^{\star},v^{\star})]+G(\bar{x},v^{\star})-G(x^{\star},v^{\star})\big{)}.$

By the same manner, we also have

$\mathsf{E}_{j_{k}}\|t_{k}-\nabla\ell(u_{k})\|^{2}\leq
4L_{1}\big{(}[G(x^{\star},v^{\star})-G(x^{\star},v_{k})]+G(x^{\star},v^{\star})-G(x^{\star},\bar{v})\big{)}.$

Therefore, (3.4) is proved. Now, let us consider the case $\theta=1$. We have

$\displaystyle\mathsf{E}_{i_{k}}\left[\|z_{k}-\nabla h(y_{k})\|^{2}\right]$
$\displaystyle\leq\dfrac{4}{n}\sum_{i=1}^{n}\dfrac{1}{nq_{i}}\big{(}\|\nabla
h_{i}(y_{k})-\nabla h_{i}(x_{k})\|^{2}+\|\nabla h_{i}(x_{k})-\nabla
h_{i}(x^{\star})\|^{2}\big{)}$ $\displaystyle\
+\dfrac{2}{n}\sum_{i=1}^{n}\dfrac{1}{nq_{i}}\|\nabla h_{i}(\bar{x})-\nabla
h_{i}(x^{\star})\|^{2}$
$\displaystyle\leq\dfrac{4}{n}\sum_{i=1}^{n}\dfrac{\mu_{i}^{2}}{nq_{i}}\|x_{k}-x_{k-1}\|^{2}+8L_{Q}[G(x_{k},v^{\star})-G(x^{\star},v^{\star})]$
$\displaystyle\ \ +4L_{Q}[G(\bar{x},v^{\star})-G(x^{\star},v^{\star})]$
$\displaystyle\leq
4L_{2}\|x_{k}-x_{k-1}\|^{2}+8L_{1}[G(x_{k},v^{\star})-G(x^{\star},v^{\star})]$
$\displaystyle\ \ +4L_{1}[G(\bar{x},v^{\star})-G(x^{\star},v^{\star})].$

Similarly, we also have

$\mathsf{E}_{j_{k}}\left[\|t_{k}-\nabla\ell(u_{k})\|^{2}\right]\leq
4L_{2}\|v_{k}-v_{k-1}\|^{2}+8L_{1}[G(x^{\star},v^{\star})-G(x^{\star},v_{k})]+4L_{1}[G(x^{\star},v^{\star})-G(x^{\star},\bar{v})).$

Hence, the proof is completed.

###### Lemma 3.5

Suppose that Assumption 2.4 is satisfied. Let
$(x_{k})_{k\in\mathbb{N}},(y_{k})_{k\in\mathbb{N}},$
$(u_{k})_{k\in\mathbb{N}},(v_{k})_{k\in\mathbb{N}}$,
$(z_{k})_{k\in\mathbb{N}}$ $(t_{k})_{k\in\mathbb{N}}$ be sequences generated
by Algorithm 3.1 at the stage $s$. Let
$\mathsf{x}^{*}=(x^{*},v^{*})\in\mathcal{S}$. Define

$\big{(}\forall k\in\\{0,\ldots
m\\}\big{)}\begin{cases}\mathsf{x}_{k}&=(x_{k},v_{k}),\mathsf{y}_{k}=(y_{k},u_{k}),\;\hat{\mathsf{x}}_{k}=(\hat{x}_{k},\hat{v}_{k}),\\\
r_{k}&=(z_{k},t_{k}),\\\ \mathsf{R}_{k}&=(\nabla
h(y_{k}),\nabla\ell(u_{k})),\\\
L\colon&\mathcal{X}\times\mathcal{Y}^{*}\to\mathcal{X}^{*}\times\mathcal{Y}\colon(x,v)\mapsto(K^{*}v,-Kx),\\\
\varphi\oplus\psi\colon&(x,v)\mapsto\varphi(x)+\psi(v),\\\
b_{k}&={\langle{{L(\mathsf{x}_{k}-\mathsf{x}_{k-1})},{\mathsf{x}_{k}-\mathsf{x}^{\star}}}\rangle}.\end{cases}$
(3.6)

Set $\mu_{0}=\max\ \\{\mu,\nu\\}$ and $D=D_{\varphi\oplus\psi}.$ The following
hold for any strictly positive $M$:

  1. (i)

If $\theta=0$, then

$\displaystyle G(x_{k+1},v^{*})-G(x^{*},v_{k+1})$ $\displaystyle\leq
2\|K\|\big{(}MD(\mathsf{x}_{k+1},\mathsf{x}_{k})+\dfrac{D(\mathsf{x}^{*},\mathsf{x}_{k+1})}{M}\big{)}-\alpha
D(\mathsf{x}^{*},\mathsf{x}_{k+1})$ $\displaystyle\
+\dfrac{1}{\gamma}\big{(}D(\mathsf{x}^{*},\mathsf{x}_{k})-D(\mathsf{x}^{*},\mathsf{x}_{k+1})-D(\mathsf{x}_{k+1},\mathsf{x}_{k})\big{)}$
$\displaystyle\
+\mu_{0}D(\mathsf{x}_{k+1},\mathsf{x}_{k})+\gamma\|r_{k}-\mathsf{R}_{k}\|^{2}+{\langle{{\hat{}\mathsf{x}_{k+1}-\mathsf{x}^{*}},{\mathsf{R}_{k}-r_{k}}}\rangle}.$
(3.7)

  2. (ii)

If $\theta=1$, then

$\displaystyle\gamma[G(x_{k+1},v^{\star})-G(x^{\star},v_{k+1})]$
$\displaystyle\leq D(\mathsf{x}^{\star},\mathsf{x}_{k})-\gamma
b_{k}-D(\mathsf{x}^{\star},\mathsf{x}_{k+1})+\gamma b_{k+1}$
$\displaystyle-(1-2\gamma\mu_{0}-\gamma\|K\|)D(\mathsf{x}_{k+1},\mathsf{x}_{k})$
$\displaystyle+(2\gamma\mu_{0}+\gamma\|K\|)D(\mathsf{x}_{k},\mathsf{x}_{k-1})$
$\displaystyle+\gamma^{2}\|r_{k}-\mathsf{R}_{k}\|^{2}+\gamma{\langle{{\hat{}\mathsf{x}_{k+1}-\mathsf{x}},{\mathsf{R}_{k}-r_{k}}}\rangle}.$
(3.8)

Proof. Let $k\in\\{0,\ldots,m-1\\}$. We have
$v_{k+1}=(\nabla\psi+\gamma\partial g^{*})^{-1}(\nabla\psi(v_{k})-\gamma
t_{k}+\gamma Ky_{k})$, which is equivalent to

$Ky_{k}-t_{k}+\dfrac{1}{\gamma}(\nabla\psi(v_{k})-\nabla\psi(v_{k+1}))\in\partial
g^{*}(v_{k+1}).$

Since $g^{*}$ is $\alpha$-strongly convex relative to $\psi$, which implies
that

$g^{*}(v)\geq
g^{*}(v_{k+1})+{\langle{{Ky_{k}-t_{k}+\dfrac{1}{\gamma}(\nabla\psi(v_{k})-\nabla\psi(v_{k+1}))},{v-v_{k+1}}}\rangle}+\alpha
D_{\psi}(v,v_{k+1}).$

Using Lemma 2.2 (i), we have

$\displaystyle g^{*}(v_{k+1})-g^{*}(v)$
$\displaystyle\leq{\langle{{t_{k}-Ky_{k}},{v-v_{k+1}}}\rangle}+\dfrac{1}{\gamma}{\langle{{\nabla\psi(v_{k})-\nabla\psi(v_{k+1})},{v_{k+1}-v}}\rangle}-\alpha
D_{\psi}(v,v_{k+1})$
$\displaystyle={\langle{{t_{k}-Ky_{k}},{v-v_{k+1}}}\rangle}+\dfrac{1}{\gamma}(D_{\psi}(v,v_{k})-D_{\psi}(v_{k+1},v_{k})-D_{\psi}(v,v_{k+1}))$
$\displaystyle\quad-\alpha D_{\psi}(v,v_{k+1}).$ (3.9)

Since $\ell$ is convex differentiable with $\nu$-Lipschitz gradient, we have

$\ell(v_{k+1})-\ell(v)\leq{\langle{{v_{k+1}-v},{\nabla\ell(u_{k})}}\rangle}+\dfrac{\nu}{2}\|v_{k+1}-u_{k}\|^{2}.$
(3.10)

We derive from (3.9) and (3.10) that

$\displaystyle G(x_{k+1},v)-$ $\displaystyle
G(x_{k+1},v_{k+1})={\langle{{Kx_{k+1}},{v-v_{k+1}}}\rangle}-g^{*}(v)+g^{*}(v_{k+1})-\ell(v)+\ell(v_{k+1})$
$\displaystyle\leq{\langle{{K(x_{k+1}-y_{k})},{v-v_{k+1}}}\rangle}+\dfrac{1}{\gamma}(D_{\psi}(v,v_{k})-D_{\psi}(v_{k+1},v_{k})-D_{\psi}(v,v_{k+1}))$
$\displaystyle\ \
+\frac{\nu}{2}\|v_{k+1}-u_{k}\|^{2}+{\langle{{\nabla\ell(u_{k})-t_{k}},{v_{k+1}-v}}\rangle}-\alpha
D_{\psi}(v,v_{k+1}).$ (3.11)

Similar to (3.11), we have,

$\displaystyle G(x_{k+1},v_{k+1})-$ $\displaystyle
G(x,v_{k+1})=h(x_{k+1})-h(x)+{\langle{{K(x_{k+1}-x)},{v_{k+1}}}\rangle}+f(x_{k+1})-f(x)$
$\displaystyle\leq{\langle{{K(x_{k+1}-x)},{v_{k+1}-u_{k}}}\rangle}+\frac{1}{\gamma}(D_{\varphi}(x,x_{k})-D_{\varphi}(x_{k+1},x_{k})-D_{\varphi}(x,x_{k+1}))$
$\displaystyle\ \
+\dfrac{\mu}{2}\|x_{k+1}-y_{k}\|^{2}+{\langle{{x_{k+1}-x},{\nabla
h(y_{k})-z_{k}}}\rangle}-\alpha D_{\varphi}(x,x_{k+1}).$ (3.12)

Adding (3.11) and (3.12), we obtain

$\displaystyle
G(x_{k+1},v)-G(x,v_{k+1})\leq\big{(}{\langle{{K(x_{k+1}-x)},{v_{k+1}-u_{k}}}\rangle}+{\langle{{K(x_{k+1}-y_{k})},{v-v_{k+1}}}\rangle}\big{)}$
$\displaystyle\
+\dfrac{1}{\gamma}\bigg{(}D_{\varphi}(x,x_{k})-D_{\varphi}(x_{k+1},x_{k})-D_{\varphi}(x,x_{k+1})+D_{\psi}(v,v_{k})-D_{\psi}(v_{k+1},v_{k})-D_{\psi}(v,v_{k+1})\bigg{)}$
$\displaystyle\
+\dfrac{\mu}{2}\|x_{k+1}-y_{k}\|^{2}+\dfrac{\nu}{2}\|v_{k+1}-u_{k}\|^{2}+{\langle{{x_{k+1}-x},{\nabla
h(y_{k})-z_{k}}}\rangle}+{\langle{{\nabla\ell(u_{k})-t_{k}},{v_{k+1}-v}}\rangle}$
$\displaystyle-\alpha D_{\varphi}(x,x_{k+1})-\alpha D_{\psi}(v,v_{k+1}).$
(3.13)

Let us set

$\begin{cases}\hat{x}_{k+1}&=(\nabla\varphi+\gamma\partial
f)^{-1}(\nabla\varphi(x_{k})-\gamma\nabla h(y_{k})-\gamma K^{*}u_{k}),\\\
\hat{v}_{k+1}&=(\nabla\psi+\gamma\partial
g^{*})^{-1}(\nabla\psi(v_{k})-\gamma\nabla\ell(u_{k})+\gamma
Ky_{k}).\end{cases}$ (3.14)

Then, the first equation in (3.14) is equivalent to

$\nabla\varphi(x_{k})-\gamma\nabla h(y_{k})-\gamma K^{*}u_{k}\in\gamma\partial
f(\hat{x}_{k+1})+\nabla\varphi(\hat{x}_{k+1}).$ (3.15)

Since $\varphi$ is $1$-strongly convex, $\gamma\partial f+\nabla\varphi$ is
$1$-strongly monotone. Hence, it follows from (3.15) that

$\displaystyle\|\hat{x}_{k+1}-x_{k+1}\|^{2}$
$\displaystyle\leq{\langle{{\hat{x}_{k+1}-x_{k+1}},{\nabla\varphi(x_{k})-\gamma\nabla
h(y_{k})-\gamma K^{*}u_{k}+\gamma z_{k}+\gamma
K^{*}u_{k}-\nabla\varphi(x_{k})}}\rangle}$
$\displaystyle=\gamma{\langle{{\hat{x}_{k+1}-x_{k+1}},{\nabla
h(y_{k})-z_{k}}}\rangle},$ (3.16)

which implies that

$\|\hat{x}_{k+1}-x_{k+1}\|\leq\gamma\|z_{k}-\nabla h(y_{k})\|.$ (3.17)

In turn,

$\displaystyle{\langle{{x_{k+1}-x},{\nabla h(y_{k})-z_{k}}}\rangle}$
$\displaystyle\quad={\langle{{x_{k+1}-\hat{x}_{k+1}},{\nabla
h(y_{k})-z_{k}}}\rangle}+\left\langle{\hat{x}_{k+1}-x}\mid{\nabla
h(y_{k})-z_{k}}\right\rangle$ $\displaystyle\ \ \ \leq\|z_{k}-\nabla
h(y_{k})\|\|x_{k+1}-\hat{x}_{k+1}\|+{\langle{{\hat{x}_{k+1}-x},{\nabla
h(y_{k})-z_{k}}}\rangle}$ $\displaystyle\ \ \ \leq\gamma\|z_{k}-\nabla
h(y_{k})\|^{2}+{\langle{{\hat{x}_{k+1}-x},{\nabla h(y_{k})-z_{k}}}\rangle}.$
(3.18)

By the same way,

$\displaystyle{\langle{{\nabla\ell(u_{k})-t_{k}},{v_{k+1}-v}}\rangle}\leq\gamma\|t_{k}-\nabla\ell(u_{k})\|^{2}+{\langle{{\nabla\ell(u_{k})-t_{k}},{\hat{v}_{k+1}-v}}\rangle}.$
(3.19)

Let us define $\mathcal{X}\times\mathcal{Y}^{*}$ the standard product space
equipped with the norm $(x,v)\mapsto\sqrt{\|x\|^{2}+\|v\|^{2}}$. Then
$\|L\|=\|K\|$ and
$\nabla(\varphi\oplus\psi)(x,v)=(\nabla\varphi(x),\nabla\varphi(v))$. Hence,
for every $(x,v)$ and $(y,w)$ in $\mathcal{X}\times\mathcal{Y}^{*}$,

$\displaystyle D_{\varphi}(x,y)+D_{\psi}(v,w)$
$\displaystyle=\varphi(x)+\psi(v)-(\varphi(y)+\psi(w))-({\langle{{x-y},{\nabla\varphi(x)}}\rangle}+{\langle{{v-w},{\nabla\psi(w)}}\rangle})$
$\displaystyle=\varphi\oplus\psi(x,v)+\varphi\oplus\psi(y,w)-{\langle{{(x,v)-(y,w)},{\nabla(\varphi\oplus\psi)(x,v)}}\rangle}$
$\displaystyle=D((x,v),(y,w)).$ (3.20)

In turn, the term in the second line in (3.13) can be rewritten as

$\displaystyle\dfrac{1}{\gamma}\big{(}D_{\varphi}(x,x_{k})-D_{\varphi}(x_{k+1},x_{k})-$
$\displaystyle
D_{\varphi}(x,x_{k+1})+D_{\psi}(v,v_{k})-D_{\psi}(v_{k+1},v_{k})-D_{\psi}(v,v_{k+1})\big{)}$
$\displaystyle=\dfrac{1}{\gamma}\big{(}D_{\varphi\oplus\psi}(\mathsf{x},\mathsf{x}_{k})-D_{\varphi\oplus\psi}(\mathsf{x},\mathsf{x}_{k+1})-D_{\varphi\oplus\psi}(\mathsf{x}_{k+1},\mathsf{x}_{k})\big{)}$
$\displaystyle=\dfrac{1}{\gamma}\big{(}D(\mathsf{x},\mathsf{x}_{k})-D(\mathsf{x},\mathsf{x}_{k+1})-D(\mathsf{x}_{k+1},\mathsf{x}_{k})\big{)}.$
(3.21)

(i). Let us consider the case when $\theta=0$. we can rewrite (3.13):

$\displaystyle G(x_{k+1},v)-G(x,v_{k+1})$
$\displaystyle\leq\big{(}{\langle{{K(x_{k+1}-x)},{v_{k+1}-v_{k}}}\rangle}+{\langle{{K(x_{k+1}-x_{k})},{v-v_{k+1}}}\rangle}\big{)}$
$\displaystyle\
+\dfrac{1}{\gamma}\bigg{(}D(\mathsf{x},\mathsf{x}_{k})-D(\mathsf{x}_{k+1},\mathsf{x}_{k})-D(\mathsf{x},\mathsf{x}_{k+1})\bigg{)}$
$\displaystyle\
+\dfrac{\mu}{2}\|x_{k+1}-x_{k}\|^{2}+\dfrac{\nu}{2}\|v_{k+1}-v_{k}\|^{2}-\alpha
D(\mathsf{x},\mathsf{x}_{k+1})$ $\displaystyle+{\langle{{x_{k+1}-x},{\nabla
h(x_{k})-z_{k}}}\rangle}+{\langle{{\nabla\ell(v_{k})-t_{k}},{v_{k+1}-v}}\rangle}.$
(3.22)

The term in the first and the third line in (3.22) can be estimated:

$\displaystyle{\langle{{K(x_{k+1}-x_{k})},{v-v_{k+1}}}\rangle}$
$\displaystyle+{\langle{{K(x_{k+1}-x)},{v_{k+1}-v_{k}}}\rangle}$
$\displaystyle\leq\|K\|\bigg{(}M\|\mathsf{x}_{k+1}-\mathsf{x}_{k}\|^{2}+\dfrac{\|\mathsf{x}_{k+1}-\mathsf{x}\|^{2}}{M}\bigg{)}$
$\displaystyle\leq
2\|K\|\big{(}MD(\mathsf{x}_{k+1},\mathsf{x}_{k})+\dfrac{D(\mathsf{x},\mathsf{x}_{k+1})}{M}\big{)}.$
(3.23)

Since $\varphi\oplus\psi$ is $1$-strongly convex, we have

$\displaystyle\dfrac{\mu}{2}\|x_{k+1}-x_{k}\|^{2}+\frac{\nu}{2}\|v_{k+1}-v_{k}\|^{2}$
$\displaystyle\leq\mu_{0}D(\mathsf{x}_{k+1},\mathsf{x}_{k}).$ (3.24)

Therefore, using (3.18) and (3.19), we derive from (3.22) that

$\displaystyle G(x_{k+1},v)-G(x,v_{k+1})$ $\displaystyle\leq
2\|K\|\big{(}MD(\mathsf{x}_{k+1},\mathsf{x}_{k})+\dfrac{D(\mathsf{x},\mathsf{x}_{k+1})}{M}\big{)}-\alpha
D(\mathsf{x},\mathsf{x}_{k+1})$ $\displaystyle\
+\dfrac{1}{\gamma}\big{(}D(\mathsf{x},\mathsf{x}_{k})-D(\mathsf{x},\mathsf{x}_{k+1})-D(\mathsf{x}_{k+1},\mathsf{x}_{k})\big{)}$
$\displaystyle\
+\mu_{0}D(\mathsf{x}_{k+1},\mathsf{x}_{k})+\gamma\|r_{k}-\mathsf{R}_{k}\|^{2}+{\langle{{\hat{}\mathsf{x}_{k+1}-\mathsf{x}},{\mathsf{R}_{k}-r_{k}}}\rangle},$
(3.25)

which is (3.7).
(ii). We next consider the case $\theta=1.$ The term in the first line in
(3.13) with $x=x^{\star},\ v=v^{\star}$ can be estimated as

$\displaystyle{\langle{{K(x_{k+1}-y_{k})},{v^{\star}-v_{k+1}}}\rangle}+\left\langle{K(x_{k+1}-x^{\star})}\mid{v_{k+1}-u_{k}}\right\rangle$
$\displaystyle\quad={\langle{{L(\mathsf{x}_{k+1}-\mathsf{x}_{k})},{\mathsf{x}_{k+1}-\mathsf{x}^{\star}}}\rangle}-{\langle{{L(\mathsf{x}_{k}-\mathsf{x}_{k-1})},{\mathsf{x}_{k}-\mathsf{x}^{\star}}}\rangle}-{\langle{{L(\mathsf{x}_{k}-\mathsf{x}_{k-1})},{\mathsf{x}_{k+1}-\mathsf{x}_{k}}}\rangle}$
$\displaystyle\quad\leq
b_{k+1}-b_{k}+\dfrac{\|K\|}{2}\big{(}\|\mathsf{x}_{k}-\mathsf{x}_{k-1})\|^{2}+\|\mathsf{x}_{k+1}-\mathsf{x}_{k}\|^{2}\big{)}$
$\displaystyle\quad\leq
b_{k+1}-b_{k}+\|K\|\big{(}D(\mathsf{x}_{k},\mathsf{x}_{k-1})+D(\mathsf{x}_{k+1},\mathsf{x}_{k})\big{)}.$
(3.26)

Using the triangle inequality and the strong convexity of $\varphi$ and
$\psi$, we obtain

$\displaystyle\dfrac{\mu}{2}\|x_{k+1}-y_{k}\|^{2}+\frac{\nu}{2}\|v_{k+1}-u_{k}\|^{2}$
$\displaystyle\leq\mu_{0}\big{(}\|\mathsf{x}_{k}-\mathsf{x}_{k+1}\|^{2}+\|\mathsf{x}_{k}-\mathsf{x}_{k-1}\|^{2}\big{)}$
$\displaystyle\leq
2\mu_{0}(D(\mathsf{x}_{k+1},\mathsf{x}_{k})+D(\mathsf{x}_{k},\mathsf{x}_{k-1})).$
(3.27)

We can estimate the two last term in the third line of (3.13) as

$\displaystyle{\langle{{x_{k+1}-x},{\nabla
h(y_{k})-z_{k}}}\rangle}+{\langle{{\nabla\ell(u_{k})-t_{k}},{v_{k+1}-v}}\rangle}\leq\gamma\|r_{k}-\mathsf{R}_{k}\|^{2}+{\langle{{\hat{}\mathsf{x}_{k+1}-\mathsf{x}},{\mathsf{R}_{k}-r_{k}}}\rangle}.$
(3.28)

Therefore, inserting (3.26), (3.21), (3.27) and (3.28) into (3.13), we get

$\displaystyle G(x_{k+1},v^{\star})-G(x^{\star},v_{k+1})$ $\displaystyle\leq
b_{k+1}-b_{k}+\|K\|\big{(}D(\mathsf{x}_{k},\mathsf{x}_{k-1})+D(\mathsf{x}_{k+1},\mathsf{x}_{k})\big{)}$
$\displaystyle\
+\dfrac{1}{\gamma}\big{(}D(\mathsf{x}^{\star},\mathsf{x}_{k})-D(\mathsf{x}^{\star},\mathsf{x}_{k+1})-D(\mathsf{x}_{k+1},\mathsf{x}_{k})\big{)}$
$\displaystyle\
+2\mu_{0}(D(\mathsf{x}_{k+1},\mathsf{x}_{k})+D(\mathsf{x}_{k},\mathsf{x}_{k-1}))$
$\displaystyle\
+\gamma\|r_{k}-\mathsf{R}_{k}\|^{2}+{\langle{{\hat{}\mathsf{x}_{k+1}-\mathsf{x}},{\mathsf{R}_{k}-r_{k}}}\rangle},$
(3.29)

which implies that

$\displaystyle\gamma[G(x_{k+1},v^{\star})-G(x^{\star},v_{k+1})]$
$\displaystyle\leq D(\mathsf{x}^{\star},\mathsf{x}_{k})-\gamma
b_{k}-D(\mathsf{x}^{\star},\mathsf{x}_{k+1})+\gamma b_{k+1}$
$\displaystyle-(1-2\gamma\mu_{0}-\gamma\|K\|)D(\mathsf{x}_{k+1},\mathsf{x}_{k})$
$\displaystyle+(2\gamma\mu_{0}+\gamma\|K\|)D(\mathsf{x}_{k},\mathsf{x}_{k-1})$
$\displaystyle+\gamma^{2}\|r_{k}-\mathsf{R}_{k}\|^{2}+\gamma{\langle{{\hat{}\mathsf{x}_{k+1}-\mathsf{x}},{\mathsf{R}_{k}-r_{k}}}\rangle},$
(3.30)

which proves (3.8).

The convergence of Agorithm 3.1 depends on the choices of $\theta$ and
$(\omega_{k})_{k\in\mathbb{N}}$. We first main convergence result can be now
stated where we prove the sublinear convergence rate in expeactation of the
primal-dual gap for general convex case, i.e. $\alpha=0$.

###### Theorem 3.6

Let $(\bar{x}_{s})_{s\in\mathbb{N}},\ (\bar{v}_{s})_{s\in\mathbb{N}}$ be
generated by Algorithm 3.1 with $\theta=1,\omega_{k}=1/m$. Suppose that
Assumption 2.5 and Assumption 2.6 are satisfied. Assume that

$\displaystyle\begin{cases}12\gamma L_{1}&<1\\\
4\gamma\mu_{0}+2\gamma\|K\|+8L_{2}\gamma^{2}&\leq 1.\end{cases}$ (3.31)

For every $N\in\mathbb{N}$, define

$\hat{x}_{N}=\big{(}\sum_{s=1}^{N}\bar{x}_{s}\big{)}/N;\text{and}\;\
\hat{v}_{N}=\big{(}\sum_{s=1}^{N}\bar{v}_{s}\big{)}/N.$ (3.32)

Then we have

$\mathsf{E}[G(\hat{x}_{N},v^{\star})-G(x^{\star},\hat{v}_{N})]\leq\dfrac{D(\mathsf{x}^{\star},\bar{}\mathsf{x}_{0})+4L_{1}\gamma^{2}(m+2)\big{[}G(\bar{x}_{0},v^{\star})-G(x^{\star},\bar{v}_{0})\big{]}}{m\gamma(1-12L_{1}\gamma)N}.$
(3.33)

Proof. Let $s\in\mathbb{N}$, consider the stage $s$, using Lemma 3.5 (ii) with
$\alpha=0$, we have

$\displaystyle\gamma[G(x_{k+1},v^{\star})-G(x^{\star},v_{k+1})]$
$\displaystyle\leq D(\mathsf{x}^{\star},\mathsf{x}_{k})-\gamma
b_{k}-D(\mathsf{x}^{\star},\mathsf{x}_{k+1})+\gamma b_{k+1}$
$\displaystyle-(1-2\gamma\mu_{0}-\gamma\|K\|)D(\mathsf{x}_{k+1},\mathsf{x}_{k})$
$\displaystyle+(2\gamma\mu_{0}+\gamma\|K\|)D(\mathsf{x}_{k},\mathsf{x}_{k-1})$
$\displaystyle+\gamma^{2}\|r_{k}-\mathsf{R}_{k}\|^{2}+\gamma{\langle{{\hat{}\mathsf{x}_{k+1}-\mathsf{x}},{\mathsf{R}_{k}-r_{k}}}\rangle}.$
(3.34)

Set

$T_{k}=G(x_{k},v^{\star})-G(x^{\star},v_{k})\geq 0.$ (3.35)

Let us next denote $\xi_{k}=(i_{k},j_{k})$ and $\xi_{[k]}$ denote that history
$\\{\xi_{0},\xi_{1},\ldots,\xi_{k}\\}$. We also denote by
$\mathsf{E}_{\xi_{k}}$ the conditional expectation with respect to
$\xi_{[k-1]}$. It follows that

$\displaystyle\gamma\mathsf{E}_{\xi_{k}}\big{[}T_{k+1}\big{]}$
$\displaystyle\leq D(\mathsf{x}^{\star},\mathsf{x}_{k})-\gamma
b_{k}-\mathsf{E}_{\xi_{k}}D(\mathsf{x}^{\star},\mathsf{x}_{k+1})+\gamma\mathsf{E}_{\xi_{k}}b_{k+1}-(1-2\gamma\mu_{0}-\gamma\|K\|)\mathsf{E}_{\xi_{k}}D(\mathsf{x}_{k+1},\mathsf{x}_{k})$
$\displaystyle\ \
+(2\gamma\mu_{0}+\gamma\|K\|)D(\mathsf{x}_{k},\mathsf{x}_{k-1})+\gamma^{2}\mathsf{E}_{\xi_{k}}\|r_{k}-\mathsf{R}_{k}\|^{2}.$
(3.36)

Moreover, using (3.5) in Corollary 3.4,

$\mathsf{E}_{\xi_{k}}\|r_{k}-\mathsf{R}_{k}\|^{2}\leq
8L_{2}D(\mathsf{x}_{k},\mathsf{x}_{k-1})+8L_{1}T_{k}+4L_{1}G(\bar{x},v^{\star})-G(x^{\star},\bar{v}).$
(3.37)

Therefore, we derive from (3.36), (3.37) and (3.31) that

$\displaystyle\gamma\mathsf{E}_{\xi_{k}}\big{[}T_{k+1}\big{]}$
$\displaystyle\leq\big{[}D(\mathsf{x}^{\star},\mathsf{x}_{k})+(2\gamma\mu_{0}+\gamma\|K\|+8L_{2}\gamma^{2})D(\mathsf{x}_{k},\mathsf{x}_{k-1})-\gamma
b_{k}\big{]}$ $\displaystyle\ \
-\mathsf{E}_{\xi_{k}}\big{[}D(\mathsf{x}^{\star},\mathsf{x}_{k+1})+(2\gamma\mu_{0}+\gamma\|K\|+8L_{2}\gamma^{2})D(\mathsf{x}_{k+1},\mathsf{x}_{k})-\gamma
b_{k+1}\big{]}$ $\displaystyle\ \
+8L_{1}\gamma^{2}T_{k}+4L_{1}\gamma^{2}\big{(}G(\bar{x},v^{\star})-G(x^{\star},\bar{v})\big{)}$
$\displaystyle\leq
e_{k}-\mathsf{E}_{\xi_{k}}e_{k+1}+8L_{1}\gamma^{2}T_{k}+4L_{1}\gamma^{2}\big{(}G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})\big{)},$
(3.38)

where we set

$e_{k}=D(\mathsf{x}^{\star},\mathsf{x}_{k})+(2\gamma\mu_{0}+\gamma\|K\|+8L_{2}\gamma^{2})D(\mathsf{x}_{k},\mathsf{x}_{k-1})-\gamma
b_{k}.$

We have

$\displaystyle|b_{k}|$
$\displaystyle\leq\|L\|\|\mathsf{x}_{k}-\mathsf{x}_{k-1}\|\|\mathsf{x}_{k}-\mathsf{x}^{\star}\|$
$\displaystyle\leq\dfrac{\|K\|}{2}\big{(}\|\mathsf{x}_{k}-\mathsf{x}_{k-1}\|^{2}+\|\mathsf{x}_{k}-\mathsf{x}^{\star}\|^{2}\big{)}.$

So the condition (3.31) implies that $e_{k}\geq 0\ \ \forall k\in\mathbb{N}.$
Taking the expectation with respect to all the history in the stage $s$ and
summing the inequality (3.38) from $k=0$ to $k=m-1$, we obtain

$\displaystyle\gamma\sum\limits_{k=0}^{m-1}\mathsf{E}[T_{k+1}]$
$\displaystyle\leq
e_{0}-\mathsf{E}e_{m}+8L_{1}\gamma^{2}\sum\limits_{k=0}^{m-1}\mathsf{E}[T_{k}]+4mL_{1}\gamma^{2}\big{[}G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})\big{]}$
$\displaystyle\leq(e_{0}+8L_{1}\gamma^{2}T_{0})-(\mathsf{E}e_{m}+8L_{1}\gamma^{2}\mathsf{E}[T_{m}])+8L_{1}\gamma^{2}\sum\limits_{k=1}^{m}\mathsf{E}[T_{k}]$
$\displaystyle\ \
+4mL_{1}\gamma^{2}\big{[}G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})\big{]}.$
(3.39)

In turn,

$\displaystyle\gamma(1-8L_{1}\gamma)\sum\limits_{k=1}^{m}\mathsf{E}[T_{k}]$
$\displaystyle\leq(e_{0}+8L_{1}\gamma^{2}T_{0})-(\mathsf{E}e_{m}+8L_{1}\gamma^{2}\mathsf{E}[T_{m}])$
$\displaystyle\ \
+4mL_{1}\gamma^{2}\big{[}G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})\big{]}.$

Using the convexity-concavity of $G$, we obtain

$\displaystyle
m\gamma(1-8L_{1}\gamma)\mathsf{E}[G(\bar{x}_{s+1},v^{\star})-G(x^{\star},\bar{v}_{s+1})]$
$\displaystyle\leq(e_{0}+8L_{1}\gamma^{2}T_{0})-(\mathsf{E}e_{m}+8L_{1}\gamma^{2}\mathsf{E}[T_{m}])$
$\displaystyle\ \
+4mL_{1}\gamma^{2}\big{[}G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})\big{]}.$
(3.40)

Note that by the choices of $(x_{0}^{s})_{s\in\mathbb{N}}$ and
$(x_{-1}^{s})_{s\in\mathbb{N}}$, we have

$\mathsf{E}e_{m}+8L_{1}\gamma^{2}\mathsf{E}[T_{m}]=\mathsf{E}e^{s+1}_{0}+8L_{1}\gamma^{2}\mathsf{E}T^{s+1}_{0}.$

Summing (3) from $s=0$ to $s=N-1$, we derive

$\displaystyle
m\gamma(1-8L_{1}\gamma)\sum\limits_{s=1}^{N}\mathsf{E}[G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})]$
$\displaystyle\leq(e^{0}_{0}+8L_{1}\gamma^{2}T^{0}_{0})-(\mathsf{E}e^{N-1}_{m}+8L_{1}\gamma^{2}\mathsf{E}[T^{N-1}_{m}])$
$\displaystyle+4mL_{1}\gamma^{2}\sum\limits_{s=0}^{N-1}\mathsf{E}[G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})],$
(3.41)

which implies that

$\displaystyle
m\gamma(1-12L_{1}\gamma)\sum\limits_{s=1}^{N}\mathsf{E}[G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})]$
$\displaystyle\leq(e^{0}_{0}+8L_{1}\gamma^{2}T^{0}_{0})-(\mathsf{E}e^{N-1}_{m}+8L_{1}\gamma^{2}\mathsf{E}[T^{N-1}_{m}])$
$\displaystyle\ \
+4mL_{1}\gamma^{2}[G(\bar{x}_{0},v^{\star})-G(x^{\star},\bar{v}_{0})]$
$\displaystyle\leq
D(\mathsf{x}^{\star},\bar{}\mathsf{x}_{0})+4L_{1}\gamma^{2}(m+2)\big{[}G(\bar{x}_{0},v^{\star})-G(x^{\star},\bar{v}_{0})\big{]}.$
$\Rightarrow\mathsf{E}[G(\hat{x}_{N},v^{\star})-G(x^{\star},\hat{v}_{N})]\leq\dfrac{D(\mathsf{x}^{\star},\bar{}\mathsf{x}_{0})+4L_{1}\gamma^{2}(m+2)\big{[}G(\bar{x}_{0},v^{\star})-G(x^{\star},\bar{v}_{0})\big{]}}{m\gamma(1-12L_{1}\gamma)N}.$

The proof is completed.

###### Remark 3.7

Recently, there appeared various publications where the convex-concave saddle
problems were investigated in stochastic setting; see [3, 12, 14, 21, 33, 34,
24, 30, 27, 36, 41, 42] for instances and the reference therein. These
existing methods are different from our proposed algorithm. Thus we highlight
several works in which the convergence of the gap functions were investigated
for non-strongly convex-concave problems.

  1. (i)

Theorem 3.6 improves the result in [21, Section 4] in which the variance
reduction technique as well as the Bregman distances were not exploited.
Further connections to existing works [33, 15, 30] can be found in [21].

  2. (ii)

Theorem 3.6 showed that the ergodic convergence rate in expectation of the
primal dual gap is $\mathcal{O}(1/N)$ in which the constant is independent of
the problem size $n$. This rate was also achieved in [24] with a different
method but the constant depends on $n$. Note that the rate $\mathcal{O}(1/N)$
is as fast as the several deterministic methods [18, 5, 6, 10, 25].

  3. (iii)

The rate $\mathcal{O}{(1/\sqrt{N}})$ of the the ergodic convergence rate in
expectation of the primal dual gap was obtained in [30, 27, 41].

We next show that one can improve the rate of the gap function from the
sublinear convergence to linear convergence when the $f$ and $g^{*}$ are
strongly convex relative to $\varphi$ and $\psi$.

###### Theorem 3.8

Suppose that Assumptions 2.3, 2.4 and 2.5 are satisfied. Choose
$M^{\prime}>\dfrac{2\|K\|}{\alpha}$, denote
$\alpha^{\prime}=\alpha-\frac{2\|K\|}{M^{\prime}}$,
$\tau=1+\gamma\alpha^{\prime}$, $\eta=4\gamma^{2}L_{1}$,
$\sum\limits_{k=1}^{m}\tau^{k-1}=\delta$. Assume that

$\displaystyle 0<\gamma<\min\big{\\{}\dfrac{1}{2\|K\|M^{\prime}+\mu_{0}},\
\dfrac{-1+\sqrt{1+\frac{\alpha^{\prime}}{4L_{1}}}}{\alpha^{\prime}}\big{\\}}$
(3.42)

Let $m$ is a positive integer such that

$\displaystyle m>\dfrac{\ln\lambda}{\ln\tau}\ \ \text{where}\
\lambda=\dfrac{\gamma-\eta\tau}{\eta}.$ (3.43)

Let $(\bar{x}_{s})_{s\in\mathbb{N}},\ (\bar{v}_{s})_{s\in\mathbb{N}}$ be
sequences generated by Algorithm 3.1 with $\theta=0$,
$\omega_{k}=\tau^{k-1}/\delta$. Then, we have

$\displaystyle\mathsf{E}[G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s}]\leq\dfrac{\lambda^{-s}}{\eta\delta}[D(\mathsf{x}^{\star},\bar{}\mathsf{x}_{0})+\eta(1+\delta)(G(\bar{x}_{0},v^{\star})-G(x^{\star},\bar{v}_{0}))].$
(3.44)

Proof. By our assumption, $\alpha^{\prime}=\alpha-2\|K\|/M^{\prime}>0$. Hence,
we can rewrite (3.7) with $M=M^{\prime}$ as

$\displaystyle\gamma[G(x_{k+1},v^{\star})$
$\displaystyle-G(x^{\star},v_{k+1})]$ $\displaystyle\leq
D(\mathsf{x}^{\star},\mathsf{x}_{k})-(1+{\gamma\alpha^{\prime}})D(\mathsf{x}^{\star},\mathsf{x}_{k+1})-(1-2\gamma\|K\|M^{\prime}-\gamma\mu_{0})D(\mathsf{x}_{k+1},\mathsf{x}_{k})$
$\displaystyle+\gamma^{2}\|r_{k}-\mathsf{R}_{k}\|^{2}+\gamma{\langle{{\hat{}\mathsf{x}_{k+1}-\mathsf{x}},{\mathsf{R}_{k}-r_{k}}}\rangle}.$
(3.45)

Taking the conditional expectation with respect to $\xi_{[k-1]}$ both sides of
(3.45), using the condition (3.42) and Corollary 3.4, we get:

$\displaystyle\gamma\mathsf{E}_{\xi_{k}}[G(x_{k+1},v^{\star})$
$\displaystyle-G(x^{\star},v_{k+1})]\leq
D(\mathsf{x}^{\star},\mathsf{x}_{k})-(1+\gamma\alpha^{\prime})\mathsf{E}_{\xi_{k}}D(\mathsf{x}^{\star},\mathsf{x}_{k+1})$
$\displaystyle\ \
+4\gamma^{2}L_{1}\bigg{(}[G(x_{k},v^{\star})-G(x^{\star},v_{k})]+[G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})]\bigg{)}.$
(3.46)

Denote $T^{s}_{k}:=T_{k}=G(x_{k},v^{\star})-G(x^{\star},v_{k}),\
\bar{T}_{s}=G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s})$,
$d^{s}_{k}:=d_{k}:=D(\mathsf{x}^{\star},\mathsf{x}_{k})$.
We have:

$\displaystyle(1+\gamma\alpha^{\prime})\mathsf{E}_{\xi_{k}}d_{k+1}\leq
d_{k}-\gamma\mathsf{E}_{\xi_{k}}T_{k+1}+4\gamma^{2}L_{1}(T_{k}+\bar{T}_{s}).$
(3.47)

Take expectation on both sides of (3.47), we obtain

$\displaystyle\tau\mathsf{E}d_{k+1}\leq\mathsf{E}d_{k}-\gamma\mathsf{E}T_{k+1}+\eta\mathsf{E}T_{k}+\eta\bar{T}_{s}.$
(3.48)

Multiplying both sides by $\tau^{k}$ and telescoping from $k=0$ to $m-1$, we
derive

$\displaystyle\tau^{m}\mathsf{E}d_{m}\leq d_{0}+\eta
T_{0}+\eta\sum_{k=1}^{m-1}\tau^{k}\mathsf{E}T_{k}+\eta\bar{T}_{s}\sum_{k=0}^{m-1}\tau^{k}-\gamma\sum_{k=1}^{m}\tau^{k-1}\mathsf{E}T_{k},$
(3.49)

which implies

$\displaystyle\tau^{m}\mathsf{E}(d_{m}+\eta
T_{m})+(\gamma-\eta\tau)\mathsf{E}\sum_{k=1}^{m}\tau^{k-1}T_{k}\leq d_{0}+\eta
T_{0}+\eta\sum_{k=1}^{m}\tau^{k-1}\bar{T}_{s}.$ (3.50)

From the conditions of $m$ and $\gamma$, we have
$\tau^{m}>\dfrac{\gamma-\eta\tau}{\eta}$, so we obtain:

$\displaystyle\dfrac{\gamma-\eta\tau}{\eta}\mathsf{E}(d_{m}+\eta
T_{m})+(\gamma-\eta\tau)\mathsf{E}\sum_{k=1}^{m}\tau^{k-1}T_{k}\leq d_{0}+\eta
T_{0}+\eta\sum_{k=1}^{m}\tau^{k-1}\bar{T}_{s}.$ (3.51)

From $G$ is convex-concave, (3.51) implies

$\displaystyle\mathsf{E}[d^{s+1}_{0}+\eta
T^{s+1}_{0}+\eta\delta\bar{T}_{s+1}]\leq\dfrac{\eta}{\gamma-\eta\tau}[d^{s}_{0}+\eta
T^{s}_{0}+\eta\delta\bar{T}_{s}].$ (3.52)

Therefore

$\displaystyle\mathsf{E}[D(\mathsf{x}^{\star},\mathsf{x}^{s+1}_{0}]+\eta(G(x^{s+1}_{0},v^{\star})$
$\displaystyle-G(x^{\star},v^{s+1}_{0}))+\eta\delta\bar{T}_{s+1}]$
$\displaystyle\leq\dfrac{\eta}{\gamma-\eta\tau}[D(\mathsf{x}^{\star},\mathsf{x}^{s}_{0})+\eta(G(x^{s}_{0},v^{\star})-G(x^{\star},v^{s}_{0}))+\eta\delta\bar{T}_{s}].$
(3.53)

Hence,

$\displaystyle\eta\delta\mathsf{E}[G(\bar{x}_{s},v^{\star})-G(x^{\star},\bar{v}_{s}]\leq\lambda^{-s}[D(\mathsf{x}^{\star},\bar{}\mathsf{x}_{0})+\eta(1+\delta)(G(\bar{x}_{0},v^{\star})-G(x^{\star},\bar{v}_{0}))].$
(3.54)

The proof is completed.

###### Remark 3.9

Here are some remarks.

The choice of $(\omega_{k})_{0\leq k\leq m}$ is the same in [36]. However, the
resulting algorithm is full-splitting and hence it is different from [36].
Theorem 3.8 can be viewed a development of [36, Theorem 1] for our splitting
method.

In (3.44), $\lambda$ is greater than 1, indeed:

$\lambda>1\Leftrightarrow\dfrac{1-4\gamma L_{1}\tau}{4\gamma
L_{1}}>1\Leftrightarrow\gamma(\tau+1)<\dfrac{1}{4L_{1}}\Leftrightarrow\gamma(2+\gamma\alpha^{\prime})<\dfrac{1}{4L_{1}},$

which is satisfied by (3.42).

###### Remark 3.10

Here are some connections to existing works where variance reduction
techniques are used.

  1. (i)

Linear convergence in expectation of the primal-dual gap was established in
[36] for a different stochastic variance reduce algorithm.

  2. (ii)

The authors in [3] also proposed stochastic variance reduce algorithm for
saddle point problems with the linear convergence in expectation of the
iterates.

  3. (iii)

In the context of solving empirical composition optimization problem, the
stochastic variance reduced primal dual algorithms with the Euclidean norms
were in [16] in which the linear convergences of the iterates in expectation
were achieved.

  4. (iv)

For a special case of Problem 1.1 where $\ell=0$ and $f=0$, under additional
assumption on the linear operator $L$, the method proposed in [19] with the
Euclidean distances achieves the linear convergence rate even when the
strongly convex-concave condition is not full-filled.

## References

  * [1] H. H. Bauschke, J. M. Borwein, and P. L. Combettes, Essential smoothness, essential strict convexity, and Legendre functions in Banach spaces, Commun. Contemp. Math., vol. 3, pp. 615–647, 2001.
  * [2] H. H. Bauschke, J. M. Borwein, and P. L. Combettes, Bregman monotone optimization algorithms, SIAM J. Control Optim., vol. 42, pp. 596–636, 2003.
  * [3] P. Balamurugan and F. Bach, Stochastic Variance Reduction Methods for Saddle-Point Problems, Advances in Neural Information Processing Systems, pp. 1416–1424, 2016.
  * [4] R. I. Boţ and C. Hendrich, A Douglas–Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators, SIAM J. Optim., Vol. 23, pp. 2541–2565, 2013.
  * [5] R. I. Boţ and C. Hendrich, Convergence Analysis for a Primal-Dual Monotone + Skew Splitting Algorithm with Applications to Total Variation Minimization, J. Math. Imaging Vis., Vol. 49, pp. 551–568, 2014.
  * [6] R. I. Boţ, E.R. Csetnek and C. Hendrich, On the convergence rate improvement of a primal- dual splitting algorithm for solving monotone inclusion problems, Math. Program., Vol. 150, pp.251-279, 2015.
  * [7] L. M. Bregman,.The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics, Vol. 7, pp.200–217, 1967.
  * [8] M.N. Bùi and P. L . Combettes, Multivariate monotone inclusions in saddle form, https://arxiv.org/pdf/2002.06135.pdf.
  * [9] M.N. Bùi and P. L . Combettes, Bregman forward-backward operator splitting, Set-Valued Var. Anal., 2020.
  * [10] A. Chambolle,T. Pock, On the ergodic convergence rates of a first-order primal–dual algorithm, Math. Program., Vol. 159, pp. 253-287, 2016.
  * [11] G. Chen and M.Teboulle, Convergence analysis of aproximal-like minimization algorithm using Bregman functions. SIAM J. Optim., Vol.3, pp.538-543, 1993
  * [12] Y. Chen, G. Lan, Y. Ouyang, Optimal primal–dual methods for a class of saddle point problems, SIAM J. Optim., Vol 24, 1779-1814, 2014.
  * [13] P. L. Combettes and J.-C. Pesquet, Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators, Set-Valued Var. Anal., Vol. 20, pp. 307-330, 2012.
  * [14] P. L. Combettes and J.-C. Pesquet, Stochastic approximations and perturbations in forward-backward splitting for monotone operators, Pure and Applied Functional Analysis, vol. 1, no. 1, pp. 13-37, 2016.
  * [15] V. Cevher and B. C. Vũ, A reflected forward-backward splitting method for monotone inclusions involving Lipschitzian operators, Set-Valued Var. Anal., 2020\.
  * [16] A.M., Devraj, J. Chen, Stochastic variance reduced primal dual algorithms for empirical composition optimization, Advances in Neural Information Processing Systems, pp. 9882-9892, 2019.
  * [17] C. D. Dang, G. Lan, Stochastic block mirror descent methods for nonsmooth and stochastic optimization, SIAM J. Optim., vol. 25, pp. 856-81, 2015.
  * [18] Y. Drori, S. Sabach, and M. Teboulle, A simple algorithm for a class of nonsmooth convex- concave saddle-point problems,Oper. Res. Lett., Vol. 43, pp. 209-214, 2015.
  * [19] S. S. Du, W. Hu, Linear convergence of the primal-dual gradient method for convex-concave saddle point problems without strong convexity, Proc. International Conference on Artificial Intelligence and Statistics, pp. 196-205, 2019.
  * [20] J. C. Duchi , S. Shalev-Shwartz, Y. Singer, A. Tewari, Composite Objective Mirror Descent, InCOLT, pp. 14-26, 2010.
  * [21] N. V. Dung and B. C. Vũ , Convergence analysis of the stochastic reflected forward-backward splitting algorithm, https://arxiv.org/abs/2102.08906.
  * [22] H. Lu, R. Freund, Yu. Nesterov, Relatively smooth convex optimization by first-order methods,and applications, SIAM J. Optim., Vol.28, pp. 333-354,2018.
  * [23] Robert M. Gower, Mark Schmidt, Francis Bach, Peter Richtarik, Variance-Reduced Methods for Machine Learning, Proceedings of the IEEE, Vol. 108, 2020.
  * [24] E. Y. Hamedani, A. Jalilzadeh, A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems, https://arxiv.org/abs/2012.13456
  * [25] E.Y. Hamedani, N.S. Aybat, A primal-dual algorithm for general convex-concave saddle point problems, arXiv:1803.01401
  * [26] L. T. K. Hien, C. Lu, H. Xu, and J. Feng, Accelerated stochastic mirror descent algorithms for composite non-strongly convex optimization, 2016, arXiv:1605.06892v4.
  * [27] A. Juditsky, A.S. Nemirovski,C. Tauvel, Solving variational inequalities with stochastic mirror-prox algorithm, Stochastic Systems, Vol. 1 pp. 17-58, 2011.
  * [28] Y. Lei, and D. X.Zhou, Analysis of online composite mirror descent algorithm, Neural computation, vol. 29, pp.825–860, 2017.
  * [29] J. J. Moreau, Fonctionnelles sous-différentiables, C. R. Acad. Sci. Paris Sér. A Math., vol. 257, pp. 4117–4119, 1963.
  * [30] A. Nemirovski, A. Juditsky, G. Lan and A. Shapiro, Robust stochastic approximation approach to stochastic programming, SIAM Journal on Optimization, 19(4): 1574–1609, 2009.
  * [31] A. Nitanda, Stochastic proximal gradient descent with acceleration techniques. Advances in Neural Information Processing Systems, pp. 1574–1582, 2014.
  * [32] Q. Van Nguyen, Forward-backward splitting with Bregman distances, Vietnam J. Math. Vol. 45, pp.519-539,2017.
  * [33] L. Rosasco, S. Villa, B. C. Vũ, A stochastic inertial forward-backward splitting algorithm for multivariate monotone inclusions, Optimization, Vol. 65, pp. 1293-1314, 2016.
  * [34] L. Rosasco, S. Villa, B. C. Vũ, A First-order stochastic primal-dual algorithm with correction step, Numer. Funct. Anal. Optim., Vol. 38, pp.602-626, 2017.
  * [35] E. K. Ryu and B. C. Vũ, Finding the Forward-Douglas-Rachford-Forward Method, J. Optim. Theory Appl., Vol. 184, pp. 858–876, 2020.
  * [36] Z. Shi, X. Zhang, and Y. Yu, Bregman divergence for stochastic variance reduction: Saddle- point and adversarial prediction, In Advances in Neural Information Processing Systems, 2017.
  * [37] P. Tseng, On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM J. Optim. 2008.
  * [38] B. C. Vũ, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math., Vol. 38, pp. 667–681, 2013.
  * [39] L. Xiao and T. Zhang, A proximal stochastic gradient method with progressive variance reduction, SIAM J. Optim., vol. 24, pp. 2057-2075.
  * [40] Z. Allen-Zhu and E. Hazan, Variance Reduction for Faster Non-Convex Optimization, Proceedings of The 33rd Internationa Conference on Machine Learning, PMLR, Vol.48, pp.699-707, 2016.
  * [41] R. Zhao, Optimal stochastic algorithms for convex-concave saddle-point problems. arXiv preprint arXiv:1903.01687,
  * [42] J. Wang, L. Xiao, Exploiting strong convexity from data with primal-dual first-order algorithms, arXiv preprint arXiv:1703.02624.


# High entropy metallic glasses, what does it mean?

G.V. Afonin  Department of General Physics, Voronezh State Pedagogical
University, Voronezh 394043, Russia  J.C. Qiao  School of Mechanics and Civil
Architecture, Northwestern Polytechnical University, Xi’an 710072, China  A.S.
Makarov  Department of General Physics, Voronezh State Pedagogical University,
Voronezh 394043, Russia  R.A. Konchakov  Department of General Physics,
Voronezh State Pedagogical University, Voronezh 394043, Russia  E.V.
Goncharova  Department of General Physics, Voronezh State Pedagogical
University, Voronezh 394043, Russia  N.P. Kobelev  Institute of Solid State
Physics, Russian Academy of Sciences, Chernogolovka, Moscow district 142432,
Russia  V.A. Khonik<EMAIL_ADDRESS>Department of General Physics,
Voronezh State Pedagogical University, Voronezh 394043, Russia

###### Abstract

We performed calorimetric measurements on 30 bulk metallic glasses differing
with their mixing entropies $\Delta S_{mix}$. On this basis, the excess
entropies $\Delta S$ and excess enthalpies $\Delta H$ of glasses with respect
to their maternal crystalline states are calculated. It is found that the
excess entropy $\Delta S$ on the average decreases with increasing mixing
entropy $\Delta S_{mix}$. This means that so-called "high-entropy metallic
glasses" (i.e. the glasses having high $\Delta S_{mix}$) actually constitute
glasses with low excess entropy $\Delta S$. We predict that such glasses
should have reduced relaxation ability. We also found that the excess enthalpy
$\Delta H$ of glass linearly increases with its excess entropy $\Delta S$, in
line with a general thermodynamic estimate.

††preprint: AIP/123-QED

Entropy-based approaches currently constitute a new major way to the
understanding of structure and physical properties of crystalline and non-
crystalline metallic and non-metallic materials Murty2014 ; GaoSpringer2016 ;
NemilovEntropy2018 ; ZhangSpringer2019 ; FengFundRes2022 . In particular, this
applies for crystalline alloys, which were discovered in the beginning of the
2000s and contain five or more metallic elements each having the atomic
percentage between 5 and 35 %. These alloys can be characterized by the
entropy of mixing, which reflects the changes of the entropy upon alloy
preparation and determined as

$\Delta S_{mix}=-R\sum\limits_{i=1}^{n}c_{i}lnc_{i},$ (1)

where $R$ is the universal gas constant, $c_{i}$ is the molar fraction of the
i-th element in the alloy and $n$ is the number of constituent elements
YehAdvEngMater2004 ; CantorMaterSciEng2004 . The alloys with the mixing
entropy $S_{mix}\geq 1.5\;R$ were named as high-entropy (HE) alloys
GeorgeNatRevMater2019 ; DuEncMater2022 ; OhashiJALCOM2022 ;
LuanJMaterSciTechnol2023 .

A few years later it was shown that HE melts can be solidified in the non-
crystalline state forming high-entropy metallic glasses
(HEMGs)TakeuchiIntermetallics2011 ; GaoJNCS2011 ; WangJOM2014 . It was found
that HEMGs have relatively high glass-forming ability WadaMaterialia2019 ;
OhashiJALCOM2022 ; WangJNCS2022  and enhanced thermal stability
CaoIntermetallics2018 ; DehkordiJNCS2022 ; HuoChinPhysLett2022 ;
LuanNatComm2022 , which results in higher activation energies
ChenIntermetallics2023 . Other peculiarities of HEMGs are related to lower
atomic mobility ChenIntermetallics2023 , sluggish diffusion DuanPRL2022 ;
JiangNatComm2021  and crystallization kinetics JiangJA2016 ;
YangMaterResLett2018 , slow dynamics of homogeneous flow ZhangScrMater2022 ,
decreased dynamic and spatial heterogeneities JiangNatComm2021 . HEMGs were
found to have good mechanical properties HuoChinPhysLett2022 ;
LuanJMaterSciTechnol2023 ; QiIntermetallics2015  and sometimes display
superior magnetic characteristics QiIntermetallics2015 ; XuJNCS2018 ;
ChenJALCOM2021 , superplastic behavior above the glass transition temperature
$T_{g}$ DehkordiJNCS2022 ; ZhangIntJPlast2022 , unique biomedical properties
WangJOM2014  as well as excellent irradiation tolerance WangJNucLMater2019 .
It is sometimes said that HEMGs combine the features of both metallic glasses
and high entropy crystalline alloys ChenJALCOM2021 .

Like HE crystalline alloys, HEMGs are defined as glasses having high mixing
entropy $\Delta S_{mix}/R\geq 1.5$ defined by Eq.(1). However, despite of
intense investigations in the past decade, it is still unclear what does high
$\Delta S_{mix}$ mean from a physical point and to what consequences does it
lead. This seems to be a major issue of the physics of high-entropy non-
crystalline materials. This work is addressed to this problem. We determined
the excess entropy $\Delta S$ of 30 bulk metallic glasses with respect to
their maternal crystalline states and compared it with the mixing entropy
$\Delta S_{mix}$ accepted as a state variable. We found that on the average
the high mixing entropy $\Delta S_{mix}$ corresponds to the low excess entropy
$\Delta S$. This conclusion appears to be quite expectable and understable and
explains why HEMGs should have reduced relaxation ability. Besides that, we
show that an increase of the excess entropy leads to a linear growth of the
excess enthalpy of glass, which is also quite explainable.

The determination of MGs’ entropy (as well as other thermodynamic potentials)
was considered long ago (e.g. Ref.BuschJApplPhys1998 ) and the works basing on
the thermodynamic approach have continued to the present
SchaweThermochimActa2020 ; NeuberActamater2021 . Such works utilize heat
capacity data in the liquid state and/or below $T_{g}$ together with the heat
of fusion for the calculation of the excess thermodynamic potentials of the
supercooled liquid state with respect to the maternal crystal. The obtained
results were used mainly for an estimate of the glass-forming ability of
supercooled liquids and their crystallization kinetics.

Recently, we suggested a method to calculate the excess entropy of solid glass
$\Delta S$ with respect to the maternal crystal (by this crystal we understand
a polycrystalline structure that arises as a result of the complete
crystallization of glass and does not undergo any subsequent phase
transformations), which is defined in line with classical thermodynamics using
calorimetric data as MakarovJPCM2021b ; MakarovJETPLett2022

$\Delta S(T)=\frac{1}{\dot{T}}\int_{T}^{T_{cr}}\frac{\Delta W(T)}{T}dT,$ (2)

where $\Delta W$ is the differential heat flow specified below, $T_{cr}$ is
the temperature of the complete crystallization and $\dot{T}$ is the heating
rate. To calculate temperature dependence $\Delta S(T)$ with this equation, we
performed differential scanning calorimetry (DSC) measurements using a Hitachi
DSC 7020 instrument operating in high-purity (99.999%) $N_{2}$ atmosphere at a
rate of 3 K/min. For this investigation, we tested 30 X-ray amorphous bulk
metallic glasses (MGs) prepared by melt suction. The compositions of these MGs
are listed in Table 1 in the order with their mixing entropy $\Delta
S_{mix}/R$ calculated using Eq.(1). It is seen that the mixing entropy changes
in the range $0.83\leq\Delta S_{mix}/R\leq 1.79$, i.e. covers almost the whole
possible range, from a minimal value $\Delta S_{mix}/R=0.83$ for a three-
component MG to $\Delta S_{mix}/R=1.79$ for a HE equiatomic six-component
glass.

To decrease the effect of the preparation conditions on the excess entropy,
all glasses were tested in the relaxed (preannealed) state according to the
following protocol: i) initial sample was heated up to the temperature of the
complete crystallization $T_{cr}$ with empty reference DSC cell. This
crystallized sample was next moved to the reference DSC cell; ii) a new sample
in the initial state was heated into the supercooled liquid state (i.e.
between $T_{g}$ and the crystallization onset temperature) and cooled back to
room temperature at the same rate of 3 K/min; iii) the same (relaxed) sample
was tested up to $T_{cr}$ (run 2) and, finally, iv) the same (crystallized)
specimen is again heated up to $T_{cr}$ (run 3). This protocol allows
performing DSC measurements with the reference cell containing fully
crystallized sample of approximately the same mass ($\approx$ 70 mg) so that
the measured heat flow $\Delta W$ constitutes the difference between the heat
flow coming from relaxed glass $W_{gl}$ and its crystalline counterpart
$W_{cr}$ and termed as the differential heat flow, i.e. $\Delta
W=W_{gl}-W_{cr}$, which enters Eq.(2). It is seen that if temperature
$T=T_{cr}$ then $\Delta S=0$ and, therefore, the quantity $\Delta S$ given by
this equation represents the excess entropy of solid glass with respect to the
maternal crystal.

Panel (a) in Fig.1 gives the differential heat flow $\Delta W$ for a relaxed
HE glass Zr35Hf17.5Ti5.5Al12.5Co7.5Ni12Cu10 taken as an example. The plot
illustrates common regularities of DSC testing on preannealed MGs given by an
endothermal effect below $T_{g}$ and in the supercooled liquid state (above
$T_{g}$) and strong crystallization-induced exothermal reaction at higher
temperatures up to the temperature of the complete crystallization $T_{cr}$.
Panel (b) shows the excess entropy $\Delta S$ calculated with Eq.(2) using
$\Delta W$-data given in panel (a). The excess entropy is first nearly
constant (up to $\approx 500$ K), then increases with temperature due to the
endothermal heat flow below and near $T_{g}$, next rapidly increases due to
strong endothermal disordering in the supercooled liquid state and finally
falls to zero because of the complete crystallization at $T=T_{cr}$. This is a
typical $\Delta S(T)$-pattern generally characteristic of all MGs under
investigation. The characteristic values of the excess entropy at room
temperature ($\Delta S_{rt}$), at the glass transition temperature ($\Delta
S_{Tg}$) and in the supercooled liquid state ($\Delta S_{sql}$) are indicated.

Table 1:  Metallic glasses under investigation and their mixing entropies $\Delta S_{mix}/R$ calculated with Eq.(1).  No | Composition (at.%) | $\Delta S_{mix}/R$ | No | Composition (at.%) | $\Delta S_{mix}/R$
---|---|---|---|---|---
1 |  Cu48Zr48Al4 | 0.83 | 16 |  Zr48Cu34Ag8Al8Pd2 | 1.20
2 |  Zr47.5Cu47.5Al5 | 0.86 | 17 |  Pd43.2Cu28Ni8.8P20 | 1.25
3 |  Zr46Cu46Al8 | 0.92 | 18 |  Zr57Nb5Al10Cu15.4Ni12.6 | 1.25
4 |  Cu49Hf42Al9 | 0.93 | 19 |  Pt42.5Cu27Ni9.5P21 | 1.26
5 |  La55Ni10Al35 | 0.93 | 20 |  Pd40Cu30Ni10P20 | 1.28
6 |  Zr50Cu40Al10 | 0.94 | 21 |  Zr52.5Ti5Cu17.9Ni14.6Al10 | 1.31
7 |  Zr47Cu45Al7Fe1 | 0.95 | 22 |  Zr31.6Hf13.4Al8.7Ag8.4Cu37.8 | 1.42
8 |  Zr56Co28Al16 | 0.97 | 23 |  Ti32.8Zr30.2Cu9Ni5.3Be22.7 | 1.45
9 |  Zr46Cu45Al7Ti2 | 0.98 | 24 |  Zr31Ti27Be26Cu10Ni6 | 1.46
10 |  La55Al25Co20 | 0.99 | 25 |  Ti20Zr20Hf20Cu20Be20 | 1.61
11 |  Zr55Co25Al20 | 0.99 | 26 |  Ti20Zr20Hf20Ni20Be20 | 1.61
12 |  Zr65Al10Ni10Cu15 | 1.03 | 27 |  Zr35Hf13Al11Ag8Ni8Cu25 | 1.63
13 |  Pd40Ni40P20 | 1.05 | 28 |  Zr40Hf10Ti4Y1Al10Cu25Ni7Co2Fe1 | 1.66
14 |  Zr50Cu34Ag8Al8 | 1.12 | 29 |  Zr35Hf17.5Ti5.5Al12.5Co7.5Ni12Cu10 | 1.77
15 |  Zr46Cu36.8Ag9.2Al8 | 1.15 | 30 |  Ti16.7Zr16.7Hf16.7Cu16.7Ni16.7Be16.7 | 1.79
Figure 1:  Differential heat flow of relaxed HE glassy
Zr35Hf17.5Ti5.5Al12.5Co7.5Ni12Cu10 (a) and temperature dependences of its
excess entropy $\Delta S$ and excess enthalpy $\Delta H$ calculated with Eqs
(2) and (3), respectively (b). The glass transition temperature $T_{g}$ and
the temperature of the complete crystallization $T_{cr}$ are shown by the
arrows. The excess entropies at room temperature ($\Delta S_{rt}$), glass
transition temperature ($\Delta S_{Tg}$) and in the supercooled liquid state
($\Delta S_{sql}$) are indicated.

Figure 2 gives the dependences of the excess entropy $\Delta S_{rt}$ (panel
(a)), $\Delta S_{Tg}$ (panel (b)) and $\Delta S_{sql}$ (panel (c)) as a
function of the mixing entropy $\Delta S_{mix}$. The numbers indicate the
glass compositions according to Table 1. It is seen that, despite of some
scatter, the excess entropies on the average decrease with the mixing entropy
as evidenced by the least square linear fits. At that, the slopes of the
linear fits in panels (a) to (c) are equal within $\approx 6\%$ or even less.

Figure 2:  Excess entropy at room temperature $\Delta S_{rt}$ (a), at the
glass transition temperature $\Delta S_{Tg}$ (b) and in the supercooled liquid
state $\Delta S_{sql}$ (c) as function of the mixing entropy $\Delta S_{mix}$.
The numbers indicate glass compositions according to Table 1. The straight
lines give least-square-fit approximations. The corresponding slopes $d\Delta
S_{rt}/d\Delta S_{mix}$, $d\Delta S_{Tg}/d\Delta S_{mix}$ and $d\Delta
S_{sql}/d\Delta S_{mix}$ in panels (a), (b) and (c) are indicated. It is seen
that the excess entropy $\Delta S$ in any case on the average decreases with
the mixing entropy $\Delta S_{mix}$.

Thus, one can conclude that the excess entropy of glass with respect to the
maternal crystal decreases with the mixing entropy, independent of what
quantity ($\Delta S_{rt}$, $\Delta S_{Tg}$ or $\Delta S_{sql}$) is taken to
quantify this dependence. In general, the origin of this dependence seems to
be clear. The high mixing entropy for many-component MGs assumes that the
supercooled melt is strongly relaxed (stabilized GeorgeNatRevMater2019 ) due
to accomodative movements of different atoms into many of available potential
wells in the structure. This relaxed melt is then quenched to form a solid
glass, which to a certain extent inherits the relaxed state of the melt. Thus,
the more is the mixing entropy, the more the degree of glass relaxation should
be. It is also important to emphasize that the mixing entropy $\Delta S_{mix}$
does not depend on the state of glass (i.e. does not vary upon structural
relaxation) and, moreover, has the same value both in the amorphous and
crystalline states. Thus, the mixing entropy $\Delta S_{mix}$ is not a part of
the excess entropy $\Delta S$.

On the other hand, the excess entropy $\Delta S$ characterizes the disorder of
glass and, therefore, the level of its non-equilibrium (see
Ref.MakarovScrMater2024  for a discussion). Thus, it is clear that glass
excess entropy should decrease with the mixing entropy. At that, while $\Delta
S_{mix}$ reflects only the percentage of different atoms, the excess entropy
accounts for all glass parameters (chemical composition, interatomic
interaction, melt quenching rate, entropy changes due to glass formation,
etc.). This seems to be the origin of the data scatter in Fig.2. It is also
worthy of notice that $\Delta S$ in any case is notably bigger than $\Delta
S_{mix}$ (see Fig.2) pointing out a major role of the excess entropy in the
glass formation, as argued earlier MakarovScrMater2024 .

Since the excess entropy directly reflects the disorder in glass
MakarovScrMater2024 , one has also to conclude that MGs with higher $\Delta S$
should be more prone to structural relaxation below the glass transition.
Conversely, glasses with lower $\Delta S$ (i.e. higher $\Delta S_{mix}$)
should be more ordered and more resistant to structural relaxation upon
thermal and other external impact. A number of HEMGs’ peculiarities mentioned
above (enhanced thermal stability, higher activation energies, lower atomic
mobility, sluggish diffusion and crystallization kinetics, etc.) are in line
with this conclusion. It is to be noted also that one-component glasses (e.g.
molecular organic and inorganic glasses, with SiO2 as an example) have zero
mixing entropy. For such glasses the factors determining their excess entropy
and relaxation ability, in addition to those mentioned above, should be
revealed.

Figure 3:  Excess enthalpy at room temperature $\Delta H_{rt}$ (a), at the
glass transition temperature $\Delta H_{Tg}$ (b) and in the supercooled liquid
state $\Delta H_{sql}$ (c) as a function of the corresponding excess entropies
$\Delta S_{rt}$, $\Delta S_{Tg}$ and $\Delta S_{sql}$. The straight lines
gives least-square-fit approximations. The slopes of these lines are equal to
637 K with an error of $\approx 10\%$ or less.

Calorimetric measurements performed in the present study also allow the
calculation of the excess enthalpy of glass $\Delta H$ as MakarovJPCM2021b ;
MakarovJETPLett2022

$\Delta H(T)=\frac{1}{\dot{T}}\int_{T}^{T_{cr}}\Delta W(T)dT,$ (3)

where all quantities are defined above. Figure 1(b) gives an example of
$\Delta H(T)$ temperature dependence, which is calculated with DSC thermogram
in Fig.1(a) using Eq.(3). It is seen that temperature dependence of the excess
enthalpy is similar to that of the excess entropy. The characteristic values
of the excess enthalpy at room temperature $(\Delta H_{rt}$), glass transition
temperature $(\Delta H_{Tg}$) and in the supercooled liquid state $(\Delta
H_{sql}$) are defined similarly to the corresponding values of the excess
entropy shown in Fig.1(b). Panels (a), (b) and (c) in Fig.3 show the
dependences of the excess enthalpy at room temperature $\Delta H_{rt}$, at the
glass transition temperature $\Delta H_{Tg}$ and in the supercooled liquid
state $\Delta H_{sql}$ as functions of the corresponding excess entropies
$\Delta S_{rt}$, $\Delta S_{Tg}$ and $\Delta S_{sql}$, respectively. It is
seen that the excess enthalpies in all cases linearly increase with the excess
entropies and the corresponding slopes $\Delta S/\Delta H$ are equal to 637 K
with an uncertainty of $\approx 10\%$ or less. This result is quite reasonable
since the enthalpy change due to glass formation at $T_{g}$ can be estimated
using a general thermodynamic relation as $\Delta H_{Tg}\approx T_{g}\Delta
S_{Tg}$, where $\Delta S_{Tg}$ is the corresponding entropy change. Then, the
derivative derivative $d\Delta H_{Tg}/d\Delta S_{Tg}$ should be equal to the
glass transition temperature. Since the experimental value of this derivative
is 637 K while the glass transition temperature averaged over all 30 MGs
listed in Table 1 is 626 K, one can state that the above calculations of the
excess entropy and excess enthalpy are in a good agreement with general
thermodynamic consideration.

It is to be emphasized that the excess enthalpy $\Delta H$ and its temperature
dependence can be to a very good precision described as a result of the
evolution of the system of frozen-in defects similar to dumbbell interstitials
in crystalline metals. As shown earlier, $\Delta H$ at any temperature equals
to the elastic energy of these defects accurate to within 10–15% and
crystallization of glass can be considered just as the dissipation of this
elastic energy into heat MakarovJPCM2021b ; MakarovJETPLett2022 . Since the
excess entropy $\Delta S$ is uniquely determined by the excess enthalpy
$\Delta H$, the former is also intrinsically linked to glass defect system and
its changes upon heat treatment. In turn, the degree of glass disorder
described by $\Delta S$ (as demonstrated in Ref.MakarovScrMater2024 ) is
related to the defect system of glass as well.

Finally, it is to be noted that the excess entropy $\Delta S$ can be used for
the calculation of the relaxation time within the framework of the Adam-Gibbs
model. This consideration shows that $\Delta S$ calculated near $T_{g}$ is
inversely proportional to the thermodynamic fragility KonchakovJETPLett2024 ,
which is known to be a major characteristic of supercooled liquids and
glasses. Thus, the fragility is also linked to the degree of disorder and
defect structure of glass as suggested earlier MakarovJPCM2021 .

In conclusion, we performed calorimetric measurements of 30 bulk metallic
glasses with the mixing entropies $\Delta S_{mix}/R$ changing from 0.8-0.9 for
simple three-component MGs to 1.7–1.8 for high-entropy six-component glasses.
On this basis, we calculated the excess entropy and excess enthalpy of glass
with respect to the maternal crystalline state using Eqs.(2) and (3), which
directly follow from classical thermodynamics without any additional
assumptions. First, we found that the excess entropies determined for the
characterisitic temperatures (room temperature, glass transition temperature
and the peak temperature of the excess entropy in the supercooled liquid
state) on the average decrease with the mixing entropy. This leads to an
answer formulated in the title of this Letter as: so-called "high-entropy
metallic glasses" with high mixing entropy actually constitute the glasses
with relatively low excess entropy, which are, consequently, least disordered.
We therefore predict that "high entropy metallic glasses" should display
reduced relaxation ability upon thermal or other external impacts.

We also show that the excess enthalpy $\Delta H$ at any of the above
characteristic temperatures linearly increases with the excess entropy $\Delta
S$ and the derivative $d\Delta H/d\Delta S$ is close to the glass transition
temperature, in a good agreement with general thermodynamic estimate of the
entropy and enthalpy changes upon glass transition.

The obtained results bring an important question on how the high-excess-
entropy state is related to mechanical and other physical behaviors of
metallic glasses. The corresponding studies are on the agenda.

## AUTHOR DECLARATIONS

## Conflict of Interest

The authors have no conflicts to disclose.

## Author Contributions

G.V. Afonin: experimental investigation and data analysis; J.C. Qiao: samples,
discussion, editing; A.S. Makarov: experimental investigation and data
analysis; R.A. Konchakov: data analysis; E.V. Goncharova: data analysis; N.P.
Kobelev: discussion and editing; V.A. Khonik: general conceptualization,
manuscript preparation.

## DATA AVAILABILITY

The data that support the findings of this study are available from the
corresponding authors upon reasonable request.

## Acknowledgments

This work was supported by the Russian Science Foundation under the grant No
23-12-00162.

## References

## References

  * (1) B.S. Murty, J.W. Yeh, S. Ranganathan, High-Entropy alloys, Butterworth-Heinemann, Oxford, Amstaerdam, San-Diego, 2014.
  * (2) High-Entropy Alloys. Fundamentals and Applications, M.C. Gao, J.-W. Yeh, P.K. Liaw, Y. Zhang, Eds. Springer, Switzerland, 2016.
  * (3) S.V. Nemilov, On the possibility of calculating entropy, free energy, and enthalpy of vitreous substances, Entropy 20 (2018) 187.
  * (4) Y. Zhang High-Entropy materials. A Brief Introduction. Springer Nature Singapore Pte Ltd., 2019.
  * (5) X. Feng, Y. Yue, J. Qiu, H. Jain, S. Zhou, Entropy engineering in inorganic non-metallic glass, Fundamental Research 2, 783-793 (2022).
  * (6) J.-W. Yeh, S.-K. Chen, S.-J. Lin, J.-Y. Gan, T.-S. Chin, T.-T. Shun, C.-H. Tsau, S.-Y. Chang, Nanostructured high-entropy alloys with multiple principal elements: novel alloy design concepts and outcomes, Adv.Eng. Mater. 6, (2004) 299-303 (2004).
  * (7) B. Cantor, I.T.H. Chang, P. Knight, A.J.B. Vincent, Microstructural development in equiatomic multicomponent alloys, Mater. Sci. Eng. A 375–377, 213–218 (2004).
  * (8) E.P George, D. Raabe, R.O. Ritchie, High-entropy alloys, Nat. Rev. Mater. 4, 515-534 (2019).
  * (9) Y. Du, Q. Zhou, H. Wang. High-entropy alloys: bulk metallic glasses. Encyclopedia of materials: metals and alloys, 2, 318-326 (2022).
  * (10) Y. Ohashi, T. Wada, H. Kato, High-entropy design and its influence on glass-forming ability in Zr–Cu-based metallic glass, J. Alloys Compd. 915, 165366 (2022).
  * (11) H. Luan, K. Li, L. Shi, W. Zhao, H. Bu, P. Gong, K.-F. Yao, Recent progress in high-entropy metallic glasses, J. Mater. Sci. Technol. 161, 50–62 (2023).
  * (12) A. Takeuchi, N. Chen, T. Wada, Y. Yokoyama, H. Kato, A. Inoue, J.W. Yeh, Pd20Pt20Cu20Ni20P20 high-entropy alloy as a bulk metallic glass in the centimeter, Intermetallics 19, 1546-1554 (2011).
  * (13) X.Q. Gao, K. Zhao, H.B. Ke, D.W. Ding, W.H. Wang, H.Y. Bai, High mixing entropy bulk metallic glasses, J. Non-Cryst.Sol. 357, 3557–3560 (2011).
  * (14) W.H. Wang, High-entropy metallic glasses, JOM 66, 2067–2077 (2014).
  * (15) T. Wada, J. Jiang, K. Yubuta, H. Kato, A. Takeuchi, Septenary Zr–Hf–Ti–Al–Co–Ni–Cu high-entropy bulk metallic glasses with centimeter-scale glass-forming ability, Materialia 7, 100372 (2019).
  * (16) Y. Wang, Z. Zhu, A. Wang, H. Zhang, Ultrastrong behaviors of a non-equiatomic Ti-Zr-Ni-Cu-Be high entropy metallic glass with ultrahigh glass forming ability, J. Non-Cryst Sol. 577, 121323 (2022).
  * (17) Z.K. Dehkordi, M. Malekan, M. Nili-Ahmadabadi, Superplastic formability of the developed Zr40Hf10Ti5Al10Cu25Ni10 high entropy bulk metallic glass with enhanced thermal stability, J. Non-Cryst.Sol. 576, 121265 (2022).
  * (18) D. Cao, Y. Wu, H.X. Li, X.J. Liu, H. Wang, X.Z. Wang, Z.P. Lu, Beneficial effects of oxygen addition on glass formation in a high-entropy bulk metallic glass, Intermetallics 99, 44–50 (2018).
  * (19) J. Huo, K. Li, B. Zang, M. Gao, L.-M. Wang, B. Sun, M. Li, L. Son, J.-Q. Wang, W.-H. Wang, High mixing entropy enhanced energy states in metallic glasses, Chin. Phys. Lett. 39, 046401 (2022).
  * (20) H. Luan, X. Zhang, H. Ding, F. Zhang, J.H. Luan, Z.B. Jiao, Y.-C. Yang, H. Bu, R. Wang, J. Gu, C. Shao, Q. Yu, Y. Shao, Q. Zeng, N. Chen, C.T. Liu, K.-F. Yao, High-entropy induced a glass-to-glass transition in a metallic glass, Nat. Comm. 13, 2183 (2022).
  * (21) C.J. Chen, R. Xu, B.J. Yin, Y.Z. He, J.Y. Zhang, P. Zhang, B.L. Shen, Dynamic mechanical relaxation behavior of TiZrHfCu-Ni/Be/NiBe high-entropy metallic glasses, Intermetallics 157, 107887 (2023).
  * (22) Y.J. Duan, L.T. Zhang, J.C. Qiao, Y.-J. Wang, Y. Yang, T. Wada, H. Kato, J.M. Pelletier, E. Pineda, D. Crespo, Intrinsic correlation between the fraction of liquidlike zones and the $\beta$ relaxation in high-entropy metallic glasses, Phys. Rev. Lett. 129, 175501 (2022).
  * (23) J. Jiang, Z. Lu, J. Shen, T. Wada, H. Kato, M. Chen, Decoupling between calorimetric and dynamical glass transitions in high-entropy metallic glasses, Nature Comm. 12, 3843 (2021).
  * (24) M. Yang, X.J. Liu, H.H. Ruan, Y. Wu, H. Wang, Z.P. Lu, High thermal stability and sluggish crystallization kinetics of high-entropy bulk metallic glasses, J. Appl. Phys. 119, 245112 (2016).
  * (25) M. Yang, X.J. Liu, Y. Wu, H. Wang, X.Z. Wang, P.Z. Lu, Unusual relation between glass-forming ability and thermal stability of high-entropy bulk metallic glasses, Mater. Res. Lett. 6, 495-500 (2018).
  * (26) L.T. Zhang, Y.J. Wang, E. Pineda, H. Kato, Y. Yang, J.C. Qiao, Sluggish dynamics of homogeneous flow in high-entropy metallic glasses, Scr. Mater. 214, 114673 (2022).
  * (27) T. Qi, Y. Li, A. Takeuchi, G. Xie, H. Miao, W. Zhang, Soft magnetic Fe25Co25Ni25(B, Si)25 high entropy bulk metallic glasses, Intermetallics 66, 8-12 (2015).
  * (28) Yu Chen, Z.-W. Dai, J.-Z. Jiang, High entropy metallic glasses: glass formation, crystallization and properties, J. Alloys Compd. 866, 158852 (2021).
  * (29) Y. Xu, Y. Li, Z. Zhu, W. Zhang, Formation and properties of Fe25Co25Ni25(P,C,B,Si)25 high-entropy bulk metallic glasses, J. Non-Cryst. Sol. 487, 60–64 (2018).
  * (30) L.T. Zhang, Y.J. Wang, E. Pineda, Y. Yang, J.C. Qiao, Achieving structural rejuvenation in metallic glass by modulating $-beta$ relaxation intensity via easy-to-operate mechanical cycling, Int. J. Plasticity 157, 103402 (2022).
  * (31) Y. Wang, K. Zhang, Y. Feng, Y. Li, W. Tang, Y. Zhang, B. We, Z. Hu, Excellent irradiation tolerance and mechanical behaviors in high-entropy metallic glasses, J. Nucl. Mater. 527, 151785 (2019).
  * (32) R. Busch, W. Liu, W. L. Johnson, Thermodynamics and kinetics of the Mg65Cu25Y10 bulk metallic glass forming liquid, J. Appl. Phys. 93, 4134-4141 (1998).
  * (33) J.E.K. Schawe, S. Pogatscher, J.F. Löffler, Thermodynamics of polymorphism in a bulk metallic glass: Heat capacity measurements by fast differential scanning calorimetry, Thermochim. Acta 685, 178518 (2020).
  * (34) N. Neuber, O. Gross, M. Frey, B. Bochtler, A. Kuball, S. Hechler, I. Gallino, R. Busch, On the thermodynamics and its connection to structure in the Pt-Pd-Cu-Ni-P bulk metallic glass forming system, Acta Mater. 220, 117300 (2021).
  * (35) A.S. Makarov, G.V. Afonin, J.C. Qiao, A.M Glezer, N.P. Kobelev, V.A. Khonik, Determination of the thermodynamic potentials of metallic glasses and their relation to the defect structure, J. Phys.: Condens. Matter 33, 435701 (2021).
  * (36) A.S. Makarov, M.A. Kretova, G.V. Afonin, J.C. Qiao, A.M. Glezer, N.P. Kobelev, V.A. Khonik, On the nature of the excess internal energy and entropy of metallic glasses, J. Exp. Theor. Phys Lett. 115, 102–107 (2022).
  * (37) A.S. Makarov, G.V. Afonin, R.A. Konchakov, V.A. Khonik, J.C. Qiao, A.N. Vasiliev, N.P. Kobelev, Dimensionless parameter of structural ordering and excess entropy of metallic and tellurite glasses, Scr. Mater. 239, 115783 (2024).
  * (38) R.A. Konchakov, A.S. Makarov, G.V. Afonin, J.C. Qiao, N.P. Kobelev, V.A. Khonik, Relationship of the fragility of metallic glasses with the mixing entropy and excess entropy with respect to the maternal crystal, Pisma v Zhurnal Experimentalnoi i Teoreticheskoi Fiziki” (J. Exp. Theor. Phys. Lett.) v.119, 446 (2024), http://jetpletters.ru/ps/2456 article 36112 (to be translated in English).
  * (39) A.S. Makarov, J.C. Qiao, N.P. Kobelev, A.S. Aronin, V.A. Khonik, Relation of the fragility and heat capacity jump in the supercooled liquid region with the shear modulus relaxation in metallic glasses, J. Phys. Cond. Matter 33 (2021) 275701.