∎

11institutetext:  A. Nedić 22institutetext: School of Electrical, Computer and
Energy Engineering
Arizona State University, Tempe, USA
22email<EMAIL_ADDRESS>33institutetext: I. Necoara 44institutetext:
Department of Automatic Control and Systems Engineering
University Politehnica Bucharest, 060042 Bucharest, Romania
44email<EMAIL_ADDRESS>(corresponding author).

# Random minibatch projection algorithms for convex problems with functional
constraints

Angelia Nedić  Ion Necoara

(Received: 28 February 2019 / Accepted: date)

###### Abstract

In this paper we consider non-smooth convex optimization problems with
(possibly) infinite intersection of constraints. In contrast to the classical
approach, where the constraints are usually represented as intersection of
simple sets, which are easy to project onto, in this paper we consider that
each constraint set is given as the level set of a convex but not necessarily
differentiable function. For these settings we propose subgradient iterative
algorithms with random minibatch feasibility updates. At each iteration, our
algorithms take a step aimed at only minimizing the objective function and
then a subsequent step minimizing the feasibility violation of the observed
minibatch of constraints. The feasibility updates are performed based on
either parallel or sequential random observations of several constraint
components. We analyze the convergence behavior of the proposed algorithms for
the case when the objective function is restricted strongly convex and with
bounded subgradients, while the functional constraints are endowed with a
bounded first-order black-box oracle. For a diminishing stepsize, we prove
sublinear convergence rates for the expected distances of the weighted
averages of the iterates from the constraint set, as well as for the expected
suboptimality of the function values along the weighted averages. Our
convergence rates are known to be optimal for subgradient methods on this
class of problems. Moreover, the rates depend explicitly on the minibatch size
and show when minibatching helps a subgradient scheme with random feasibility
updates.

###### Keywords:

Convex minimization functional constraints subgradient algorithms random
minibatch projection algorithms convergence rates.

##  1 Introduction

The large sum of functions in the objective function and/or the large number
of constraints in most of the practical optimization applications led the
stochastic optimization field to become an essential tool for many applied
mathematics areas, such as machine learning and statistics MouBac:11 ; Vap:98
, constrained control PatNec:17 , sensor networks BlaHer:06 , computer science
KunBac:18 , inverse problems BotHei:12 . For example, in machine learning
applications the optimization algorithms involve numerical computation of
parameters for a system designed to make decisions based on yet unseen data
MouBac:11 ; Vap:98 . In particular, in support vector machines one maps the
data into a higher dimensional input space and constructs an optimal
separating hyperplane in this space by learning, eventually online, the
hyperplanes corresponding to each data in the training set Vap:98 . This leads
to a convex optimization problem with a large number of functional
constraints.

Contributions. To deal with such optimization problems having (possibly)
infinite number of functional constraints, we propose subgradient methods with
random feasibility updates. At each iteration, the algorithms take a step
aimed at only minimizing the objective function, followed by a feasibility
step for minimizing the feasibility violation of the observed minibatch of
convex constraints. The feasibility updates in the first algorithm are
performed using parallel random observations of several constraint components,
while in the second algorithm we consider sequential random observations of
constraints. Both algorithms are reminiscent of a learning process where we
try to learn the constraint set while simultaneously minimizing an objective
function. The proposed algorithms are applicable to the situation where the
whole constraint set of the problem is not known in advance, but it is rather
learned in time through observations. Also, these algorithms are of interest
for (non-smooth) constrained optimization problems where the constraints are
known but their number is either large or not finite.

We study the convergence properties of the proposed random minibatch
projection algorithms for the case when the objective function need not be
differentiable but it is restricted strongly convex, while the functional
constraints are accessed trough a bounded first-order black-box oracle. In
doing so, we can avoid the need for projections to the set of constraints,
which may be expensive computationally. For a diminishing stepsize, we prove
sublinear convergence rates of order ${\cal O}(1/t)$, where $t$ is the
iteration counter, for the expected distances of the weighted averages of the
iterates from the constraint set, as well as for the expected suboptimality of
the function values along the weighted averages. Our convergence rates are
known to be optimal for this class of subgradient schemes for solving non-
smooth convex problems with functional constraints. Moreover, our rates depend
explicitly on the minibatch size and show when minibatching works for a
subgradient method with random feasibility updates. To the best of our
knowledge, this is the first work proving that subgradient methods with random
minibatch feasibility steps are better than their non-minibatch variants. More
explicitly, the convergence estimate for the parallel algorithm depends on a
key parameter $L_{N}$, which determines whether minibatching helps ($L_{N}<1$)
or not ($L_{N}=1$) and how much (the smaller $L_{N}$, the better is the
complexity), see Theorem 2. For the sequential variant, we show that
minibatching always helps and the complexity depends exponentially on the
minibatch size (see Theorem 3).

Related works. The most prominent work for stochastic optimization problems is
stochastic gradient descent (SGD) MouBac:11 ; NemJud:09 ; PolJud:92 . Even
though SGD is a mature methodology, it only applies to optimization problems
with simple constraints, requiring the whole feasible set to be projectable. A
line of work that is known as alternating projections, focus on applying
random projections for solving problems that are involving the intersection of
(infinite) number of sets. The case when the objective function is not present
in the formulation, which corresponds to the convex feasibility problem, is
studied e.g. in BauBor:96 ; KeyZho:16 ; Ned:10 ; NecRic:18 . For this
particular setting, Ned:10 ; NecRic:18  combines the smoothing technique with
(minibatch) SGD, leading to stochastic alternating projection algorithms
having linear convergence rates. In PatNec:17  stochastic proximal point type
steps are combined with alternating projections for solving stochastic
optimization problems with infinite intersection of sets. In order to prove
sublinear convergence rates ${\cal O}(1/t)$, PatNec:17  requires smooth and
strongly convex objective functions, while our results are valid for a more
relaxed strong convexity assumption. Lastly, PatNec:17  assumes the
projectability of individual sets, whereas in our case, the constraints might
not be projectable. Stochastic forward-backward algorithms have been also
applied to solve optimization problems with many constraints. However, the
papers introducing those very general algorithms focused on proving
convergence and did not present convergence rates, or they assume the number
of constraints is finite, which is more restricted than our settings BiaHac:17
; SheTeb:14 ; WanChe:15 .

In the case where the number of constraints is finite and the objective
function is deterministic, Nesterov’s smoothing framework is studied in
BotHen:13 ; OuyGra:12 ; TraFer:18  in the setting of accelerated proximal
gradient methods. Incremental subgradient or primal-dual approaches were also
proposed for solving convex problems with finite intersection of simple sets
through an exact penalty reformulation in Ber:11 ; KunBac:18 . The paper most
related to our work is Ned:11 , where iterative subgradient methods with
random feasibility steps are proposed for solving convex problems with
functional constraints. Our algorithms are minibatch extensions of the
algorithm proposed in Ned:11 . Moreover, in Ned:11  only sublinear convergence
rates of order ${\cal O}(1/\sqrt{t})$ have been established for convex
objective functions, while in this paper we show that ${\cal O}(1/t)$ rates
are valid under a relaxed strong convexity condition. Finally, since we deal
with minibatching and a relaxed strong convexity assumption, our convergence
analysis requires additional insights that differ from that of Ned:11 .

Notation. The inner product of two vectors $x$ and $y$ in $\mathbb{R}^{n}$ is
denoted by $\langle x,y\rangle$, while $\|x\|$ denotes the standard Euclidean
norm. We write ${\rm dist}(\bar{x},X)$ for the distance of a vector $\bar{x}$
from a closed convex set $X$, i.e., ${\rm dist}(\bar{x},X)=\min_{x\in
X}\|x-\bar{x}\|$, while $\Pi_{X}[\bar{x}]$ denotes the projection of $\bar{x}$
onto $X$, i.e., $\Pi_{X}[\bar{x}]=\mathop{\rm argmin}_{x\in
X}\|x-\bar{x}\|^{2}$. For a scalar $a$, we write $a^{+}=\max\\{a,0\\}$. For a
convex function $h$, we denote $s_{h}(x)$ a subgradient of $h$ at $x$ and
$\partial h(x)$ denote the set of all subgradients of $h$ at $x$. We write
$\mathsf{Pr}\left\\{\omega\right\\}$ and $\mathsf{E}\\!\left[\omega\right]$ to
denote respectively the probability distribution and the expectation of a
random variable $\omega$.

###  1.1 Problem formulation

In this paper we are interested in solving the following convex constrained
minimization problem:

minimize $\displaystyle f(x)$ (1) subject to $\displaystyle x\in X,\quad
X\triangleq Y\cap\left(\cap_{\omega\in\mathscr{A}}X_{\omega})\right),$ (2)
with $\displaystyle X_{\omega}=\\{x\in\mathbb{R}^{n}\mid g_{\omega}(x)\leq
0\\}\qquad\hbox{for every $\omega\in\mathscr{A}$},$

where $\mathscr{A}$ is an arbitrary collection of indices. The objective
function $f$ and all constraint functions $g_{\omega}$ are assumed convex. We
also assume that the optimization problem (1) has finite optimum and we let
$f^{*}$ and $X^{*}$ denote the optimal value and the optimal set,
respectively,

$f^{*}=\inf_{x\in X}f(x),\qquad X^{*}=\\{x\in X\mid f(x)=f^{*}\\}.$

We work under the premise that the collection $\mathscr{A}$ is large, possibly
infinite (even uncountable). Let us now formally state the assumptions on the
functions $f$ and $g_{\omega}$, $\omega\in\mathscr{A}$, of problem (1).

###### Assumption 1

Let the following hold:

  * (a)

The set $Y$ is closed and convex, and the constraint set $X$ is nonempty.

  * (b)

The objective function $f:\mathbb{R}^{n}\to\mathbb{R}$ is restricted strongly
convex on the set $Y$ with a constant $\mu>0$, i.e., there exists $x^{*}\in
X^{*}$ such that

$f(x)\geq f(x^{*})+\frac{\mu}{2}\|x-x^{*}\|^{2}\quad\forall x\in Y.$

The subgradients of the function $f$ are uniformly bounded on the set $Y$,
i.e., there is $M_{f}>0$ such that

$\|s_{f}(x)\|\leq M_{f}\quad\forall s_{f}(x)\in\partial f(x)\;\hbox{and}\;x\in
Y.$

  * (c)

The functional constraints $g_{\omega}:\mathbb{R}^{n}\to\mathbb{R}$ are
convex, not necessarily differentiable, and have bounded subgradients on the
set $Y$, i.e., there is $M_{g}>0$ such that

$\|d\|\leq M_{g}\quad\forall d\in\partial g_{\omega}(x),\;x\in Y\;\hbox{and
}\;\omega\in\mathscr{A}.$

