An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization

I Introduction

Many optimization problems that arise in machine learning, signal processing, and statistical estimation can be formulated as regularized stochastic optimization (also referred to as stochastic composite optimization) problems in which one jointly minimizes the expectation of a stochastic loss function plus a possibly nonsmooth regularization term. Examples include Tikhonov and elastic net regularization, Lasso, sparse logistic regression, and support vector machines .

Stochastic approximation methods such as stochastic gradient descent were among the first algorithms developed for solving stochastic optimization problems . Recently, these methods have received significant attention due to their simplicity and effectiveness (see, e.g., ). In particular, Nemirovski et. al. demonstrated that for nonsmooth stochastic convex optimization problems, a modified stochastic approximation method, the mirror descent, exhibits an unimprovable convergence rate $\mathcal{O}(1/\sqrt{T})$, where $T$ is the number of iterations. Later, Lan developed a mirror descent algorithm for stochastic composite convex problems which explicitly accounts for the smoothness of the loss function and achieves the optimal rate. A similar result for the dual averaging method was obtained by Xiao .

The methods for solving stochastic optimization problems cited above are inherently serial in the sense that the gradient computations take place on a single processor which has access to the whole dataset. However, it happens more and more often that one single computer is unable to store and handle the amounts of data that we encounter in practical problems. This has caused a strong interest in developing parallel optimization algorithms which are able to split the data and distribute the computation across multiple processors or multiple computer clusters (see, e.g., and references therein).

One simple and popular stochastic approximation method is mini-batching, where iterates are updated based on the average gradient with respect to multiple data points rather than based on gradients evaluated at a single data at a time. Recently, Dekel et. al. proposed a parallel mini-batch algorithm for regularized stochastic optimization problems, in which multiple processors compute gradients in parallel using their own local data, and then aggregate the gradients up a spanning tree to obtain the averaged gradient. While this algorithm can achieve linear speedup in the number of processors, it has the drawback that the processors need to synchronize at each round and, hence, if one of them fails or is slower than the rest, then the entire algorithm runs at the pace of the slowest processor.

In this paper, we propose an asynchronous mini-batch algorithm for regularized stochastic optimization problems with smooth loss functions that eliminates the overhead associated with global synchronization. Our algorithm allows multiple processors to work at different rates, perform computations independently of each other, and update global decision variables using out-of-date gradients. A similar model of parallel asynchronous computation was applied to coordinate descent methods for deterministic optimization in and mirror descent and dual averaging methods for stochastic optimization in . In particular, Agarwal and Duchi have analyzed the convergence of asynchronous mini-batch algorithms for smooth stochastic convex problems, and interestingly shown that bounded delays do not degrade the asymptotic convergence. However, they only considered the case where the regularization term is the indicator function of a compact convex set.

We extend the results of to general regularization functions (like the $l_{1}$ norm, often used to promote sparsity), and establish a sharper expected-value type of convergence rate than the one given in . Specifically, we make the following contributions:

For general convex regularization functions, we show that when the constraint set is closed and convex (but not necessarily bounded), the running average of the iterates generated by our algorithm with constant step-sizes converges at rate $\mathcal{O}(1/T)$ to a ball around the optimum. We derive an explicit expression that quantifies how the convergence rate and the residual error depends on loss function properties and algorithm parameters such as the constant step-size, the batch size, and the maximum delay bound $\tau_{\max}$.

For general convex regularization functions and compact constraint sets, we prove that the running average of the iterates produced by our algorithm with a time-varying step-size converges to the true optimum (without residual error) at rate

This result improves upon the previously known rate

for delayed stochastic mirror descent methods with time-varying step-sizes given in . In this case, our algorithm enjoys near-linear speedup as long as the number of processors is $\mathcal{O}(T^{1/4})$.

When the regularization function is strongly convex and the constraint set is closed and convex, we establish that the iterates converge at rate

