# A single cut proximal bundle method for stochastic convex composite
optimization

Jiaming Liang Vincent Guigues Renato D.C. Monteiro Department of Computer
Science, Yale University, New Haven, CT 06511 (email<EMAIL_ADDRESS>School of Data Science, The Chinese University of Hong Kong, Shenzhen, 518172,
China (email: liangjiaming@cuhk.edu.cn).School of Applied Mathematics
FGV/EMAp, 22250-900 Rio de Janeiro, Brazil. (email:
vincent.guigues@fgv.br).School of Industrial and Systems Engineering, Georgia
Institute of Technology, Atlanta, GA 30332. (email:
renato.monteiro@isye.gatech.edu). This work was partially supported by AFORS
Grant FA9550-22-1-0088.

(July 18, 2022)

###### Abstract

In this paper, we consider optimization problems where the objective is the
sum of a function given by an expectation and a Lipschitz continuous convex
function. For such problems, we propose a Stochastic Composite Proximal Bundle
(SCPB) method with optimal complexity. The method does not require estimation
of parameters involved in the assumptions on the objective functions.
Moreover, to the best of our knowledge, this is the first proximal bundle
method for stochastic programming able to deal with continuous distributions.
Finally, we present the results of numerical experiments where SCPB slightly
outperforms Stochastic Mirror Descent.

Keywords. stochastic nonsmooth composite optimization, iteration-complexity,
proximal bundle method, optimal complexity bound.

AMS subject classifications. 49M37, 65K05, 68Q25, 90C25, 90C30, 90C60.

##  1 Introduction

The main goal of this paper is to propose and study the complexity of a
stochastic composite proximal bundle (SCPB) framework to solve the stochastic
convex composite optimization (SCCO) problem

$\phi_{*}:=\min\left\\{\phi(x):=f(x)+h(x):x\in\mathbb{R}^{n}\right\\}$ (1)

where

$f(x)=\mathbb{E}_{\xi}[F(x,\xi)].$ (2)

We assume the following conditions hold: i)
$f,h:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$ are proper closed
convex functions such that $\mathrm{dom}\,h\subseteq\mathrm{dom}\,f$; ii) $h$
is $M_{h}$-Lipschitz continuous on $\mathrm{dom}\,h$ for some
$M_{h}\in\mathbb{R}_{+}$; iii) a stochastic first-order oracle, which for
every $x\in\mathrm{dom}\,h$ and almost every random vector $\xi$ returns
$s(x,\xi)$ such that $\mathbb{E}[s(x,\xi)]\in\partial f(x)$, is available; and
iv) for every $x\in\mathrm{dom}\,h$, $\mathbb{E}[\|s(x,\xi)\|^{2}]\leq M^{2}$
for some $M\in\mathbb{R}_{+}$.

Literature Review. Methods for solving (1) where $f$ can efficiently be
computed exactly (e.g., $\xi$ is a discrete random vector with small support)
have been discussed for example in [2, 3] and are usually based on solving a
deterministic (but large-scale) reformulation of (1), usually using
decomposition (such as the L-shaped method [22]) possibly combined with
regularization as in [9, 8].

Solution methods for problem (1) in which $\xi$ has a continuous distribution
are basically based on one of the following three ideas: i) a single (usually
expensive) approximation of (1) where $f$ is approximated by a Monte Carlo
average $H_{N}(x):=\sum_{i=1}^{N}F(\cdot,\xi_{i})/N$ for a large i.i.d. sample
$(\xi_{1},\ldots,\xi_{N})$ of $\xi$ is constructed at the beginning of the
method and is then solved to yield an approximation solution of (1) (SAA type
methods); see for instance [23, 11, 20, 10, 7] and also Chapter 5 of [21] for
their complexity analysis; ii) simple approximations of (1) are constructed at
every iteration based on a small (usually a single) sample and their solutions
are used to obtain an approximation solution of (1) (SA type methods); SA type
methods have been originally proposed in [19] and further extended in [15, 17,
18, 16, 14, 5, 6]; and iii) hybrid type methods which sit in between SAA and
SA type ones in that they use partial Monte Carlo averages $H_{k}(\cdot)$ (and
their expensive subgradients) for increasing iteration indices $k$ [9].

Contributions. Although cutting plane methodology can be used in the context
of SAA methods to solve single approximations of (1) generated at their
outset, such methodology has not been used in the context of SA type methods.
This paper partially addresses this issue by developing a regularized
aggregate cutting plane scheme for solving (1) where some of the most recent
(linear approximation) cuts (in expectation) are combined, i.e., a suitable
convex combination of them is chosen, so that a single aggregated cut (in
expectation) is obtained. More specifically, two proximal (aggregated one cut)
bundle variants are proposed which can be viewed as natural extensions of the
one-cut variant developed in [13] (based on the analysis of [12]) for solving
the deterministic version of (1). At every iteration, the SCPB framework
solves the prox bundle subproblem

$x=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\Gamma(u)+\frac{1}{2{\lambda}}\|u-x^{c}\|^{2}\right\\}$
(3)

where ${\lambda}>0$ is the prox stepsize, $x^{c}$ is the current prox-center,
and $\Gamma$ is the current bundle function in expectation, i.e., it satisfies
$\mathbb{E}[\Gamma(\cdot)]\leq\phi(\cdot)$. As in the proximal bundle method
of [13], it also performs two types of iterations, i.e., serious or null ones.
In the beginning of a serious iteration, the prox-center is updated to
$x^{c}\leftarrow x$ and the bundle function $\Gamma$ is chosen to be the
composite linear approximation of $F(\cdot,\xi)+h$ at $x$ given by
$F(x,\xi)+\langle s(x,\xi),\cdot-x\rangle+h(\cdot)$ for some new independent
sample $\xi$. In a null iteration, the prox-center remains the same but
$\Gamma$ is set to be a convex combination of the previous bundle function and
the above composite linear approximation of $F(\cdot,\xi)+h(\cdot)$ at $x$. It
is then shown that both variants of SCPB obtain an $\bar{\varepsilon}$-pair
$(y,u)\in\mathbb{R}^{n}\times\mathbb{R}$ of (1), i.e., satisfying

$\mathbb{E}[\phi(y)]-\phi_{*}\leq\mathbb{E}[u]-\phi_{*}\leq\bar{\varepsilon}$

where $\phi_{*}$ is as in (1), in ${\cal O}(\bar{\varepsilon}^{-2})$
iterations/resolvent evaluations. To our knowledge, this is the first SA type
proximal bundle method for SCCO problems where $\xi$ can have a continuous
distribution.

Organization of the paper. The paper is laid out as follows. In Section 2 the
assumptions on the problem data and the SCPB framework are given. This
framework involves a sequence $\\{j_{k}\\}$ determining the length of the
cycles. Two sets of sequences $\\{j_{k}\\}$ are considered (see (B1) and (B2))
for the complexity analysis. The complexity analysis of the corresponding SCPB
variants is given in Theorem 2.1 for variant (B1) and in Theorem 2.2 for
variant (B2). The proof of Theorem 2.1 is given in Section 3 while the proof
of Theorem 2.2 is given in Section 4. Finally, numerical experiments are
reported in Section 5.

###  1.1 Basic definitions and notation

The sets of real numbers and non-negative real numbers are denoted by
$\mathbb{R}$ and $\mathbb{R}_{+}$, respectively. Let $\mathbb{R}^{n}$ denote
the standard $n$-dimensional Euclidean space equipped with inner product and
norm denoted by $\left\langle\cdot,\cdot\right\rangle$ and $\|\cdot\|$,
respectively.

Let $\psi:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ be given. The effective
domain of $\psi$ is denoted by
$\mathrm{dom}\,\psi:=\\{x\in\mathbb{R}^{n}:\psi(x)<\infty\\}$ and $\psi$ is
proper if $\mathrm{dom}\,\psi\neq\emptyset$. Moreover, a proper function
$\psi:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ is $\mu$-convex for some
$\mu\geq 0$ if

$\psi(\alpha
z+(1-\alpha)u)\leq\alpha\psi(z)+(1-\alpha)\psi(u)-\frac{\alpha(1-\alpha)\mu}{2}\|z-u\|^{2}$

for every $z,u\in\mathrm{dom}\,\psi$ and $\alpha\in[0,1]$. The set of all
proper lower semicontinuous convex functions
$\psi:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ is denoted by
$\overline{\mbox{\rm Conv}}\,(\mathbb{R}^{n})$. For $\varepsilon\geq 0$, the
_$\varepsilon$ -subdifferential_ of $\psi$ at $z\in\mathrm{dom}\,\psi$ is
denoted by
$\partial_{\varepsilon}\psi(z):=\left\\{s\in\mathbb{R}^{n}:\psi(u)\geq\psi(z)+\left\langle
s,u-z\right\rangle-\varepsilon,\forall u\in\mathbb{R}^{n}\right\\}$. The
subdifferential of $\psi$ at $z\in\mathrm{dom}\,\psi$, denoted by
$\partial\psi(z)$, is by definition the set $\partial_{0}\psi(z)$. We use the
notation $\xi_{[t]}=(\xi_{0},\xi_{1},\ldots,\xi_{t})$ for the history of the
sampled observations of $\xi$ up to iteration $t$.

##  2 Assumptions and the SCPB framework

This section presents the assumptions made on problem (1) and states the SCPB
framework for solving it. It then presents two main complexity results
corresponding to two natural instances of the framework. Viewing a cycle as a
sequence of iterations consisting of a serious one and the subsequent
consecutive null ones, these variants essentially differ in the way the number
of iterations within each cycle is determined.

###  2.1 Assumptions

Let $\Xi$ denote the support of random vector $\xi$. For some pair
$(M,M_{h})\in\mathbb{R}_{+}^{2}$, the following conditions on (1)-(2) are
assumed to hold:

  * (A1)

$h\in\overline{\mbox{\rm Conv}}\,(\mathbb{R}^{n})$ is $M_{h}$-Lipschitz
continuous on its domain, i.e., $|h(x)-h(x^{\prime})|\leq
M_{h}\|x-x^{\prime}\|$ for every $x,x^{\prime}\in\mathrm{dom}\,h$;

  * (A2)

$f\in\overline{\mbox{\rm Conv}}\,(\mathbb{R}^{n})$ is such that
$\mathrm{dom}\,f\supset\mathrm{dom}\,h$;

  * (A3)

for almost every $\xi\in\Xi$, a functional oracle
$F(\cdot,\xi):\mathrm{dom}\,h\to\mathbb{R}$ and a stochastic subgradient
oracle $s(\cdot,\xi):\mathrm{dom}\,h\to\mathbb{R}^{n}$ satisfying

$f(x)=\mathbb{E}[F(x,\xi)],\quad
f^{\prime}(x):=\mathbb{E}[s(x,\xi)]\in\partial f(x)$

