An incremental mirror descent subgradient algorithm with random sweeping and proximal step

ABSTRACT

We investigate the convergence properties of incremental mirror descent type subgradient algorithms for minimizing the sum of convex functions. In each step, we only evaluate the subgradient of a single component function and mirror it back to the feasible domain, which makes iterations very cheap to compute. The analysis is made for a randomized selection of the component functions, which yields the deterministic algorithm as a special case. Under supplementary differentiability assumptions on the function which induces the mirror map, we are also able to deal with the presence of another term in the objective function, which is evaluated via a proximal type step. In both cases, we derive convergence rates of $\mathcal{O}\left(1/\sqrt{k}\right)$ in expectation for the kth best objective function value and illustrate our theoretical findings by numerical experiments in positron emission tomography and machine learning.

KEYWORDS:

• Nonsmooth convex minimization
• incremental mirror descent algorithm
• global rate of convergence
• random sweeping

AMS SUBJECT CLASSIFICATIONS:

• 90C25
• 90C90
• 90C06

1. Introduction

We consider the problem of minimizing the sum of nonsmooth convex functions (1) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right),$(1) where $C\subseteq {\mathbb{R}}^n$ is a nonempty, convex and closed set and, for every $i=1,\dots ,m$, the so-called component functions $f_i:{\mathbb{R}}^n\to \overline{\mathbb{R}}:=\mathbb{R}\cup \{\pm \mathrm{\infty }\}$ are assumed to be proper and convex and will be evaluated via their respective subgradients. Implicitly we will assume that m is large and it is therefore very costly to evaluate all component functions in each iteration. Consequently, we will examine algorithms which only use the subgradient of a single component function in each iteration. These so-called incremental algorithms, see [1,2], have been applied for large-scale problems arising in tomography [3], generalized assignment problems [2] or machine learning [4]. We refer also to [5] for a slightly different approach, where in the spirit of incremental algorithms only the gradient of one of the component functions is evaluated in each step, but gradients at old iterates are used for the other components. Both subgradient algorithms and incremental methods usually require decreasing stepsizes in order to converge, which makes them slow near an optimal solution. However, they provide a very small number of iterations a low accuracy optimal value and possess a rate of convergence which is almost independent of the dimension of the problem. We refer the reader to [6] for a subgradient algorithm designed for the minimization of a nonsmooth nonconvex function under the making use of proximal subgradients.

When solving optimization problems of type (1(1) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right),$(1) ), one might want to capture in the formulation of the iterative scheme the geometry of the feasible set C. This can be done by a so-called mirror map, that mirrors each iterate onto the feasible set. The Bregman distance associated with the function that induces the mirror map plays an essential role in the convergence analysis and in the formulation of convergence rates results (see [7,8]). So-called mirror descent algorithms were first discussed in [9] and more recently in [8,10,11] in a very general framework, in [4,12] from a statistical learning point of view and in [13] for the case of dynamical systems. The mirror map can be viewed as a generalization of the ordinary orthogonal projection on C in Hilbert spaces (see Example 2.4), but allows also for a more careful consideration of the structure of the problems, as it is the case when the objective function is subdifferentiable only on the relative interior of the feasible set. In such a setting, one can design a mirror map which maps not onto the entire feasible set but only on a subset of it where the objective function is subdifferentiable (see Example 2.5).

There exists already a rich literature on incremental algorithms dealing with similar problems. In [1,2] incremental subgradient methods with a random selection of the component functions and even projections onto a feasible set are considered, but no mirror descent. Incremental subgradient algorithms utilizing mirror descent techniques are investigated in [3]; however, an additional projection onto the feasible set is required which thus excludes the case where $\mathrm{dom}f⊉C$ (this is taken care of in our case by the weak assumption that $\text{im}\left(\mathrm{\nabla }{H}^{\ast }\right)\subseteq \mathrm{dom}f$). Furthermore, the results appearing in Section 4 discussing Bregman proximal steps appear to completely novel for this kind of problems and are only known from a forward–backward setting [7].

The basic concepts in the formulation of mirror descent algorithms are recalled in Section 2. We also provide some illustrating examples, which present some special cases, as the general setting might not be immediately intuitive. In Section 3 we formulate an incremental mirror descent subgradient algorithm with random sweeping of the component functions which we show to have a convergence rate of $\mathcal{O}\left(1/\sqrt{k}\right)$ in expectation for the kth best objective function value. In Section 4 we ask additionally for differentiability of the function which induces the mirror map and are then able to add another nonsmooth convex function to the objective function which is evaluated in the iterative scheme by a proximal type step. For the resulting algorithm, we show a similar convergence result. In the last section, we illustrate the theoretical findings by numerical experiments in positron emission tomography (PET) and machine learning.

2. Elements of convex analysis and the mirror descent algorithm

Throughout the paper, we assume that ${\mathbb{R}}^n$ is endowed with the Euclidean inner product $⟨\cdot ,\cdot ⟩$ and corresponding norm $\parallel \cdot \parallel =\sqrt{⟨\cdot ,\cdot ⟩}$. For a nonempty convex set $C\subseteq {\mathbb{R}}^n$ we denote by $\mathrm{ri}C$ its relative interior, which is the interior of C relative to its affine hull. For a convex function $f:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ we denote by $\mathrm{dom}f:=\{x\in {\mathbb{R}}^n:f(x)<+\mathrm{\infty }\}$ its effective domain and say that f is proper, if $f>-\mathrm{\infty }$ and $\mathrm{dom}f\ne \mathrm{\varnothing }$. The subdifferential of f at $x\in {\mathbb{R}}^n$ is defined as $\mathrm{\partial }f\left(x\right):=\{p\in {\mathbb{R}}^n:f(y)\ge f(x)+⟨p,y-x⟩\mathrm{\forall }y\in {\mathbb{R}}^n\}$, for $f\left(x\right)\in \mathbb{R}$, and as $\mathrm{\partial }f\left(x\right):=\mathrm{\varnothing }$, otherwise. We will write $f^{\prime }\left(x\right)$ for an arbitrary subgradient, i.e. an element of the subdifferential $\mathrm{\partial }f\left(x\right)$.

Problem 2.1

Consider the optimization problem (2) $\underset{x\in C}{min}f\left(x\right),$(2) where $C\subseteq {\mathbb{R}}^n$ is a nonempty, convex and closed set, $f:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ is a proper and convex function, and $H:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ is a proper, lower semicontinuous and σ-strongly convex function such that $C=\overline{\mathrm{dom}H}$ and $\text{im}\left(\mathrm{\nabla }{H}^{\ast }\right)\subseteq \mathrm{int}\left(\mathrm{dom}f\right)$.

We say that $H:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ is σ-strongly convex for $\sigma >0$, if for every $x,x^{\prime }\in {\mathbb{R}}^n$ and every $\lambda \in [0,1]$ it holds $\left(\sigma /2\right)\lambda (1-\lambda )\parallel x-x^{\prime }{\parallel }^2+H(\lambda x+(1-\lambda \left)x^{\prime }\right)\le \lambda H\left(x\right)+(1-\lambda )H\left(x^{\prime }\right)$. It is well known that, when H is proper, lower semicontinuous and σ-strongly convex, then its conjugate function $H^{\ast }:{\mathbb{R}}^n\to \overline{\mathbb{R}},H^{\ast }\left(y\right)=\underset{x\in {\mathbb{R}}^n}{sup}\{⟨y,x⟩-H(x\left)\right\}$, is Fréchet differentiable (thus it has full domain) and its gradient $\mathrm{\nabla }{H}^{\ast }$ is $1/\sigma$-Lipschitz continuous or, equivalently, $H^{\ast }$ is Fréchet differentiable and its gradient $\mathrm{\nabla }{H}^{\ast }$ is σ-cocoercive, which means that for every $y,y^{\prime }\in {\mathbb{R}}^n$ it holds $\sigma \parallel \mathrm{\nabla }{H}^{\ast }\left(y\right)-\mathrm{\nabla }{H}^{\ast }\left(y^{\prime }\right){\parallel }^2\le ⟨y-y^{\prime },\mathrm{\nabla }{H}^{\ast }\left(y\right)-\mathrm{\nabla }{H}^{\ast }\left(y^{\prime }\right)⟩$. Recall that $\text{im}\left(\mathrm{\nabla }{H}^{\ast }\right):=\left\{\mathrm{\nabla }{H}^{\ast }\right(y):y\in {\mathbb{R}}^n\}$.