If the number of processors is of the order of $\mathcal{O}(T^{1/4})$, this rate is $\mathcal{O}(1/T)$ asymptotically in $T$, which is the best known rate for strongly convex stochastic optimization problems in a serial setting.

The remainder of the paper is organized as follows. In Section II, we introduce the notation and review some preliminaries that are essential for the development of the results in this paper. In Section III, we formulate the problem and discuss our assumptions. The proposed asynchronous mini-batch algorithm and its main theoretical results are presented in Section IV. Computational experience is reported in Section V while Section VI concludes the paper.

II Notation and Preliminaries

II-B Preliminaries

Next, we review the key definitions and results necessary for developing the main results of this paper. We start with the definition of a Bregman distance function, also referred to as a prox-function.

Every distance generating function introduces a corresponding Bregman distance function

For example, choosing $\omega(x)=\frac{1}{2}\|x\|_{2}^{2}$, which is $1$-strongly convex with respect to the $l_{2}$-norm over any convex set $X$, would result in $D_{\omega}(x,y)=\frac{1}{2}\|x-y\|_{2}^{2}$. Another common example of distance generating functions is the entropy function

which is $1$-strongly convex with respect to the $l_{1}$-norm over the standard simplex

and its associated Bregman distance function is

The main motivation to use a generalized distance generating function, instead of the usual Euclidean distance function, is to design optimization algorithms that can take advantage of the geometry of the feasible set (see, e.g., ).

The strong convexity of the distance generating function $\omega$ always ensures that

and $D_{\omega}(x,y)=0$ if and only if $x=y$.

Throughout the paper, there is no loss of generality to assume that $\mu_{\omega}=1$. Indeed, if $\mu_{\omega}\neq 1$, we can choose the scaled function $\overline{\omega}(x)=\frac{1}{\mu_{\omega}}\omega(x)$, which has modulus $\overline{\mu}_{\omega}=1$, to generate the Bregman distance function.

The following definition introduces subgradients of proper convex functions.

The set of all subgradients of $\Psi$ at $x$ is called the subdifferential of $\Psi$ at $x$, and is denoted by $\partial\Psi(x)$.

III Problem Setup

We consider stochastic convex optimization problems of the form

We also impose the following assumptions on Problem (1).

Note that under Assumption 2, $\nabla f(x)$ is also Lipschitz continuous with the same constant $L$ .

There exists a constant $\sigma\geq 0$ such that

Unconstrained smooth minimization: $\Psi(x)=0$.

$l_{1}$-regularized minimization: $\Psi(x)=\lambda\|x\|_{1}$ with $\lambda>0$.

Constrained $l_{1}$-regularized minimization: In this case, $\Psi(x)=\lambda\|x\|_{1}+I_{C}(x)$ with $\lambda>0$.

Several practical problems in machine learning, statistical applications, and signal processing satisfy Assumptions 1–4 (see, e.g., ). One such example is $l_{1}$-regularized logistic regression for sparse binary classification. We are then given a large number of observations

drawn i.i.d. from an unknown distribution $\mathcal{P}$, and want to solve the minimization problem (1) with

and $\Psi(x)=\lambda\|x\|_{1}$. The role of $l_{1}$ regularization is to produce sparse solutions.

One approach for solving Problem (1) is the serial mini-batch method based on the mirror descent scheme . Given a point $x\in\textup{dom}\;\Psi$, a single processor updates the decision variable $x$ by sampling $b$ i.i.d. random variables $\xi_{1},\ldots,\xi_{b}$ from $\mathcal{P}$, computing the averaged stochastic gradient

and performing the composite mirror descent update

where $\gamma$ is a positive step-size parameter. Under Assumptions 1–4 and choosing an appropriate step-size, this algorithm is guaranteed to converge to the optimum [32, Theorem 9]. However, in many emerging applications, such as large-scale machine learning and statistics, the size of dataset is so huge that it cannot fit on one machine. Hence, we need optimization algorithms that can be conveniently and efficiently executed in parallel on multiple processors.