for every $x\in\mathbb{R}^{n}$ are available;

  * (A4)

for every $x\in\mathrm{dom}\,h$, we have $\mathbb{E}[\|s(x,\xi)\|^{2}]\leq
M^{2}$;

  * (A5)

$\mathrm{dom}\,h$ has a finite diameter $D>0$;

  * (A6)

the set of optimal solutions $X^{*}$ of (1)-(2) is nonempty.

We now make some observations about Assumptions (A1)-(A6). First, as in [14],
function $F(\cdot)$ is not assumed to convex. Second, Assumption (A4) implies
that

$\|f^{\prime}(x)\|=\|\mathbb{E}[s(x,\xi)]\|\leq\mathbb{E}[\|s(x,\xi)\|]\leq\left(\mathbb{E}[\|s(x,\xi)\|^{2}]\right)^{1/2}\leq
M\quad\forall x\in\mathrm{dom}\,h.$ (4)

Third, defining for every $\xi\in\Xi$ and $x\in\mathrm{dom}\,h$,

$\Phi(\cdot,\xi)=F(\cdot,\xi)+h(\cdot),\quad\ell_{\Phi}(\cdot;x,\xi)=F(x,\xi)+\langle
s(x,\xi),\cdot-x\rangle+h(\cdot),$ (5)

it follows from (A3), the second identity in (5), and the convexity of $f$ by
(A2), that

$\mathbb{E}[\Phi(\cdot,\xi)]=\phi(\cdot)\geq f(x)+\langle
f^{\prime}(x),\cdot-x\rangle+h(\cdot)=\mathbb{E}[\ell_{\Phi}(\cdot;x,\xi)]$
(6)

where $\phi(\cdot)$ is as in (1).

###  2.2 The SCPB framework and main results

At the end of every iteration $j\geq 1$ (as well as at the beginning of the
first one), the SCPB framework samples an independent realization $\xi_{j}$ of
$\xi$.

The SCPB framework is given below.

SCPB

  * 0.

Let ${\lambda},\theta>0$, integer $K>0$, and $x_{0}\in\mathrm{dom}\,h$ be
given, and set $x_{0}^{c}=x_{0}$, $j=k=1$, $j_{0}=0$, and

$\tau=\frac{\theta K}{\theta K+1};$ (7)

moreover, take a sample $\xi_{0}$ of r.v. $\xi$;

  * 1.

compute

$\displaystyle x_{j}^{c}=\left\\{\begin{array}[]{ll}x_{j_{k-1}},&\text{ if
}j=j_{k-1}+1,\\\ x_{j-1}^{c},&\text{ otherwise},\end{array}\right.$ (10)
$\displaystyle
x_{j}=\underset{u\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\Gamma_{j}^{\lambda}(u):=\Gamma_{j}(u)+\frac{1}{2{\lambda}}\|u-x_{j}^{c}\|^{2}\right\\},$
(11)

where

$\displaystyle\Gamma_{j}(\cdot):=\left\\{\begin{array}[]{ll}\ell_{\Phi}(\cdot;x_{j_{k-1}},\xi_{j_{k-1}}),&\text{
if }j=j_{k-1}+1,\\\
(1-\tau)\ell_{\Phi}(\cdot;x_{j-1},\xi_{j-1})+\tau\Gamma_{j-1}(\cdot),&\text{
otherwise};\end{array}\right.$ (14)

also, compute

$\displaystyle y_{j}=(1-\tau)x_{j}+\left\\{\begin{array}[]{ll}\tau
x_{j-1},&\text{ if }j=j_{k-1}+1,\\\ \tau y_{j-1},&\text{
otherwise},\end{array}\right.$ (17)

and take a sample $\xi_{j}$ of r.v. $\xi$ which is independent of
$\\{\xi_{0},\xi_{1},\ldots,\xi_{j-1}\\}$, and set

$\displaystyle
u_{j}=(1-\tau)\Phi(x_{j},\xi_{j})+\left\\{\begin{array}[]{ll}\tau\Phi(x_{j-1},\xi_{j-1}),&\text{
if }j=j_{k-1}+1,\\\ \tau u_{j-1},&\text{ otherwise};\end{array}\right.$ (20)

  * 2.

if $j=j_{k-1}+1$, then choose an integer $j_{k}$ such that

$j_{k}\geq j_{k-1}+2;$ (21)

if $j<j_{k}$, then set $j\leftarrow j+1$ and go to step 1; else, set
$\hat{u}_{k}=u_{j_{k}}$ and $\hat{y}_{k}=y_{j_{k}}$, and go to step 3;

  * 3.

if $k=K$ then stop and output

$\hat{y}_{K}^{a}=\frac{1}{\lceil K/2\rceil}\sum_{k=\lfloor
K/2\rfloor+1}^{K}\hat{y}_{k},\quad\hat{u}_{K}^{a}=\frac{1}{\lceil
K/2\rceil}\sum_{k=\lfloor K/2\rfloor+1}^{K}\hat{u}_{k};$ (22)

otherwise, set $k\leftarrow k+1$ and $j\leftarrow j+1$, and go to step 1.

We first discuss the roles played by the two index counts $j$ and $k$ used by
SCPB. First, $j$ counts the total number of iterations/resolvent evaluations
performed by SCPB since it is increased by one every time SCPB returns to step
1. Second, defining the $k$-th cycle as the iteration indices $j$ lying in

${\cal C}_{k}:=\\{i_{k},\ldots,j_{k}\\},\quad\mbox{\rm where}\ \ \
i_{k}:=j_{k-1}+1,$ (23)

it immediately follows that $k$ counts the number of cycles generated by SCPB.
Third, it follows from (21) that $j_{k}>i_{k}$, and hence that every cycle
contains at least two iteration indices. Fourth, step 1 determines two types
of iterations depending on whether $j=i_{k}$ (serious iteration) or $j\in{\cal
C}_{k}\setminus\\{i_{k}\\}$ (null iteration). Hence, the first iteration of a
cycle is a serious one while the others are null ones. Fifth, as currently
stated, SCPB can be a viewed as a framework since it is not a completely
specified algorithm. More specifically, SCPB does not specify how to select
$j_{k}$ in step 2. Specific choices for $j_{k}$ will be discussed below before
the main theorems describing the convergence rate of SCPB.

We now make several basic remarks about SCPB. First, every execution of step 1
involves one resolvent evaluation of $\partial h$, i.e., an evaluation of the
point-to-point operator $(I+\alpha\partial h)^{-1}(\cdot)$ for some
$\alpha>0$. Second, SCPB generates three sequences of iterates, namely, the
sequence of prox centers $\\{x_{j}^{c}\\}$ computed in (10), the auxiliary
sequence $\\{x_{j}\\}$ determined by (11), and the sequence $\\{y_{j}\\}$
given by (17). Third, it follows from (10) that $x^{c}_{j}=x_{j_{k-1}}$ for
every $j\in{\cal C}_{k}$. Hence, the prox-center $x^{c}_{j}$ remains constant
within every cycle and can only change at the beginning of its only serious
iteration. Fourth, $\\{\hat{y}_{k}\\}$ is the subsequence of $\\{y_{j}\\}$
consisting of all last iterates of the cycles generated by SCPB. Fifth, the
convergence rates described in Theorems 2.1 and 2.2 for SCPB are with respect
to the average of the iterates $\hat{y}_{\lfloor
K/2\rfloor+1},\ldots,\hat{y}_{K}$, namely, the point $\hat{y}_{K}^{a}$ as in
(22). Sixth, it is shown in Lemma 3.1 (resp., Theorem 2.1(b)) that the
expected value of $u_{j}$ (resp., $\hat{u}_{K}^{a}$) computed in (20) (resp.,
(22)) majorizes the expected value of $\phi(y_{j})$ (resp.,
$\phi(\hat{y}_{K}^{a})$).

We now describe two possible ways of choosing the index $j_{k}$ in step 2 of
SCPB, namely, for a given constant $C>0$, choose $j_{k}$ as

  * (B1)

the smallest integer $j_{k}$ satisfying (21) and
${\lambda}k\tau^{j_{k}-i_{k}}\leq C$;

  * (B2)

the smallest integer $j_{k}$ satisfying (21) and
${\lambda}k\tau^{j_{k}-i_{k}}[u_{i_{k}}-\Gamma_{i_{k}}^{\lambda}(x_{i_{k}})]\leq
C$.

In what follows, we state two convergence rate results for SCPB, the first one
based on the above choice (B1) for $j_{k}$ and the second one based on the
above choice (B2) for $j_{k}$. Both results, as well as other technical lemmas
in the paper, use the following notation: $d_{0}$ denotes the distance of the
initial point $x_{0}$ to optimal set $X^{*}$, i.e.,

$d_{0}:=\|x_{0}-x_{0}^{*}\|,\ \ \mbox{\rm where}\ \ \
x_{0}^{*}:=\mathrm{argmin}\,\\{\|x_{0}-x^{*}\|:x^{*}\in X^{*}\\}.$ (24)

######  Theorem 2.1.

Assume that conditions (A1)-(A6) hold. Moreover, for a given $C>0$, assume
also that (B1) holds for every $k\geq 1$. Then, SCPB satisfies the following
statements:

  * a)

the number of iterations within the $k$-th cycle ${\cal C}_{k}$ (see (23)) is
bounded by

$\left\lceil(\theta K+1)\ln\left(\frac{{\lambda}k}{C}+1\right)\right\rceil+1;$

  * b)

we have

$\mathbb{E}[\phi(\hat{y}_{K}^{a})]-\phi_{*}\leq\mathbb{E}[\hat{u}_{K}^{a}]-\phi_{*}\leq\frac{1}{K}\left(\frac{3C(2M+M_{h})D+d_{0}^{2}}{{\lambda}}+\frac{2{\lambda}M^{2}}{\theta}\right).$
(25)

For the complexity analysis of the variant of SCPB which selects sequence
$\\{j_{k}\\}$ according to choice (B2), we make the following additional
assumption:

  * (A7)

there is $\sigma>0$ such that for every $x\in\mathrm{dom}\,h$, we have
$\mathbb{E}[|\Phi(x,\xi)-\phi(x)|]\leq\sigma$.

######  Theorem 2.2.

Assume that conditions (A1)-(A7) hold. Moreover, for a given $C>0$, assume
also that (B2) holds for every $k\geq 1$. Then, SCPB satisfies the following
statements:

  * a)

the expected number of iterations within the $k$-th cycle ${\cal C}_{k}$ (see
(23)) is bounded by

$\left\lceil(\theta
K+1)\ln\left(\frac{(2M+M_{h})D{\lambda}k}{C}+1\right)\right\rceil+1;$ (26)

  * b)

we have