It is known that restricted strong convexity is a weaker condition than strong
convexity since it is implied by strong convexity along the direction of the
solution, see NecNes:15  for more details. Note that the conditions of
Assumption 1(b) may look contradictory since the following relations need to
hold:

$\frac{\mu}{2}\|x-x^{*}\|^{2}\leq f(x)-f(x^{*})\leq\langle
s_{f}(x),x-x^{*}\rangle\leq M_{f}\|x-x^{*}\|\quad\forall x\in
Y,x^{*}\\!\in\\!X^{*}\\!,$

where the second inequality follows from the convexity of $f$ and the third
one from the Cauchy-Schwartz inequality. This implies that $\|x-x^{*}\|\leq
2M_{f}/\mu$ for any $x\in Y$. Note that this inequality is always valid
provided that the set $Y$ is compact and our optimization model (1) allows us
to impose such an assumption on the set $Y$. In fact, the reader should note
that we can replace the boundedness on the subgradients of $f$, i.e.
assumption $\|s_{f}(x)\|\leq M_{f}$, with a more general assumption, that is
there exist two constants $M_{f,1},M_{f,2}\geq 0$ and $x^{*}\in X^{*}$ such
that:

$\|s_{f}(x)\|\leq M_{f,1}+M_{f,2}\|x-x^{*}\|\quad\forall s_{f}(x)\in\partial
f(x)\;\hbox{and}\;x\in Y.$

Clearly, this condition covers the class of functions with bounded gradients,
e.g. take $M_{f,2}=0$, and also the class of functions with Lipschitz
continuous gradients Nes:04 . Indeed, if there is $L_{f}>0$ such that
$\|\nabla f(x)-\nabla f(y)\|\leq L_{f}\|x-y\|$ for all $x,y\in Y$, then
$\|\nabla f(x)\|\leq\|\nabla f(x^{*})\|+\|\nabla f(x)-\nabla
f(x^{*})\|\leq\|\nabla f(x^{*})\|+L_{f}\|x-x^{*}\|$, which proves our
inequality for $M_{f,1}=\max_{x\in X^{*}}\|\nabla f(x^{*})\|$ and
$M_{f,2}=L_{f}$. All our derivations from the present work will hold under
this more general assumption, however, the recurrence relations will be more
cumbersome. Therefore, for the sake of simplicity, our convergence analysis is
derived under Assumption 1(b). Moreover, when the sets $X_{\omega}$ are simple
for projection operation, then one may choose an alternative equivalent
description of the constraint sets by letting $g_{\omega}(x)={\rm
dist}(x,X_{\omega})$ for all $x\in\mathbb{R}^{n}$. Note that in this case
$d(x)=\frac{x-\Pi_{X_{\omega}}[x]}{{\rm dist}(x,X_{\omega})}\in\partial
g_{\omega}(x)$ for all $x\not\in X_{\omega}$. Moreover, $\|d(x)\|=1$, thus the
subgradients are bounded with $M_{g}=1$ in this case. Therefore, our approach
is more general than those from most of the existing works (see Related works
paragraph from Section 1), which usually assume projectability of each
$X_{\omega}$.

##  2 Parallel random minibatch projections algorithm

To solve the convex problem with functional constraints (1), we first propose
a subgradient method with parallel random minibatch feasibility updates. More
precisely, our first algorithm is a parallel minibatch extension of the
algorithm proposed in Ned:11 . Let $x_{k-1}$ be available at iteration $k$,
and define the update:

$\displaystyle v_{k}=\Pi_{Y}[x_{k-1}-\alpha_{k-1}s_{f}(x_{k-1})],$ (3a)
$\displaystyle
z_{k}^{i}=v_{k}-\beta\,\frac{g^{+}_{\omega_{k}^{i}}(v_{k})}{\|d_{k}^{i}\|^{2}}\,d_{k}^{i}\qquad\qquad\hbox{for
}i=1,\ldots N,$ (3b) $\displaystyle x_{k}=\Pi_{Y}[\bar{z}_{k}],\quad\hbox{with
}\bar{z}_{k}=\frac{1}{N}\sum_{i=1}^{N}z_{k}^{i}.$ (3c)

Here, $\alpha_{k}>0$ and $\beta>0$ are deterministic stepsizes and recall that
$s_{f}(x)$ denotes a subgradient of $f$ at $x$ and
$g_{\omega}^{+}(x)=\max\\{g_{\omega}(x),0\\}$. The method takes one
subgradient step for the objective function, followed by $N$ feasibility
updates in parallel, which are then averaged and projected onto the set $Y$.
At each of the feasibility update step a random constraint is selected from
the collection of the constraint sets, i.e., the index variable
$\omega_{k}^{i}$ is random with values in the set $\mathscr{A}$. The vector
$d_{k}^{i}$ is chosen as $d_{k}^{i}\in\partial g^{+}_{\omega_{k}^{i}}(v_{k})$
if $g^{+}_{\omega_{k}^{i}}(v_{k})>0$ and $d_{k}^{i}=d$ for some $d\neq 0$ if
$g^{+}_{\omega_{k}^{i}}(v_{k})=0$. When $g^{+}_{\omega_{k}^{i}}(v_{k})=0$, we
have $z_{k}^{i}=v_{k}$ for any choice of $d\neq 0$. The initial point
$x_{0}\in Y$ is selected randomly with an arbitrary distribution. The
projection on the set $Y$ in the updates (3a) and (3c) is used to ensure that
each $v_{k}$ and $x_{k}$ remain in the set $Y$, over which the functions $f$
and $g_{\omega}$ are assumed to have bounded subgradients. Our next assumption
deals with the random variables $\omega_{k}^{i}$. For this, we introduce the
sigma-field $\mathscr{F}_{k}$ induced by the history of the method, i.e., by
the realizations of the initial point $x_{0}$ and the variables
$\omega_{t}^{i}$ up to main iteration $k$:

$\mathscr{F}_{k}=\\{x_{0}\\}\cup\left\\{\omega_{t}^{j}\mid\;1\leq t\leq
k,\;1\leq j\leq N\right\\},$

which contains the same information as the set
$\\{x_{0}\\}\cup\\{\\{v_{t},x_{t}\\}\mid 1\leq t\leq k\\}$. For notational
convenience, we will allow $k=0$ by letting $\mathscr{F}_{0}=\\{x_{0}\\}$. We
impose the following assumption.

###### Assumption 2

There exists a constant $c\in(0,\infty)$ such that

${\rm dist}^{2}(y,X)\leq
c\cdot\mathsf{E}\\!\left[(g^{+}_{\omega_{k}^{i}}(y))^{2}\mid\mathscr{F}_{k-1}\right]\quad\forall
y\in Y,\;k\geq 1\;\hbox{and }i=1,\ldots,N.$

Assumption 2 does not require that $\omega_{k}^{1},\ldots,\omega_{k}^{N}$ are
conditionally independent, given $\mathscr{F}_{k-1}$. For example, when the
collection $\mathscr{A}$ is finite, the indices $i\in\mathscr{A}$ can be
selected randomly without replacement, i.e., given the realizations of
$\omega_{k}^{1}=j_{1},\ldots,\omega_{k}^{i-1}=j_{i-1}$, the index
$\omega_{k}^{i}$ can be random with realizations in
$\mathscr{A}\setminus\\{j_{1},\ldots,j_{i-1}\\}$. As another example, the
index set $\mathscr{A}$ can be partitioned in $N$ disjoint sets
$\cup_{i=1}^{N}\mathscr{A}_{1}=\mathscr{A}$, and each $w_{k}^{i}$ can be
uniformly distributed over the index set $\mathscr{A}_{i}$. Such a sampling
allows for a parallel computation of all $z_{k}^{i}$ in the algorithm (3). One
can also combine the preceding two possibilities, by using a smaller partition
of the set $\mathscr{A}$, and in each of the partitions choose the
corresponding $\omega_{k}^{i}$ sequentially, without replacement. Assumption 2
is crucial in our convergence analysis of method (3). It summarizes all the
information we need regarding the distributions of the random variables
$\omega_{k}^{i}$ and the initial point $x_{0}$. A discussion on the connection
between the constant $c$ of Assumption 2 and the linear regularity constant
for the sets $X_{\omega}$ can be found in Ned:10 ; Ned:11 ; NecRic:18 . When
each set $X_{\omega}$ is given by either linear inequality or a linear
equality, one can verify that the sets are linearly regular, see BurFer:93 ;
NecRic:18 . Hence, Assumption 2 is also satisfied in this case. However,
Assumption 2 holds for more general sets, e.g., when a strengthened Slater
condition holds for the collection of functional constraints
$(X_{\omega})_{\omega\in\mathscr{A}}$ such as the generalized Robinson
condition, as detailed in Corollary 2 of LewPan:98 .

###  2.1 Preliminary results

In this section, we derive some preliminary results for later use in the
convergence analysis of method (3). We start by recalling a basic property of
the projection operation on a closed convex set $Y\subseteq\mathbb{R}^{n}$
Ned:10 :

$\|\Pi_{Y}[v]-y\|^{2}\leq\|v-y\|^{2}-\|\Pi_{Y}[v]-v\|^{2}\qquad\hbox{for any
$v\in\mathbb{R}^{n}$ and $y\in Y$.}$ (4)

We now show that the parameter $c$ in Assumption 2 satisfies the following
inequality:

###### Lemma 1

Let Assumption 1(c) and Assumption 2 hold. Then, we have:

$cM_{g}^{2}\geq 1.$

###### Proof

Let $y\in Y$ be such that $y\not\in X$. Then, there exists
$\bar{\omega}\in\mathscr{A}$ such that the convex function $g_{\bar{\omega}}$
satisfies $g_{\bar{\omega}}(y)>0$. Consequently, for any $s_{g}(y)\in\partial
g_{\bar{\omega}}(y)$ we also have $s_{g}(y)\in\partial
g_{\bar{\omega}}^{+}(y)$, and using convexity of $g_{\bar{\omega}}^{+}$, we
obtain:

$\displaystyle 0=g_{\bar{\omega}}^{+}(\Pi_{X}[y])\geq
g_{\bar{\omega}}^{+}(y)+\langle s_{g}(y),\Pi_{X}[y]-y\rangle\geq
g_{\bar{\omega}}^{+}(y)-M_{g}\|\Pi_{X}[y]-y\|,$

or equivalently

$g_{\bar{\omega}}^{+}(y)\leq M_{g}\|\Pi_{X}[y]-y\|.$

On the other hand for those $\omega\in\mathscr{A}$ for which $g_{\omega}(y)=0$
we automatically have

$0=g_{\omega}^{+}(y)\leq M_{g}\|\Pi_{X}[y]-y\|.$

In conclusion, for any $\omega\in\mathscr{A}$ there holds:

$g_{\omega}^{+}(y)\leq M_{g}\|\Pi_{X}[y]-y\|.$

