A single cut proximal bundle method for
stochastic convex composite optimization

Let $\mathbb{N}_{++}$ denote the set of positive integers. The sets of real numbers, non-negative and positive real numbers are denoted by $\mathbb{R}$, $\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$. 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)$. Moreover, a proper function $\psi:\mathbb{R}^{n}\rightarrow(-\infty,+\infty]$ is $\mu$-strongly convex for some $\mu\geq 0$ if

for every $z,u\in\mathrm{dom}\,\psi$ and $\alpha\in[0,1]$. Note that we say $\psi$ is convex when $\mu=0$. 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$. Define $\ln_{0}^{+}(\cdot):=\max\{0,\ln(\cdot)\}$. Define the diameter of a set $X$ to be $D_{X}:=\sup\{\|x-x^{\prime}\|:x,x^{\prime}\in\mathrm{dom}\,X\}$.

Let $\Xi$ denote the support of random vector $\xi$ and assume that the following conditions on (1) are assumed to hold:

We now make some observations about the above conditions. First, as in [22], condition (A2) does not require $F(\cdot,\xi)$ to be convex. Second, condition (A3) implies that

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

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

where $\phi(\cdot)$ is as in (1). Hence, $\ell(\cdot;x,\xi)$ is a stochastic composite linear approximation of $\phi(\cdot)$ in the sense that its expectation is a true composite linear approximation of $\phi(\cdot)$. (The terminology “composite” refers to the function $h$ which is included in the approximation $\ell(\cdot;x,\xi)$ as is.)

Before describing the two SCPB variants, we motivate them by interpreting them as inexact implementations of the (theoretical) proximal point method for solving (1).

Their $k$-th cycle of iterations performs a finite number of iterations to solve the prox subproblem

where $\hat{x}_{k-1}$ denotes the prox-center during the cycle. Each iteration within the cycle solves a subproblem of the form

where ${\cal A}(\cdot)$ is an affine bundle for $f$ in expectation, i.e., an affine function such that $\mathbb{E}[{\cal A}(\cdot)]\leq f(\cdot)$. (This type of bundle has been considered in the inexact proximal point approach considered in [20] where it is referred to as a one-cut bundle for $f$.) The bundle ${\cal A}^{+}$ for the next subproblem in the cycle is then taken to be a linear combination of the current bundle ${\cal A}$ and a newly generated stochastic linear approximation of $f$ of the form $F(x,\xi)+\langle s(x,\xi),\cdot-x\rangle$. Moreover, the first iteration of every cycle starts by setting the prox-center to the most recently generated $x$ as in (7) and the bundle to the most recently generated stochastic linear approximation of $f$ at $x$.

Both SCPB variants are based on the SCPB scheme described below. As stated below, the scheme is not a completely specified algorithm since its step 2 does not describe how to select the index $j_{k}$. Two rules for doing so, and hence the complete description of the two aforementioned SCPB variants, are then given following the statement of the scheme.

At every iteration $j\geq 1$, the SCPB scheme samples an independent realization $\xi_{j-1}$ of $\xi$.

SCPB

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

it immediately follows that $k$ counts the number of cycles generated by SCPB. Third, step 1 determines two types of iterations depending on whether $j=j_{k}$ (serious iteration) or $j\in{\cal C}_{k}\setminus\{j_{k}\}$ (null iteration). Hence, the last iteration of a cycle is a serious one while the others are null ones.

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 (11), the sequence $\{x_{j}\}$ determined by (15), and the sequence $\{y_{j}\}$ given by (18). Third, it follows from (11) that $x^{c}_{j}=x_{j_{k-1}}$ for every $j\in{\cal C}_{k}$. Hence, the prox-center $x^{c}_{j}$ remains constant between consecutive iterations within a cycle and (possibly) changes only at the beginning of the first iteration of the following cycle. Fourth, $\{\hat{y}_{k}\}$ is the subsequence of $\{y_{j}\}$ consisting of all the last cycle iterates $y_{j_{k}}$ generated by SCPB. Fifth, the convergence rates for the two specific variants of the SCPB scheme described below 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 (19) (see Theorems 3.1 and 4.1 below).

As already mentioned in the second paragraph preceding the description of SCPB, the scheme is not completely specified since its step 2 does not describe how to select $j_{k}$. We now describe two cycle rules for doing so which depend on a pre-specified parameter $R>0$, namely:

• (B1)

  for every $k\geq 1$, let $j_{k}$ be the smallest integer $\geq i_{k}$ such that ${\lambda}k\tau^{j_{k}-i_{k}}\leq R$;