$\mathbb{E}[\phi(\hat{y}_{K}^{a})]-\phi_{*}\leq\mathbb{E}[\hat{u}_{K}^{a}]-\phi_{*}\leq\frac{3C+d_{0}^{2}}{{\lambda}K}+\frac{2\sigma+2{\lambda}M^{2}}{\theta
K}+\frac{2{\lambda}M^{2}}{\theta^{2}K^{2}}.$ (27)

##  3 Proof of Theorem 2.1

This section is devoted to the proof of Theorem 2.1. It also presents an
iteration-complexity result for SCPB to obtain an $\bar{\varepsilon}$-pair of
(1) in expectation.

We now introduce some notation that will be used throughout the analysis of
this paper. We recall that for every $j\geq 0$

$\xi_{[j]}=(\xi_{0},\xi_{1},\ldots,\xi_{j})$ (28)

and for $p\leq q$ positive integers we denote by $\xi_{[p:q]}$ the portion
$\xi_{[p:q]}=(\xi_{p},\xi_{p+1},\ldots,\xi_{q})$ of realizations of the r.v.
$\xi$ over the iterations $p,p+1,\ldots,q$.

The first result below provides some basic relations which are often used in
our analysis.

######  Lemma 3.1.

For every $j\geq 1$, we have

$\displaystyle\mathbb{E}[\Phi(x_{j},\xi_{j})]$
$\displaystyle=\mathbb{E}[\phi(x_{j})],$ (29)
$\displaystyle\mathbb{E}[\phi(y_{j})]$ $\displaystyle\leq\mathbb{E}[u_{j}],$
(30) $\displaystyle\mathbb{E}[\Gamma_{j}(x)]$
$\displaystyle\leq\phi(x)\quad\forall x\in\mathbb{R}^{n}.$ (31)

Proof: Observe that $x_{j}$ is a function of $\xi_{[j-1]}$ and not of
$\xi_{j}$. Hence, $x_{j}$ is independent of $\xi_{j}$ in view of the fact that
$\xi_{j}$ is chosen in step 1 of SCPB to be independent of $\xi_{[j-1]}$.
Using the relation $f(x)=\mathbb{E}[F(x,\xi)]$, it follows that

$\begin{array}[]{lcl}\mathbb{E}[\Phi(x_{j},\xi_{j})]&=&\mathbb{E}_{\xi_{[j]}}[F(x_{j},\xi_{j})+h(x_{j})]=\mathbb{E}_{\xi_{[j-1]}}[\mathbb{E}_{\xi_{j}}[F(x_{j},\xi_{j})+h(x_{j})|\xi_{[j-1]}]]\\\
&=&\mathbb{E}_{\xi_{[j-1]}}[f(x_{j})+h(x_{j})]=\mathbb{E}[\phi(x_{j})],\end{array}$

which is identity (29). It then suffices to show that, for any given $k\geq
1$, (30) and (31) hold for every $j$ in the $k$-th cycle, i.e.,
$j\in\mathcal{C}_{k}$. Indeed, we show this by induction on $j$ where $j$ is
the iteration count. If $j=i_{k}$, then it follows from (17), (20), (29), (A3)
and the convexity of $\phi$ that

$\begin{array}[]{lcl}\mathbb{E}[u_{j}]&=&(1-\tau)\mathbb{E}[\Phi(x_{j},\xi_{j})]+\tau\mathbb{E}[\Phi(x_{j-1},\xi_{j-1})]\\\
&\overset{\eqref{eq:exp}}{=}&(1-\tau)\mathbb{E}[\phi(x_{j})]+\tau\mathbb{E}[\phi(x_{j-1})]\geq\mathbb{E}[\phi((1-\tau)x_{j}+\tau
x_{j-1})]\overset{\eqref{def:yj}}{=}\mathbb{E}[\phi(y_{j})],\end{array}$

and from (6) with $x=x_{j-1}$ and (14) with $j=i_{k}$ that for every
$x\in\mathrm{dom}\,h$,

$\mathbb{E}[\Gamma_{j}(x)]=\mathbb{E}[\ell_{\Phi}(x;x_{j-1},\xi_{j-1})]\overset{\eqref{eq:exp0}}{\leq}\phi(x).$

Let $j$ be such that $j>i_{k}$ and (30) and (31) hold for $j$. Then, it
follows from (17), (20), (A3), the fact that (30) holds for $j$, and the
convexity of $\phi$, that

$\displaystyle\mathbb{E}[u_{j+1}]$
$\displaystyle=(1-\tau)\mathbb{E}[\Phi(x_{j+1},\xi_{j+1})]+\tau\mathbb{E}[u_{j}]$
$\displaystyle\geq(1-\tau)\mathbb{E}[\phi(x_{j+1})]+\tau\mathbb{E}[\phi(y_{j})]\geq\mathbb{E}[\phi((1-\tau)x_{j+1}+\tau
y_{j})]=\mathbb{E}[\phi(y_{j+1})],$

and from (6), (14) and the fact that (31) holds for $j$, that

$\mathbb{E}[\Gamma_{j+1}(x)]=\tau\mathbb{E}[\Gamma_{j}(x)]+(1-\tau)\mathbb{E}[\ell_{\Phi}(x;x_{j},\xi_{j})]\leq\tau\phi(x)+(1-\tau)\mathbb{E}[\Phi(x,\xi_{j})]=\phi(x).$

It is worth noting that the proof of (31) is strongly based on the fact that
$\Gamma_{j}$ is a convex combination of affine functions whose expected values
are underneath $\phi$. Moreover, this inequality would not necessarily be true
if $\Gamma_{j}$ were for example the maximum of functions as just described.

The next result provides some useful estimates for the quantity
$\Phi(x_{j},\xi_{j})-\ell_{\Phi}(x_{j};x_{j-1},\xi_{j-1})$.

######  Lemma 3.2.

For every $j\geq 1$, let

$s_{j}:=s(x_{j};\xi_{j}),\quad\Delta_{j}:=\Phi(x_{j},\xi_{j})-\phi(x_{j}).$
(32)

Then, for every $j\in{\cal C}_{k}$ such that $j\geq j_{k-1}+2$, we have:

$\Phi(x_{j},\xi_{j})-\ell_{\Phi}(x_{j};x_{j-1},\xi_{j-1})\leq\Delta_{j}-\Delta_{j-1}+(M+\|s_{j-1}\|)\|x_{j}-x_{j-1}\|.$
(33)

Proof: Using the definitions of $\Phi$, $\ell_{\Phi}(\cdot;x,\xi)$, and
$\Delta_{j}$ in (5) and (32), respectively, we have

$\displaystyle\Phi(x_{j},\xi_{j})$
$\displaystyle-\ell_{\Phi}(x_{j};x_{j-1},\xi_{j-1})=F(x_{j},\xi_{j})-F(x_{j-1},\xi_{j-1})-\langle
s_{j-1},x_{j}-x_{j-1}\rangle$
$\displaystyle=f(x_{j})-f(x_{j-1})+\Delta_{j}-\Delta_{j-1}-\langle
s_{j-1},x_{j}-x_{j-1}\rangle$ $\displaystyle\leq\langle
f^{\prime}(x_{j})-s_{j-1},x_{j}-x_{j-1}\rangle+\Delta_{j}-\Delta_{j-1}$

where the inequality is due to the convexity of $f$. The above inequality, the
Cauchy-Schwarz inequality, the triangle inequality and (4) then imply (33).

The technical result below introduces a key quantity, namely, scalar $t_{j}$
below, and provides a useful recursive relation for it over the iterations of
the $k$-th cycle. This recursive relation will then be used in Proposition 3.6
to show that the $t_{j}$ at the end of the $k$-th cycle, namely $t_{j_{k}}$,
is relatively small in expectation.

######  Lemma 3.3.

For every $j\geq 1$, define

$t_{j}:=u_{j}-\Gamma_{j}^{\lambda}(x_{j}),\quad
b_{j+1}:=\frac{{\lambda}(M^{2}+\|s_{j}\|^{2})}{\theta
K}+\Delta_{j+1}-\Delta_{j}$ (34)

where $\lambda$, $\theta$, and $K$ are as in step 0 of SCPB, and $s_{j}$ and
$\Delta_{j}$ are as in (32). Then, for every $j\in{\cal C}_{k}$ such that
$j\geq i_{k}+1$, we have

$t_{j}\leq\tau t_{j-1}+(1-\tau)b_{j}$ (35)

where $\tau$ is as in (7), and hence

$t_{j}\leq\tau^{j-i_{k}}t_{i_{k}}+(1-\tau)\sum_{i=i_{k}+1}^{j}\tau^{j-i}b_{i}.$
(36)

Proof: It follows from the definitions of $\Gamma_{j}$ and
$\Gamma_{j}^{\lambda}$ in (14) and (11), respectively, that

$\displaystyle\Gamma_{j}^{\lambda}(x_{j})$
$\displaystyle\geq(1-\tau)\ell_{\Phi}(x_{j};x_{j-1},\xi_{j-1})+\tau\Gamma_{j-1}^{\lambda}(x_{j})$
$\displaystyle\geq(1-\tau)\ell_{\Phi}(x_{j};x_{j-1},\xi_{j-1})+\tau\left[\Gamma_{j-1}^{\lambda}(x_{j-1})+\frac{1}{2{\lambda}}\|x_{j}-x_{j-1}\|^{2}\right],$
(37)

where the second inequality is due to the facts that $\Gamma_{j}^{\lambda}$ is
$(1/{\lambda})$-strongly convex and $x_{j-1}$ is the minimizer of
$\Gamma_{j-1}^{\lambda}$ (see (11)). Using (7), (33) and (37), we have

$\displaystyle\Gamma_{j}^{\lambda}(x_{j})-\tau\Gamma_{j-1}^{\lambda}(x_{j-1})\overset{\eqref{def:tau},\eqref{ineq:Gamma}}{\geq}(1-\tau)\left[\ell_{\Phi}(x_{j};x_{j-1},\xi_{j-1})+\frac{\theta
K}{2{\lambda}}\|x_{j}-x_{j-1}\|^{2}\right]$
$\displaystyle\overset{\eqref{ineq:Phi}}{\geq}(1-\tau)(\Phi(x_{j},\xi_{j})-\Delta_{j}+\Delta_{j-1})+(1-\tau)\left[\frac{\theta
K}{2{\lambda}}\|x_{j}-x_{j-1}\|^{2}-(M+\|s_{j-1}\|)\|x_{j}-x_{j-1}\|\right]$
$\displaystyle\geq(1-\tau)(\Phi(x_{j},\xi_{j})-\Delta_{j}+\Delta_{j-1})-(1-\tau)\frac{{\lambda}(M+\|s_{j-1}\|)^{2}}{2\theta
K}$

where the last inequality is obtained by minimizing its left hand side with
respect to $\|x_{j}-x_{j-1}\|$. The above inequality, the fact that
$(\alpha_{1}+\alpha_{2})^{2}\leq 2\alpha_{1}^{2}+2\alpha_{2}^{2}$ for every
$\alpha_{1},\alpha_{2}\in\mathbb{R}$, and the definition of $b_{j}$ in (34)
imply that