Combining the preceding inequality and Assumption 2, we obtain:

$\displaystyle{\rm dist}^{2}(y,X)$ $\displaystyle=\|\Pi_{X}[y]-y\|^{2}\leq
c\mathsf{E}\\!\left[(g^{+}_{\omega_{k}^{i}}(y))^{2}\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\leq
c\mathsf{E}\\!\left[M_{g}^{2}\|\Pi_{X}[y]-y\|^{2}\mid\mathscr{F}_{k-1}\right]=cM_{g}^{2}\
{\rm dist}^{2}(y,X),$

which proves our relation $cM_{g}^{2}\geq 1$. $\square$

We now derive a relation between the iterates $v_{k+1}$ and $x_{k}$.

###### Lemma 2

Let Assumptions 1(a) and 1(b) hold. Let $v_{k+1}$ be obtained via equation
(3a) for a given $x_{k}\in Y$. Then, for any optimal solution $x^{*}$ of the
problem (1) and any $\rho\in(0,\;1)$, we have:

$\displaystyle\|v_{k+1}-x^{*}\|^{2}+2\alpha_{k}(1-\rho)\left(f(\Pi_{X}[x_{k}])-f^{*}\right)$
$\displaystyle\qquad\qquad\leq(1-\alpha_{k}\rho\mu)\|x_{k}-x^{*}\|^{2}+2\alpha_{k}(1-\rho)M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|+\alpha_{k}^{2}M_{f}^{2}.$

###### Proof

Using the standard analysis of the projected subgradient method and the fact
that the subgradients of $f$ are uniformly bounded on $Y$, we have for any
$x^{*}\in X^{*}$:

$\|v_{k+1}-x^{*}\|^{2}\leq\|x_{k}-x^{*}\|^{2}-2\alpha_{k}\left(f(x_{k})-f(x^{*})\right)+\alpha_{k}^{2}M_{f}^{2}.$
(5)

We provide a lower bound on $f(x_{k})-f(x^{*})$. We consider two choices,
namely, one is based on the restricted strong convexity of $f$ and the other
is based on considering another intermittent point. By the restricted strong
convexity of $f$, we have

$f(x_{k})-f(x^{*})\geq\frac{\mu}{2}\|x_{k}-x^{*}\|^{2}.$ (6)

The other choice consists of adding and subtracting $f(\Pi_{X}[x_{k}])$, which
yields

$\displaystyle f(x_{k})-f(x^{*})$
$\displaystyle=f(x_{k})-f(\Pi_{X}[x_{k}])+f(\Pi_{X}[x_{k}])-f(x^{*})$
$\displaystyle\geq-\|s_{f}(\Pi_{X}[x_{k}])\|\,\|\Pi_{X}[x_{k}]-x_{k}\|+f(\Pi_{X}[x_{k}])-f(x^{*}),$

where the last inequality follows by the convexity of $f$ and the Cauchy-
Schwarz inequality. By Assumption 1(b), the subgradients of $f$ are uniformly
bounded on $Y$ and hence, also on $X$, implying that

$f(x_{k})-f(x^{*})\geq
f(\Pi_{X}[x_{k}])-f(x^{*})-M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|.$ (7)

We now let $\rho\in(0,1)$ be arbitrary. By multiplying relation (6) with
$\rho$ and relation (7) with $(1-\rho)$, and by adding the resulting
relations, we obtain

$\displaystyle f(x_{k})-f(x^{*})$ $\displaystyle\geq$
$\displaystyle\frac{\rho\mu}{2}\|x_{k}-x^{*}\|^{2}$
$\displaystyle+(1-\rho)\left(f(\Pi_{X}[x_{k}])-f(x^{*})\right)-(1-\rho)M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|.$

By using the estimate (2.1) in relation (5), we obtain

$\displaystyle\|v_{k+1}-x^{*}\|^{2}$ $\displaystyle\leq$
$\displaystyle(1-\alpha_{k}\rho\mu)\|x_{k}-x^{*}\|^{2}-2\alpha_{k}(1-\rho)\left(f(\Pi_{X}[x_{k}])-f(x^{*})\right)$
(10)
$\displaystyle+2\alpha_{k}(1-\rho)M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|+\alpha^{2}_{k}M_{f}^{2},$

and after re-arranging some of the terms we get the relation of the lemma.
$\square$

###### Remark 1

The best choice for the parameter $\rho$ is not apparent at this point. It is
important to have it in order to have the function value involved in the
expression, but it can be that $\rho=\frac{1}{2}$ will just do fine.

We next state a result that will be used to provide a basic relation between
the iterates $v_{k}$ and $x_{k-1}$. The relation is stated in a generic form,
and its proof can be found in Pol:69 .

###### Lemma 3

Pol:69  Let $g$ be a convex function over a closed convex set $Z$, and let $y$
be given by

$y=\Pi_{Z}\left[v-\beta\frac{g^{+}(v)}{\|d\|^{2}}\,d\right]\qquad\hbox{for
$v\in Z$, $d\in\partial g^{+}(v)$ and $\beta>0$},$

where $d\neq 0$. Then, for any $\bar{z}\in Z$ such that $g^{+}(\bar{z})=0$, we
have

$\|y-\bar{z}\|^{2}\leq\|v-\bar{z}\|^{2}-\beta(2-\beta)\,\frac{(g^{+}(v))^{2}}{\|d\|^{2}}.$

In the analysis, we will also make use of the relation for averages, stating
that for given vectors $u_{1},\ldots,u_{N}\in\mathbb{R}^{n}$ and their average
$\bar{u}=\frac{1}{N}\sum_{i=1}^{N}u_{i}$, the following relation is valid for
any vector $w\in\mathbb{R}^{n}$:

$\|\bar{u}-w\|^{2}=\frac{1}{N}\sum_{i=1}^{N}\|u_{i}-w\|^{2}-\frac{1}{N}\sum_{j=1}^{N}\|u_{j}-\bar{u}\|^{2}.$
(11)

Now we provide a basic relation for the iterate $x_{k}$ upon completion of the
$N$ randomly sampled feasibility updates.

###### Lemma 4

Let Assumption 1(a) hold. Let $x_{k}$ be obtained via updates (3b) and (3c)
for a given $v_{k}\in Y$ and $\beta>0$. Then, the following relation holds:

$\displaystyle{\rm dist}^{2}(x_{k},X)\leq{\rm
dist}^{2}(v_{k},X)-\frac{\beta(2-\beta)}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}-\beta^{2}V_{N}(v_{k}),$

where $V_{N}(v_{k})$ is the total variation of the minibatch subgradients,
i.e.,

$V_{N}(v_{k})=\frac{1}{N}\sum_{i=1}^{N}\left\|\frac{g_{\omega_{k}^{i}}^{+}(v_{k})}{\|d_{k}^{i}\|^{2}}\,d_{k}^{i}-\frac{1}{N}\sum_{j=1}^{N}\frac{g_{\omega_{k}^{j}}^{+}(v_{k})}{\|d_{k}^{j}\|^{2}}\,d_{k}^{j}\right\|^{2}.$

###### Proof

By the projection property (4) and the definition of $x_{k}$, we have for any
$y\in X$ that:

$\|x_{k}-y\|^{2}\leq\left\|\bar{z}_{k}-y\right\|^{2}-\left\|x_{k}-\bar{z}_{k}\right\|^{2}.$
(12)

By the definition we have $\bar{z}_{k}=\frac{1}{N}\sum_{i=1}^{N}z_{k}^{i}$.
Thus, by using relation (11) for the collection $z_{k}^{1},\ldots,z_{k}^{N}$,
we have for any $w\in\mathbb{R}^{n}$,

$\left\|\bar{z}_{k}-w\right\|^{2}=\frac{1}{N}\sum_{i=1}^{N}\|z_{k}^{i}-w\|^{2}-\frac{1}{N}\sum_{i=1}^{N}\left\|z_{k}^{i}-\bar{z}_{k}\right\|^{2}.$
(13)

Letting $w=y$ in the preceding relation and combining the resulting relation
with (12), we obtain

$\|x_{k}-y\|^{2}\leq\frac{1}{N}\sum_{i=1}^{N}\|z_{k}^{i}-y\|^{2}-\frac{1}{N}\sum_{i=1}^{N}\left\|z_{k}^{i}-\bar{z}_{k}\right\|^{2}-\|x_{k}-\bar{z}_{k}\|^{2}.$

Now, we use the definition of the iterates $z_{k}^{i}$ in algorithm (3) and
Lemma 3, with $Z=\mathbb{R}^{n}$. Thus, we obtain for any $y\in X$ (for which
we would have $g_{\omega_{k}^{i}}^{+}(y)=0$ for any realization of
$\omega_{k}^{i}$) and for any $i=1,\ldots,N$,

$\|z_{k}^{i}-y\|^{2}\leq\|v_{k}-y\|^{2}-\beta(2-\beta)\,\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}.$

Hence, it follows that for any $y\in X$,

$\|x_{k}-y\|^{2}\leq\|v_{k}-y\|^{2}-\frac{\beta(2-\beta)}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}-\frac{1}{N}\sum_{i=1}^{N}\|z_{k}^{i}-\bar{z}_{k}\|^{2}-\|x_{k}-\bar{z}_{k}\|^{2}.$

From the definition of the iterates $z_{k}^{i}$ in algorithm (3), we see that

$\|z_{k}^{i}-\bar{z}_{k}\|^{2}=\beta^{2}\left\|\frac{g_{\omega_{k}^{i}}^{+}(v_{k})}{\|d_{k}^{i}\|^{2}}\,d_{k}^{i}-\frac{1}{N}\sum_{j=1}^{N}\frac{g_{\omega_{k}^{j}}^{+}(v_{k})}{\|d_{k}^{j}\|^{2}}\,d_{k}^{j}\right\|^{2}.$

By defining

$V_{N}(v_{k})=\frac{1}{N}\sum_{i=1}^{N}\left\|\frac{g_{\omega_{k}^{i}}^{+}(v_{k})}{\|d_{k}^{i}\|^{2}}\,d_{k}^{i}-\frac{1}{N}\sum_{j=1}^{N}\frac{g_{\omega_{k}^{j}}^{+}(v_{k})}{\|d_{k}^{j}\|^{2}}\,d_{k}^{j}\right\|^{2},$

we have

$\frac{1}{N}\sum_{i=1}^{N}\|z_{k}^{i}-\bar{z}_{k}\|^{2}=\beta^{2}V_{N}(v_{k}).$

Therefore, we obtain for any $y\in X$,

$\displaystyle\|x_{k}-y\|^{2}\leq\|v_{k}-y\|^{2}-\frac{\beta(2-\beta)}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}-\beta^{2}V_{N}(v_{k}).$
(14)