The following mirror descent algorithm has been introduced in [10] under the name dual averaging.

Algorithm 2.2

Consider for some initial values $x_0\in \mathrm{int}\left(\mathrm{dom}f\right),y_0\in {\mathbb{R}}^n$ and sequence of positive stepsizes $(t_k{)}_{k\ge 0}$ the following iterative scheme: $(\mathrm{\forall }k\ge 0)\left[\begin{array}{l}{y}_{k+1}=y_k-t_k{f}^{\prime }\left(x_k\right)\\ x_{k+1}=\mathrm{\nabla }{H}^{\ast }\left(y_{k+1}\right).\end{array}\right.$

We notice that, since the sequence $(x_k{)}_{k\ge 0}$ is contained in the interior of the effective domain of f, the algorithm is well defined. The assumptions concerning the function H, which induces the mirror map $\mathrm{\nabla }{H}^{\ast }$, are not consistent in the literature. Sometimes H is assumed to be a Legendre function as in [7], or strongly convex and differentiable as in [8,11]. In the following section, we will only assume that H is proper, lower semicontinuous and strongly convex.

Example 2.3

For $H=\frac{1}{2}\parallel \cdot {\parallel }^2$ we have that $H^{\ast }=\frac{1}{2}\parallel \cdot {\parallel }^2$ and thus $\mathrm{\nabla }{H}^{\ast }$ is the identity operator on ${\mathbb{R}}^n$. Consequently, Algorithm 2.2 reduces to the classical subgradient method: $(\mathrm{\forall }k\ge 0)x_{k+1}=x_k-t_k{f}^{\prime }\left(x_k\right).$

Example 2.4

For $C\subseteq {\mathbb{R}}^n$ a nonempty, convex and closed set, take $H\left(x\right)=\frac{1}{2}\parallel x{\parallel }^2$, for $x\in C$, and $H\left(x\right)=+\mathrm{\infty }$, otherwise. Then $\mathrm{\nabla }{H}^{\ast }=P_C$, where $P_C$ denotes the orthogonal projection onto C. In this setting, Algorithm 2.2 becomes: $(\mathrm{\forall }k\ge 0)\left[\begin{array}{l}{y}_{k+1}=y_k-t_k{f}^{\prime }\left(x_k\right)\\ x_{k+1}=P_C\left(y_{k+1}\right).\end{array}\right.$ This iterative scheme is similar to, but different from the well-known subgradient projection algorithm, which reads: $(\mathrm{\forall }k\ge 0)\left[\begin{array}{l}{y}_{k+1}=x_k-t_k{f}^{\prime }\left(x_k\right)\\ x_{k+1}=P_C\left(y_{k+1}\right).\end{array}\right.$

Example 2.5

When considering numerical experiments in PET, one often minimizes over the unit simplex $\mathrm{\Delta }:=\{x=(x_1,\dots ,x_n{)}^T\in {\mathbb{R}}^n:\sum _{j=1}^n{x}_j=1,x\ge 0\}$. An appropriate choice for the function H is $H\left(x\right)=\sum _{j=1}^n{x}_j\log \left(x_j\right)$ for $x\in \mathrm{\Delta }$, where $0\log \left(0\right)=0$, and $H\left(x\right)=+\mathrm{\infty }$, if $x\notin \mathrm{\Delta }$. In this case $\mathrm{\nabla }{H}^{\ast }$ is given for every $y\in {\mathbb{R}}^n$ by $\mathrm{\nabla }{H}^{\ast }\left(y\right)=\frac{1}{\sum _{i=1}^n\exp \left(y_i\right)}(\exp (y_1),\exp (y_2),\dots ,\exp (y_n){)}^T,$ and maps into the relative interior of Δ.

The following result will play an important role in the convergence analysis that we will carry out in the next sections.

Lemma 2.6

Let $H:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ be a proper, lower semicontinuous and σ-strongly convex function, for $\sigma >0$, $x\in {\mathbb{R}}^n$ and $y\in \mathrm{\partial }H\left(x\right)$. Then it holds $H\left(x\right)+⟨y,x^{\prime }-x⟩+\frac{\sigma }{2}\parallel x^{\prime }-x{\parallel }^2\le H\left(x^{\prime }\right)\mathrm{\forall }{x}^{\prime }\in {\mathbb{R}}^n.$

Proof.

The function $\tilde{H}(\cdot ):=H(\cdot )-\left(\sigma /2\right)\parallel \cdot {\parallel }^2$ is convex and $y-\sigma x\in \mathrm{\partial }\tilde{H}\left(x\right)$. Thus $\tilde{H}\left(x\right)+⟨y-\sigma x,\tilde{x}-x⟩\le \tilde{H}\left(\tilde{x}\right)\mathrm{\forall }\tilde{x}\in {\mathbb{R}}^n$ or, equivalently, $H\left(x\right)-\frac{\sigma }{2}\parallel x{\parallel }^2+⟨y-\sigma x,\tilde{x}-x⟩\le H\left(\tilde{x}\right)-\frac{\sigma }{2}\parallel \tilde{x}{\parallel }^2\mathrm{\forall }\tilde{x}\in {\mathbb{R}}^n.$ Rearranging the terms, leads to the desired conclusion.

3. A stochastic incremental mirror descent algorithm

In this section, we will address the following optimization problem.

Problem 3.1

Consider the optimization problem (3) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right),$(3) where $C\subseteq {\mathbb{R}}^n$ is a nonempty, convex and closed set, for every $i=1,\dots ,m$, the functions $f_i:{\mathbb{R}}^n\mapsto \overline{\mathbb{R}}$ are proper and convex, and $H:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ is a proper, lower semicontinuous and σ-strongly convex function such that $C=\overline{\mathrm{dom}H}$ and $\text{im}\left(\mathrm{\nabla }{H}^{\ast }\right)\subseteq \mathrm{int}\left(\bigcap _{i=1}^m\mathrm{dom}{f}_i\right)$.

In this section, we apply the dual averaging approach described in Algorithm 2.2 to the optimization problem (3(3) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right),$(3) ) by only using the subgradient of a component function at a time. This incremental approach (see, also, [1,2]) is similar to but slightly different from the extension suggested in [8]. Furthermore, we introduce a stochastic sweeping of the component functions. For a similar strategy, but in the random selection of coordinates we refer to [14].

Algorithm 3.2

Consider for some initial values $x_0\in \mathrm{int}\left(\bigcap _{i=1}^m\mathrm{dom}{f}_i\right),y_{m,-1}\in {\mathbb{R}}^n$ and sequence of positive stepsizes $(t_k{)}_{k\ge 0}$ the following iterative scheme: $(\mathrm{\forall }k\ge 0)\left[\begin{array}{l}{\psi }_{0,k}=x_k\\ y_{0,k}=y_{m,k-1}\\ fori=1,\dots ,m\\ y_{i,k}=y_{i-1,k}-{ϵ}_{i,k}\frac{t_k}{p_i}{f}_i^{\prime }\left({\psi }_{i-1,k}\right)\\ {\psi }_{i,k}=\mathrm{\nabla }{H}^{\ast }\left(y_{i,k}\right)\\ end\\ x_{k+1}={\psi }_{m,k},\end{array}\right.$ where ${ϵ}_{i,k}isa\{0,1\}$ valued random variable for every $i=1,\dots ,m$ and $k\ge 0$, such that ${ϵ}_{i,k}$ is independent of ${\psi }_{i-1,k}$ and $\mathbb{P}({ϵ}_{i,k}=1)=p_i$ for every $i=1,\dots ,m$ and $k\ge 0$.

One can notice that in the above iterative scheme $y_{i,k}\in \mathrm{\partial }H\left({\psi }_{i,k}\right)$ for every $i=1,\dots ,m$ and $k\ge 0$.

In the convergence analysis of Algorithm 3.2 we will make use of the following Bregman-distance-like function associated to the proper and convex function $H:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ and defined as (4) $d_H:{\mathbb{R}}^n\times \mathrm{dom}H\times {\mathbb{R}}^n\to \overline{\mathbb{R}},d_H(x,y,z):=H\left(x\right)-H\left(y\right)-⟨z,x-y⟩.$(4) We notice that $d_H(x,y,z)\ge 0$ for every $(x,y)\in {\mathbb{R}}^n\times \mathrm{dom}H$ and every $z\in \mathrm{\partial }H\left(y\right)$, due to subgradient inequality.

The function $d_H$ is an extension of the Bregman distance (see [4,7,11]), which is associated to a proper and convex function $H:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ fulfilling $\mathrm{dom}\mathrm{\nabla }H:=\{x\in {\mathbb{R}}^n:H\text{is differentiable at}x\}\ne \mathrm{\varnothing }$ and defined as (5) $D_H:{\mathbb{R}}^n\times \mathrm{dom}\mathrm{\nabla }H\to \overline{\mathbb{R}},D_H(x,y)=H\left(x\right)-H\left(y\right)-⟨\mathrm{\nabla }H\left(y\right),x-y⟩.$(5)

Theorem 3.3

In the setting of Problem 3.1, assume that the functions $f_i$ are $L_{f_i}$-Lipschitz continuous on $\mathrm{im}\left(\mathrm{\nabla }{H}^{\ast }\right)$ for $i=1,\dots ,m$. Let $(x_k{)}_{k\ge 0}$ be a sequence generated by Algorithm 3.2. Then for every $N\ge 1$ and every $y\in {\mathbb{R}}^n$ it holds $\begin{array}{rl}& \mathbb{E}\left(\underset{0\le k\le N-1}{min}\sum _{i=1}^m{f}_i\left(x_k\right)-\sum _{i=1}^m{f}_i\left(y\right)\right)\\ & \le \frac{d_H(y,x_0,y_{0,0})+\frac{1}{\sigma }{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+1\right)\sum _{k=0}^{N-1}{t}_k^2}{\sum _{k=0}^{N-1}{t}_k}.\end{array}$

Proof.

Let $y\in \bigcap _{i=1}^m\mathrm{dom}{f}_i\cap \mathrm{dom}H$ be fixed. For y outside this set the conclusion follows automatically.

For every $i=1,\dots ,m$ and every $k\ge 0$ it holds $\begin{array}{rl}{d}_H(y,{\psi }_{i,k},y_{i,k})& =H\left(y\right)-H\left({\psi }_{i,k}\right)-⟨y_{i,k},y-{\psi }_{i,k}⟩\\ & =H\left(y\right)-H\left({\psi }_{i,k}\right)-⟨y_{i-1,k}-\frac{t_k}{p_i}{ϵ}_{i,k}{f}_i^{\prime }\left({\psi }_{i-1,k}\right),y-{\psi }_{i,k}⟩.\end{array}$ Rearranging the terms, this yields for every $i=1,\dots ,m$ and every $k\ge 0$ to $\begin{array}{rl}{d}_H(y,{\psi }_{i,k},y_{i,k})& =d_H(y,{\psi }_{i-1,k},y_{i-1,k})-d_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})+\frac{t_k}{p_i}{ϵ}_{i,k}⟨f_i^{\prime }\left({\psi }_{i-1,k}\right),y-{\psi }_{i,k}⟩\\ & =d_H(y,{\psi }_{i-1,k},y_{i-1,k})-d_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})+\frac{t_k}{p_i}{ϵ}_{i,k}⟨f_i^{\prime }\left({\psi }_{i-1,k}\right),y-{\psi }_{i-1,k}⟩\\ & -\frac{t_k}{p_i}{ϵ}_{i,k}⟨f_i^{\prime }\left({\psi }_{i-1,k}\right),{\psi }_{i,k}-{\psi }_{i-1,k}⟩\\ & \le d_H(y,{\psi }_{i-1,k},y_{i-1,k})-d_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})+\frac{t_k}{p_i}{ϵ}_{i,k}\left(f_i\right(y)-f_i({\psi }_{i-1,k}\left)\right)\\ & +\frac{t_k}{p_i}{ϵ}_{i,k}\parallel f_i^{\prime }\left({\psi }_{i-1,k}\right)\parallel \parallel {\psi }_{i-1,k}-{\psi }_{i,k}\parallel .\end{array}$ From here we get for every $i=1,\dots ,m$ and every $k\ge 0$ $\begin{array}{rl}{d}_H(y,{\psi }_{i,k},y_{i,k})& \le d_H(y,{\psi }_{i-1,k},y_{i-1,k})-d_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})+\frac{t_k}{p_i}{ϵ}_{i,k}\left(f_i\right(y)-f_i({\psi }_{i-1,k}\left)\right)\\ & +\frac{1}{\sigma }{t}_k^2\frac{1}{p_i^2}{ϵ}_{i,k}^2\parallel f_i^{\prime }\left({\psi }_{i-1,k}\right){\parallel }^2+\frac{\sigma }{4}\parallel {\psi }_{i-1,k}-{\psi }_{i,k}{\parallel }^2\end{array}$ which, by using that H is σ-strongly convex and Lemma 2.6, yields $\begin{array}{rl}{d}_H(y,{\psi }_{i,k},y_{i,k})& \le d_H(y,{\psi }_{i-1,k},y_{i-1,k})-d_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})+\frac{t_k}{p_i}{ϵ}_{i,k}\left(f_i\right(y)-f_i({\psi }_{i-1,k}\left)\right)\\ & +\frac{1}{\sigma }{t}_k^2\frac{1}{p_i^2}{ϵ}_{i,k}\parallel f_i^{\prime }\left({\psi }_{i-1,k}\right){\parallel }^2+\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\\ & =d_H(y,{\psi }_{i-1,k},y_{i-1,k})+\frac{t_k}{p_i}{ϵ}_{i,k}\left(f_i\right(y)-f_i({\psi }_{i-1,k}\left)\right)+\frac{1}{\sigma }{t}_k^2\frac{1}{p_i^2}{ϵ}_{i,k}\parallel f_i^{\prime }\left({\psi }_{i-1,k}\right){\parallel }^2\\ & -\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k}).\end{array}$ Using the fact that $f_i$ is $L_{f_i}$-Lipschitz continuous, it follows that $\parallel f_i^{\prime }\left({\psi }_{i-1,k}\right)\parallel \le L_{f_i}$, for every i=1,...,m and every $k\ge 0$, thus $\begin{array}{rl}{d}_H(y,{\psi }_{i,k},y_{i,k})& \le d_H(y,{\psi }_{i-1,k},y_{i-1,k})+\frac{t_k}{p_i}{ϵ}_{i,k}\left(f_i\right(y)-f_i({\psi }_{i-1,k}\left)\right)+\frac{1}{\sigma }{t}_k^2\frac{1}{p_i^2}{ϵ}_{i,k}{L}_{f_i}^2\\ & -\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k}).\end{array}$ Since all the involved functions are measurable, we can take the expected value on both sides of the above inequality and get due to the assumed independence of ${ϵ}_{i,k}$ and ${\psi }_{i-1,k}$ for every $i=1,\dots ,m$ and every $k\ge 0$ $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,{\psi }_{i,k},y_{i,k}\left)\right)\le & \mathbb{E}\left(d_H\right(y,{\psi }_{i-1,k},y_{i-1,k}\left)\right)+\mathbb{E}\left(\frac{t_k}{p_i}\left(f_i\right(y)-f_i({\psi }_{i-1,k}\left)\right)\right)\mathbb{E}\left({ϵ}_{i,k}\right)\\ & +\frac{1}{\sigma }{t}_k^2\frac{1}{p_i^2}{L}_{f_i}^2\mathbb{E}\left({ϵ}_{i,k}\right)-\mathbb{E}\left(\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\right).\end{array}$ Since $\mathbb{E}\left({ϵ}_{i,k}\right)=p_i$, we get for every $i=1,\dots ,m$ and every $k\ge 0$ $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,{\psi }_{i,k},y_{i,k}\left)\right)& \le \mathbb{E}\left(d_H\right(y,{\psi }_{i-1,k},y_{i-1,k}\left)\right)+\mathbb{E}\left(t_k\right(f_i\left(y\right)-f_i\left({\psi }_{i-1,k}\right)\left)\right)\\ & +\frac{1}{\sigma }{t}_k^2\frac{1}{p_i}{L}_{f_i}^2-\mathbb{E}\left(\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\right).\end{array}$ Summing the above inequality for $i=1,\dots ,m$ and using that $\begin{array}{r}\sum _{i=1}^m{L}_{f_i}^2\frac{1}{p_i}\le {\left(\sum _{i=1}^m{L}_{f_i}^4\right)}^{1/2}{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}\le {\left(\sum _{i=1}^m{L}_{f_i}\right)}^2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2},\end{array}$ it yields for every $k\ge 0$ $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,{\psi }_{m,k},y_{m,k}\left)\right)& \le \mathbb{E}\left(d_H\right(y,x_k,y_{0,k}\left)\right)+\mathbb{E}\left(t_k\sum _{i=1}^m\left(f_i\right(y)-f_i({\psi }_{i-1,k}\left)\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}-\mathbb{E}\left(\sum _{i=1}^m\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\right)\end{array}$ or, equivalently, $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,{\psi }_{m,k},y_{m,k}\left)\right)& \le \mathbb{E}\left(d_H\right(y,x_k,y_{0,k}\left)\right)+\mathbb{E}\left(t_k\sum _{i=1}^m\left(f_i\right(y)-f_i(x_k)+f_i(x_k)-f_i({\psi }_{i-1,k}\left)\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}-\mathbb{E}\left(\sum _{i=1}^m\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\right).\end{array}$ Thus, for every $k\ge 0$, (6) $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,{\psi }_{m,k},y_{m,k}\left)\right)& \le \mathbb{E}\left(d_H\right(y,x_k,y_{0,k}\left)\right)+t_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(y\right)-\sum _{i=1}^m{f}_i\left(x_k\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}-\mathbb{E}\left(\sum _{i=1}^m\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\right)\\ & +\mathbb{E}\left(t_k\sum _{i=1}^m\left(f_i\right(x_k)-f_i({\psi }_{i-1,k}\left)\right)\right).\end{array}$(6) On the other hand, by using the Lipschitz continuity of $\mathrm{\nabla }{H}^{\ast }$ it yields for every $k\ge 0$ $\begin{array}{rl}\sum _{i=1}^m\left(f_i\right(x_k)-f_i({\psi }_{i-1,k}\left)\right)& =\sum _{i=2}^m\sum _{j=1}^{i-1}\left(f_i\right({\psi }_{j-1,k})-f_i({\psi }_{j,k}\left)\right)\\ & \le \sum _{i=2}^m\sum _{j=1}^{i-1}{L}_{f_i}\parallel {\psi }_{j-1,k}-{\psi }_{j,k}\parallel \le \left(\sum _{l=1}^m{L}_{f_l}\right)\sum _{i=2}^m\parallel {\psi }_{i-1,k}-{\psi }_{i,k}\parallel ,\\ & \le \left(\sum _{l=1}^m{L}_{f_l}\right)\sum _{i=2}^m\parallel \mathrm{\nabla }{H}^{\ast }\left(y_{i-1,k}\right)-\mathrm{\nabla }{H}^{\ast }\left(y_{i,k}\right)\parallel \\ & \le \frac{1}{\sigma }\left(\sum _{l=1}^m{L}_{f_l}\right)\sum _{i=2}^m\parallel y_{i-1,k}-y_{i,k}\parallel \\ & =\frac{1}{\sigma }\left(\sum _{l=1}^m{L}_{f_l}\right)\sum _{i=2}^m∥{ϵ}_{i,k}\frac{t_k}{p_i}{f}_i^{\prime }\left({\psi }_{i-1,k}\right)∥\\ & \le \frac{1}{\sigma }{t}_k\left(\sum _{l=1}^m{L}_{f_l}\right)\left(\sum _{i=1}^m\frac{{ϵ}_{i,k}}{p_i}{L}_{f_i}\right).\end{array}$ Therefore, for every $k\ge 0$ (7) $\begin{array}{rl}\mathbb{E}\left(t_k\sum _{i=1}^m\left(f_i\right(x_k)-f_i({\psi }_{i-1,k}\left)\right)\right)& \le \frac{1}{\sigma }{t}_k^2\left(\sum _{l=1}^m{L}_{f_l}\right)\mathbb{E}\left(\sum _{i=1}^m\frac{{ϵ}_{i,k}}{p_i}{L}_{f_i}\right)\\ & \le \frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2.\end{array}$(7) Combining (6(6) $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,{\psi }_{m,k},y_{m,k}\left)\right)& \le \mathbb{E}\left(d_H\right(y,x_k,y_{0,k}\left)\right)+t_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(y\right)-\sum _{i=1}^m{f}_i\left(x_k\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}-\mathbb{E}\left(\sum _{i=1}^m\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\right)\\ & +\mathbb{E}\left(t_k\sum _{i=1}^m\left(f_i\right(x_k)-f_i({\psi }_{i-1,k}\left)\right)\right).\end{array}$(6) ) and (7(7) $\begin{array}{rl}\mathbb{E}\left(t_k\sum _{i=1}^m\left(f_i\right(x_k)-f_i({\psi }_{i-1,k}\left)\right)\right)& \le \frac{1}{\sigma }{t}_k^2\left(\sum _{l=1}^m{L}_{f_l}\right)\mathbb{E}\left(\sum _{i=1}^m\frac{{ϵ}_{i,k}}{p_i}{L}_{f_i}\right)\\ & \le \frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2.\end{array}$(7) ) gives for every $k\ge 0$ (8) $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,{\psi }_{m,k},y_{m,k}\left)\right)& \le \mathbb{E}\left(d_H\right(y,x_k,y_{0,k}\left)\right)+t_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(y\right)-\sum _{i=1}^m{f}_i\left(x_k\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}-\mathbb{E}\left(\sum _{i=1}^m\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2.\end{array}$(8) Since ${\psi }_{m,k}=x_{k+1}$ and $y_{m,k}=y_{0,k+1}$ we get for every $k\ge 0$ that $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,x_{k+1},y_{0,k+1}\left)\right)& \le \mathbb{E}\left(d_H\right(y,x_k,y_{0,k}\left)\right)+t_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(y\right)-\sum _{i=1}^m{f}_i\left(x_k\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+1\right).\end{array}$ By summing up this inequality from k=0 to N−1, where $N\ge 1$, we get $\begin{array}{rl}& \sum _{k=0}^{N-1}{t}_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(x_k\right)-\sum _{i=1}^m{f}_i\left(y\right)\right)+\mathbb{E}\left(d_H\right(y,x_N,y_{0,N}\left)\right)\\ & \le \mathbb{E}\left(d_H\right(y,x_0,y_{0,0}\left)\right)+\sum _{k=0}^{N-1}\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+1\right).\end{array}$ Since $d_H(y,x_N,y_{0,N})\ge 0$, as $y_{0,N}\in \mathrm{\partial }H\left(x_N\right)$, we get $\begin{array}{rl}& \mathbb{E}\left(\underset{0\le k\le N-1}{min}\sum _{i=1}^m{f}_i\left(x_k\right)-\sum _{i=1}^m{f}_i\left(y\right)\right)\\ & \le \frac{d_H(y,x_0,y_{0,0})+\frac{1}{\sigma }{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+1\right)\sum _{k=0}^{N-1}{t}_k^2}{\sum _{k=0}^{N-1}{t}_k}\end{array}$ and this finishes the proof.