IV An Asynchronous Mini-Batch Algorithm

In this section, we will present an asynchronous mini-batch algorithm that exploits multiple processors to solve Problem (1). We characterize the iteration complexity and the convergence rate of the proposed algorithm, and show that these compare favourably with the state of the art.

We assume p processors have access to a shared memory for the decision variable $x$. The processors may have different capabilities (in terms of processing power and access to data) and are able to update $x$ without the need for coordination or synchronization. Conceptually, the algorithm lets each processor run its own stochastic composite mirror descent process, repeating the following steps:

Read $x$ from the shared memory and load it into the local storage location $\widehat{x}$;

Sample $b$ i.i.d random variables $\xi_{1},\ldots,\xi_{b}$ from the distribution $\mathcal{P}$;

Compute the averaged stochastic gradient vector

Update current $x$ in the shared memory via

The algorithm can be implemented in many ways as depicted in Figure 1. One way is to consider the $p$ processors as peers that each execute the four-step algorithm independently of each other and only share the global memory for storing $x$. In this case, each processor reads the decision vector twice in each round: once in the first step (before evaluating the averaged gradient), and once in the last step (before carrying out the minimization). To ensure correctness, Step 4 must be an atomic operation, where the executing processor puts a write lock on the global memory until it has written back the result of the minimization (cf. Figure 1, left). The algorithm can also be executed in a master-worker setting. In this case, each of the worker nodes retrieves $x$ from the master in Step 1 and returns the averaged gradient to the master in Step 3; the fourth step (carrying out the minimization) is executed by the master (cf. Figure 1, right)

Independently of how we choose to implement the algorithm, processors may work at different rates: while one processor updates the decision vector (in the shared memory setting) or send its averaged gradient to the master (in the master-worker setting), the others are generally busy computing averaged gradient vectors. The processors that perform gradient evaluations do not need to be aware of updates to the decision vector, but can continue to operate on stale information about $x$. Therefore, unlike synchronous parallel mini-batch algorithms , there is no need for processors to wait for each other to finish the gradient computations. Moreover, the value $\widehat{x}$ at which the average of gradients is evaluated by a processor may differ from the value of $x$ to which the update is applied.

can be viewed as the delay between reading and updating for processors and captures the staleness of the information used to compute the average of gradients for the k-th update. We assume that the delay is not too long, i.e., there is a nonnegative integer $\tau_{\max}$ such that

The value of $\tau_{\max}$ is an indicator of the asynchronism in the algorithm and in the execution platform. In practice, $\tau_{\max}$ will depend on the number of parallel processors used in the algorithm . Note that the cyclic-delay mini-batch algorithm , in which the processors are ordered and each updates the decision variable under a fixed schedule, is a special case of Algorithm 1 where $d(k)=k-p+1$, or, equivalently, $\tau(k)=p-1$ for all $k$.

IV-B Convergence Rate for General Convex Regularization

The following theorem establishes convergence properties of Algorithm 1 when a constant step-size is used.

where ${x}_{\textup{ave}}(T)$ is the Cesáro average of the iterates, i.e.,

Furthermore, $b$ is the batch size, the expectation is taken with respect to all random variables $\{\xi_{i}(k)\;|\;i=1,\ldots,b,\;k=0,\ldots,T-1\}$, and $c\in[1,b]$ is given by

it follows from Theorem 1 that the corresponding ${x}_{\textup{ave}}(T)$ satisfies

where \epsilon_{0}=D_{\omega}\bigl{(}x(0),x^{\star}\bigr{)}. This inequality tells us that if the first term on the right-hand side is less than $\epsilon/2$, i.e., if