The statement of the lemma follows by letting $y=\Pi_{X}[v_{k}]$ in the
preceding relation and using the fact that
$\|x_{k}-\Pi_{X}[x_{k}]\|\leq\|x_{k}-\Pi_{X}[v_{k}\|\|$. $\square$

Let us define the following parameters:

$\displaystyle
L_{N}^{k}=\left\|\frac{1}{N}\sum_{i=1}^{N}\frac{g_{\omega_{k}^{i}}^{+}(v_{k})}{\|d_{k}^{i}\|^{2}}\,d_{k}^{i}\right\|^{2}\Big{/}\frac{1}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}\quad\text{and}\quad
L_{N}=\max_{k\geq 0}L_{N}^{k}.$ (15)

From Jensen’s inequality it follows that $L_{N}^{k}\leq 1$. However, there are
also convex functions $g_{\omega}$ such that $L_{N}^{k}<1$. We postpone the
derivation of such examples of functional constraints satisfying condition
$L_{N}^{k}<1$ until Section 2.3. The parameter $L_{N}\leq 1$ will play a key
role in our derivations below. In particular, we obtain the following
simplification for Lemma 4.

###### Lemma 5

Let Assumptions 1(a) and 1(c) hold. Let $L_{N}\leq 1$ as defined in (15) and
$x_{k}$ be obtained via updates (3b) and (3c) for a given $v_{k}\in Y$ and
$\beta\in(0,\,2/L_{N})$. Then, the following relation holds:

$\displaystyle{\rm dist}^{2}(x_{k},X)\leq{\rm
dist}^{2}(v_{k},X)-\frac{\beta(2-\beta
L_{N})}{NM_{g}^{2}}\sum_{i=1}^{N}(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}.$

###### Proof

Note that the total variation of the minibatch subgradients $V_{N}(v_{k})$ can
be written equivalently as:

$V_{N}(v_{k})=\frac{1}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}-\left\|\frac{1}{N}\sum_{i=1}^{N}\frac{g_{\omega_{k}^{i}}^{+}(v_{k})}{\|d_{k}^{i}\|^{2}}\,d_{k}^{i}\right\|^{2}.$

Using the previous expression of $V_{N}$ and the definitions of $L_{N}^{k}$
and $L_{N}$ from (15) in Lemma 4, we get:

$\displaystyle{\rm dist}^{2}(x_{k},X)\leq{\rm
dist}^{2}(v_{k},X)-\frac{\beta(2-\beta)}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}-\beta^{2}V_{N}(v_{k})$
$\displaystyle={\rm
dist}^{2}(v_{k},X)-\frac{\beta(2-\beta)}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}-\frac{\beta^{2}(1-L_{N}^{k})}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}$
$\displaystyle\leq{\rm dist}^{2}(v_{k},X)-\frac{\beta(2-\beta
L_{N})}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}$

By Assumption 1(c) each function $g_{i}$ has bounded subgradients uniformly on
$Y$. Hence, we have $\|d_{k}^{i}\|\leq M_{g}$, which used in the previous
inequality implies the statement of the lemma. $\square$

Note that the largest decrease in Lemma 5 is obtained by maximizing
$\beta(2-\beta L_{N})$, that is, the optimal stepsize is $\beta=1/L_{N}$. We
now combine Lemma 2 and Lemma 5 to provide a basic relation for the subsequent
analysis.

###### Lemma 6

Consider the method in (3), and let Assumption 1 hold. Let the stepsize
$\alpha_{k}$ be such that $1-\frac{\alpha_{k}\mu}{2}>0$ for all $k\geq 0$ and
stepsize $\beta\in(0,\;2/L_{N})$, with $L_{N}\leq 1$ defined in (15). Then,
the iterates of the method (3) satisfy the following recurrence for any
optimal solution $x^{*}\in X$ and for all $k\geq 0$:

$\displaystyle\|v_{k+1}-x^{*}\|^{2}+\alpha_{k}\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|v_{k}-x^{*}\|^{2}$
$\displaystyle\qquad-\left(1-\frac{\alpha_{k}\mu}{2}\right)\frac{\beta(2-\beta
L_{N})}{N\,M_{g}^{2}}\sum_{i=1}^{N}(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}+\frac{\eta}{2}\|\Pi_{X}[x_{k}]-x_{k}\|^{2}$
$\displaystyle\qquad+\alpha_{k}^{2}\left(1+\frac{1}{2\eta}\right)M_{f}^{2},$

where $\eta>0$ is arbitrary.

###### Proof

Let $x^{*}\in X$ be an optimal solution of problem (1). Then, we use Lemma 2
for $\rho=\frac{1}{2}$ so that for all $k\geq 0$, we have

$\displaystyle\|v_{k+1}-x^{*}\|^{2}$ $\displaystyle+$
$\displaystyle\alpha_{k}\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|x_{k}-x^{*}\|^{2}$
$\displaystyle+\alpha_{k}M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|+\alpha_{k}^{2}M_{f}^{2}.$

Using the same reasoning as in the proof of Lemma 5 for the inequality (14)
with $y=x^{*}$ gives:

$\displaystyle\|x_{k}-x^{*}\|^{2}$
$\displaystyle\leq\|v_{k}-x^{*}\|^{2}-\frac{\beta(2-\beta)}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}-\beta^{2}V_{N}(v_{k})$
$\displaystyle\leq\|v_{k}-x^{*}\|^{2}-\frac{\beta(2-\beta
L_{N})}{N\,M_{g}^{2}}\sum_{i=1}^{N}(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}.$

Combining the preceding two relations yields

$\displaystyle\|v_{k+1}-x^{*}\|^{2}+\alpha_{k}\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|v_{k}-x^{*}\|^{2}$
(16) $\displaystyle-\left(1-\frac{\alpha_{k}\mu}{2}\right)\frac{\beta(2-\beta
L_{N})}{N\,M_{g}^{2}}\sum_{i=1}^{N}(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}+\alpha_{k}M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|+\alpha_{k}^{2}M_{f}^{2}.$

We next approximate the term that is linear in $\alpha_{k}$, i.e.
$\alpha_{k}M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|$, with a sum of two quadratic terms,
one of which is in the order of $\alpha_{k}^{2}$, as:

$\displaystyle\alpha_{k}M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|$
$\displaystyle=(\alpha_{k}\sqrt{\eta^{-1}}M_{f})(\sqrt{\eta}\|\Pi_{X}[x_{k}]-x_{k}\|)$
$\displaystyle\leq\frac{1}{2}\left(\alpha_{k}^{2}\eta^{-1}M_{f}^{2}+\eta\|\Pi_{X}[x_{k}]-x_{k}\|^{2}\right),$

for any arbitrary $\eta>0$. Substituting the preceding estimate in (16), we
obtain the stated relation. $\square$

###  2.2 Convergence rates

In this section we derive the convergence rates of algorithm (3). For this, we
first provide a recurrence relation for the iterates in expectation, which is
the key relation for our convergence rate results. Note that $cM_{g}^{2}\geq
1$ according to Lemma 1 and $L_{N}\in(0,1]$. Thus, by increasing $c$, $M_{g}$
and/or $L_{N}$, we can always ensure that $cM_{g}^{2}L_{N}>1$. In the sequel,
we assume that $cM_{g}^{2}L_{N}>1$.

###### Theorem 2.1

Consider the iterative process (3), and let Assumption 1 and Assumption 2
hold. Let the stepsizes $\alpha_{k}$ be such that
$1-\frac{\alpha_{k}\mu}{2}>0$ for all $k\geq 0$ and $\beta\in(0,\;2/L_{N})$,
with $L_{N}\leq 1$ defined in (15). Then, for the algorithm (3), by defining
$q_{N}=\frac{\beta(2-\beta L_{N})}{cM_{g}^{2}}<1$, we have almost surely for
all $k\geq 0$,

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\mid\mathscr{F}_{k-1}\right]+\alpha_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|v_{k}-x^{*}\|^{2}-\frac{1}{2}\left(1-\frac{\alpha_{k}\mu}{2}\right)\frac{q_{N}}{1-q_{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\quad+\alpha_{k}^{2}\left(1+\frac{1-q_{N}}{q_{N}(2-\alpha_{k}\mu)}\right)M_{f}^{2}.$

###### Proof

From Lemma 6, by taking the conditional expectation on the past
$\mathscr{F}_{k-1}$, we have almost surely for all $k\geq 0$,

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\mathscr{F}_{k-1}\right]+\alpha_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\mid\mathscr{F}_{k-1}\right]$
(17)
$\displaystyle\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|v_{k}-x^{*}\|^{2}-\left(1-\frac{\alpha_{k}\mu}{2}\right)\frac{\beta(2-\beta
L_{N})}{NM_{g}^{2}}\sum_{i=1}^{N}\mathsf{E}\\!\left[(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}\mid\mathscr{F}_{k-1}\right]$
(18)
$\displaystyle\qquad+\frac{\eta}{2}\mathsf{E}\\!\left[\|\Pi_{X}[x_{k}]-x_{k}\|^{2}\mid\mathscr{F}_{k-1}\right]+\alpha_{k}^{2}\left(1+\frac{1}{2\eta}\right)M_{f}^{2},$
(19)

where $\eta>0$ is arbitrary. By Assumption 2, it follows that

$\mathsf{E}\\!\left[(g^{+}_{\omega_{k}^{i}}(v_{k}))^{2}\mid\mathscr{F}_{k-1}\right]\geq\frac{1}{c}{\rm
dist}^{2}(v_{k},X)\qquad\hbox{for all }i=1,\ldots,N.$

Hence

$\frac{1}{N}\sum_{i=1}^{N}\mathsf{E}\\!\left[(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}\mid\mathscr{F}_{k-1}\right]\geq\frac{1}{c}{\rm
dist}^{2}(v_{k},X).$ (20)

Taking the conditional expectation on the past $\mathscr{F}_{k-1}$ in the
relation of Lemma 4, and using relation (20), we obtain almost surely

$\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]\leq\left(1-q_{N}\right){\rm
dist}^{2}(v_{k},X),$

where we denote

$q_{N}=\frac{\beta(2-\beta L_{N})}{cM_{g}^{2}}.$ (21)

Recall that we assume $cM_{g}^{2}L_{N}>1$, then $q_{N}<1$ (since
$\max_{\beta}\beta(2-\beta L_{N})=1/L_{N}$). Hence, $1-q_{N}>0$. By dividing
with $1-q_{N}$, we further obtain