$\begin{array}[]{lcl}\Gamma_{j}^{\lambda}(x_{j})-\tau\Gamma_{j-1}^{\lambda}(x_{j-1})&\geq&(1-\tau)(\Phi(x_{j},\xi_{j})-\Delta_{j}+\Delta_{j-1})-(1-\tau)\frac{{\lambda}(M^{2}+\|s_{j-1}\|^{2})}{\theta
K}\\\
&\overset{\eqref{def:delta}}{=}&(1-\tau)\Phi(x_{j},\xi_{j})-(1-\tau)b_{j}.\end{array}$

Rearranging the above inequality, using the definition of $t_{j}$ in (34) and
identity (20), we then conclude that

$\begin{array}[]{lcl}\Gamma_{j}^{\lambda}(x_{j})+(1-\tau)b_{j}&\geq&\tau\Gamma_{j-1}^{\lambda}(x_{j-1})+(1-\tau)\Phi(x_{j},\xi_{j})\\\
&\overset{\eqref{def:delta}}{=}&\tau(u_{j-1}-t_{j-1})+(1-\tau)\Phi(x_{j},\xi_{j})\overset{\eqref{def:u}}{=}u_{j}-\tau
t_{j-1}.\end{array}$

The above inequality and the definition of $t_{j}$ in (34) imply that (35)
holds. As a consequence, (36) immediately follows from (35).

The following technical result provides some useful bounds on $b_{j}$, as well
as on an intermediate quantity that appears in the definition of $b_{j}$ in
(34).

######  Lemma 3.4.

For every $j\geq 1$, define

$\tilde{b}_{j}:=\frac{{\lambda}(M^{2}+\|s_{j-1}\|^{2})}{\theta K}.$ (38)

Then, for every $\ell\geq 0$ and $j\geq\ell+2$, we have

$\mathbb{E}[\tilde{b}_{j}]\leq\frac{2{\lambda}M^{2}}{\theta
K},\quad\mathbb{E}[b_{j}\,|\xi_{[\ell]}]\leq\frac{2{\lambda}M^{2}}{\theta
K},\quad\mathbb{E}[b_{j}]\leq\frac{2{\lambda}M^{2}}{\theta K}.$ (39)

Proof: We first show that for every $j\geq 1$ and $\ell\leq j-1$,

$\mathbb{E}[\Delta_{j}\,|\,\xi_{[\ell]}]=0,\quad\mathbb{E}[\|s_{j}\|^{2}\,|\,\xi_{[\ell]}]\leq
M^{2}.$ (40)

Fix $j\geq 1$. Since $x_{j}$ becomes deterministic when $\xi_{[j-1]}$ is
given, it follows from (A3) and (A4) with $x=x_{j}$, and the definitions of
$\Delta_{j}$ and $s_{j}$ in (32) that

$\mathbb{E}_{\xi_{j}}[\Delta_{j}\,|\,\xi_{[j-1]}]=0,\quad\mathbb{E}_{\xi_{j}}[\|s_{j}\|^{2}\,|\,\xi_{[j-1]}]\leq
M^{2}.$

Now, if $\ell\leq j-2$, then the above relations together with the law of
total expectation imply that

$\mathbb{E}[\Delta_{j}\,|\,\xi_{[\ell]}]=\mathbb{E}_{\xi_{[\ell+1:j]}}[\Delta_{j}\,|\,\xi_{[\ell]}]=\mathbb{E}_{\xi_{[\ell+1:j-1]}}[\mathbb{E}_{\xi_{j}}[\Delta_{j}\,|\,\xi_{[j-1]}]]=0,$

and

$\mathbb{E}[\|s_{j}\|^{2}\,|\,\xi_{[\ell]}]=\mathbb{E}_{\xi_{[\ell+1:j]}}[\|s_{j}\|^{2}\,|\,\xi_{[\ell]}]=\mathbb{E}_{\xi_{[\ell+1:j-1]}}[\mathbb{E}_{\xi_{j}}[\|s_{j}\|^{2}\,|\,\xi_{[j-1]}]]\leq
M^{2}.$

We have thus shown that (40) holds for any $\ell\leq j-1$.

It follows from the definition of $\tilde{b}_{j}$ in (38) and the second
inequality in (40) that

$\mathbb{E}[\tilde{b}_{j}\,|\xi_{[\ell]}]\leq\frac{2{\lambda}M^{2}}{\theta
K}.$ (41)

This inequality and the law of total expectation imply that the first
inequality in (39) holds. It follows from (34) and (38) that for every $j\geq
2$,

$b_{j}=\tilde{b}_{j}+\Delta_{j}-\Delta_{j-1}.$

Taking conditional expectation with respect to $\xi_{[\ell]}$ in the above
identity, noting that $\ell\leq j-2$, and using the first identity in (40)
twice, first with $j$ and then with $j$ replaced by $j-1$, we conclude that

$\mathbb{E}[b_{j}\,|\xi_{[\ell]}]=\mathbb{E}[\tilde{b}_{j}\,|\xi_{[\ell]}].$

The second inequality in (39) immediately follows from the above identity and
(41). Finally, the last inequality in (39) follows from the second one in (39)
and the law of total expectation.

The next technical result provides a bound on the initial $t_{j}$ for the
$k$-th cycle, namely $t_{i_{k}}$, in expectation.

######  Lemma 3.5.

For every $k\geq 1$, we have $\mathbb{E}[t_{i_{k}}]\leq\bar{T}:=(2M+M_{h})D$
where $i_{k}$ and $t_{j}$ are as in (23) and (34), respectively.

Proof: Using the definitions of $t_{j}$ and $\Gamma_{j}^{\lambda}$ in (34) and
(14), respectively, (20) with $j=j_{k-1}$, and (23), we have

$\displaystyle t_{i_{k}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{def:delta}}}{{=}}u_{i_{k}}-\Gamma_{i_{k}}^{{\lambda}}(x_{i_{k}})\stackrel{{\scriptstyle\eqref{eq:Gamma}}}{{\leq}}u_{i_{k}}-\ell_{\Phi}(x_{i_{k}};x_{j_{k-1}},\xi_{j_{k-1}})$
$\displaystyle\stackrel{{\scriptstyle\eqref{def:u}}}{{=}}\tau\Phi(x_{j_{k-1}},\xi_{j_{k-1}})+(1-\tau)\Phi(x_{i_{k}},\xi_{i_{k}})-\ell_{\Phi}(x_{i_{k}};x_{j_{k-1}},\xi_{j_{k-1}})$
$\displaystyle=(1-\tau)\left[\Phi(x_{i_{k}},\xi_{i_{k}})-\ell_{\Phi}(x_{i_{k}};x_{j_{k-1}},\xi_{j_{k-1}})\right]+\tau\left[\Phi(x_{j_{k-1}},\xi_{j_{k-1}})-\ell_{\Phi}(x_{i_{k}};x_{j_{k-1}},\xi_{j_{k-1}})\right].$
(42)

We will now bound the expectation of the quantity in the first square bracket
above. Using (5), the triangle inequality and condition (A5), we have

$\displaystyle\Phi(x_{i_{k}},\xi_{i_{k}})-\ell_{\Phi}(x_{i_{k}};x_{j_{k-1}},\xi_{j_{k-1}})$
$\displaystyle=F(x_{i_{k}},\xi_{i_{k}})-F(x_{j_{k-1}},\xi_{j_{k-1}})-\langle
s(x_{j_{k-1}},\xi_{j_{k-1}}),x_{i_{k}}-x_{j_{k-1}}\rangle$ $\displaystyle\leq
F(x_{i_{k}},\xi_{i_{k}})-F(x_{j_{k-1}},\xi_{j_{k-1}})+\|s(x_{j_{k-1}},\xi_{j_{k-1}})\|D.$

Taking expectation of the above inequality and using the triangle inequality,
(A2), (A3) and (A5), we have

$\displaystyle\mathbb{E}[\Phi(x_{i_{k}},\xi_{i_{k}})-\ell_{\Phi}(x_{i_{k}};x_{j_{k-1}},\xi_{j_{k-1}})]$
$\displaystyle\stackrel{{\scriptstyle\text{(A3)}}}{{\leq}}\mathbb{E}[f(x_{i_{k}})-f(x_{j_{k-1}})]+\mathbb{E}[\|s(x_{j_{k-1}},\xi_{j_{k-1}})\|]D$
$\displaystyle\stackrel{{\scriptstyle\text{(A2)}}}{{\leq}}\mathbb{E}[\|f^{\prime}(x_{i_{k}})\|\|x_{i_{k}}-x_{j_{k-1}}\|]+\mathbb{E}[\|s(x_{j_{k-1}},\xi_{j_{k-1}})\|]D$
$\displaystyle\stackrel{{\scriptstyle\text{(A5)}}}{{\leq}}\left(\mathbb{E}[\|f^{\prime}(x_{i_{k}})\|]+\mathbb{E}[\|s(x_{j_{k-1}},\xi_{j_{k-1}})\|]\right)D\stackrel{{\scriptstyle\eqref{ineq:fp}}}{{\leq}}2MD$
(43)

where the last inequality is due to (4). We will now bound the expectation of
the quantity in the second square bracket of the right hand side of (42). It
follows from (5), condition (A1) and the triangle inequality that

$\displaystyle\mathbb{E}[\Phi(x_{j_{k-1}},\xi_{j_{k-1}})-\ell_{\Phi}(x_{i_{k}};x_{j_{k-1}},\xi_{j_{k-1}})]$
$\displaystyle=\mathbb{E}[h(x_{j_{k-1}})-h(x_{i_{k}})-\langle
s_{j_{k-1}},x_{i_{k}}-x_{j_{k-1}}\rangle]$
$\displaystyle\leq\mathbb{E}[(M_{h}+\|s_{j_{k-1}}\|)\|x_{i_{k}}-x_{j_{k-1}}\|]$
$\displaystyle\leq(M_{h}+M)D$ (44)

where the last inequality is due to condition (A5) and (4). The conclusion of
the lemma now follows by taking expectation of (42) and using both (43) and
(44).

All the results developed above hold regardless of the way $j_{k}$ is chosen
in step 2. On the other hand, the results below all depend on condition (B1).

We are now ready to derive a bound on the last $t_{j}$ for the $k$-th cycle in
expectation.

######  Proposition 3.6.

In addition to conditions (A1)-(A6), assume also that (B1) holds. Then, for
every $k\geq 1$, we have

$\mathbb{E}[t_{j_{k}}]\leq\frac{C\bar{T}}{{\lambda}k}+\frac{2{\lambda}M^{2}}{\theta
K}$ (45)

where $t_{j}$ is as in (34).

Proof: Fix $k\geq 1$. It follows from condition (B1) and inequality (36) with
$j=j_{k}$ that