As long as the maximum delay bound $\tau_{\max}$ is of the order $1/\sqrt{\epsilon}$, the first term in (6) is asymptotically negligible, and hence the iteration complexity of Algorithm 1 is asymptotically $\mathcal{O}(c\sigma^{2}/b{\epsilon}^{2})$, which is exactly the iteration complexity achieved by the mini-batch algorithm for solving stochastic convex optimization problems in a serial setting . As discussed before, $\tau_{\max}$ is related to the number of processors used in the algorithm. Therefore, if the number of processors is of the order of $\mathcal{O}(1/\sqrt{\epsilon})$, parallelization does not appreciably degrade asymptotic convergence of Algorithm 1. Furthermore, as $p$ processors are being run in parallel, updates occur roughly $p$ times as quickly and in time scaling as $T/p$, the processors may compute $T$ averaged gradient vectors (instead of $T/p$ vectors). This means that the near-linear speedup in the number of processors can be expected.

Another strategy for the selection of the constant step-size in Algorithm 1 is to use $\gamma$ that depends on the prior knowledge of the number of iterations to be performed. More precisely, assume that the number of iterations is fixed in advance, say equal to $T_{F}$. By choosing $\gamma$ as

for some $\alpha>0$, it follows from Theorem 1 that the running average of the iterates after $T_{F}$ iterations satisfies

It is easy to verify that the optimal choice of $\alpha$, which minimizes the second term on the right-hand-side of the above inequality, is

With this choice of $\alpha$, we then have

In the case that $\tau_{\max}=0$, the preceding guaranteed bound reduces to the one obtained in [8, Theorem 1] for the serial stochastic mirror descent algorithm with constant step-sizes. Note that in order to implement Algorithm 1 with the optimal constant step-size policy, we need to estimate an upper bound on D_{\omega}\bigl{(}x(0),x^{\star}\bigr{)}, since D_{\omega}\bigl{(}x(0),x^{\star}\bigr{)} is usually unknown.

The following theorem characterizes the convergence of Algorithm 1 with a time-varying step-size sequence when $\textup{dom}\;\Psi$ is bounded in addition to being closed and convex.

Suppose that Assumptions 1–4 hold. In addition, suppose that $\textup{dom}\;\Psi$ is compact and that $D_{\omega}(\cdot,\cdot)$ is bounded on $\textup{dom}\;\Psi$. Let

then the Cesáro average of the iterates generated by Algorithm 1 satisfies

The time-varying step-size $\gamma(k)$, which ensures the convergence of the algorithm, consists of two terms: the time-varying term $\eta(k)$ should control the errors from stochastic gradient information while the role of the constant term ($L(\tau_{\max}+1)^{2}$) is to decrease the effects of asynchrony (bounded delays) on the convergence of the algorithm. According to Theorem 2, in the case that $\tau_{\max}=\mathcal{O}(T^{1/4})$, the delay becomes increasingly harmless as the algorithm progresses and the expected function value evaluated at ${x}_{\textup{ave}}(T)$ converges asymptotically at a rate $\mathcal{O}(1/\sqrt{T})$, which is known to be the best achievable rate of the mirror descent method for nonsmooth stochastic convex optimization problems .

For the special case of the optimization problem (1) where $\Psi$ is restricted to be the indicator function of a compact convex set, Agarwal and Duchi [36, Theorem 2] showed that the convergence rate of the delayed stochastic mirror descent method with time-varying step-size is

IV-C Convergence Rate for Strongly Convex Regularization

In this subsection, we restrict our attention to stochastic composite optimization problems with strongly convex regularization terms. Specifically, we assume that $\Psi$ is $\mu_{\Psi}$-strongly convex with respect to $\|\cdot\|$, that is, for any $x,y\in\textup{dom}\;\Psi$,

Examples of the strongly convex function $\Psi$ include:

$l_{2}$-regularization: $\Psi(x)=(\rho/2)\|x\|_{2}^{2}$ with $\rho>0$.

Elastic net regularization: $\Psi(x)=\lambda\|x\|_{1}+(\rho/2)\|x\|_{2}^{2}$ with $\lambda>0$ and $\rho>0$.