Remark 3.4

The set from which the variable y is chosen in the previous theorem might seem to be restrictive, however, we would like to recall that in many applications $\mathrm{dom}H$ is the set of feasible solutions of the optimization problem (3(3) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right),$(3) ). Since $\text{im}\left(\mathrm{\nabla }{H}^{\ast }\right)=\mathrm{dom}\mathrm{\partial }H:=\{x\in {\mathbb{R}}^n:\mathrm{\partial }H(x)\ne \mathrm{\varnothing }\}\subseteq \mathrm{dom}H$, the inequality in Theorem 3.3 is fulfilled for every $y\in \text{im}\left(\mathrm{\nabla }{H}^{\ast }\right)$.

Remark 3.5

Note furthermore that so far we have not made any assumptions about the stepsizes in Theorem 3.3. It is, however, clear from the statement that in the case where $y=x^{\ast }$ for an optimal solution $x^{\ast }$ and the stepsizes $(t_k{)}_{k\in \mathbb{N}}$ fulfil the classical condition that $\sum _{k=1}^{\mathrm{\infty }}{t}_k=+\mathrm{\infty }$ and $\sum _{k=1}^{\mathrm{\infty }}{t}_k^2<+\mathrm{\infty }$ it follows that $\underset{N\in \mathbb{N}}{lim}\mathbb{E}\left(\underset{0\le k\le N-1}{min}\sum _{i=1}^m{f}_i\right(x_k)-\sum _{i=1}^m{f}_i(x^{\ast }\left)\right)=0$.