$t_{j_{k}}\leq\tau^{j_{k}-i_{k}}t_{i_{k}}+(1-\tau)\sum_{i=i_{k}+1}^{j_{k}}\tau^{j_{k}-i}b_{i}.$

In view of (B1) and (23), it follows that $j_{k}$ and $i_{k}$ are both
deterministic. Hence, taking expectation of the above inequality and using the
last inequality in (39), condition (B1) and Lemma 3.5, we conclude that

$\displaystyle\mathbb{E}[t_{j_{k}}]$
$\displaystyle\leq\tau^{j_{k}-i_{k}}\mathbb{E}[t_{i_{k}}]+(1-\tau)\sum_{i=i_{k}+1}^{j_{k}}\tau^{j_{k}-i}\mathbb{E}[b_{i}]$
$\displaystyle\leq\frac{C\bar{T}}{{\lambda}k}+(1-\tau)\frac{2{\lambda}M^{2}}{\theta
K}\sum_{i=i_{k}+1}^{j_{k}}\tau^{j_{k}-i},$

and hence that (45) holds.

In the remaining part of this subsection, we analyze the behavior of the
“outer” sequence of iteration pairs
$\\{(\hat{y}_{k},\hat{u}_{k})\\}=\\{(y_{j_{k}},u_{j_{k}})\\}\subset\mathbb{R}^{n}\times\mathbb{R}$
generated in step 2 of SCPB. For this purpose, define

$\hat{\Gamma}_{k}:=\Gamma_{j_{k}}\quad\forall k\geq 1$ (46)

and

$\hat{x}_{k}:=x_{j_{k}}.$ (47)

In what follows, we make some remarks about the above “outer” sequences which
follow as immediate consequences of the results developed above. In view of
the above definitions, relation (11) with $j=j_{k}$, and the way the prox
centers $x_{j}^{c}$ are updated in (10), we have that

$\hat{x}_{k}=\underset{x\in\mathbb{R}^{n}}{\mathrm{argmin}\,}\left\\{\hat{\Gamma}_{k}(x)+\frac{1}{2{\lambda}}\|x-\hat{x}_{k-1}\|^{2}\right\\}\quad\forall
k\geq 1.$ (48)

Moreover, it follows from (30) and (31) with $j=j_{k}$ that

$\mathbb{E}[\phi(\hat{y}_{k})]\leq\mathbb{E}[\hat{u}_{k}]$ (49)

and

$\mathbb{E}[\hat{\Gamma}_{k}(z)]\leq\phi(z)\quad\forall z\in\mathrm{dom}\,h.$
(50)

The following result describes an important recursive formula for the outer
sequence $\\{(\hat{y}_{k},\hat{u}_{k})\\}$ generated by SCPB.

######  Lemma 3.7.

In addition to conditions (A1)-(A6), assume also that (B1) holds. Then, for
every $k\geq 1$ and $z\in\mathrm{dom}\,h$, we have

$\frac{C\bar{T}}{{\lambda}k}+\frac{2{\lambda}M^{2}}{\theta
K}+\frac{1}{2{\lambda}}[d_{k-1}(z)]^{2}-\frac{1}{2{\lambda}}[d_{k}(z)]^{2}\geq\mathbb{E}[\hat{u}_{k}]-\phi(z)$

where

$d_{k}(z):=\left(\mathbb{E}[\|\hat{x}_{k}-z\|^{2}]\right)^{1/2}.$ (51)

Proof: First observe that (46), (47), the fact that $\hat{u}_{k}=u_{j_{k}}$,
and the definitions of $\Gamma_{j}^{\lambda}$ and $t_{j}$ in (11) and (34),
respectively, imply that (45) is equivalent to

$\mathbb{E}\left[\hat{u}_{k}-\hat{\Gamma}_{k}(\hat{x}_{k})-\frac{1}{2{\lambda}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}\right]\leq\frac{C\bar{T}}{{\lambda}k}+\frac{2{\lambda}M^{2}}{\theta
K}.$ (52)

It follows from (48) and the fact that the objective function of (48) is
$(1/{\lambda})$-strongly convex that for every $z\in\mathrm{dom}\,h$,

$\hat{\Gamma}_{k}(\hat{x}_{k})+\frac{1}{2{\lambda}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}\leq\hat{\Gamma}_{k}(z)+\frac{1}{2{\lambda}}\|z-\hat{x}_{k-1}\|^{2}-\frac{1}{2{\lambda}}\|z-\hat{x}_{k}\|^{2},$

and hence that

$\hat{u}_{k}-\hat{\Gamma}_{k}(\hat{x}_{k})-\frac{1}{2{\lambda}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}+\frac{1}{2{\lambda}}\|\hat{x}_{k-1}-z\|^{2}\geq\hat{u}_{k}-\hat{\Gamma}_{k}(z)+\frac{1}{2{\lambda}}\|\hat{x}_{k}-z\|^{2}.$

Taking expectation of the above inequality and using (51) and (52), we
conclude that

$\frac{C\bar{T}}{{\lambda}k}+\frac{2{\lambda}M^{2}}{\theta
K}+\frac{1}{2{\lambda}}[d_{k-1}(z)]^{2}\geq\mathbb{E}[\hat{u}_{k}]-\mathbb{E}[\hat{\Gamma}_{k}(z)]+\frac{1}{2{\lambda}}[d_{k}(z)]^{2}$

which, in view of (50), immediately implies the conclusion of the lemma.

We are now in a position to prove Theorem 2.1.

Proof of Theorem 2.1: a) This statement directly follows from (7), condition
(B1), and the facts that $|{\cal C}_{k}|=j_{k}-i_{k}+1$ and $\ln\tau^{-1}\geq
1-\tau$.

b) It follows from (22), (49), and the fact that $\phi$ is convex, that

$\displaystyle\mathbb{E}[\phi(\hat{y}_{K}^{a})]\leq\frac{1}{\lceil
K/2\rceil}\sum_{k=\lfloor
K/2\rfloor+1}^{K}\mathbb{E}[\phi(\hat{y}_{k})]\overset{\eqref{ineq:uk}}{\leq}\frac{1}{\lceil
K/2\rceil}\sum_{k=\lfloor
K/2\rfloor+1}^{K}\mathbb{E}[\hat{u}_{k}]\overset{\eqref{eq:output}}{=}\mathbb{E}\left[\hat{u}_{K}^{a}\right],$

and hence that the first inequality of (25) holds. Using the definition of
$\hat{u}_{K}^{a}$ in (22) and Lemma 3.7 with $z=x_{0}^{*}$ where $x_{0}^{*}$
is as in (24), we have for every $K\geq 2$,

$\displaystyle\mathbb{E}[\hat{u}_{K}^{a}]-\phi_{*}$
$\displaystyle=\frac{1}{\lceil K/2\rceil}\sum_{k=\lfloor
K/2\rfloor+1}^{K}(\mathbb{E}[\hat{u}_{k}]-\phi_{*})$
$\displaystyle\leq\frac{1}{\lceil K/2\rceil}\sum_{k=\lfloor
K/2\rfloor+1}^{K}\left(\frac{C\bar{T}}{{\lambda}k}+\frac{2{\lambda}M^{2}}{\theta
K}+\frac{1}{2{\lambda}}[d_{k-1}(x_{0}^{*})]^{2}-\frac{1}{2{\lambda}}[d_{k}(x_{0}^{*})]^{2}\right)$
$\displaystyle\leq\frac{3C\bar{T}}{{\lambda}K}+\frac{2{\lambda}M^{2}}{\theta
K}+\frac{d_{0}^{2}}{{\lambda}K}$ (53)

where the last inequality is due to the facts that $\lceil K/2\rceil\geq K/2$
and

$\sum_{k=\lfloor K/2\rfloor+1}^{K}\frac{1}{k}\leq\int_{\lfloor
K/2\rfloor}^{K}\frac{1}{x}dx=\ln\frac{K}{\lfloor
K/2\rfloor}\leq\ln\frac{K}{K/4}=\ln 4\leq\frac{3}{2}\quad\forall K\geq 2.$

It is also easy to see that (53) holds for $K=1$. The second inequality of
(25) immediately follows from (53) and the definition of $\bar{T}$ in Lemma
3.5. ∎

Theorem 2.1 derives a convergence rate bound for SCPB. The following result
describes the iteration-complexity for SCPB to obtain an
$\bar{\varepsilon}$-pair of (1) in expectation.

######  Corollary 3.8.

Assume that conditions (A1)-(A6) hold. Moreover, for a given $C>0$, assume
that (B1) holds for every $k\geq 1$. Let tolerance $\bar{\varepsilon}>0$ be
given and set the input $K$ of SCPB as

$\displaystyle
K=K_{\bar{\varepsilon}}:=\left\lfloor\frac{3C(2M+M_{h})D+d_{0}^{2}}{{\lambda}\bar{\varepsilon}}+\frac{2{\lambda}M^{2}}{\theta\bar{\varepsilon}}\right\rfloor+1.$
(54)

Then, the pair
$(\hat{y}_{K}^{a},\hat{u}_{K}^{a})\in\mathbb{R}^{n}\times\mathbb{R}$ found by
SCPB is an $\bar{\varepsilon}$-pair in expectation, i.e., it satisfies

$\mathbb{E}[\phi(\hat{y}_{K}^{a})]-\phi_{*}\leq\mathbb{E}[\hat{u}_{K}^{a}]-\phi_{*}\leq\bar{\varepsilon}.$
(55)

Moreover, the expected overall iteration/resolvent evaluation complexity of
SCPB is given by

${\cal O}\left(K_{\bar{\varepsilon}}\left[(1+\theta
K_{\bar{\varepsilon}})\log\left(\frac{{\lambda}K_{\bar{\varepsilon}}}{C}+1\right)+1\right]\right)$
(56)

where ${\lambda}$ and $\theta$ are the other two inputs for SCPB and $C>0$ is
as in (B1).

Proof: It immediately follows from Theorem 2.1(b) and the definition of
$K_{\bar{\varepsilon}}$ in (54) that (55) holds. The complexity bound (56)
directly follows from Theorem 2.1(a).

It follows from Corollary 3.8 that, in terms of $\bar{\varepsilon}$ only, the
iteration/resolvent evaluation complexity to obtain an
$\bar{\varepsilon}$-pair of (1) is ${\cal O}(\bar{\varepsilon}^{-2})$, up to a
logarithmic term.

######  Corollary 3.9.

Assume that conditions (A1)-(A6) and condition (B1) with $C=D/(2M+M_{h})$ hold
where $M_{h}$ and $D$ are as in (A1) and (A5), respectively. Let tolerance
$\bar{\varepsilon}>0$ be given, and consider SCPB with input triple
$({\lambda},\theta,K)$ where ${\lambda}$ is arbitrary and $(\theta,K)$ is
given by