• (B2)

  for every $k\geq 1$, let $j_{k}$ be the smallest integer $\geq i_{k}+1$ such that

  $${\lambda}k\tau^{j_{k}-i_{k}}\left(F(x_{i_{k}},\xi_{i_{k}})-\tilde{\ell}_{k}(x_{i_{k}})-\frac{1}{2{\lambda}}\|x_{i_{k}}-x_{i_{k}}^{c}\|^{2}\right)\leq R$$

  (21)

  where $i_{k}$ is as in (20) and

  $$\tilde{\ell}_{k}(\cdot):=F(x_{i_{k}-1},\xi_{i_{k}-1})+\langle s(x_{i_{k}-1},\xi_{i_{k}-1}),\cdot-x_{i_{k}-1}\rangle.$$

  (22)

We make the following remarks about cycle rules (B1) and (B2). First, the sequence $\{j_{k}\}$ determined by the cycle rule (B1) is deterministic, while the one determined by (B2) is stochastic since the sequence $\{x_{i_{k}}\}$ used in (21) is stochastic. Second, another difference between the two cycle rules is that (B1) allows $j_{k}=i_{k}$, while $j_{k}$ in (B2) is at least $i_{k}+1$. In other words, the cycle length for (B1) may be equal to one, but the one for (B2) is at least two. Third, the length of cycle ${\cal C}_{k}$ for both rules above depends on the cycle index $k$. Hence, even though (B1) is deterministic, the length of the cycles generated by it changes with $k$.

Throughout our presentation, SCPB based on cycle rule (B1) (resp., (B2)) is referred to as SCPB1 (resp., SCPB2).

The following result states a general convergence rate result for SCPB1 that holds for bounded $\mathrm{dom}\,h$ and for any choice of input $({\lambda},\theta,K)$ in SCPB1 and constant $R$ as in (B1). The proof is postponed to Subsection 5.2.

We now make some remarks about Theorem 3.1. First, its overall iteration complexity is given by $K$, which is its outer iteration complexity, times its inner iteration complexity given in (23). Second, (24) gives a bound on the expected primal gap $\mathbb{E}[\phi(\hat{y}_{K}^{a})]-\phi_{*}$ in terms of $K$, and hence provides a sufficient condition on how large $K$ should be chosen for SCPB1 to generate a desired approximate solution.

Even though Theorem 3.1 holds for the general case in which $\mathrm{dom}\,h$ is unbounded, all its corollaries stated in this subsection and Subsection 3.3 assume that $\mathrm{dom}\,h$ is bounded. For any given $({\lambda},K)$, the following result describes a convergence rate bound for SCPB1 with a specific choice of $(\theta,R)$.

b) It follows from Theorem 3.1(a) that the overall complexity (up to a logarithmic term) is ${\cal O}(\theta K^{2}+K)$, which in turn is (27) in view of $\theta$ as in (25).    

We now argue that the overall iteration (and sample) complexity of the SCPB1 variant of Corollary 3.2 for finding an $\varepsilon$-solution $x$ of (1), i.e., one that satisfies $\mathbb{E}[\phi(x)]-\phi_{*}\leq\varepsilon$, is optimal for a large range of prox stepsizes. Indeed, setting $K=\lceil T_{\varepsilon}\rceil$ where

it follows from the above result that $\mathbb{E}[\phi(\hat{y}_{K}^{a})]-\phi_{*}\leq\varepsilon$. Since $K\leq T_{\varepsilon}+1$, we conclude from (27) that the expected overall iteration complexity of SCPB1 is bounded by

In particular, if $D\geq D_{h}$ and $M\geq\bar{M}$, or equivalently, $\kappa_{D}\leq 1$ and $\kappa_{M}\leq 1$, then the above complexity reduces to

Moreover, under the assumption that the prox stepsize $\lambda$ lies in the interval $[\varepsilon/M^{2},D^{2}/\varepsilon]$, the above complexity bound further reduces to ${\cal O}(M^{2}D^{2}/\varepsilon^{2})$, which is known to be the optimal complexity of finding an $\varepsilon$-solution for any instance of (1) such that its corresponding pair $(D_{h},\bar{M})$ satisfies the condition that $D\geq D_{h}$ and $M\geq\bar{M}$ (e.g., see [24]).

We argue in this subsection that RSA can be viewed as a special instance of SCPB1 where every cycle ${\cal C}_{k}$ contains only one index (or equivalently, an instance for which every iteration is serious).

Recall that the RSA method of [22], which is developed under the assumption that $h$ is the indicator function of a nonempty compact convex set $X$, with a given initial point $x_{0}\in X$ and constant prox stepsize ${\lambda}>0$ recursively computes its iteration sequence $\{x_{j}\}_{j=1}^{N}$ according to

For the purpose of reviewing the iteration complexity of RSA, assume that $D$ is an upper bound on the diameter of $X$ and $M$ is an upper bound on $\bar{M}$. For $1\leq i\leq N$, let $\tilde{x}_{i}^{N}$ denote the average of the iterates $\{x_{j}\}_{j=i}^{N}$, i.e.,

It is shown in equation (2.24) of [22] that if the stepsize ${\lambda}>0$ is chosen as