The strong convexity of $\Psi$ implies that Problem (1) has a unique minimizer $x^{\star}$ [41, Corollary 11.16].

In order to derive the convergence rate of Algorithm 1 for solving (1) with a strongly convex regularization term, we need to assume that the Bregman distance function $D(x,y)$ used in the algorithm satisfies the next assumption.

For all $x,y\in\textup{dom}\;\Psi$, we have

For example, if $\omega(x)=\frac{1}{2}\|x\|_{2}^{2}$, then $D_{\omega}(x,y)=\frac{1}{2}\|x-y\|_{2}^{2}$ and $Q=1$. Note that Assumption 5 will automatically hold when the distance generating function $\omega$ has Lipschitz continuous gradient with a constant $Q$ .

The associated convergence result now reads as follows.

then the iterates produced by Algorithm 1 satisfies

An interesting point regarding Theorem 3 is that for solving stochastic composite optimization problems with strongly convex regularization functions, the maximum delay bound $\tau_{\max}$ can be as large as $\mathcal{O}(T^{1/4})$ without affecting the asymptotic convergence rate of Algorithm 1. In this case, our asynchronous mini-batch algorithm converges asymptotically at a rate of $\mathcal{O}(1/T)$, which matches the best known rate achievable in a serial setting.

V Experimental Results

We have developed a complete master-worker implementation of our algorithm in C/++ using the Massage Passing Interface libraries (OpenMPI). Although we argued in Section IV that Algorithm 1 can be implemented using atomic operations on shared-memory computing architectures, we have chosen the MPI implementation due to its flexibility in scaling the problem to distributed-memory environments.

We evaluated our algorithm on a document classification problem using the text categorization dataset rcv1 . This dataset consists of $m\approx 800000$ documents, with $n\approx 50000$ unique stemmed tokens spanning 103 topics. Out of these topics, we decided to classify sports-related documents. To this end, we trained a sparse (binary) classifier by solving the following $l_{1}$-regularized logistic regression problem

Figure 2 presents the achieved relative speedup of the algorithm with respect to the number of workers used. The relative speedup of the algorithm on $p$ processors is defined as $S(p)=t_{1}/t_{p}$, where $t_{1}$ and $t_{p}$ are the time it takes to run the corresponding algorithm (to $\epsilon$-accuracy) on 1 and $p$ processing units, respectively. We observe a near-linear relative speedup, consistent with our theoretical results. The timings are averaged over 10 Monte Carlo runs.

VI Conclusions

We have proposed an asynchronous mini-batch algorithm that exploits multiple processors to solve regularized stochastic optimization problems with smooth loss functions. We have established that for closed and convex constraint sets, the iteration complexity of the algorithm with constant step-sizes is asymptotically $\mathcal{O}(1/\epsilon^{2})$. For compact constraint sets, we have proved that the running average of the iterates generated by our algorithm with time-varying step-size converges to the optimum at a rate $\mathcal{O}(1/\sqrt{T})$. When the regularization function is strongly convex and the constraint set is closed and convex, the algorithm achieves the rate of the order $\mathcal{O}(1/T)$. We have shown that the penalty in convergence rate of the algorithm due to asynchrony is asymptotically negligible and a near-linear speedup in the number of processors can be expected. Our computational experience confirmed the theory.

In this section, we prove the main results of the paper, namely, Theorems 1–3. We first state three key lemmas which are instrumental in our argument.

The following result establishes an important recursion for the iterates generated by Algorithm 1.

where $x^{\star}\in X^{\star}$, $\{\eta(k)\}$ is a sequence of strictly positive numbers, and $e(k):=\nabla f(x(k))-{g}_{\textup{ave}}(k)$ is the error in the gradient estimate.

We start with the first-order optimality condition for the point $x(k+1)$ in the minimization problem (3): there exists subgradient $s(k+1)\in\partial\Psi(x(k+1))$ such that for all $z\in\textup{dom}\;\Psi$, we have