The optimal stepsize choice, which we provide in the following corollary, is a consequence of [8, Proposition 4.1], which states that the function $z\mapsto \frac{c+(2\sigma {)}^{-1}{z}^{T}Dz}{b^{T}z},$ where $c>0,b\in {\mathbb{R}}_{++}^d:=\left\{\right(z_1,\dots ,z_d{)}^T\in {\mathbb{R}}^d:z_i>0,i=1,\dots ,d\}$ and $D\in {\mathbb{R}}^{d\times d}$ is a symmetric positive definite matrix, attains its minimum on ${\mathbb{R}}_{++}^d$ at $z^{\ast }=\sqrt{\left(2c\sigma /b^T{D}^{-1}b\right)}{D}^{-1}b$ and this provides $\sqrt{2c/\sigma b^T{D}^{-1}b}$ as optimal objective value.

Corollary 3.6

In the setting of Problem 3.1, assume that the functions $f_i$ are $L_{f_i}$-Lipschitz continuous on $\mathrm{im}\left(\mathrm{\nabla }{H}^{\ast }\right)$ for $i=1,\dots ,m$. Let $x^{\ast }\in \mathrm{dom}H$ be an optimal solution of (3(3) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right),$(3) ) and $(x_k{)}_{k\ge 0}$ be a sequence generated by Algorithm 3.2 with optimal stepsize $t_k:=\frac{1}{\sum _{i=1}^m{L}_{f_i}}\sqrt{\frac{d_H(x^{\ast },x_0,y_{0,0})}{{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+1}}\frac{1}{\sqrt{k}}\mathrm{\forall }k\ge 0.$ Then for every $N\ge 1$ it holds $\mathbb{E}\left(\underset{0\le k\le N-1}{min}\sum _{i=1}^m{f}_i\left(x_k\right)-\sum _{i=1}^m{f}_i\left(x^{\ast }\right)\right)\le 2\left(\sum _{i=1}^m{L}_{f_i}\right)\sqrt{\frac{d_H(x^{\ast },x_0,y_{0,0})\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+1\right)}{\sigma }}\frac{1}{\sqrt{N}}.$