for some fixed scalar $\alpha>0$, then the ergodic iterate $\tilde{x}^{N}_{i}$ with $i=\lfloor N/2\rfloor+1$ satisfies

Hence, for a given tolerance $\varepsilon>0$, the smallest $N$ satisfying $\mathbb{E}[\phi(\tilde{x}^{N}_{\lfloor N/2\rfloor+1})]-\phi_{*}\leq\varepsilon$ has the property that

It turns out that RSA is a special case of SCPB1 with $R$ in (B1) given by

Indeed, it follows from the above choice of $R$ and ${\lambda}$ as in (30) with $N$ replaced by $K$ that

and hence that $j_{k}=i_{k}$ satisfies (B1). Thus, every cycle only performs one iteration, i.e., its only serious iteration. Moreover, every iteration of this SCPB1 variant is a serious one and $K$ is its total number of iterations.

From a computational point of view, the choice of $\theta$ in Corollary 3.2 usually results in the quantity $\theta K$, and hence the inner complexity bound (23), being large. The following result provides a practical variant of SCPB1 with an alternative choice for $\theta$ and $R$ which partially remedies the above drawback by forcing $\theta K$ to be constant. A nice feature of this variant is that it is able to choose large prox stepsizes without loosing the optimality of its overall iteration complexity.

b) This statement immediately follows from Theorem 3.1(a) with $\theta$, $R$, and ${\lambda}$ as in (33).

c) This statement follows from (b) and the fact that SCPB1 has $K$ cycles.    

We now make two remarks about the practical SCPB1 variant of Corollary 3.3. First, although $\theta$ in (33) depends neither on $M$ nor $D$, the choice of $R$ depends on both of these estimates. On the other hand, SCPB2 will be analyzed in Section 4 where $\theta$ depends neither on $M$ nor $D$, and $R$ depends on $D$ but not $M$. Second, Corollary 3.3 (see its statement (b)) implies that the number of iterations within a cycle of SCPB1 is bounded (up to a logarithmic term) by the a priori (user specified) constant $C$. Thus, the SCPB1 variant of Corollary 3.3 can be viewed as an extended version of RSA where the number of iterations within a cycle can be larger than one, instead of being equal to one as in RSA (see the discussion in the second paragraph of Subsection 3.2).

In the remaining part of this subsection, we compare the performance of RSA and SCPB1 when both use the prox stepsize ${\lambda}$ as in (33) for some relatively large scalar $C\geq 1$. For this discussion, we assume that their performance measure is the overall iteration complexity (or sample complexity) for finding an $\varepsilon$-solution of (1). For simplicity, we assume as in Subsection 3.2 that $h$ is the indicator function of a nonempty closed convex set and that the estimation pair $(D,M)$ satisfies $D\geq D_{h}$ and $M\geq\bar{M}$, or equivalently, $\kappa_{D}\leq 1$ and $\kappa_{M}\leq 1$.

We first consider the performance (see the previous paragraph) of SCPB1. It follows from Corollary 3.3(a) that there exists $K={\cal O}(D^{2}M^{2}/(C\varepsilon^{2}))$ such that $\hat{y}_{K}^{a}$ is an $\varepsilon$-solution of (1). Hence, it follows from Corollary 3.3(c) that the performance of SCPB1 is ${\cal O}(M^{2}D^{2}/\varepsilon^{2})$. In conclusion, SCPB1 with the above choice of $K$ is able to choose a prox stepsize ${\lambda}$ as in (33) with a large constant $C$ while preserving its optimal performance. We now consider the performance of RSA. It follows from (30) and (32) with $\alpha=\sqrt{C}$ that the performance of RSA is ${\cal O}\left(CD^{2}M^{2}/\varepsilon^{2}\right)$. In conclusion, while both RSA and SCPB1 with prox stepsize ${\lambda}$ as in (33) have their own performance guarantee, the one for RSA becomes worse than that of SCPB1 as $C$ becomes large.

Finally, although the SCPB1 variant of Corollary 3.3 chooses ${\lambda}$ as in (33), our numerical experiments uses a more aggressive prox stepsize, i.e.,

where $\beta_{1}=10$. It is possible to show that similar conclusions (with slightly modified bounds) as those of Corollary 3.3 hold for this choice of $\lambda$. Finally, SCPB1 with this prox stepsize ${\lambda}$ substantially outperforms RSA on the (relatively small number of) instances considered in the computational experiments of Section 6.

We assume Assumption 2.1 holds throughout this subsection. Recall that for every $j\geq 0$

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$. For convenience, in what follows we set

For every $k\geq 1$ and $j\in{\cal C}_{k}$, define

and

where $\Phi(\cdot,\xi)$ and $\ell(\cdot;x,\xi)$ are as in (5) and and $\tilde{\ell}_{k}(\cdot)$ is as in (22). It is easy to see from (14), (15), and the above definition of $\Gamma_{j}$ that

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