$\theta=\frac{{\lambda}^{2}M^{2}}{D^{2}},\quad K=K_{\bar{\varepsilon}}$ (57)

where $K_{\bar{\varepsilon}}$ is as in (54). Then, its expected overall
iteration/resolvent evaluation complexity (up to a logarithmic term) is

${\cal O}\left(\frac{M^{2}D^{2}}{\bar{\varepsilon}^{2}}+1\right).$ (58)

Proof: It follows from (54) with $C=D/(M+M_{h})$ and the fact that $d_{0}\leq
D$ that

$K_{\bar{\varepsilon}}={\cal
O}\left(\frac{D^{2}}{{\lambda}\bar{\varepsilon}}+\frac{{\lambda}M^{2}}{\theta\bar{\varepsilon}}+1\right).$
(59)

We observe from (56) that the overall complexity (up to a logarithmic term) is

${\cal O}(\theta K_{\bar{\varepsilon}}^{2}+1)={\cal O}\left(\frac{\theta
D^{4}}{{\lambda}^{2}\bar{\varepsilon}^{2}}+\frac{{\lambda}^{2}M^{4}}{\theta\bar{\varepsilon}^{2}}+\frac{D^{2}M^{2}}{{\bar{\varepsilon}}^{2}}+1\right).$

This observation, the first identity in (57) and (59) immediately imply bound
(58).

It is worth noting that in the deterministic setting, condition (A5) becomes
$\|f^{\prime}(x)\|\leq M$ for every $x\in\mathrm{dom}\,h$ and (58) is the
optimal complexity bound.

##  4 Proof of Theorem 2.2

This section is devoted to the proof of Theorem 2.2. It also presents an
iteration-complexity result for SCPB under conditions (A1)-(A7) and (B2) to
obtain an $\bar{\varepsilon}$-pair of (1) in expectation.

The following technical result presents a useful bound on $|b_{i_{k}+1}|$ that
is used in the next proposition to derive a bound on $\mathbb{E}[t_{j_{k}}]$.

######  Lemma 4.1.

Assume that conditions (A1)-(A7) hold. Then, for every $k\geq 1$,

$\mathbb{E}[\,|b_{i_{k}+1}|\,]\leq 2\sigma+\frac{2{\lambda}M^{2}}{\theta K}.$
(60)

Proof: It follows from SCPB that $x_{j}$ is deterministic given $\xi_{[j-1]}$.
This fact, the definition of $\Delta_{j}$ in (32), and (A7) with $x=x_{j}$,
then imply that for every $j\geq 1$,

$\mathbb{E}\left[|\Delta_{j}|\,|\,\xi_{[j-1]}\right]=\mathbb{E}\left[|\Phi(x_{j},\xi_{j})-\phi(x_{j})|\,|\,\xi_{[j-1]}\right]\leq\sigma.$

Using the above inequality and the law of total expectation, we have for every
$j\geq 1$,

$\mathbb{E}\left[|\Delta_{j}|\right]\leq\sigma.$ (61)

It follows from (34), (38) and the triangle inequality that

$|b_{i_{k}+1}|\leq|\Delta_{i_{k}+1}|+|\Delta_{i_{k}}|+\tilde{b}_{i_{k}+1}.$

Taking expectation of the above inequality, we conclude that

$\mathbb{E}[|b_{i_{k}+1}|]\leq\mathbb{E}[|\Delta_{i_{k}+1}|]+\mathbb{E}[|\Delta_{i_{k}}|]+\mathbb{E}[\tilde{b}_{i_{k}+1}],$

and hence that (60) holds in view of (61) and the first inequality in (39).

The next two results assume that $j_{k}$ is allowed to be stochastic and
satisfies condition (B2). We note that in view of the definition of $t_{j}$ in
(34), the condition on $j_{k}$ in (B2) is equivalent to

${\lambda}k\tau^{j_{k}-i_{k}}t_{i_{k}}\leq C.$ (62)

The following proposition derives a bound on the last $t_{j}$ for the $k$-th
cycle in expectation. It is an analogue of Proposition 3.6 under the
conditions (A1)-(A7) and (B2).

######  Proposition 4.2.

In addition to conditions (A1)-(A7), assume also that (B2) holds. For every
$k\geq 1$, we have

$\mathbb{E}[t_{j_{k}}]\leq\frac{C}{{\lambda}k}+\frac{2\sigma+2{\lambda}M^{2}}{\theta
K}+\frac{2{\lambda}M^{2}}{\theta^{2}K^{2}}.$ (63)

Proof: Using (36) with $j=j_{k}$, (62), and the facts that $j_{k}\geq i_{k}+1$
in view of (21) and (23), and $\tau\in(0,1)$ in view of (7), we conclude that

$t_{j_{k}}-(1-\tau)\sum_{i=i_{k}+2}^{j_{k}}\tau^{j_{k}-i}b_{i}\overset{\eqref{ineq:recursive}}{\leq}\tau^{j_{k}-i_{k}}t_{i_{k}}+(1-\tau)\tau^{j_{k}-i_{k}-1}|b_{i_{k}+1}|\leq\frac{C}{{\lambda}k}+(1-\tau)|b_{i_{k}+1}|.$

Noting that $j_{k}$ becomes deterministic once $\xi_{[i_{k}]}$ is given,
taking expectation of the above inequality conditioned on $\xi_{[i_{k}]}$,
rearranging the terms, and using the second inequality in (39), we have

$\displaystyle\mathbb{E}\left[t_{j_{k}}|\xi_{[i_{k}]}\right]-\frac{C}{{\lambda}k}-(1-\tau)\mathbb{E}[|b_{i_{k}+1}||\xi_{[i_{k}]}]$
$\displaystyle\leq(1-\tau)\sum_{i=i_{k}+2}^{j_{k}}\tau^{j_{k}-i}\mathbb{E}[b_{i}|\xi_{[i_{k}]}]$
$\displaystyle\overset{\eqref{ineq:bj}}{\leq}(1-\tau)\left(\sum_{i=i_{k}+2}^{j_{k}}\tau^{j_{k}-i}\right)\frac{2{\lambda}M^{2}}{\theta
K}\leq\frac{2{\lambda}M^{2}}{\theta K}.$

Taking expectation of the above inequality with respect to $\xi_{[i_{k}]}$,
rearranging the terms, and using (60) and the fact that $1-\tau\leq 1/(\theta
K)$ by (7), we conclude that

$\displaystyle\mathbb{E}[t_{j_{k}}]$
$\displaystyle\leq\frac{C}{{\lambda}k}+(1-\tau)\mathbb{E}[|b_{i_{k}+1}|]+\frac{2{\lambda}M^{2}}{\theta
K}$ $\displaystyle\leq\frac{C}{{\lambda}k}+\frac{1}{\theta
K}\left(2\sigma+\frac{2{\lambda}M^{2}}{\theta
K}\right)+\frac{2{\lambda}M^{2}}{\theta K},$

and hence that (63) holds.

The following lemma is an analogue of Lemma 3.7 under the conditions (A1)-(A7)
and (B2).

######  Lemma 4.3.

In addition to conditions (A1)-(A7), assume also that (B2) holds. Then, for
every $z\in\mathrm{dom}\,h$ and $k\geq 1$, we have

$\frac{C}{{\lambda}k}+\frac{2\sigma+2{\lambda}M^{2}}{\theta
K}+\frac{2{\lambda}M^{2}}{\theta^{2}K^{2}}+\frac{1}{2{\lambda}}[d_{k-1}(z)]^{2}-\frac{1}{2{\lambda}}[d_{k}(z)]^{2}\geq\mathbb{E}[\hat{u}_{k}]-\phi(z)$

where $d_{k}(z)$ is as in (51).

Proof: First observe that the definitions of $\Gamma_{j}^{\lambda}$ and
$t_{j}$ in (11) and (34), respectively, imply that (63) is equivalent to

$\mathbb{E}\left[\hat{u}_{k}-\hat{\Gamma}_{k}(\hat{x}_{k})-\frac{1}{2{\lambda}}\|\hat{x}_{k}-\hat{x}_{k-1}\|^{2}\right]\leq\frac{C}{{\lambda}k}+\frac{2\sigma+2{\lambda}M^{2}}{\theta
K}+\frac{2{\lambda}M^{2}}{\theta^{2}K^{2}}.$ (64)

The remaining part of the proof is now similar to that of Lemma 3.7 except
that (64) is used in place of (52).

We are now in a position to prove Theorem 2.2.

Proof of Theorem 2.2: a) Using (7), (62), and the facts that $|{\cal
C}_{k}|=j_{k}-i_{k}+1$ and $\ln\tau^{-1}\geq 1-\tau$, we have

$|{\cal
C}_{k}|\leq\frac{1}{1-\tau}\ln\left(1+\frac{t_{i_{k}}{\lambda}k}{C}\right)+1=(\theta
K+1)\ln\left(1+\frac{t_{i_{k}}{\lambda}k}{C}\right)+1.$

Taking expectation of the above inequality, and using the Jensen’s inequality
and the fact that $\ln x$ is a concave function, we then conclude that

$\displaystyle\mathbb{E}[|{\cal C}_{k}|]$ $\displaystyle\leq(\theta
K+1)\mathbb{E}\left[\ln\left(1+\frac{t_{i_{k}}{\lambda}k}{C}\right)\right]+1\leq(\theta
K+1)\ln\left(\frac{1+\mathbb{E}[t_{i_{k}}]{\lambda}k}{C}\right)+1$
$\displaystyle\leq(\theta
K+1)\ln\left(1+\frac{(2M+M_{h})D{\lambda}k}{C}\right)+1,$

where the last inequality is due to Lemma 3.5.

b) This statement follows from the same argument as in the proof of Theorem
2.1(b) except that Lemma 4.3 is used in place of Lemma 3.7. ∎

Theorem 2.2 derives a convergence rate bound for SCPB under the conditions
(A1)-(A7) and (B2). The following result describes the iteration-complexity
for SCPB under the same conditions to obtain an $\bar{\varepsilon}$-pair of
(1) in expectation.

######  Corollary 4.4.

Assume that conditions (A1)-(A7) hold. Moreover, for a given $C>0$, assume
that (B2) holds for every $k\geq 1$. Let tolerance $\bar{\varepsilon}>0$ be
given and set the input $K$ of SCPB as

$\displaystyle K_{\bar{\varepsilon}}$
$\displaystyle:=\left\lfloor\frac{3C+d_{0}^{2}}{{\lambda}\bar{\varepsilon}}+\frac{2{\lambda}M^{2}+2\sigma}{\theta\bar{\varepsilon}}+\frac{\sqrt{2{\lambda}}M}{\theta\sqrt{\bar{\varepsilon}}}\right\rfloor+1.$
(65)