Remark 3.7

In the last step of the proof of Theorem 3.3, one could have chosen to use the following inequality $\left(\sum _{k=0}^{N-1}{t}_k\right)\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(\frac{\sum _{k=0}^{N-1}{t}_k{x}_k}{\sum _{k=0}^{N-1}{t}_k}\right)-\sum _{i=1}^m{f}_i\left(y\right)\right)\le \sum _{k=0}^{N-1}{t}_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(x_k\right)-\sum _{i=1}^m{f}_i\left(y\right)\right)$ given by the convexity of $\sum _{i=1}^m{f}_i(\cdot )$ in order to prove convergence of the function values for the ergodic sequence ${\overline{x}}_k:=\left(1/\sum _{i=0}^k{t}_i\right)\sum _{i=0}^k{t}_i{x}_i$ for all $k\ge 0$. This would lead for every $N\ge 1$ and every $y\in {\mathbb{R}}^n$ to $\mathbb{E}\left(\sum _{i=1}^m{f}_i\left({\overline{x}}_{N-1}\right)-\sum _{i=1}^m{f}_i\left(y\right)\right)\le \frac{d_H(y,x_0,y_{0,0})+\frac{1}{\sigma }{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+1\right)\sum _{k=0}^{N-1}{t}_k^2}{\sum _{k=0}^{N-1}{t}_k}$ and for the optimal stepsize choice from Corollary 3.6 to $\mathbb{E}\left(\sum _{i=1}^m{f}_i\left({\overline{x}}_{N-1}\right)-\sum _{i=1}^m{f}_i\left(y\right)\right)\le 2\left(\sum _{i=1}^m{L}_{f_i}\right)\sqrt{\frac{d_H(x^{\ast },x_0,y_{0,0})\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+1\right)}{\sigma }}\frac{1}{\sqrt{N}},$ and might be beneficial, as it does not require the computation of objective function values, which are by our implicit assumption of m being large expensive to compute.

4. A stochastic incremental mirror descent algorithm with Bregman proximal step

In this section, we add another nonsmooth convex function to the objective function of the optimization problem (3(3) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right),$(3) ) and provide an extension of Algorithm 3.2, which evaluates in particular the new summand by a proximal type step. However, this asks for supplementary differentiability assumption on the function inducing the mirror map.

Problem 4.1

Consider the optimization problem (9) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right)+g\left(x\right),$(9) where $C\subseteq {\mathbb{R}}^n$ is a nonempty, convex and closed set, for every $i=1,\dots ,m$, the functions $f_i:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ are proper and convex and $g:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ is a proper, convex and lower semicontinuous function, and $H:{\mathbb{R}}^m\to \overline{\mathbb{R}}$ is a proper, σ-strongly convex and lower semicontinuous function such that $C=\overline{\mathrm{dom}H}$, H is continuously differentiable on $\mathrm{int}\left(\mathrm{dom}H\right)$, $\mathrm{im}\left(\mathrm{\nabla }{H}^{\ast }\right)\subseteq \mathrm{int}\left(\bigcap _{i=1}^m\mathrm{dom}{f}_i\right)\cap \mathrm{int}\left(\mathrm{dom}H\right)$ and $\mathrm{int}\left(\mathrm{dom}H\right)\cap \mathrm{dom}g\ne \mathrm{\varnothing }$.

For a proper, convex, lower semicontinuous function $h:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ we define its Bregman-proximal operator with respect to the proper, σ-strongly convex and lower semicontinuous function $H:{\mathbb{R}}^n\to \overline{\mathbb{R}}$ as being ${\mathrm{prox}}_h^H:\mathrm{dom}\mathrm{\nabla }H\to {\mathbb{R}}^n,{\mathrm{prox}}_h^H\left(x\right):=\underset{u\in {\mathbb{R}}^n}{\arg \min }\left\{h\right(u)+D_H(u,x\left)\right\}.$ Due to the strong convexity of H, the Bregman-proximal operator is well defined. For $H=\left(\frac{1}{2}\right)\parallel \cdot {\parallel }^2$ it coincides with the classical proximal operator.

We are now in the position to formulate the iterative scheme we would like to propose for solving (9(9) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right)+g\left(x\right),$(9) ). In case g=0, this algorithm gives exactly the incremental version of the iterative method in [8], actually suggested by the two authors in this paper.

Algorithm 4.2