where $\nabla_{(2)}D_{\omega}(\cdot,\cdot)$ denotes the partial derivative of the Bregman distance function with respect to the second variable. Plugging the following equality

into the previous inequality and re-arranging terms gives

by the (strong) convexity of $\Psi$. We now use the following well-known three point identity of the Bregman distance function to rewrite the left-hand side of (8):

From this relation, with $a=x(k)$, $b=x(k+1)$, and $c=z$, we have

Substituting the preceding equality into (8) and re-arranging terms result in

Since the distance generating function $\omega(x)$ is $1$-strongly convex, we have the lower bound

for any $z\in\textup{dom}\;\Psi$. Combining inequalities (9) and (10), and recalling that $\phi(x)=f(x)+\Psi(x)$, we obtain

We now rewrite the above inequality in terms of the error $e(d(k))=\nabla f(x(d(k)))-{g}_{\textup{ave}}(d(k))$ as follows:

where the second inequality follows from the Fenchel-Young inequality applied to the conjugate pair $\frac{1}{2}\|\cdot\|^{2}$ and $\frac{1}{2}\|\cdot\|_{*}^{2}$, i.e.,

We now turn to $U_{2}$. It follows from definition $\tau(k)=k-d(k)$ that

Then, by the convexity of the norm $\|\cdot\|$, we conclude that

Setting $z=x^{\star}$, where $x^{\star}\in X^{\star}$, completes the proof. ∎

The next result follows from Lemma 1 by taking summation of the relations in (7).

adding and subtracting \gamma(k+1)^{-1}D_{\omega}\bigl{(}x(k+1),x^{\star}\bigr{)} to the left-hand side of (7), and re-arranging terms, we obtain

where the second inequality used the facts

and $x(k)=x(0)$ for all $k\leq 0$. Dropping the second term on the left-hand side of (14) concludes the proof. ∎

The result follows from [44, Lemma B.2] and convexity of the norm $\|\cdot\|_{*}$. For further details, see [32, §4.1]. ∎

for some $\eta>0$. It is clear that $\gamma$ satisfies (4). Applying Lemma 2 with $\mu_{\Psi}=0$, $\gamma(k)=\gamma$ and $\eta(k)=\eta$, we obtain

Moreover, as $\xi_{i}$ and $\xi_{j}$ are independent whenever $i\neq j$, it follows from Lemma 3 that

where the last inequality follows from Assumption 3. Taking expectation on both sides of (15) and using the above observations yield

Substituting $\eta=\gamma^{-1}-L(\tau_{\max}+1)^{2}$ into the above inequality proves the theorem.

-B Proof of Theorem 2

Since $\gamma(k)$ is a non-increasing sequence, and $D_{\omega}(x,y)\leq R^{2}$ for all $x,y\in\;\textup{dom}\;\Psi$, we have

Applying Lemma 2 with $\mu_{\Psi}=0$ and $\eta(k)=\alpha(k)$, taking expecation, and using Lemma 3 completely identically to the proof of Theorem 1, we then obtain

Viewing the sum as an lower-estimate of the integral of the function $y(t)=1/\sqrt{t+1}$, one can verify that

where $\widetilde{\alpha}=(\sigma\sqrt{c})/(R\sqrt{b})$. Substituting this inequality into the bound (16), we obtain the claimed guaranteed bound.

-C Proof of Theorem 3

We first describe some important properties of $\gamma(k)$ relevant to our proof. Clearly, $\gamma(k)$ is non-increasing, i.e.,

We are now ready to prove Theorem 3. Applying Lemma 1 with

Multiplying both sides of this relation by $1/\gamma(k)$, and then using (19), we have

What remains is to bound the third term on the right-hand side of (21). It follows from (17)–(20) that

Substituting the above inequality into (21), and then taking expectation on both sides (similarly to the proof of Theorems 1 and 2), we have

Moreover, by the definition of $\gamma(k)$,

Combing these inequalities with the bound (22), we conclude

References