Then, the pair
$(\hat{y}_{K}^{a},\hat{u}_{K}^{a})\in\mathbb{R}^{n}\times\mathbb{R}$ found by
SCPB is an $\bar{\varepsilon}$-pair in expectation, i.e., it satisfies (55).
Moreover, the expected overall iteration/resolvent evaluation complexity of
SCPB is given by

${\cal O}\left(K_{\bar{\varepsilon}}\left[\left\lceil(1+\theta
K_{\bar{\varepsilon}})\log\left(\frac{{\lambda}(M+M_{h})DK_{\bar{\varepsilon}}}{C}+1\right)\right\rceil+1\right]\right)$
(66)

where ${\lambda}$ and $\theta$ are the other two inputs for SCPB and $C>0$ is
as in (B2).

Proof: It immediately follows from Theorem 2.2(b) and the definition of
$K_{\bar{\varepsilon}}$ in (65) that (55) holds. The complexity bound (66)
directly follows from Theorem 2.2(a).

It follows from Corollary 4.4 that, in terms of $\bar{\varepsilon}$ only, the
iteration/resolvent evaluation complexity to obtain an
$\bar{\varepsilon}$-pair of (1) is ${\cal O}(\varepsilon^{-2})$, up to a
logarithmic term.

######  Corollary 4.5.

Assume that conditions (A1)-(A7) and condition (B2) with $C=D^{2}$ hold where
$D$ is as in (A5). Let tolerance $\bar{\varepsilon}>0$ be given, and consider
SCPB with input triple $({\lambda},\theta,K)$ where ${\lambda}$ is arbitrary
and $(\theta,K)$ is given by

$\theta=\frac{{\lambda}^{2}M^{2}+{\lambda}\sigma}{D^{2}},\quad
K=K_{\bar{\varepsilon}}$ (67)

where $K_{\bar{\varepsilon}}$ is as in (65). Then, its expected overall
iteration/resolvent evaluation complexity (up to a logarithmic term) is

${\cal O}\left(\frac{M^{2}D^{2}}{\bar{\varepsilon}^{2}}+\frac{\sigma
D^{2}}{{\lambda}\bar{\varepsilon}^{2}}+1\right).$ (68)

Proof: It follows from (65) with $C=D^{2}$ and the fact that $d_{0}\leq D$
that

$K_{\bar{\varepsilon}}={\cal
O}\left(\frac{D^{2}}{{\lambda}\bar{\varepsilon}}+\frac{{\lambda}M^{2}+\sigma}{\theta\bar{\varepsilon}}+1\right).$
(69)

We observe from (66) that the overall complexity (up to a logarithmic term) is

${\cal O}(\theta K_{\bar{\varepsilon}}^{2}+1)={\cal O}\left(\frac{\theta
D^{4}}{{\lambda}^{2}\bar{\varepsilon}^{2}}+\frac{{\lambda}^{2}M^{4}+\sigma^{2}}{\theta\bar{\varepsilon}^{2}}+\frac{D^{2}M^{2}}{\bar{\varepsilon}^{2}}+1\right).$

This observation, the first identity in (67) and (69) immediately imply bound
(68).

If, in addition to the assumptions of Corollary 4.5, we assume
$\sigma/{\lambda}={\cal O}(M^{2})$, then the complexity bound (68) for SCPB
reduces to (58), which is known to be optimal in the deterministic setting.

##  5 Numerical experiments

In this section, we test our one-cut stochastic bundle method SCPB on three
simple stochastic programs. The correctness of the method and implementation
will be checked comparing the approximate optimal values (and CPU time)
obtained running SMD (Stochastic Mirror Descent) and SCPB on these problems.

The first (two-stage) stochastic program is