${\rm dist}^{2}(v_{k},X)\geq\frac{1}{1-q_{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right].$

Substituting the preceding estimate in relation (20), yields

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\mathsf{E}\\!\left[(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\geq$ $\displaystyle\frac{1}{c(1-q_{N})}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right].$ (22)

We now use estimate (22) in relation (17), and thus obtain

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\mathscr{F}_{k-1}\right]+\alpha_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|v_{k}-x^{*}\|^{2}-\left(1-\frac{\alpha_{k}\mu}{2}\right)\frac{\beta(2-\beta
L_{N})}{(1-q_{N})cM_{g}^{2}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\qquad+\frac{\eta}{2}\mathsf{E}\\!\left[\|\Pi_{X}[x_{k}]-x_{k}\|^{2}\mid\mathscr{F}_{k-1}\right]+\alpha_{k}^{2}\left(1+\frac{1}{2\eta}\right)M_{f}^{2}.$

By the definition of $q$ (see (21)), we have

$\frac{\beta(2-\beta L_{N})}{(1-q_{N})cM_{g}^{2}}=\frac{q_{N}}{1-q_{N}}.$

Hence,

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\mathscr{F}_{k-1}\right]+\alpha_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|v_{k}-x^{*}\|^{2}-\left(\left(1-\frac{\alpha_{k}\mu}{2}\right)\frac{q_{N}}{1-q_{N}}-\frac{\eta}{2}\right)\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\quad+\alpha_{k}^{2}\left(1+\frac{1}{2\eta}\right)M_{f}^{2},$

and by letting
$\eta=\left(1-\frac{\alpha_{k}\mu}{2}\right)\frac{q_{N}}{1-q_{N}}>0$, the
desired relation follows. $\square$

We now turn our attention to the stepsize $\alpha_{k}$. We consider
$\alpha_{k}$ of the form:

$\alpha_{k}=\frac{2}{\mu}\gamma_{k}\qquad\hbox{for all }k\geq 0,$

for some diminishing sequence $\gamma_{k}$ as detailed below. Indeed, for this
choice, the recurrence from Theorem 2.1 becomes:

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\mid\mathscr{F}_{k-1}\right]+\frac{2}{\mu}\gamma_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\mid\mathscr{F}_{k-1}\right]$
(23)
$\displaystyle\leq\left(1-\gamma_{k}\right)\|v_{k}-x^{*}\|^{2}-\frac{1}{2}\left(1-\gamma_{k}\right)\frac{q_{N}}{1-q_{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$ (24)
$\displaystyle\quad+\frac{4}{\mu^{2}}\gamma_{k}^{2}\left(1+\frac{1-q_{N}}{q_{N}(2-2\gamma_{k})}\right)M_{f}^{2},$

where recall that $q_{N}=\frac{\beta(2-\beta L_{N})}{cM_{g}^{2}}$. Let
$\gamma_{k}$ be given by

$\gamma_{k}=\frac{2}{k+1},\quad\hbox{hence the
stepsize}\quad\alpha_{k}=\frac{4}{\mu(k+1)},\;\;\;\forall k\geq 0.$

Since the sequence $\gamma_{k}$ is decreasing, we have

$\gamma_{k}\leq\frac{2}{3}\qquad\hbox{for all }k\geq 1,$

implying that

$1-\gamma_{k}\geq\frac{1}{3}\qquad\hbox{for all }k\geq 1.$

Using this estimate in (23), we obtain

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\mathscr{F}_{k-1}\right]+\frac{2}{\mu}\gamma_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\mid\mathscr{F}_{k-1}\right]$
(25)
$\displaystyle\leq\left(1-\gamma_{k}\right)\|v_{k}-x^{*}\|^{2}-\frac{1}{6}\frac{q_{N}}{1-q_{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$ (26)
$\displaystyle\quad+\frac{4}{\mu^{2}}\gamma_{k}^{2}\left(1+\frac{2(1-q_{N})}{q_{N}}\right)M_{f}^{2}.$

Next, we note that

$\frac{1-\gamma_{k}}{\gamma_{k}^{2}}\leq\frac{1}{\gamma_{k-1}^{2}}\qquad\qquad\hbox{for
all }k\geq 1.$

Dividing (25) by $\gamma_{k}^{2}$ and using the preceding inequality we have
for all $k\geq 1$, after taking total expectations and rearranging terms:

$\displaystyle\gamma_{k}^{-2}\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\right]+\frac{2}{\mu}\gamma_{k}^{-1}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\right]+\frac{\gamma_{k}^{-2}}{6}\frac{q_{N}}{1-q_{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\right]$
$\displaystyle\leq\gamma_{k-1}^{-2}\mathsf{E}\\!\left[\|v_{k}-x^{*}\|^{2}\right]+\frac{4}{\mu^{2}}\left(1+\frac{2(1-q_{N})}{q_{N}}\right)M_{f}^{2}.$

Summing these over $k=1,\ldots,t$, for some $t>0$, we obtain

$\displaystyle\gamma_{t}^{-2}\mathsf{E}\\!\left[\|v_{t+1}-x^{*}\|^{2}\right]+\frac{2}{\mu}\sum_{k=1}^{t}\gamma_{k}^{-1}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\right]$
(27)
$\displaystyle+\frac{1}{6}\frac{q_{N}}{1-q_{N}}\sum_{k=1}^{t}\gamma_{k}^{-2}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\right]\leq\gamma_{0}^{-2}\mathsf{E}\\!\left[\|v_{1}-x^{*}\|^{2}\right]+t\frac{4}{\mu^{2}}\left(1+\frac{2(1-q_{N})}{q_{N}}\right)M_{f}^{2}.$

Using the definition of $\gamma_{k}$, (27) implies

$\displaystyle\frac{(t+1)^{2}}{4}\mathsf{E}\\!\left[\|v_{t+1}-x^{*}\|^{2}\right]+\frac{1}{\mu}\sum_{k=1}^{t}(k+1)\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\right]$
(28)
$\displaystyle+\frac{q_{N}}{24(1\\!-\\!q_{N})}\\!\sum_{k=1}^{t}(k+1)^{2}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\right]\\!\leq\\!\frac{1}{4}\mathsf{E}\\!\left[\|v_{1}-x^{*}\|^{2}\right]+\\!\frac{4t}{\mu^{2}}\\!\left(1+\frac{2(1-q_{N})}{q_{N}}\right)\\!M_{f}^{2}.$

We finally obtain by the linearity of the expectation operation:

$\displaystyle\frac{(t+1)^{2}}{4}\mathsf{E}\\!\left[\|v_{t+1}-x^{*}\|^{2}\right]+\frac{1}{(t+1)\mu}\mathsf{E}\\!\left[\sum_{k=1}^{t}(k+1)^{2}\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\right]$
(29)
$\displaystyle\qquad+\frac{q_{N}}{24(1-q_{N})}\mathsf{E}\\!\left[\sum_{k=1}^{t}(k+1)^{2}\|x_{k}-\Pi_{X}[x_{k}]\|^{2}\right]$
(30)
$\displaystyle\leq\frac{1}{4}\mathsf{E}\\!\left[\|v_{1}-x^{*}\|^{2}\right]+\frac{4t}{\mu^{2}}\left(1+\frac{2(1-q_{N})}{q_{N}}\right)M_{f}^{2}.$

Define for $t\geq 1$ the sum

$S_{t}=\sum_{k=1}^{t}(k+1)^{2}\sim{\cal O}(t^{3}).$

Define also the following weighted averages (convex combinations)

$\displaystyle\hat{x}_{t}=\sum_{k=1}^{t}a_{k}\,x_{k},\qquad\hat{w}_{t}=\sum_{k=1}^{t}a_{k}\,\Pi_{X}[x_{k}],$
(31)

with $a_{k}=\frac{(k+1)^{2}}{S_{t}}$, hence satisfying
$\sum_{k=1}^{t}a_{k}=1$. Using convexity of the function $f$ and of the norm-
squared, we have

$\displaystyle\frac{(t+1)^{2}}{4}\mathsf{E}\\!\left[\|v_{t+1}-x^{*}\|^{2}\right]+\frac{S_{t}}{(t+1)\mu}\mathsf{E}\\!\left[\left(f(\hat{w}_{t})-f^{*}\right)\right]+\frac{q_{N}S_{t}}{24(1-q_{N})}\mathsf{E}\\!\left[\|\hat{w}_{t}-\hat{x}_{t}\|^{2}\right]$
(32)
$\displaystyle\leq\frac{1}{4}\mathsf{E}\\!\left[\|v_{1}-x^{*}\|^{2}\right]+\frac{4t}{\mu^{2}}\left(1+\frac{2(1-q_{N})}{q_{N}}\right)M_{f}^{2}.$
(33)

If we define $b_{N}^{p}=q_{N}(1-q_{N})^{-1}=(1-q_{N})^{-1}-1$, then (32)
becomes:

$\displaystyle\frac{(t+1)^{2}}{4}\mathsf{E}\\!\left[\|v_{t+1}-x^{*}\|^{2}\right]+\frac{S_{t}}{(t+1)\mu}\mathsf{E}\\!\left[\left(f(\hat{w}_{t})-f^{*}\right)\right]+\frac{b_{N}^{p}S_{t}}{24}\mathsf{E}\\!\left[\|\hat{w}_{t}-\hat{x}_{t}\|^{2}\right]$
(34)
$\displaystyle\leq\frac{1}{4}\mathsf{E}\\!\left[\|v_{1}-x^{*}\|^{2}\right]+\frac{4t}{\mu^{2}}\left(1+\frac{2}{b_{N}^{p}}\right)M_{f}^{2}.$
(35)

Next theorem summarizes the convergence rates followed from the previous
discussion. For simplicity of the exposition, we omit the constants and
express the rates only in terms of the dominant powers of $t$:

###### Theorem 2.2

Let Assumption 1 and Assumption 2 hold and the stepsizes
$\alpha_{k}=\frac{4}{\mu(k+1)}$ and $\beta\in(0,\;2/L_{N})$, with $L_{N}\leq
1$ defined in (15). Let also $q_{N}=\frac{\beta(2-\beta L_{N})}{cM_{g}^{2}}<1$
and $b_{N}^{p}=(1-q_{N})^{-1}-1$. Then, the following sublinear rates for
suboptimality and feasibility violation hold for the average sequence
$\hat{x}_{t}$ generated by the parallel algorithm (3):

$\mathsf{E}\\!\left[|f(\hat{x}_{t})-f^{*}|\right]\leq{\cal
O}\left(\frac{1}{t}+\frac{1}{\sqrt{b_{N}^{p}}t}\right),\quad\mathsf{E}\\!\left[{\rm
dist}_{X}(\hat{x}_{t})\right]\leq{\cal
O}\left(\frac{1}{\sqrt{b_{N}^{p}}t}\right).$

###### Proof

From the recurrence (34), omitting the constants but keeping the terms
depending on $b_{N}^{p}=(1-q_{N})^{-1}-1$, we get the following convergence
rates in terms of these weighted averages $\hat{w}_{t}$ and $\hat{x}_{t}$:

$\mathsf{E}\\!\left[f(\hat{w}_{t})-f^{*})\right]\leq{\cal
O}\left(\frac{1}{t}+\frac{1}{b_{N}^{p}t}\right)\quad\text{and}\quad\mathsf{E}\\!\left[\|\hat{w}_{t}-\hat{x}_{t}\|^{2}\right]\leq{\cal
O}\left(\frac{1}{b_{N}^{p}t^{2}}\right).$

Since $\hat{w}_{t}\in X$ and using the Jensen’s inequality we get the
following convergence rate for the feasibility violation of the constraints:

$\mathsf{E}\\!\left[{\rm
dist}_{X}(\hat{x}_{t})\right]\leq\mathsf{E}\\!\left[\|\hat{w}_{t}-\hat{x}_{t}\|\right]\leq\sqrt{\mathsf{E}\\!\left[\|\hat{w}_{t}-\hat{x}_{t}\|^{2}\right]}\leq{\cal
O}\left(\frac{1}{\sqrt{b_{N}^{p}}t}\right).$

Since $\hat{x}_{t}\in Y$ and $\hat{w}_{t}\in X\subset Y$, by the subgradient
boundedness of $f$ on $Y$, it follows that

$\mathsf{E}\\!\left[|f(\hat{x}_{t})-f(\hat{w}_{t})|\right]\leq
M_{f}\mathsf{E}\\!\left[\|\hat{x}_{t}-\hat{w}_{t}\|\right]\leq{\cal
O}\left(\frac{1}{\sqrt{b_{N}^{p}}t}\right),$

which combined with $\mathsf{E}\\!\left[f(\hat{w}_{t})-f^{*})\right]\leq{\cal
O}\left(\frac{1}{t}+\frac{1}{b_{N}^{p}t}\right)$, yields also the following
convergence rate for suboptimality

$\mathsf{E}\\!\left[|f(\hat{x}_{t})-f^{*}|\right]\leq{\cal
O}\left(\frac{1}{t}+\frac{1}{\sqrt{b_{N}^{p}}t}\right),$

which proves our theorem. $\square$

We observe that the convergence estimate for the feasibility violation depends
explicitly on the minibatch size $N$ via the key parameter $L_{N}$. For the
optimal stepsize $\beta=1/L_{N}$ we get $q_{N}=1/cM_{g}^{2}L_{N}$ and
$b_{N}^{p}=1/(cM_{g}^{2}L_{N}-1)$. Hence, $b_{N}^{p}$ is large provided that
$L_{N}\ll 1$ (small). Note that if $L_{N}=1$, then $b_{N}^{p}$ does not depend
on $N$ and hence complexity does not improve with minibatch size $N$. However,
as long as $L_{N}<1$ (and it can be also the case that $L_{N}\sim 0$), then
$b_{N}^{p}$ becomes large, which shows that minibatching improves complexity.
To the best of our knowledge, this is the first time that a subgradient method
with random minibatch feasibility updates is shown to be better than its non-
minibatch variant. We have identified $L_{N}$ as the key quantity determining
whether minibatching helps ($L_{N}<1$) or not ($L_{N}=1$), and how much (the
smaller $L_{N}$, the more it helps). Note also that the suboptimality estimate
contains a term which does not depend on the minibatch size $N$ as it happens
for feasibility violation estimate. This is natural, since the minibatch
feasibility steps have no effect on the minimization step of the objective
function.

###### Remark 2

Note that the convergence rates ${\cal O}\left(\frac{1}{t}\right)$ for
feasibility and suboptimality are known to be optimal for the stochastic
subgradient method for solving the optimization problem (1) under Assumption
1, see NemYud:83 ; Nes:04 . Moreover, the iterative process (3) does not
require knowledge of the subgradient norm bounds $M_{f}$ and $M_{g}$ from
Assumption 1, nor the constant $c$ from Assumption 2. These values are only
affecting the constants in the convergence rates, they are not needed for the
stepsize selection. The stepsize $\alpha_{k}$ requires only knowledge of some
estimate of the restricted strong convexity constant $\mu$. Moreover, since
$L_{N}\leq 1$, we can use e.g., stepsize
$\beta\in(0,\;2)\subseteq(0,\;2/L_{N})$. Of course, a larger stepsize $\beta$
leads to a faster convergence. Hence, if $L_{N}<1$ and it can be computed,
then we should choose an extrapolated steplength $\beta=(2-\delta)/L_{N}$ for
some $\delta\in(0,1)$ small. When $L_{N}$ cannot be computed explicitly, we
propose to approximate it online with $L_{N}^{k}$, and use at each iteration
an adaptive extrapolated stepsize $\beta_{k}$ of the form:

$\displaystyle\beta_{k}=\frac{2-\delta}{L_{N}^{k}}=\frac{2-\delta}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}\Big{/}\left\|\frac{1}{N}\sum_{j=1}^{N}\frac{g_{\omega_{k}^{j}}^{+}(v_{k})}{\|d_{k}^{j}\|^{2}}\,d_{k}^{j}\right\|^{2},$
(36)

for some $\delta\in(0,\;1)$ sufficiently small. The convergence rate of
algorithm (3) for this adaptive choice of the stepsize $\beta_{k}$ will be
analyzed in our future work.

###  2.3 Example of functional constraints having $L_{N}<1$

Let us recall the definition of the parameters $L_{N}^{k}$ and $L_{N}$ from
(15):

$\displaystyle
L_{N}^{k}=\left\|\frac{1}{N}\sum_{i=1}^{N}\frac{g_{\omega_{k}^{i}}^{+}(v_{k})}{\|d_{k}^{i}\|^{2}}\,d_{k}^{i}\right\|^{2}\Big{/}\frac{1}{N}\sum_{i=1}^{N}\frac{(g_{\omega_{k}^{i}}^{+}(v_{k}))^{2}}{\|d_{k}^{i}\|^{2}}\quad\text{and}\quad
L_{N}=\max_{k\geq 0}L_{N}^{k}.$

From Jensen’s inequality we have $L_{N}^{k}\leq 1$ and consequently $L_{N}\leq
1$. On the other hand, Theorem 2.2 shows that $L_{N}\ll 1$ is beneficial for a
subgradient scheme with minibatch feasibility updates. In this section we
provide an example of functional constraints $g_{\omega}$ for which $L_{N}<1$.
Let us consider $m$ linear inequality constraints for the convex problem (1):

$g_{\omega}(x)=a_{\omega}^{T}x+b_{\omega}\leq
0\quad\forall\omega\in\mathscr{A}=\\{1,2,\cdots,m\\}.$

Without loss of generality we assume $\|a_{\omega}\|=1$ for all $\omega$. Let
us define the matrix $A=[a_{1}\cdots a_{m}]^{T}$ and the subset of indexes
selected at the current iteration
$J_{k}=\\{\omega^{1}_{k}\cdots\omega^{N}_{k}\\}\subset\mathscr{A}$. We also
denote $J_{k}^{+}=\\{\omega\in J_{k}:a_{\omega}^{T}v_{k}+b_{\omega}>0\\}$ and
denote $A_{J_{k}^{+}}$ the submatrix of $A$ having the rows indexed in the set
$J_{k}^{+}$. With these notations and using that $\|a_{\omega}\|=1$ for all
$\omega$, then $L_{N}^{k}$ can be written explicitly as (assuming that
$|J_{k}^{+}|\geq 1$):

$\displaystyle L_{N}^{k}$ $\displaystyle=\left\|\frac{1}{N}\sum_{\omega\in
J_{k}^{+}}\frac{g_{\omega}^{+}(v_{k})}{\|d_{k}^{\omega}\|^{2}}\,d_{k}^{\omega}\right\|^{2}\Big{/}\frac{1}{N}\sum_{\omega\in
J_{k}^{+}}\frac{(g_{\omega}^{+}(v_{k}))^{2}}{\|d_{k}^{\omega}\|^{2}}$
$\displaystyle=\left\|\sum_{\omega\in
J_{k}^{+}}(a_{\omega}v_{k}+b_{\omega})a_{\omega}\right\|^{2}\Big{/}N\sum_{\omega\in
J_{k}^{+}}(a_{\omega}v_{k}+b_{\omega})^{2}$
$\displaystyle=\left\|A_{J_{k}^{+}}^{T}(A_{J_{k}^{+}}v_{k}+b_{J_{k}^{+}})\right\|^{2}/N\|A_{J_{k}^{+}}v_{k}+b_{J_{k}^{+}}\|^{2}$
$\displaystyle\leq\frac{\lambda_{\max}(A_{J_{k}^{+}}A_{J_{k}^{+}}^{T})}{N}\leq\frac{\lambda_{\max}(A_{J_{k}}A_{J_{k}}^{T})}{N}$
$\displaystyle<\frac{\text{Trace}(A_{J_{k}}A_{J_{k}}^{T})}{N}=1\quad\forall
k,$

where the first inequality follows from the definition of the maximal
eigenvalue $\lambda_{\max}$ of a matrix, the second inequality follows from
the fact that $J_{k}^{+}\subseteq J_{k}$, and the third inequality holds
strictly provided that the submatrix $A_{J_{k}}$ has at least rank two. In
conclusion, if the matrix $A$ has e.g. full row rank and consider a sampling
of $J_{k}$ based on a given probability P, then $L_{N}$ satisfies:

$\displaystyle L_{N}=\max_{J\in
2^{\mathscr{A}},|J|=N,J\sim\textbf{P}}\frac{\lambda_{\max}(A_{J}A_{J}^{T})}{N}<1.$
(37)

Note that for particular sampling rules we can compute $L_{N}$ efficiently,
such as when we consider a uniform distribution over a fixed partition of
$\mathscr{A}=\cup_{i=1}^{\ell}J_{i}$ of equal size. The reader may find other
examples of functional constraints satisfying $L_{N}<1$ and we believe that
this paper opens a window of opportunities for algorithmic research in this
direction.

##  3 Sequential random minibatch projections algorithm

In this section we consider a sequential variant of the algorithm (3) defined
in terms of the following iterative process:

$\displaystyle v_{k}=\Pi_{Y}[x_{k-1}-\alpha_{k-1}s_{f}(x_{k-1})],$ (38a)
$\displaystyle
z_{k}^{0}=v_{k},\;z_{k}^{i}=\Pi_{Y}\left[z_{k}^{i-1}-\beta\,\frac{g^{+}_{\omega_{k}^{i}}(z_{k}^{i-1})}{\|d_{k}^{i}\|^{2}}\,d_{k}^{i}\right]\qquad\hbox{for
}i=1,\ldots,N,$ (38b) $\displaystyle x_{k}=z_{k}^{N}.$ (38c)