Consider for some initial value $x_0\in \text{im}\left(\mathrm{\nabla }{H}^{\ast }\right)$ and sequence of positive stepsizes $(t_k{)}_{k\ge 0}$ the following iterative scheme: $(\mathrm{\forall }k\ge 0)\left[\begin{array}{l}{\psi }_{0,k}=x_k\\ fori=1,\dots ,m\\ {\psi }_{i,k}=\mathrm{\nabla }{H}^{\ast }\left(\mathrm{\nabla }H\right({\psi }_{i-1,k})-{ϵ}_{i,k}\frac{t_k}{p_i}{f}_i^{\prime }({\psi }_{i-1,k}\left)\right)\\ end\\ x_{k+1}={\mathrm{prox}}_{t_{k}g}^H\left({\psi }_{m,k}\right),\end{array}\right.$ where ${ϵ}_{i,k}isa\{0,1\}$ valued random variable for every $i=1,\dots ,m$ and $k\ge 0$, such that ${ϵ}_{i,k}$ is independent from ${\psi }_{i-1,k}$ and $\mathbb{P}({ϵ}_{i,k}=1)=p_i$ for every $i=1,\dots ,m$ and $k\ge 0$.

Lemma 4.3

In the setting of Problem 4.1, Algorithm 4.2 is well defined.

Proof.

As $\mathrm{im}\left(\mathrm{\nabla }{H}^{\ast }\right)\subseteq \mathrm{int}\left(\bigcap _{i=1}^m\mathrm{dom}{f}_i\right)$, it follows for every $i=2,\dots ,m$ and every $k\ge 0$ immediately that ${\psi }_{i-1,k}\in \mathrm{int}\mathrm{dom}{f}_i$, thus a subgradient of $f_i$ at ${\psi }_{i-1,k}$ exists.

In what follows we prove that this is the case also for ${\psi }_{0,k}$, for every $k\ge 0$. To this aim, it is enough to show that $x_k\in \mathrm{im}\left(\mathrm{\nabla }{H}^{\ast }\right)$ for every $k\ge 0$. For k=0 this statement is true by the choice of the initial value. For every $k\ge 0$ we have that $0\in \mathrm{\partial }(t_{k}g+H-⟨\mathrm{\nabla }H({\psi }_{m,k}),\cdot ⟩)\left(x_{k+1}\right),$ which, according to $\mathrm{int}\left(\mathrm{dom}H\right)\cap \mathrm{dom}g\ne \mathrm{\varnothing }$, is equivalent to $0\in t_k\mathrm{\partial }g\left(x_{k+1}\right)+\mathrm{\partial }H\left(x_{k+1}\right)-\mathrm{\nabla }H\left({\psi }_{m,k}\right).$ Thus, $x_{k+1}\in \mathrm{dom}\mathrm{\partial }H=\mathrm{im}\left(\mathrm{\nabla }{H}^{\ast }\right)$ for every $k\ge 0$ and this concludes the proof.

Example 4.4

Consider the case when m=1, ${ϵ}_{1,k}=1$ for every $k\ge 0$ and $H\left(x\right)=\frac{1}{2}\parallel x{\parallel }^2$ for $x\in C$, while $H\left(x\right)=+\mathrm{\infty }$ for $x\notin C$, where $C\subseteq {\mathbb{R}}^n$ is a nonempty, convex and closed set. In this setting, $\mathrm{\nabla }{H}^{\ast }$ is equal to the orthogonal projection $P_C$ onto the set C. Algorithm 4.2 yields the following iterative scheme, which basically minimizes the sum $f_1+g$ over the set C: (10) $(\mathrm{\forall }k\ge 0)x_{k+1}={\mathrm{prox}}_{t_{k}g}^H\left(P_C\right(x_k-t_k{f}_1^{\prime }\left(x_k\right)\left)\right).$(10) The difficulty in Example 4.4, assuming that it is reasonably possible to project onto the set C, lies in evaluating ${\mathrm{prox}}_{t_{k}g}^H$, for every $k\ge 0$, as this itself is a constraint optimization problem ${\mathrm{prox}}_{t_{k}g}^H\left(x\right)=\underset{u\in C}{\arg \min }\left\{t_{k}g\left(u\right)+\frac{1}{2}\parallel x-u{\parallel }^2\right\}.$ When $C={\mathbb{R}}^n$, the iterative scheme (10(10) $(\mathrm{\forall }k\ge 0)x_{k+1}={\mathrm{prox}}_{t_{k}g}^H\left(P_C\right(x_k-t_k{f}_1^{\prime }\left(x_k\right)\left)\right).$(10) ) becomes the proximal subgradient algorithm investigated in [15].

Theorem 4.5

In the setting of Problem 4.1, assume that the functions $f_i$ are $L_{f_i}$-Lipschitz continuous on $\text{im}\left(\mathrm{\nabla }{H}^{\ast }\right)$ for $i=1,\dots ,m$. Let $(x_k{)}_{k\ge 0}$ be a sequence generated by Algorithm 4.2. Then for every $N\ge 1$ and every $y\in {\mathbb{R}}^n$ it holds $\begin{array}{rl}& \mathbb{E}\left(\underset{0\le k\le N-1}{min}\left(\sum _{i=1}^m{f}_i+g\right)\left(x_{k+1}\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(y\right)\right)\\ & \le \frac{2\sigma D_H(y,x_0)+\left(2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+3+2m\right){\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\sum _{k=0}^{N-1}{t}_k^2}{2\sigma \sum _{k=0}^{N-1}{t}_k}.\end{array}$

Proof.

Let $y\in \bigcap _{i=1}^m\mathrm{dom}{f}_i\cap \mathrm{dom}g\cap \mathrm{dom}H$ be fixed. For y outside this set the conclusion follows automatically.

As in the first part of the proof of Theorem 3.3, we obtain instead of (8(8) $\begin{array}{rl}\mathbb{E}\left(d_H\right(y,{\psi }_{m,k},y_{m,k}\left)\right)& \le \mathbb{E}\left(d_H\right(y,x_k,y_{0,k}\left)\right)+t_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(y\right)-\sum _{i=1}^m{f}_i\left(x_k\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}-\mathbb{E}\left(\sum _{i=1}^m\frac{1}{2}{d}_H({\psi }_{i,k},{\psi }_{i-1,k},y_{i-1,k})\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2.\end{array}$(8) ) the following inequality which holds for every $i=1,\dots ,m$ and every $k\ge 0$ (11) $\begin{array}{rl}\mathbb{E}\left(D_H\right(y,{\psi }_{m,k}\left)\right)& \le \mathbb{E}\left(D_H\right(y,x_k\left)\right)+t_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(y\right)-\sum _{i=1}^m{f}_i\left(x_k\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+1\right)-\mathbb{E}\left(\sum _{i=1}^m\frac{1}{2}{D}_H({\psi }_{i,k},{\psi }_{i-1,k})\right).\end{array}$(11) As pointed out in the proof of Lemma 4.3, for every $k\ge 0$ we have $0\in t_k\mathrm{\partial }g\left(x_{k+1}\right)+\mathrm{\nabla }H\left(x_{k+1}\right)-\mathrm{\nabla }H\left({\psi }_{m,k}\right),$ thus $t_k\left(g\right(y)-g(x_{k+1}\left)\right)\ge ⟨\mathrm{\nabla }H\left({\psi }_{m,k}\right)-\mathrm{\nabla }H\left(x_{k+1}\right),y-x_{k+1}⟩.$ The three point identity leads to $t_k\left(g\right(y)-g(x_{k+1}\left)\right)\ge -\left(D_H\right(y,{\psi }_{m,k})-D_H(y,x_{k+1})-D_H(x_{k+1},{\psi }_{m,k}\left)\right)$ or, equivalently, $t_k\left(g\right(x_{k+1})-g(y\left)\right)+D_H(y,x_{k+1})\le D_H(y,{\psi }_{m,k})-D_H(x_{k+1},{\psi }_{m,k})$ for every $k\ge 0$. Since the involved functions are measurable, we can take the expected value on both sides and obtain for every $k\ge 0$ (12) $t_k\mathbb{E}\left(\right(g\left(x_{k+1}\right)-g\left(y\right)\left)\right)+\mathbb{E}\left(D_H\right(y,x_{k+1}\left)\right)\le \mathbb{E}\left(D_H\right(y,{\psi }_{m,k}\left)\right)-\mathbb{E}\left(D_H\right(x_{k+1},{\psi }_{m,k}\left)\right).$(12) Combining (11(11) $\begin{array}{rl}\mathbb{E}\left(D_H\right(y,{\psi }_{m,k}\left)\right)& \le \mathbb{E}\left(D_H\right(y,x_k\left)\right)+t_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(y\right)-\sum _{i=1}^m{f}_i\left(x_k\right)\right)\\ & +\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+1\right)-\mathbb{E}\left(\sum _{i=1}^m\frac{1}{2}{D}_H({\psi }_{i,k},{\psi }_{i-1,k})\right).\end{array}$(11) ) and (12(12) $t_k\mathbb{E}\left(\right(g\left(x_{k+1}\right)-g\left(y\right)\left)\right)+\mathbb{E}\left(D_H\right(y,x_{k+1}\left)\right)\le \mathbb{E}\left(D_H\right(y,{\psi }_{m,k}\left)\right)-\mathbb{E}\left(D_H\right(x_{k+1},{\psi }_{m,k}\left)\right).$(12) ) gives for every $k\ge 0$ $\begin{array}{rl}& t_k\mathbb{E}\left(\right(g\left(x_{k+1}\right)-g\left(y\right)\left)\right)+t_k\mathbb{E}\left(\sum _{i=1}^m{f}_i\left(x_k\right)-\sum _{i=1}^m{f}_i\left(y\right)\right)+\mathbb{E}\left(D_H\right(y,x_{k+1}\left)\right)\\ & \le \mathbb{E}\left(D_H\right(y,x_k\left)\right)+\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+1\right)\\ & -\mathbb{E}\left(D_H\right(x_{k+1},{\psi }_{m,k}\left)\right)-\sum _{i=1}^m\frac{1}{2}\mathbb{E}\left(D_H\right({\psi }_{i,k},{\psi }_{i-1,k}\left)\right).\end{array}$ By adding and subtracting $\mathbb{E}\left(\sum _{i=1}^m{f}_i\right(x_{k+1}\left)\right)$ and by using afterwards the Lipschitz continuity of $\sum _{i=1}^m{f}_i$, we get for every $k\ge 0$ $\begin{array}{rl}& t_k\mathbb{E}\left(\left(\sum _{i=1}^m{f}_i+g\right)\left(x_{k+1}\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(y\right)\right)\\ & -t_k\left(\sum _{i=1}^m{L}_{f_i}\right)\mathbb{E}(\parallel x_k-x_{k+1}\parallel )+\mathbb{E}\left(D_H\right(y,x_{k+1}\left)\right)\\ & \le \mathbb{E}\left(D_H\right(y,x_k\left)\right)+\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+1\right)\\ & -\mathbb{E}\left(D_H\right(x_{k+1},{\psi }_{m,k}\left)\right)-\sum _{i=1}^m\frac{1}{2}\mathbb{E}\left(D_H\right({\psi }_{i,k},{\psi }_{i-1,k}\left)\right).\end{array}$ By the triangle inequality, we obtain for every $k\ge 0$ $\begin{array}{rl}& t_k\mathbb{E}\left(\left(\sum _{i=1}^m{f}_i+g\right)\left(x_{k+1}\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(y\right)\right)+\mathbb{E}\left(D_H\right(y,x_{k+1}\left)\right)\\ & \le \mathbb{E}\left(D_H\right(y,x_k\left)\right)+\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+1\right)-\mathbb{E}\left(D_H\right(x_{k+1},{\psi }_{m,k}\left)\right)\\ & +t_k\left(\sum _{i=1}^m{L}_{f_i}\right)\mathbb{E}(\left.∥x_k-{\psi }_{m,k}\parallel \right)+t_k\left(\sum _{i=1}^m{L}_{f_i}\right)\mathbb{E}(\left.∥{\psi }_{m,k}-x_{k+1}\parallel \right)\\ & -\sum _{i=1}^m\frac{1}{2}\mathbb{E}\left(D_H\right({\psi }_{i,k},{\psi }_{i-1,k}\left)\right),\end{array}$ which, due to Young's inequality and the strong convexity of H, leads to $\begin{array}{rl}& t_k\mathbb{E}\left(\left(\sum _{i=1}^m{f}_i+g\right)\left(x_{k+1}\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(y\right)\right)+\mathbb{E}\left(D_H\right(y,x_{k+1}\left)\right)\\ & \le \mathbb{E}\left(D_H\right(y,x_k\left)\right)+\frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left({\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+1\right)-\mathbb{E}\left(D_H\right(x_{k+1},{\psi }_{m,k}\left)\right)\\ & +t_k\left(\sum _{i=1}^m{L}_{f_i}\right)\mathbb{E}(\left.∥x_k-{\psi }_{m,k}\parallel \right)+\frac{1}{2\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\\ & +\mathbb{E}\left(D_H\right(x_{k+1},{\psi }_{m,k}\left)\right)-\sum _{i=1}^m\frac{1}{2}\mathbb{E}\left(D_H\right({\psi }_{i,k},{\psi }_{i-1,k}\left)\right).\end{array}$ Since $\parallel x_k-{\psi }_{m,k}\parallel =∥\sum _{i=1}^m({\psi }_{i-1,k}-{\psi }_{i,k})∥\le \sum _{i=1}^m\parallel {\psi }_{i-1,k}-{\psi }_{i,k}\parallel ,$ we get for every $k\ge 0$ that $\begin{array}{rl}& t_k\mathbb{E}\left(\left(\sum _{i=1}^m{f}_i+g\right)\left(x_{k+1}\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(y\right)\right)+\mathbb{E}\left(D_H\right(y,x_{k+1}\left)\right)\\ & \le \mathbb{E}\left(D_H\right(y,x_k\left)\right)+\frac{1}{2\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left(2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+3\right)\\ & +t_k\left(\sum _{i=1}^m{L}_{f_i}\right)\mathbb{E}\left(\sum _{i=1}^m\parallel {\psi }_{i-1,k}-{\psi }_{i,k}\parallel \right)-\sum _{i=1}^m\frac{1}{2}\mathbb{E}\left(D_H\right({\psi }_{i,k},{\psi }_{i-1,k}\left)\right).\end{array}$ Young's inequality and the strong convexity of H imply that for every $i=1,\dots ,m$ and every $k\ge 0$ $\begin{array}{rl}{t}_k\left(\sum _{i=1}^m{L}_{f_i}\right)\parallel {\psi }_{i-1,k}-{\psi }_{i,k}\parallel & \le \frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2+\frac{\sigma }{4}\parallel {\psi }_{i-1,k}-{\psi }_{i,k}{\parallel }^2\\ & \le \frac{1}{\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2+\frac{1}{2}{D}_H({\psi }_{i,k},{\psi }_{i-1,k})\end{array}$ and thus $\begin{array}{rl}& t_k\mathbb{E}\left(\left(\sum _{i=1}^m{f}_i+g\right)\left(x_{k+1}\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(y\right)\right)+\mathbb{E}\left(D_H\right(y,x_{k+1}\left)\right)\\ & \le \mathbb{E}\left(D_H\right(y,x_k\left)\right)+\frac{1}{2\sigma }{t}_k^2{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left(2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+3+2m\right).\end{array}$ Summing up this inequality from k=0 to N−1, for $N\ge 1$, we get $\begin{array}{rl}& \sum _{k=0}^{N-1}{t}_k\mathbb{E}\left(\left(\sum _{i=1}^m{f}_i+g\right)\left(x_{k+1}\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(y\right)\right)+\mathbb{E}\left(D_H\right(y,x_N\left)\right)\\ & \le \mathbb{E}\left(D_H\right(y,x_0\left)\right)+\frac{1}{2\sigma }{\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\left(2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+3+2m\right)\sum _{k=0}^{N-1}{t}_k^2.\end{array}$ This shows that $\begin{array}{rl}& \mathbb{E}\left(\underset{0\le k\le N-1}{min}\left(\sum _{i=1}^m{f}_i+g\right)\left(x_{k+1}\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(y\right)\right)\\ & \le \frac{2\sigma D_H(y,x_0)+\left(2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^{1/2}+3+2m\right){\left(\sum _{i=1}^m{L}_{f_i}\right)}^2\sum _{k=0}^{N-1}{t}_k^2}{2\sigma \sum _{k=0}^{N-1}{t}_k}\end{array}$ and therefore finishes the proof.

The following result is again a consequence of [8, Proposition 4.1].

Corollary 4.6

In the setting Problem 4.1, assume that the functions $f_i$ are $L_{f_i}$-Lipschitz continuous on $\mathrm{im}\left(\mathrm{\nabla }{H}^{\ast }\right)$ for $i=1,\dots ,m$. Let $x^{\ast }\in \mathrm{dom}H$ be an optimal solution of (9(9) $\underset{x\in C}{min}\sum _{i=1}^m{f}_i\left(x\right)+g\left(x\right),$(9) ) and $(x_k{)}_{k\ge 0}$ be a sequence generated by Algorithm 4.2 with optimal stepsize $t_k:=\frac{1}{\sum _{i=1}^m{L}_{f_i}}\sqrt{\frac{2D_H(x^{\ast },x_0)}{2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+3+2m}}\frac{1}{\sqrt{k}}\mathrm{\forall }k\ge 0.$ Then for every $N\ge 1$ it holds $\begin{array}{rl}& \mathbb{E}\left(\underset{0\le k\le N-1}{min}\left(\sum _{i=1}^m{f}_i+g\right)\left(x_k\right)-\left(\sum _{i=1}^m{f}_i+g\right)\left(x^{\ast }\right)\right)\\ & \le \left(\sum _{i=1}^m{L}_{f_i}\right)\sqrt{\frac{2D_H(x^{\ast },x_0)\left(2{\left(\sum _{i=1}^m\frac{1}{p_i^2}\right)}^2+3+2m\right)}{\sigma }}\frac{1}{\sqrt{N}}.\end{array}$

Remark 4.7

The same considerations as in Remark 3.7 about ergodic convergence are applicable also for the rates provided in Theorem 4.5 and Corollary 4.6.

Remark 4.8

Note the straightforward dependence of the optimal stepsizes as well as the right-hand side of the convergence statement on the data, i.e. the distance of the initial point to optimality, the Lipschitz constants $L_{f_i}$ and the probabilities $p_i$. This backs up the intuition that the decreased gradient evaluation, i.e. smaller $p_i$, does not come for free but at the cost of a worse constant in the convergence rate.

5. Applications

In the numerical experiments carried out in this section, we will compare three versions of the provided algorithms. First of all, the non-incremental version, which takes full subgradient steps with respect to the sum of all component functions instead of every single one individually. This can be viewed as a special case of the algorithms given, when m=1 and ${ϵ}_{1,k}=1$ for all $k\ge 0$. Secondly, we discuss the non-stochastic incremental version, which uses the subgradient of every single component function in every iteration and thus corresponds to the case when ${ϵ}_{i,k}=1$ for every i=1,...,m and every $k\ge 0$. Lastly, we apply the algorithms as intended by evaluating the subgradients of the respective component functions incrementally with a probability different from 1.

5.1. Tomography

This application can be found in [3] and arises in the reconstruction of images in PET. We consider the following problem (13) $\underset{x\in \mathrm{\Delta }}{min}-\sum _{i=1}^m{y}_i\log \left(\sum _{j=1}^n{r}_{ij}{x}_j\right),$(13) where $\mathrm{\Delta }:=\{x\in {\mathbb{R}}^n:\sum _{j=1}^n{x}_j=1,x\ge 0\}$ and $r_{ij}$ denotes for $i=1,\dots ,m$ and $j=1,\dots ,n$ the entry of the matrix $R\in {\mathbb{R}}^{m\times n}$ in the i-th row and j-th column and all of these are assumed to be strictly positive. Furthermore, $y_i$ denotes for $i=1,\dots ,m$ the positive number of photons measured in the i-th bin. As discussed in Example 2.5 this can be incorporated into our framework with the mirror map $H\left(x\right)=\sum _{i=1}^n{x}_i\log \left(x_i\right)$ for $x\in \mathrm{\Delta }$ and $H\left(x\right)=+\mathrm{\infty }$, otherwise. As initial value, we use the all ones vector divided by the dimension n.

We also want to point out that a similar example given in [8] in which the minimization of a convex function over the unit simplex Δ somehow does not match the assumption made throughout the paper as the interior of Δ is empty and the function H can therefore not be continuously differentiable in a classical sense. However, with the setting of Section 3 we are able to tackle this problem.

The bad performance, see Figure 1, of the deterministic incremental version of Algorithm 3.2 can be explained by the fact that many more evaluations of the mirror map are needed, which increases the overall computation time dramatically. The stochastic version, however, performs rather well, after only evaluating merely roughly a fifth of the total number of component functions, see Table 1.

Figure 1. Results for the optimization problem (13(13) $\underset{x\in \mathrm{\Delta }}{min}-\sum _{i=1}^m{y}_i\log \left(\sum _{j=1}^n{r}_{ij}{x}_j\right),$(13) ). A plot of $\left(f_N-f\left(x_{best}\right)\right)/\left(f\left(x_0\right)-f\left(x_{best}\right)\right)$, where $f_N:=\underset{0\le k\le N}{min}f\left(x_k\right)$, as a function of time, i.e. $x_N$ is the last iterate computed before a given point in time.

Table 1. Results for the optimization problem (13(13) $\underset{x\in \mathrm{\Delta }}{min}-\sum _{i=1}^m{y}_i\log \left(\sum _{j=1}^n{r}_{ij}{x}_j\right),$(13) ), where NI denotes the non-incremental, DI the deterministic incremental and SI the stochastic incremental version of Algorithm 3.2.

		NI	DI	SI
$n={10}^4$,	decrease obj.fun.val. (%)	0.066	0.032	0.15
m=3n	# outer loops	10	1	63
$p_i=0.003,\mathrm{\forall }i$	# subgrad. evaluations	300,000	6939	6216
$n={10}^3$,	decrease in obj.fun.val. (%)	0.196	0.515	0.671
m=6n	# outer loops	71	8	1769
$p_i=0.0016,\mathrm{\forall }i$	# subgrad. evaluations	426,000	47,435	17,734

5.2. Support vector machines

We deal with the classic machine learning problem of binary classification based on the well-known MNIST dataset, which contains 28 by 28 images of handwritten numbers on a grey-scale pixel map. For each of the digits, the dataset comprises around 6000 training images and roughly 1000 test images. In line with [4], we train a classifier to distinguish the numbers 6 and 7, by solving the following optimization problem (14) $\underset{w\in {\mathbb{R}}^{784}}{min}\sum _{i=1}^{m}max\{0,1-y_i⟨w,x_i⟩\}+\lambda \parallel w{\parallel }_1,$(14) where for $i=1,\dots ,m$, $x_i\in \{0,1,\dots ,255{\}}^{784}$ denotes the i-th training image and $y_i\in \{-1,1\}$ denotes the label of the i-th training image. The 1-norm serves as a regularization term and $\lambda >0$ balances the two objectives of minimizing the classification error and reducing the 1-norm of the classifier w. To incorporate this problem into our framework, we set $H=\frac{1}{2}\parallel \cdot {\parallel }^2$ which leaves us with the identity as mirror map as this problem is unconstrained. The results comparing the three versions of Algorithm 4.2 discussed at the beginning of this section are illustrated in Figure 2. As initial value we simply use the all ones vector. All three versions show classical first-order behaviour, giving a fast decrease in objective function value first but then slowing down dramatically. More information about the performance can be seen in Table 2. All three algorithms result in a significant decrease in objective function after being run for only 4 s each. However, from a machine learning point of view, only the misclassification rate is of actual importance. In both regards, the stochastic incremental version clearly trumps the other two implementations. It is also interesting to note that it needs only a small fraction of the number of subgradient evaluations in comparison to the full non-incremental algorithm.

Figure 2. Numerical results for the optimization problem (14(14) $\underset{w\in {\mathbb{R}}^{784}}{min}\sum _{i=1}^{m}max\{0,1-y_i⟨w,x_i⟩\}+\lambda \parallel w{\parallel }_1,$(14) ) with $\lambda =0.01$. The plot shows $\underset{0\le k\le N}{min}f\left(x_k\right)$ as a function of time, i.e. $x_N$ is the last iterate computed before a given point in time.

Table 2. Numerical results for the optimization problem (14(14) $\underset{w\in {\mathbb{R}}^{784}}{min}\sum _{i=1}^{m}max\{0,1-y_i⟨w,x_i⟩\}+\lambda \parallel w{\parallel }_1,$(14) ), where NI denotes the non-incremental, DI the deterministic incremental and SI the stochastic incremental version of Algorithm 4.2.

		NI	DI	SI
$\lambda =0.01$	decrease in obj.fun.val. (%)	99.735	99.958	99.99
	#outer loops	83	16	370
	#subgrad. evaluations	999,006	179,531	36,962
	misclassified (%)	1.057	0.856	0.604
$\lambda =0.001$	decrease obj.fun.val. (%)	99.728	99.958	99.985
	#iter	75	15	336
	#subgrad. eval.	913,725	179,320	33,777
	misclassified (%)	1.007	0.856	0.403

Note: The computation for different regularization parameters λ show similar performances of the algorithms, but a lower misclassification rate for the lower value.

6. Conclusion

In this paper, we present two algorithms to solve nonsmooth convex optimization problems where the objective function is a sum of many functions which are evaluated by their respective subgradients under the implicit presence of a constraint set which is dealt with by a so-called mirror map. By allowing for a random selection of each component function to evaluate in each iteration, the proposed methods become suitable even for very large-scale problems. We prove a convergence order of $\mathcal{O}\left(1/\sqrt{k}\right)$ in expectation for the kth best objective function value, which is standard for subgradient methods. However, even for the case where all the objective functions are differentiable, it is not clear if better theoretical estimates can be achieved, due to the need of using diminishing stepsizes in order to obtain convergence in incremental algorithms. Future work could comprise the investigation of different stepsizes, such as constant or dynamic stepsizes as in [2]. Another possible extension of this would be to use different selection procedures such as random subsets of fixed size. Our framework, however, does not provide the right setting for such a batch approach as it would leave ${ϵ}_{i,k}$ and ${ϵ}_{j,k}$ dependent.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Radu Ioan Boţ  http://orcid.org/0000-0002-4469-314X

Additional information

Funding

The research of Radu Ioan Boţ has been partially supported by FWF (Austrian Science Fund) [project I 2419-N32]. The research of Axel Böhm has been supported by the doctoral programme Vienna Graduate School on Computational Optimization (VGSCO), FWF (Austrian Science Fund) [project W 1260].