$\left\\{\begin{array}[]{l}\min\;c^{T}x_{1}+\mathbb{E}[\mathfrak{Q}(x_{1},\xi)]\\\
x_{1}\in\mathbb{R}^{n}:x_{1}\geq 0,\sum_{i=1}^{n}x_{1}(i)=1\end{array}\right.$
(70)

where the second stage recourse function is given by

$\mathfrak{Q}(x_{1},\xi)=\left\\{\begin{array}[]{l}\displaystyle\min_{x_{2}\in\mathbb{R}^{n}}\;\frac{1}{2}\left(\begin{array}[]{c}x_{1}\\\
x_{2}\end{array}\right)^{T}\Big{(}\xi\xi^{T}+\lambda_{0}I_{2n}\Big{)}\left(\begin{array}[]{c}x_{1}\\\
x_{2}\end{array}\right)+\xi^{T}\left(\begin{array}[]{c}x_{1}\\\
x_{2}\end{array}\right)\\\ x_{2}\geq
0,\displaystyle\sum_{i=1}^{n}x_{2}(i)=1.\end{array}\right.$ (71)

The second (two-stage) stochastic program is

$\left\\{\begin{array}[]{l}\min\;c^{T}x_{1}+\mathbb{E}[\mathfrak{Q}(x_{1},\xi)]\\\
x_{1}\in\mathbb{R}^{n}:\|x_{1}-x_{0}\|_{2}\leq 1\end{array}\right.$ (72)

where cost-to-go function $\mathfrak{Q}(x_{1},\xi)$ has nonlinear objective
and constraint coupling functions and is given by

$\mathfrak{Q}(x_{1},\xi)=\left\\{\begin{array}[]{l}\displaystyle\min_{x_{2}\in\mathbb{R}^{n}}\;\frac{1}{2}\left(\begin{array}[]{c}x_{1}\\\
x_{2}\end{array}\right)^{T}\Big{(}\xi\xi^{T}+\lambda_{0}I_{2n}\Big{)}\left(\begin{array}[]{c}x_{1}\\\
x_{2}\end{array}\right)+\xi^{T}\left(\begin{array}[]{c}x_{1}\\\
x_{2}\end{array}\right)\\\
\frac{1}{2}\|x_{2}-y_{0}\|_{2}^{2}+\frac{1}{2}\|x_{1}-x_{0}\|_{2}^{2}-\frac{R^{2}}{2}\leq
0.\end{array}\right.$ (73)

These two problems were used in the numerical experiments on SMD and Inexact
SMD in [6].

The third stochastic program (used in the numerical experiments on SMD in
[14]) is given by

$\min_{x\in
X}\mathbb{E}\left[\phi\left(\displaystyle\sum_{i=1}^{n}(\frac{i}{n}+\xi_{i})x_{i}\right)\right]$
(74)

where

$X=\\{x\in\mathbb{R}^{n}:x\geq 0,\sum_{i=1}^{n}x(i)=1\\},$ (75)

$\xi_{i}\sim\mathcal{N}(0,1)$ are independent and
$\phi(t)=\max({v_{1}+s_{1}t,\ldots,v_{m}+s_{m}t)}$ is piecewise convex with 10
breakpoints, all located on $[0,1]$.

Problems (70) and (72) are of form (1)-(2) where
$F(x,\xi)=c^{T}x+\mathfrak{Q}(x,\xi)$ with $\mathfrak{Q}$ given by (71)
(resp., (73)) for problem (70) (resp., problem (72)) and where $h$ is the
indicator function of set $X$ (resp., $Y$) for problem (70) (resp., problem
(72)) where $X$ given by (75) is the probability simplex and $Y$ is the ball

$Y=\\{x\in\mathbb{R}^{n}:\|x-x_{0}\|_{2}\leq 1\\}.$

For problems (70) and (72), we refer to Lemma 2.1 in [4] for the computation
of stochastic subgradients $s(x,\xi)$. Problem (74) is also clearly of form
(1)-(2) and for all three problems $h$ is the indicator function of a convex
set and is therefore $\mu$-convex with $\mu=0$.

For problems (70) and (72) we take $\lambda_{0}=2$ and consider a Gaussian
random vector in $\mathbb{R}^{2n}$ for $\xi$. We consider two instances of
problems (70) and (72) with $n=50$ and $n=100$. For each instance, the
components of $\xi$ are independent with means and standard deviations
randomly generated in respectively intervals $[5,25]$ and $[5,15]$. The
components of $c$ are generated randomly in interval $[1,3]$. For problem
(72)-(73) we also take $R=5$ and $x_{0}(i)=y_{0}(i)=10,i=1,\ldots,n$. The only
information available for the optimization algorithms are samples from the
distribution of $\xi$. The implementations were coded in Matlab, using Mosek
optimization library [1] to solve subproblems, and run on a laptop with Intel
i7, 1.80GHz processor.

We consider four variants of SCPB:

  * •

SCPB with sequence $j_{k}$ given by (B1) with $C=1$ and $\tau=0.9$ (denoted
Bundle 1, $\tau=0.9$ or B19 for short);

  * •

SCPB with sequence $j_{k}$ given by (B1) with $C=1$ and $\tau=0.8$ (denoted
Bundle 1, $\tau=0.8$ or B18 for short);

  * •

SCPB with sequence $j_{k}$ given by (B2) with $C$ the square of the diameter
of $X$ for problems (70) and (74) and the square of the diameter of $Y$ for
problem (72) and $\tau=0.9$ (denoted Bundle 2, $\tau=0.9$ or B29 for short);

  * •

SCPB with sequence $j_{k}$ given by (B2) with $C$ the square of the diameter
of $X$ for problems (70) and (74) and the square of the diameter of $Y$ for
problem (72) and $\tau=0.8$ (denoted Bundle 2, $\tau=0.8$ or B28 for short).

For SMD run $N$ iterations, we take the constant step size
$\gamma=\frac{\theta}{\sqrt{N}}$, with $\theta=1$ in our experiments.

Experiments for problem (70). We run on an instance of (70) with $n=50$ and an
instance of (70) with $n=100$ the four variants B19, B18, B29, and B28 of SPCB
defined above for $K=4000$ outer iterations and SMD for $N=4000$ iterations.
The same samples of $\xi$ are used for all five solutions methods. For several
values of the number of outer iterations for bundle methods and of the number
of iterations for SMD (iterations 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60,
70, 80, 90, 100, 500, 1000, 1500, 2000, 2500, 3000, 3500, and 4000), we report
in Figure 1 an estimation of the objective function at the approximate
solution obtained along iterations. This estimation is obtained using a sample
of size 1000 of $\xi$ independent from the sample used in the algorithms (the
same sample is used for all iterations in these estimations). We see that
three of the four bundle variants (B29, B18, B28) obtain after a few outer
iterations an almost optimal solution. With B19, the approximate optimal
solution for the first hundreds iterations are better than with SMD but it
takes 3000 outer iterations to get a solution with approximate optimal value
within at most 5% of the approximate optimal value obtained with SMD after
4000 iterations. More precisely, in Tables 1 and 2, we report the outputs
obtained with all bundle methods when they obtain an approximate optimal value
which is at at most 5% above the approximate optimal value obtained with SMD
for $N=4000$ iterations. The number of outer and inner iterations as well as
the CPU time are given. We see that on these instances three of the four
bundle methods obtain a good solution much quicker than SMD.

|
---|---
|
Figure 1: Approximate optimal values to solve instances of problem (70) with $n=50$ (top left figure), $n=100$ (top right figure) and instances of problem (72) with $n=50$ (bottom left figure), $n=100$ (bottom right figure) along iterations of SMD and outer iterations of four variants of bundle one cut (SCPB).  Output |  | Bundle 1
---
$\tau=0.8$
| Bundle1
---
$\tau=0.9$
| Bundle 2
---
$\tau=0.8$
| Bundle2
---
$\tau=0.9$
SMD
Outer iterations | 10 | 3000 | 10 | 10 | 4000
Inner iterations | 20 | 17325 | 20 | 20 | -
CPU time (s) | 0.68 | 569.5 | 0.78 | 0.82 | 48.5
Objective value | 3.32 | 3.32 | 3.31 | 3.27 | 3.30
Table 1: CPU time, number of iterations, and approximate optimal values to solve an instance of problem (70) for $n=50$ with SMD and four variants of SCPB. Output |  | Bundle 1
---
$\tau=0.8$
| Bundle1
---
$\tau=0.9$
| Bundle 2
---
$\tau=0.8$
| Bundle2
---
$\tau=0.9$
SMD
Outer iterations | 10 | 3000 | 10 | 10 | 4000
Inner iterations | 20 | 17325 | 20 | 20 | -
CPU time (s) | 3.03 | 2550 | 3.57 | 3.56 | 234.8
Objective value | 1.21 | 1.23 | 1.17 | 1.14 | 1.18
Table 2: CPU time, number of iterations, and approximate optimal values to
solve an instance of problem (70) for $n=100$ with SMD and four variants of
SCPB.

On these two instances, all bundle methods but B19 computed in a few outer
iterations an almost optimal solution. To try and improve the performance of
B19 we tested several values of $C$ (a parameter of B19) in Assumption (B1):
$C=1,0.5,0.1$ and apply the corresponding B19 methods to solve an instance of
(70) with $n=50$. We report in Figure 2 the evolution of the approximate
optimal values obtained along several outer iterations and see that on this
instance the smallest tested value of $C$ was the best.

---
Figure 2: Approximate optimal values to solve an instance of problem (70) with
$n=50$ along iterations of B19 and three values of $C$.

Experiments for problem (72). We repeat the experiments we have just reported
for problem (70) on an instance of problem (72) with $n=50$ and an instance of
problem (73) with $n=100$. For these instances, we limited the number of SMD
iterations and bundle outer iterations to 50, which was enough to obtain good
solutions. The results are reported in Figure 1 and Tables 3 and 4. For these
instances, variants B18 and B19 of SCPB provide an approximate optimal
solution quicker than SMD.

Output |  | Bundle 1
---
$\tau=0.8$
| Bundle1
---
$\tau=0.9$
| Bundle 2
---
$\tau=0.8$
| Bundle2
---
$\tau=0.9$
SMD
Outer iterations | 3 | 3 | 3 | 3 | 50
Inner iterations | 6 | 6 | 78 | 146 | -
CPU time (s) | 0.37 | 0.36 | 3.46 | 6.30 | 0.93
Objective value | 9.909$\small{\times}10^{7}$ | 9.915$\small{\times}10^{7}$ | 9.893$\small{\times}10^{7}$ | 9.901$\small{\times}10^{7}$ | 9.900$\small{\times}10^{7}$
Table 3: CPU time, number of iterations, and approximate optimal values to solve an instance of problem (72) for $n=50$ with SMD and four variants of SCPB. Output |  | Bundle 1
---
$\tau=0.8$
| Bundle1
---
$\tau=0.9$
| Bundle 2
---
$\tau=0.8$
| Bundle2
---
$\tau=0.9$
SMD
Outer iterations | 3 | 3 | 3 | 3 | 50
Inner iterations | 6 | 6 | 87 | 169 | -
CPU time (s) | 1.24 | 1.02 | 13.44 | 20.27 | 2.74
Objective value | 4.181$\small{\times}10^{8}$ | 4.182$\small{\times}10^{8}$ | 4.180$\small{\times}10^{8}$ | 4.179$\small{\times}10^{8}$ | 4.182$\small{\times}10^{8}$
Table 4: CPU time, number of iterations, and approximate optimal values to
solve an instance of problem (72) for $n=100$ with SMD and four variants of
SCPB.

Experiments for problem (74). Finally, we repeat the experiments reported for
problem (70) on an instance of problem (74) with $n=100$ and an instance of
problem (74) with $n=500$. The analogue of Figure 1 for the instance with
$n=100$ is Figure 3. For the instance with $n=100$ (resp., $n=500$) we report
in Table 5 (resp., Table 7) the approximate optimal values and CPU time along
some iterations of SMD. For the four bundle methods, the approximate optimal
values, CPU time, and inner iterations are given for the instance with $n=100$
(resp., $n=500$) in Table 6 (resp., Table 8). For $n=100$, SCPB and SMD
exhibit similar performance but, for $n=500$, SCPB variants obtain a good
solution quicker.

---
Figure 3: Approximate optimal values to solve an instance of problem (74) with $n=100$ along iterations of SMD and outer iterations of four variants of bundle one cut (SCPB).  Iterations | 2000 | 4000 | 30 000 | 100 000
---|---|---|---|---
CPU time (s) | 0.05 | 0.09 | 0.62 | 2.1
Objective value | 12.02 | 12.01 | 11.9900 | 11.9857
Table 5: CPU time, number of iterations, and approximate optimal values to solve an instance of problem (74) for $n=100$ with SMD. Output |  | Bundle 1
---
$\tau=0.8$
| Bundle1
---
$\tau=0.9$
| Bundle 2
---
$\tau=0.8$
| Bundle2
---
$\tau=0.9$
Outer iterations | 800 | 800 | 800 | 800
Inner iterations | 1600 | 1600 | 1600 | 1600
CPU time (s) | 3.9 | 3.8 | 3.8 | 4.0
Objective value | 11.9886 | 11.9886 | 11.9890 | 11.9890
Table 6: CPU time, number of iterations, and approximate optimal values to solve an instance of problem (74) for $n=100$ with four variants of SCPB. Iterations | 2000 | 5000 | 60 000 | 150 000
---|---|---|---|---
CPU time (s) | 0.09 | 0.23 | 2.74 | 6.88
Objective value | 12.020 | 12.008 | 11.998 | 11.995
Table 7: CPU time, number of iterations, and approximate optimal values to solve an instance of problem (74) for $n=500$ with SMD. Output |  | Bundle 1
---
$\tau=0.8$
| Bundle1
---
$\tau=0.9$
| Bundle 2
---
$\tau=0.8$
| Bundle2
---
$\tau=0.9$
Outer iterations | 10 | 10 | 100 | 100
Inner iterations | 20 | 20 | 200 | 200
CPU time (s) | 0.18 | 0.18 | 1.68 | 1.66
Objective value | 11.9949 | 11.9949 | 11.9949 | 11.9949
Table 8: CPU time, number of iterations, and approximate optimal values to
solve an instance of problem (74) for $n=500$ with four variants of SCPB.

## References

  * [1] E. D. Andersen and K.D. Andersen.  The MOSEK optimization toolbox for MATLAB manual. Version 9.2, 2019\.  https://www.mosek.com/documentation/.
  * [2] J. Birge and F. Louveaux.  Introduction to Stochastic Programming.  Springer-Verlag, New York, 1997.
  * [3] J.R. Birge and F.V. Louveaux.  A multicut algorithm for two-stage stochastic linear programs.  European Journal of Operational Research, 34:384–392, 1988.
  * [4] V. Guigues.  Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs.  SIAM Journal on Optimization, 26:2468–2494, 2016.
  * [5] V. Guigues.  Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures.  Mathematical Programming, 163:169–212, 2017.
  * [6] V. Guigues.  Inexact Stochastic Mirror Descent for two-stage nonlinear stochastic programs.  Mathematical Programming, 187:533–577, 2021.
  * [7] V. Guigues, A. Juditsky, and A. Nemirovski.  Non-asymptotic confidence bounds for the optimal value of a stochastic program.  Optimization Methods & Software, 32:1033–1058, 2017.
  * [8] V. Guigues, W. Tekaya, and M. Lejeune.  Regularized decomposition methods for deterministic and stochastic convex optimization and application to portfolio selection with direct transaction and market impact costs.  Optimization & Engineering, 21:1133–1165, 2020.
  * [9] J.L. Higle and S. Sen.  Stochastic Decomposition.  Kluwer, Dordrecht, 1996.
  * [10] A.J. King and R.T. Rockafellar.  Asymptotic theory for solutions in statistical estimation and stochastic programming.  Math. Oper. Res., 18:148–162, 1993.
  * [11] A. J. Kleywegt, A. Shapiro, and T. Homem-de Mello.  The sample average approximation method for stochastic discrete optimization.  SIAM Journal on Optimization, 12(2):479–502, 2002.
  * [12] J. Liang and R. D. C. Monteiro.  A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes.  SIAM Journal on Optimization, 31(4):2955–2986, 2021.
  * [13] J. Liang and R. D. C. Monteiro.  A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems.  Available on arXiv:2110.01084, 2021.
  * [14] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro.  Robust stochastic approximation approach to stochastic programming.  SIAM J. Optim., 19:1574–1609, 2009.
  * [15] A. Nemirovski and D. Yudin.  On Cezari’s convergence of the steepest descent method for approximating saddle point of convex-concave functions.  Soviet Math. Dokl., 19, 1978.
  * [16] Y. Nesterov.  Primal-dual subgradient methods for convex problems.  Mathematical programming, 120(1):221–259, 2009.
  * [17] B.T. Polyak.  New stochastic approximation type procedures.  Automat. i Telemekh (English translation: Automation and Remote Control), 7:98–107, 1990.
  * [18] B.T. Polyak and A. Juditsky.  Acceleration of stochastic approximation by averaging.  SIAM J. Contr. and Optim., 30:838–855, 1992.
  * [19] H. Robbins and S. Monroe.  A stochastic approximation method.  Annals of Math. Stat., 22:400–407, 1951.
  * [20] A. Shapiro.  Asymptotic analysis of stochastic programs.  Ann. Oper. Res., 30:169–186, 1991.
  * [21] A. Shapiro, D. Dentcheva, and A. Ruszczyński.  Lectures on Stochastic Programming: Modeling and Theory.  SIAM, Philadelphia, 2009.
  * [22] R.M. Van Slyke and R.J.-B. Wets.  L-shaped linear programs with applications to optimal control and stochastic programming.  SIAM Journal of Applied Mathematics, 17:638–663, 1969.
  * [23] B. Verweij, S. Ahmed, A. J. Kleywegt, G. Nemhauser, and A. Shapiro.  The sample average approximation method applied to stochastic routing problems: a computational study.  Computational Optimization and Applications, 24(2-3):289–333, 2003\.