This method takes, as for the parallel variant, one subgradient step for the
objective function, followed by $N$ sequential feasibility updates. As before,
the vector $d_{k}^{i}$ is chosen as $d_{k}^{i}\in\partial
g^{+}_{\omega_{k}^{i}}(z_{k}^{i-1})$ if $g^{+}_{\omega_{k}^{i}}(v_{k})>0$, and
$d_{k}^{i}=d$ for some $d\neq 0$ if $g^{+}_{\omega_{k}^{i}}(z_{k}^{i-1})=0$.
Note that in this variant, the feasibility updates use the projection on $Y$
in order to confine the intermittent iterates $z_{k}^{i}$ and $x_{k}$ to the
set $Y$, where $g_{\omega}$’s and $f$ (for the last step) are assumed to have
uniformly bounded subgradients.

In this section we analyze the convergence properties of this new algorithm
(38). Given $x_{k-1}$, the update of $v_{k}$ is the same as in the parallel
method (3), thus Lemma 2 still applies here. We need an analog of Lemmma 5.

###### Lemma 7

Let Assumptions 1(a) and 1(c) hold. Let $x_{k}$ be generated by algorithm (38)
with $\beta\in(0,\;2)$. Then, the following relations are valid:

$\displaystyle{\rm dist}^{2}(z_{k}^{i},X)\leq{\rm
dist}^{2}(z_{k}^{i-1},X)-\frac{\beta(2-\beta)}{M_{g}^{2}}\,(g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\hbox{
for all }i=1,\ldots,N,$
$\displaystyle\|x_{k}-y\|^{2}\leq\|v_{k}-y\|^{2}-\frac{\beta(2-\beta)}{M_{g}^{2}}\,\sum_{i=1}^{N}(g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\qquad\hbox{for
all }y\in X,$ $\displaystyle{\rm dist}^{2}(x_{k},X)\leq{\rm
dist}^{2}(v_{k},X)-\frac{\beta(2-\beta)}{M_{g}^{2}}\,\sum_{i=1}^{N}(g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\qquad\hbox{for
all }k\geq 1.$

###### Proof

We start with the definition of $z_{k}^{i}$ in (38b) and Lemma 3, with $Z=Y$.
Thus, we obtain for all $y\in X$ (which satisfies
$g_{\omega_{k}^{i}}^{+}(y)=0$ for any realization of $\omega_{k}^{i}$) and for
all $i=1,\ldots,N$,

$\|z_{k}^{i}-y\|^{2}\leq\|z_{k}^{i-1}-y\|^{2}-\beta(2-\beta)\,\frac{(g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}}{\|d_{k}^{i}\|^{2}}.$

By using $\|d_{k}^{i}\|^{2}\leq M_{g}^{2}$, we have for all $i=1,\ldots,N$,

$\|z_{k}^{i}-y\|^{2}\leq\|z_{k}^{i-1}-y\|^{2}-\frac{\beta(2-\beta)}{M_{g}^{2}}\,(g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}.$
(39)

The distance relation for $z$-iterates follows by taking the minimum over
$y\in X$ on both sides of inequality (39). By summing relations (39) over
$i=1,\ldots,N$, and by using $z^{0}_{k}=v_{k}$ and $z^{N}_{k}=x_{k}$, we
obtain for any $y\in X$,

$\|x_{k}-y\|^{2}\leq\|v_{k}-y\|^{2}-\frac{\beta(2-\beta)}{M_{g}^{2}}\,\sum_{i=1}^{N}(g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}.$

The distance relation follows by taking the minimum over $y\in X$ on both
sides of the preceding inequality. $\square$

Taking $\rho=1/2$ in Lemma 2 we get:

$\displaystyle\|v_{k+1}-x^{*}\|^{2}$ $\displaystyle+$
$\displaystyle\alpha_{k}\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|x_{k}-x^{*}\|^{2}$
$\displaystyle+\alpha_{k}M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|+\alpha_{k}^{2}M_{f}^{2},$

and using the inequality for $\|x_{k}-y\|^{2}$ from Lemma 7 in $y=x^{*}$,
yields:

$\displaystyle\|v_{k+1}-x^{*}\|^{2}+\alpha_{k}\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|v_{k}-x^{*}\|^{2}$
(40)
$\displaystyle-\left(1-\frac{\alpha_{k}\mu}{2}\right)\frac{\beta(2-\beta)}{M_{g}^{2}}\,\sum_{i=1}^{N}(g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}+\alpha_{k}M_{f}\|\Pi_{X}[x_{k}]-x_{k}\|+\alpha_{k}^{2}M_{f}^{2}.$

Taking the conditional expectation on $\mathscr{F}_{k-1}$ and $z_{k}^{i-1}$,
and using Assumption 2, give

$\mathsf{E}\\!\left[g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\mid\mathscr{F}_{k-1},z_{k}^{i-1}\right]\geq\frac{1}{c}{\rm
dist}(z_{k}^{i-1},X).$

Using the iterated expectation rule, we obtain

$\mathsf{E}\\!\left[g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\mid\mathscr{F}_{k-1}\right]=\mathsf{E}\\!\left[\mathsf{E}\\!\left[g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\mid\mathscr{F}_{k-1},z_{k}^{i-1}\right]\right]\geq\frac{1}{c}\mathsf{E}\\!\left[{\rm
dist}(z_{k}^{i-1},X)\right],$ (41)

which, when combined with the distance relation of Lemma 7 gives for all
$i=1,\ldots,N$

$\mathsf{E}\\!\left[{\rm
dist}^{2}(z_{k}^{i},X)\mid\mathscr{F}_{k-1}\right]\leq\left(1-\frac{\beta(2-\beta)}{cM_{g}^{2}}\right)\mathsf{E}\\!\left[{\rm
dist}^{2}(z_{k}^{i-1},X)\mid\mathscr{F}_{k-1}\right].$

Hence, using the definition of $x_{k}$, i.e., $x_{k}=z_{k}^{N}$, and letting
$q=\frac{\beta(2-\beta)}{cM_{g}^{2}}\in(0,1)$ (since we assume $cM_{g}^{2}>1$
and $\beta\in(0,2)$), we have for all $i=1,\ldots,N$,

$\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]\leq(1-q)^{N-i+1}\mathsf{E}\\!\left[{\rm
dist}^{2}(z_{k}^{i-1},X)\mid\mathscr{F}_{k-1}\right],$

implying that for all $i=1,\ldots,N$,

$\mathsf{E}\\!\left[{\rm
dist}^{2}(z_{k}^{i-1},X)\mid\mathscr{F}_{k-1}\right]\geq\frac{1}{(1-q)^{N-i+1}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right],$ (42)

From (41) and (42) for all $i=1,\ldots,N$,

$\mathsf{E}\\!\left[g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\mid\mathscr{F}_{k-1}\right]\geq\frac{1}{c}\frac{1}{(1-q)^{N-i+1}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right].$

By summing over $i$

$\sum_{i=1}^{N}\mathsf{E}\\!\left[g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\mid\mathscr{F}_{k-1}\right]\geq\frac{1}{c}\left(\sum_{i=1}^{N}\frac{1}{(1-q)^{N-i+1}}\right)\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right].$

However,

$\sum_{i=1}^{N}\frac{1}{(1-q)^{N-i+1}}=\frac{1}{(1-q)^{N+1}}\sum_{i=1}^{N}(1-q)^{i}=\frac{1-(1-q)^{N}}{q(1-q)^{N}}.$

Finally, we get

$\sum_{i=1}^{N}\mathsf{E}\\!\left[g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\mid\mathscr{F}_{k-1}\right]\geq\frac{1}{c}\frac{\left(1-(1-q)^{N}\right)}{q(1-q)^{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$

and consequently

$\displaystyle\frac{\beta(2-\beta)}{M_{g}^{2}}\,\sum_{i=1}^{N}\mathsf{E}\\!\left[(g_{\omega_{k}^{i}}^{+}(z_{k}^{i-1}))^{2}\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\geq\frac{\beta(2-\beta)}{cM_{g}^{2}}\frac{\left(1-(1-q)^{N}\right)}{q(1-q)^{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle=q\frac{\left(1-(1-q)^{N}\right)}{q(1-q)^{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle=\frac{\left(1-(1-q)^{N}\right)}{(1-q)^{N}}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle=\left((1-q)^{-N}-1\right)\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right].$

Let us denote $b_{N}^{s}=(1-q)^{-N}-1$. It is clear that $b_{N}^{s}\to\infty$
as $N\to\infty$. Taking expectation in (40) and using the previous inequality
we get an analog of Lemma 6:

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\mid\mathscr{F}_{k-1}\right]+\alpha_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\leq\left(1-\frac{\alpha_{k}\mu}{2}\right)\|v_{k}-x^{*}\|^{2}-\left(\left(1-\frac{\alpha_{k}\mu}{2}\right)b_{N}^{s}-\frac{\eta}{2}\right)\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\mid\mathscr{F}_{k-1}\right]$
$\displaystyle\qquad+\alpha_{k}^{2}\left(1+\frac{1}{2\eta}\right)M_{f}^{2},$

for any $\eta>0$. Let us consider the same stepsize as for the parallel
scheme, i.e. $\alpha_{k}=\frac{2}{\mu}\gamma_{k}$, choose
$\eta=\left(1-\frac{\alpha_{k}\mu}{2}\right)b_{N}^{s}>0$, and take the full
expectation, to get the following recurrence (analog to Theorem 2.1):

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\right]+\frac{2}{\mu}\gamma_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\right]\leq\left(1-\gamma_{k}\right)\mathsf{E}\\!\left[\|v_{k}-x^{*}\|^{2}\right]$
$\displaystyle-\frac{1}{2}\left(1-\gamma_{k}\right)b_{N}^{s}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\right]+\frac{4}{\mu^{2}}\gamma_{k}^{2}\left(1+\frac{1}{(2-2\gamma_{k})b_{N}}\right)M_{f}^{2}.$

Using now $\gamma_{k}=\frac{2}{k+1}$, then $1-\gamma_{k}\geq\frac{1}{3}$ and
we get:

$\displaystyle\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\right]+\frac{2}{\mu}\gamma_{k}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\right]\leq\left(1-\gamma_{k}\right)\mathsf{E}\\!\left[\|v_{k}-x^{*}\|^{2}\right]$
(43) $\displaystyle-\frac{1}{6}b_{N}^{s}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\right]+\frac{4}{\mu^{2}}\gamma_{k}^{2}\left(1+\frac{2}{b_{N}^{s}}\right)M_{f}^{2}.$
(44)

Since, $\frac{1-\gamma_{k}}{\gamma_{k}^{2}}\leq\frac{1}{\gamma_{k-1}^{2}}$ for
all $k\geq 1$, dividing (43) by $\gamma_{k}^{2}$ and using the preceding
inequality we have for all $k\geq 1$:

$\displaystyle\gamma_{k}^{-2}\mathsf{E}\\!\left[\|v_{k+1}-x^{*}\|^{2}\right]+\frac{2}{\mu}\gamma_{k}^{-1}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\right]$
$\displaystyle+\frac{\gamma_{k}^{-2}}{6}b_{N}^{s}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\right]\leq\gamma_{k-1}^{-2}\mathsf{E}\\!\left[\|v_{k}-x^{*}\|^{2}\right]+\frac{4}{\mu^{2}}\left(1+\frac{2}{b_{N}^{s}}\right)M_{f}^{2}.$

Summing these over $k=1,\ldots,t$, for some $t>0$, we obtain the following
recurrence relation for the algorithm (38):

$\displaystyle\gamma_{t}^{-2}\mathsf{E}\\!\left[\|v_{t+1}-x^{*}\|^{2}\right]+\frac{2}{\mu}\sum_{k=1}^{t}\gamma_{k}^{-1}\mathsf{E}\\!\left[\left(f(\Pi_{X}[x_{k}])-f^{*}\right)\right]$
(45)
$\displaystyle+\frac{b_{N}^{s}}{6}\sum_{k=1}^{t}\gamma_{k}^{-2}\mathsf{E}\\!\left[{\rm
dist}^{2}(x_{k},X)\right]\leq\gamma_{0}^{-2}\mathsf{E}\\!\left[\|v_{1}-x^{*}\|^{2}\right]+t\frac{4}{\mu^{2}}\left(1+\frac{2}{b_{N}^{s}}\right)M_{f}^{2}.$

Using the same definition for the weighted averages $\hat{w}_{t}$ and
$\hat{x}_{t}$ from (31) and $\gamma_{k}=\frac{2}{k+1}$ in (45), we get the
main recurrence for the sequential variant (38):

$\displaystyle\frac{(t+1)^{2}}{4}\mathsf{E}\\!\left[\|v_{t+1}-x^{*}\|^{2}\right]+\frac{S_{t}}{(t+1)\mu}\mathsf{E}\\!\left[\left(f(\hat{w}_{t})-f^{*}\right)\right]+\frac{b_{N}^{s}S_{t}}{24}\mathsf{E}\\!\left[\|\hat{w}_{t}-\hat{x}_{t}\|^{2}\right]$
(46)
$\displaystyle\leq\frac{1}{4}\mathsf{E}\\!\left[\|v_{1}-x^{*}\|^{2}\right]+\frac{4t}{\mu^{2}}\left(1+\frac{2}{b_{N}^{s}}\right)M_{f}^{2}.$
(47)

Next theorem summarizes the convergence rates that follow from the recurrence
relation (46) of the sequential algorithm (38).

###### Theorem 3.1

Let Assumption 1 and Assumption 2 hold and the stepsizes $\beta\in(0,2)$ and
$\alpha_{k}=\frac{4}{\mu(k+1)}$. Let also
$q=\frac{\beta(2-\beta)}{cM_{g}^{2}}<1$ and $b_{N}=(1-q)^{-N}-1$. Then, the
following sublinear rates for suboptimality and feasibility violation hold for
the average sequence $\hat{x}_{t}$ from (31) generated by the sequential
algorithm (38):

$\mathsf{E}\\!\left[|f(\hat{x}_{t})-f^{*}|\right]\leq{\cal
O}\left(\frac{1}{t}+\frac{1}{\sqrt{b_{N}^{s}}t}\right),\quad\mathsf{E}\\!\left[{\rm
dist}_{X}(\hat{x}_{t})\right]\leq{\cal
O}\left(\frac{1}{\sqrt{b_{N}^{s}}t}\right).$

###### Proof

Defining the same average sequences $\hat{w}_{t}$ and $\hat{x}_{t}$ as in
(31), we get the following convergence rates (omitting the constants but
keeping the terms depending on $b_{N}^{s}$):

$\mathsf{E}\\!\left[f(\hat{w}_{t})-f^{*})\right]\leq{\cal
O}\left(\frac{1}{t}+\frac{1}{b_{N}^{s}t}\right),\qquad\mathsf{E}\\!\left[\|\hat{w}_{t}-\hat{x}_{t}\|^{2}\right]\leq{\cal
O}\left(\frac{1}{b_{N}^{s}t^{2}}\right).$

Hence, we get the following convergence rate for the feasibility violation of
the constraints that depends explicitly on the minibatch size $N$ via the term
$b_{N}$:

$\mathsf{E}\\!\left[{\rm dist}_{X}^{2}(\hat{x}_{t})\right]\leq{\cal
O}\left(\frac{1}{b_{N}^{s}t^{2}}\right).$

Using the same reasoning as in the proof of Theorem 2.2, we also get the
following convergence rate for suboptimality:

$\mathsf{E}\\!\left[|f(\hat{x}_{t})-f^{*}|\right]\leq{\cal
O}\left(\frac{1}{t}+\frac{1}{\sqrt{b_{N}^{s}}t}\right),$

which proves the statements of the theorem. $\square$

We observe that also for the sequential algorithm (38) the convergence
estimate for the feasibility violation depends explicitly on the minibatch
size $N$ via the term $b_{N}^{s}$ (recall that $b_{N}^{s}\to\infty$ as
$N\to\infty$). Since $b_{N}^{s}$ is an increasing sequence in $N$, it follows
that the larger is the minibatch size $N$ the better is also the complexity of
the sequential algorithm (38) in terms of constraints feasibility. In
conclusion, for the sequential variant our rates prove that minibatching
always helps and the feasibility estimate depends exponentially on the
minibatch size. On the other hand, the suboptimality estimate contains a term
which does not depend on the minibatch size $N$ as it happens for feasibility
violation estimate.

##  4 Conclusions

In this paper we have considered non-smooth convex optimization problems with
(possibly) infinite intersection of constraints. For solving this general
class of convex problems we have proposed subgradient algorithms with random
minibatch feasibility steps. At each iteration, our algorithms take first a
step for minimizing the objective function and then a subsequent step
minimizing the feasibility violation of the observed minibatch of constraints.
The feasibility updates were performed based on either parallel or sequential
random observations of several constraint components. For a diminishing
stepsize and for restricted strongly convex objective functions, we have
proved sublinear convergence rates for the expected distances of the weighted
averages of the iterates from the constraint set, as well as for the expected
suboptimality of the function values along the weighted averages. Our
convergence rates are optimal for subgradient methods with random feasibility
steps for solving this class of non-smooth convex problems. Moreover, the
rates depend explicitly on the minibatch size. From our knowledge, this work
is the first proving that subgradient methods with random minibatch
feasibility updates have better complexity than their non-minibatch variants.

###### Acknowledgements.

This research was supported by the National Science Foundation under CAREER
grants CMMI 07-42538 and by the Executive Agency for Higher Education,
Research and Innovation Funding (UEFISCDI), Romania, PNIII-P4-PCE-2016-0731,
project ScaleFreeNet, no. 39/2017.

## References

  * (1) D. Blatt and A.O. Hero, Energy based sensor network source localization via projection onto convex sets, IEEE Transactions on Signal Processing, 54(9): 3614–3619, 2006.
  * (2) H. Bauschke and J. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review 38(3): 367-376, 1996.
  * (3) R.I. Bot and C. Hendrich, A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems, Computational Optimization and Applications, 54 (2): 239–262, 2013.
  * (4) R.I. Bot and T. Hein, Iterative regularization with general penalty term - theory and application to $L_{1}$ and TV regularization, Inverse Problems, 28, 2012.
  * (5) J. Burke and M. Ferris, _Weak sharp minima in mathematical programming_ , SIAM Journal of Control and Optimization, 31(6): 1340–1359, 1993.
  * (6) P. Bianchi, W. Hachem, and A. Salim, A constant step forward-backward algorithm involving random maximal monotone operators, arXiv:1702.04144, 2017.
  * (7) D.P. Bertsekas, Incremental proximal methods for large scale convex optimization, Mathematical Programming, 129(2), 2011.
  * (8) K. Keys, H. Zhou and K. Lange, Proximal Distance Algorithms: Theory and Practice, ArXiv e-prints, 2016.
  * (9) A. Kundu, F. Bach, and C. Bhattacharya, Convex optimization over inter-section of simple sets: improved convergence rate guarantees via an exact penalty approach, arxiv.org/abs/1710.06465, 2017.
  * (10) A. Lewis and J. Pang, Error bounds for convex inequality systems, in Generalized Convexity, Generalized Monotonicity (J. Crouzeix, J. Martinez-Legaz, and M. Volle, eds.), Cambridge University Press, 75–110, 1998.
  * (11) E. Moulines and F.R. Bach, Non-asymptotic analysis of stochastic approximation algorithms for machine learning, Advances in Neural Infor. Process. Syst., 2011.
  * (12) I. Necoara, Yu. Nesterov and F. Glineur, Linear convergence of first order methods for non-strongly convex optimization, Mathematical Programming, doi.org/10.1007/s10107-018-1232-1, 2018.
  * (13) I. Necoara, P. Richtarik and A. Patrascu, Randomized projection methods for convex feasibility problems, submitted to SIAM Journal on Optimization, 2018.
  * (14) A. Nedić, _Random projection algorithms for convex set intersection Problems_ , IEEE Conference on Decision and Control, 7655–7660, 2010.
  * (15) A. Nedić, Random algorithms for convex minimization problems, Math. Program., 129(2): 225-273, 2011.
  * (16) A. Nemirovski, A. Juditsky, G. Lan and A. Shapiro, Robust stochastic approximation approach to stochastic programming, SIAM J. on Optimization, 19(4):1574–1609, 2009.
  * (17) A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization, John Wiley & Sons, 1983.
  * (18) Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer, Boston, 2004.
  * (19) H. Ouyang and A. Gray, Stochastic smoothing for nonsmooth minimizations: Accelerating SGD by exploiting structure, arXiv:1205.4481, 2012.
  * (20) A. Patrascu and I. Necoara, Nonasymptotic convergence of stochastic proximal point algorithms for constrained convex optimization, Journal of Machine Learning Research, 18(198): 1–42, 2018.
  * (21) B.T. Polyak, Minimization of unsmooth functionals, U.S.S.R. Comput. Math. and Math. Phys. 9: 14–29, 1969.
  * (22) B.T. Polyak and A. B. Juditsky, Acceleration of stochastic approximation by averaging, SIAM Journal on Control and Optimization, 30(4): 838–855, 1992.
  * (23) R. Shefi and M. Teboulle, Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization, SIAM Journal on Optimization, 24(1): 269–297, 2014.
  * (24) Q. Tran-Dinh, O. Fercoq, and V. Cevher, A smooth primal-dual optimization framework for nonsmooth composite convex minimization, SIAM Journal on Optimization, 28 (1): 96–134, 2018.
  * (25) V. Vapnik, Statistical learning theory, John Wiley, 1998.
  * (26) M. Wang, Y. Chen, J. Liu and Y. Gu, Random multiconstraint projection: stochastic gradient methods for convex optimization with many constraints, arXiv:1511.03760, 2015.