Fast-and-Light Stochastic ADMM

1 Introduction

In this big data era, tons of information are generated every day. Thus, efficient optimization tools are needed to solve the resultant large-scale machine learning problems. In particular, the well-known stochastic gradient descent (SGD) [Bottou, 2004] and its variants [Parikh and Boyd, 2014] have drawn a lot of interest. Instead of visiting all the training samples in each iteration, the gradient is computed by using one sample or a small mini-batch of samples. The per-iteration complexity is then reduced from O(n), where n is the number of training samples, to O(1). Despite its scalability, the stochastic gradient is much noisier than the batch gradient. Thus, the stepsize has to be decreased gradually as stochastic learning proceeds, leading to slower convergence.

Recently, a number of fast algorithms have been developed that try to reduce the variance of stochastic gradients [Defazio et al., 2014; Johnson and Zhang, 2013; Roux et al., 2012; Shalev-Shwartz and Zhang, 2013]. With the variance reduced, a larger constant stepsize can be used. Consequently, much faster convergence, even matching that of its batch counterpart, is attained. A prominent example is the stochastic average gradient (SAG) [Roux et al., 2012], which reuses the old stochastic gradients computed in previous iterations. A related method is stochastic dual coordinate ascent (SDCA) [Shalev-Shwartz and Zhang, 2013], which performs stochastic coordinate ascent on the dual. However, a caveat of SAG is that storing the old gradients takes O(nd) space, where d is the dimensionality of the model parameter. Similarly, SDCA requires storage of the dual variables, which scales as O(n). Thus, they can be expensive in applications with large n (big sample size) and/or large d (high dimensionality).

Moreover, many machine learning problems, such as graph-guided fused lasso and overlapping group lasso, are too complicated for SGD-based methods. The alternating direction method of multipliers (ADMM) has been recently advocated as an efficient optimization tool for a wider variety of models [Boyd et al., 2011]. Stochastic ADMM extensions have also been proposed [Ouyang et al., 2013; Suzuki, 2013; Wang and Banerjee, 2012], though they only have suboptimal convergence rates. Recently, researchers have borrowed variance reduction techniques into ADMM. The resultant algorithms, SAG-ADMM [Zhong and Kwok, 2014] and SDCA-ADMM [Suzuki, 2014], have fast convergence rate as batch ADMM but are much more scalable. The downside is that they also inherit the drawbacks of SAG and SDCA. In particular, SAG-ADMM and SDCA-ADMM require O(nd) and O(n) space, respectively, to store the past gradients and weights or dual variables. This can be problematic in large multitask learning, where the space complexities is scaled by N, the number of tasks. For example, in one of our multitask learning experiments, SAG-ADMM needs 38▷2TB for storing the weights, and SDCA-ADMM needs 9▷6GB for the dual variables.

To alleviate this problem, one can integrate ADMM with another popular variance reduction method, namely, stochastic variance reduced gradient (SVRG) [Johnson and Zhang, 2013]. In particular, SVRG is advantageous in that no extra space for the intermediate gradients or dual variables is needed. However, this integration is not straightforward. A recent initial attempt is made in [Zhao et al., 2015]. Essentially, their SCAS-ADMM algorithm uses SVRG as an inexact stochastic solver for one of the ADMM subproblems. The other ADMM variables are not updated until that subproblem has been approximately solved. Analogous to the difference between Jacobi iteration and Gauss-Seidel iteration, this slows down convergence. Indeed, on strongly convex problems, SCAS-ADMM only has sublinear convergence while SDCA-ADMM has a linear rate. On general convex problems, SCAS-ADMM requires the stepsize to be gradually reduced. This defeats the original purpose of using SVRG-based algorithms, which aim at using a larger, constant learning rate to achieve fast convergence [Johnson and Zhang, 2013].

In this paper, we propose a tighter integration of SVRG and ADMM with a constant learning rate. The per-iteration computational cost of the resultant SVRG-ADMM algorithm is as low as existing stochastic ADMM methods, but yet it admits fast linear convergence on strongly convex problems. Among existing stochastic ADMM algorithms, a similar linear convergence result is only proved in SDCA-ADMM for a special ADMM setting. Besides, it is well-known that the penalty parameter in ADMM can significantly affect convergence [Nishihara et al., 2015]. While its effect on the batch ADMM has been well-studied [Deng and Yin, 2015; Nishihara et al., 2015], that on stochastic ADMM is still unclear. We show that its optimal setting is, interestingly, the same as that in the batch setting. Moreover, SVRG-ADMM does not need to store the gradients or dual variables throughout the iterations. This makes it particularly appealing when both the number of samples and label classes are large.

Notation: For a vector x, kxk is its `2-norm, and kxkQ = pxT Qx. For a matrix X, kXk is its spectral norm, σmax(X) (resp. σmin(X)) is its largest (resp. smallest) eigenvalue, and X its pseudoinverse. For a function f, f 0 is a subgradient. When f is differentiable, we use rf as its gradient.

2 RelatedWork

Consider the regularized risk minimization problem: minx 1n Pni=1 fi(x) + r(x), where x is the model parameter, n is the number of training samples, fi is the loss due to sample i, and r is a regularizer. For many structured sparsity regularizers, r(x) is of the form g(Ax), where A is a matrix [Kim et al., 2009; Jacob et al., 2009]. By introducing an additional y, the problem can be rewritten as

where

Problem (3) can be conveniently solved by the alternating direction method of multipliers (ADMM) [Boyd et al., 2011]. In general, ADMM considers problems of the form

where f↪ g are convex functions, and A↪B (resp. c) are constant matrices (resp. vector). Let ⇢ > 0 be a penalty parameter, and u be the dual variable. At iteration t, ADMM performs the updates:

With f in (2), solving (5) can be computationally expensive when the data set is large. Recently, a number of stochastic and online variants of ADMM have been developed [Wang and Banerjee, 2012; Ouyang et al., 2013; Suzuki, 2013]. However, they converge much slower than the batch ADMM, namely, O(1◁pT) vs O(1◁T) for convex problems, and O(log T◁T ) vs linear convergence for strongly convex problems.

For gradient descent, a similar gap in convergence rates between the stochastic and batch algorithms is well-known [Roux et al., 2012]. As noted by [Johnson and Zhang, 2013], the underlying reason is that SGD has to control the gradient's variance by gradually reducing its stepsize ⌘. Recently, by observing that the training set is always finite in practice, a number of variance reduction techniques have been developed that allow the use of a constant stepsize, and consequently faster convergence. In this paper, we focus on the SVRG [Johnson and Zhang, 2013], which is advantageous in that no extra space for the intermediate gradients or dual variables is needed. The algorithm proceeds in stages. At the beginning of each stage, the gradient ˜ z = 1n Pni=1 rfi(˜x) is computed using a past parameter estimate ˜x. For each subsequent iteration t in this stage, the approximate gradient

is used, where It is a mini-batch of size b from ¶1↪ 2↪ ▷ ▷ ▷ ↪ n♦. Note that ˆrf(xt-1) is unbiased (i.e., Eˆrf(xt-1) = rf(xt-1)), and its (expected) variance goes to zero asymptotically.

Recently, variance reduction has also been incorporated into stochastic ADMM. For example, SAG-ADMM [Zhong and Kwok, 2014] is based on SAG [Roux et al., 2012]; and SDCA-ADMM [Suzuki, 2014] is based on SDCA [ShalevShwartz and Zhang, 2013]. Both enjoy low iteration complexities and fast convergence. However, SAG-ADMM requires O(nd) space for the old gradients and weights, where d is the dimensionality of x. As for SDCA-ADMM, even though its space requirement is lower, it is still proportional to N, the number of labels in a multiclass/multilabel/multitask learning problem. As N can easily be in the thousands or even millions (e.g., Flickr has more than 20 millions tags), SAG-ADMM and SDCA-ADMM can still be problematic.

3 Integrating SVRGwith Stochastic ADMM

In this paper, we make the following assumptions on the fi's in (2) and g in (3).

Assumption 1. Each fi is convex, continuously differentiable, and has Li-Lipschitz-continuous gradient. In other words, there exists Li > 0 such that fi(xj)  fi(xi) + rfi(xi)T (xj - xi) + Li 2 kxi -xjk2 for all xi↪ xj.

Assumption 2. g is convex, but can be nonsmooth.

Let (x⇤↪ y⇤) be the optimal (primal) solution of (3), and u⇤ the corresponding dual solution. At optimality, we have

3.1 Strongly Convex Problems

In this section, we consider the case where f is strongly convex. A popular example in machine learning is the square loss.

Moreover, we assume that matrix A has full row rank. This assumption has been commonly used in the convergence analysis of ADMM algorithms [Deng and Yin, 2015; Ghadimi et al., 2015; Giselsson and Boyd, 2014; Nishihara et al., 2015].

Assumption 4. Matrix A has full row rank.

The proposed procedure is shown in Algorithm 1. Similar to SVRG, it is divided into stages, each with m iterations. The updates for yt and ut are the same as batch ADMM ((4) and (6)). The key change is on the more expensive xt update. We first replace (5) by its first-order approximation f(xt-1) + rf(xt-1)T x. As in SVRG, the full gradient rf(xt-1) is approximated by ˆrf(xt-1) in (7). Recall that ˆrf(xt-1) is unbiased and its (expected) variance goes to zero. In other words, ˆrf(xt-1) ! rf(x⇤) when xt-1 and ˜x approach the optimal x⇤, which allows the use of a constant stepsize. In contrast, traditional stochastic approximations such as OPG-ADMM [Suzuki, 2013] use 1b Pit2It rfit (xt-1) to approximate the full gradient, and a decreasing step size is needed to ensure convergence.

Unlike SVRG, the optimization subproblem in Step 9 has the additional terms ⇢2 kAx+Byt-c+ut-1k2 (fromsubproblem (5)) and 1 2⌘ kx-xt-1k2G (to ensure that the next iterate is close to the current iterate xt-1). A common setting for G is simply G = I [Ouyang et al., 2013]. Step 9 then reduces to

Note that ( 1 ⌘ I + ⇢AT A)-1 above can be pre-computed. On the other hand, while some stochastic ADMM algorithms [Ouyang et al., 2013; Zhong and Kwok, 2014] also need to compute a similar matrix inverse, their ⌘'s change with iterations and so cannot be pre-computed.

When AT A is large, storage of this matrix may still be problematic. To alleviate this, a common approach is linearization (also called the inexact Uzawa method) [Zhang et al., 2011]. It sets G = γI - ⌘⇢AT A with

to ensure that G ⌫ I. The xt update in (10) then simplifies to

Note that steps 2 and 12 in Algorithm 1 involve the pseudoinverse A . As A is often sparse, this can be efficiently computed by the Lanczos algorithm [Golub and Van Loan, 2012].

Algorithm 1 SVRG-ADMM for strongly convex problems.

• 1: Input: m↪ ⌘↪ ⇢ > 0▷
• 2: initialize ˜x0↪ ˜ y0 and ˜u0 = - 1⇢ (AT ) rf(˜x0);
• 3: for s = 1↪ 2↪ ▷ ▷ ▷ do
• 4: ˜x = ˜xs-1;
• 5: x0 = ˜xs-1; y0 = ˜ ys-1; u0 = ˜us-1;
• 8: yt argminy g(y)+ ⇢2 kAxt-1+By-c+ut-1k2 ;
• 6: ˜ z = 1n Pni=1 rfi(˜x); 7: for t = 1↪ 2↪ ▷ ▷ ▷ ↪ m do
• 9: xt argminx ˆrf(xt-1)T x+ ⇢2 kAx+Byt -c+ ut-1k2 + kx-xt-1k2G 2⌘ ;
• 11: end for
• 10: ut ut-1 +Axt +Byt - c;
• 13: end for
• 12: ˜xs = 1m Pmt=1 xt; ˜ ys = 1m Pmt=1 yt; ˜us = - 1⇢ (AT ) rf(˜xs);
• 14: Output: ˜xs↪ ˜ ys;

In general, as in other stochastic algorithms, the stochastic gradient is computed based on a mini-batch of size b. The following Proposition shows that the variance can be progressively reduced. Note that this and other results in this section also hold for the batch mode, in which the whole data set is used in each iteration (i.e., b = n).

Proposition 1. The variance of ˆrf(xt-1) is bounded by Ekˆrf(xt-1) - rf(xt-1)k2  4Lmaxβ(b) (J(xt-1) -J(x⇤) +J(˜x) -J(x⇤)), where Lmax ⌘ maxi Li, β(b) = n-b b(n-1) , J(x) = f(x) + ⇢uT⇤ Ax, and J(xt-1) - J(x⇤) + J(˜x) - J(x⇤) ≥ 0.

Using (8) and (9), J(x) - J(x⇤) = f(x) - f(x⇤) - rf(x⇤)T (x - x⇤) = 0 when x ! x⇤, and thus the variance goes to zero. Moreover, as expected, the variance reduces when b increases, and goes to zero when b = n. However, a large b leads to a high per-iteration cost. Thus, there is a tradeoff between "high variance with cheap iterations" and "low variance with expensive iterations".

Convergence Analysis

In this section, we study the convergence w.r.t. R(x↪ y) ⌘ f (x)-f (x⇤)-rf (x⇤)T (x-x⇤)+g(y)-g(y⇤)-g0 (y⇤)T (yy⇤). First, note that R(x↪ y) is always non-negative.

Proposition 2. R(x↪ y) ≥ 0 for any x and y.

Using the optimality conditions in (8) and (9), R(x↪ y) can be rewritten as f(x)+g(y)+⇢uT⇤ (Ax+By-c)-(f(x⇤)+ g(y⇤) + ⇢uT⇤ (Ax⇤ + By⇤ - c)), which is the difference of the Lagrangians in (3) evaluated at (x↪ y↪ u⇤) and (x⇤↪ y⇤↪ u⇤). Moreover, R(x↪ y) ≥ 0 is the same as the variational inequality used in [He and Yuan, 2012].

The following shows that Algorithm 1 converges linearly.

Theorem 1. Let

Choose 0 < ⌘ < min n 1 Lf ↪ 1 4Lmaxβ(b) o, and the number of iterations m is sufficiently large such that  < 1. Then, ER(˜xs↪ ˜ ys)  sR(˜x0↪ ˜ y0).

Theorem 1 is similar to the SVRG results in [Johnson and Zhang, 2013; Xiao and Zhang, 2014]. However, it is not a trivial extension because of the presence of the equality constraint and Lagrangian multipliers in the ADMM formulation. Moreover, for the existing stochastic ADMM algorithms, linear convergence is only proved in SDCA-ADMM for a special case (B = -I and c = 0 in (3)). Here, we have linear convergence for a general B and any G ⌫ I (in step 9).

Corollary 1. For a fixed  and ✏ > 0, the number of stages s required to ensure ER(˜xs↪ ˜ ys)  ✏ is s ≥ log ⇣ R(˜x0↪ ˜ y0) ✏ ⌘ ◁ log ( 1 ). Moreover, for any δ 2 (0↪ 1), we have the high-probability bound: Prob(R(˜xs↪ ˜ ys)  ✏) ≥ 1- δ if s ≥ log ⇣ R(˜x0↪˜ y0) ✏δ ⌘ ◁ log ( 1 ). Optimal ADMM Parameter ⇢

With linearization, the first term in (13) becomes kγIk◁(λf⌘(1 - 4Lmax⌘β(b))m). Obviously, it is desirable to have a small convergence factor , and so we will always use γ = γmin in (11). The following Proposition obtains the optimal ⇢⇤, which yields the smallest  value and thus fastest convergence. Interestingly, this ⇢⇤ is the same as that of its batch counterpart (Theorem 7 in [Nishihara et al., 2015]). In other words, the optimal ⇢⇤ is not affected by the stochastic approximation.

3.2 General Convex Problems

In this section, we consider (general) convex problems, and only Assumptions 1, 2 are needed. The procedure (Algorithm 2) differs slightly from Algorithm 1 in the initialization of each stage (steps 2, 5, 12) and the final output (step 14).

As expected, with a weaker form of convexity, the convergence rate of Algorithm 2 is no longer linear. Following [Ouyang et al., 2013; Suzuki, 2013; Zhong and Kwok, 2014], we consider the convergence of R(¯x↪ ¯ y) + ⇣kA¯x + B ¯ y - ck, where ⇣ > 0 and kA¯x + B¯ y - ck measures the feasibility of the ADMM solution. The following Theorem shows that Algorithm 2 has O(1◁s) convergence. Since both R(¯x↪ ¯ y) and kA¯x + B ¯ y - ck are always nonnegative, obviously each term individually also has O(1◁s) convergence.

The following Corollary obtains a sublinear convergence rate for the batch case (b = n). This is similar to that of

Algorithm 2 SVRG-ADMM for general convex problems.

• 1: Input: m↪ ⌘↪ ⇢ > 0▷
• 2: initialize ˜x0 = ˆx0↪ ˆ y0 and ˆu0;
• 3: for s = 1↪ 2↪ ▷ ▷ ▷ do
• 4: ˜x = ˜xs-1;
• 5: x0 = ˆxs-1; y0 = ˆ ys-1; u0 = ˆus-1;
• 8: yt argminy g(y)+ ⇢2 kAxt-1+By-c+ut-1k2 ;
• 6: ˜ z = 1n Pni=1 rfi(˜x); 7: for t = 1↪ 2↪ ▷ ▷ ▷ ↪ m do
• 9: xt argminx ˆrf(xt-1)T x+ ⇢2 kAx+Byt -c+ ut-1k2 + kx-xt-1k2G 2⌘ ;
• 11: end for
• 10: ut ut-1 +Axt +Byt - c;
• 13: end for
• 12: ˜xs = 1m Pmt=1 xt; ˜ ys = 1m Pmt=1 yt; ˆxs = xm; ˆ ys = ym; ˆus = um;
• 14: Output: ¯x = 1s Psi=1 ˜xi↪ ¯ y = 1s Psi=1 ˜ ys.

Remark 1 in [Ouyang et al., 2013]. However, here we allow a general G while they require G = I.

3.3 Comparison with SCAS-ADMM

The recently proposed SCAS-ADMM [Zhao et al., 2015] is a more rudimentary integration of SVRG and ADMM. The main difference with our method is that SCAS-ADMM moves the updates of y and u outside the inner for loop. As such, the inner for loop focuses only on updating x, and is the same as using a one-stage SVRG to solve for an inexact x solution in (5). Variables y and u are not updated until the x subproblem has been approximately solved (after running m updates of x).

In contrast, we replace the x subproblem in (5) with its first-order stochastic approximation, and then update y and u in every iteration as x. This difference is analogous to that between the Jacobi iteration and Gauss-Seidel iteration. The use of first-order stochastic approximation has also shown clear speed advantage in other stochastic ADMM algorithms [Ouyang et al., 2013; Suzuki, 2013; Zhong and Kwok, 2014; Suzuki, 2014], and is especially desirable on big data sets.

As a result, the convergence rates of SCAS-ADMM are inferior to those of SVRG-ADMM. On strongly convex problems, SVRG-ADMM attains a linear convergence rate, while SCAS-ADMM only has O(1◁s) convergence. On general convex problems, both SVRG-ADMM and SCAS-ADMM have a convergence rate of O(1◁s). However, SCAS-ADMM requires the stepsize to be gradually reduced as O(1◁sδ ), where δ > 1. This defeats the original purpose of using SVRG-based algorithms (e.g., SVRG-ADMM), which aims at using a constant learning rate for faster convergence [Johnson and Zhang, 2013]. Moreover, (14) shows that our rate consists of three components, which converge as O(1◁s), O(1◁(ms)) and O(1◁(ms)), respectively. On the other hand, while the sublinear convergence bound in SCAS-ADMM also has three similar components, they all converge as O(1◁s).

To make the cost of full gradient computation less pronounced, a natural choice for m is m = O(n) [Johnson and Zhang, 2013]. Hence, SCAS-ADMM can be much slower than SVRG-ADMM when n is large.

3.4 Space Requirement

The space requirements of Algorithms 1 and 2 mainly come from step 12. For simplicity, we consider B = -I and c = 0, which are assumed in [Suzuki, 2013; 2014]. Moreover, we assume that the storage of the n old gradients can be reduced to the storage of n scalars, which is often the case in many machine learning models [Johnson and Zhang, 2013].

A summary of the space requirements and convergence rates for various stochastic ADMM algorithms is shown in Table 1. As can be seen, among those with variance reduction, the space requirements of SCAS-ADMM and SVRGADMM are independent of the sample size n. However, as discussed in the previous section, SVRG-ADMM has much faster convergence rates than SCAS-ADMM on both strongly convex and general convex problems.

4 Experiments

4.1 Graph-Guided Fused Lasso

We perform experiments on the generalized lasso model Pni=1 `i(x) + kAxk1, where `i is the logistic loss on sample i, and A is a matrix encoding the feature sparsity pattern. Here, we use graph-guided fused lasso [Kim et al., 2009] and set A = [G; I], where G is the sparsity pattern of the graph obtained by sparse inverse covariance estimation [Friedman et al., 2008]. For the ADMM formulation, we introduce an additional variable y and the constraint Ax = y. Experiments are performed on four benchmark data sets 1 (Table 2). We use a mini-batch size of b = 100 on protein and covertype; and b = 500 on mnist8m and dna. Experiments are performed on a PC with Intel i7-3770 3▷4GHz CPU and 32GB RAM, All methods listed in Table 1 are compared and in Matlab. The proposed SVRG-ADMM uses the linearized update in (12) and m = 2n◁b. For further speedup, we simply use the last iterates in each stage (xm↪ ym↪ um) as ˜xs↪ ˜ ys↪ ˜us in step 12 of Algorithms 1 and 2. Both SAG-ADMM and SVRG-ADMM are initialized by running OPG-ADMM for n◁b iterations. 2 For SVRG-ADMM, since the learning rate in (12) is effectively ⌘◁γ, we set γ = 1 and only tune ⌘. All parameters are tuned as in [Zhong and Kwok, 2014]. Each stochastic algorithm is run on a small training subset for a few data passes (or stages). The parameter setting with the smallest training objective is then chosen. To ensure that the ADMM constraint is satisfied, we report the performance based on (xt↪ Axt). Results are averaged over five repetitions.

1 Downloaded from http://www.csie.ntu.edu.tw/⇠cjlin/ libsvmtools/datasets/, http://osmot.cs.cornell.edu/kddcup/datasets. html, and http://largescale.ml.tu-berlin.de/instructions/.

Figure 1 shows the objective values and testing losses versus CPU time. SAG-ADMM cannot be run on mnist8m and dna because of its large memory requirement (storing the weights already takes 8.2GB for mnist8m, and 14.3GB for dna). As can be seen, stochastic ADMM methods with variance reduction (SVRG-ADMM, SAG-ADMM and SDCAADMM) have fast convergence, while those that do not use variance reduction are much slower. SVRG-ADMM, SAG-ADMM and SDCA-ADMM have comparable speeds, but SVRG-ADMM requires much less storage (see also Table 1). On the medium-sized protein and covertype, SCASADMM has comparable performance with the other stochastic ADMM variants using variance reduction. However, it becomes much slower on the larger minist8m and dna, which is consistent with the analysis in Section 3.3.

2 This extra CPU time is counted towards the first stages of SAGADMM and SVRG-ADMM.

4.2 Multitask Learning

When there are a large number of outputs, the much smaller space requirement of SVRG-ADMM is clearly advantageous. In this section, experiments are performed on an 1000-class ImageNet data set [Russakovsky et al., 2015]. We use 1,281,167 images for training, and 50↪ 000 images for testing. 4096 features are extracted from the last fully connected layer of the convolutional net VGG-16 [Simonyan and Zisserman, 2014]. The multitask learning problem is formulated as: minX PNi=1 `i(X) + λ1kXk1 + λ2kXk⇤, where X 2 Rd⇥N is the parameter matrix, N is the number of tasks, d is the feature dimensionality, `i is the multinomial logistic loss on the ith task, and k · k⇤ is the nuclear norm. To solve this problem using ADMM, we introduce an additional variable X0 with the constraint X0 = X. On setting A = [I; I], the regularizer is then g(AX) = g([X; X0 ]) = λ1kXk1 + λ2kX0 k⇤. We set λ1 = 10-5 , λ2 = 10-4 , and use a mini-batch size b = 500. SAG-ADMM requires 38.2TB for storing the weights, and SDCA-ADMM 9.6GB for the dual variables, while SVRGADMM requires 62.5MB for storing ˜x and the full gradient.

Figure 2 shows the objective value and testing error versus time. SVRG-ADMM converges rapidly to a good solution. The other non-variance-reduced stochastic ADMM algorithms are very aggressive initially, but quickly get much slower. SCAS-ADMM is again slow on this large data set.

4.3 Varying ⇢

Finally, we perform experiments on total-variation (TV) regression [Boyd et al., 2011] to demonstrate the effect of ⇢. Samples zi's are generated with i.i.d. components from the standard normal distribution. Each zi is then normalized to kzik = 1. The parameter x is generated according to http://www.stanford.edu/⇠boyd/papers/admm/. The output oi is obtained by adding standard Gaussian noise to xT zi. Given n samples ¶(z1↪ o1)↪ ▷ ▷ ▷ ↪ (zn↪ on)♦, TV regression is formulated as: minx 1 2n Pni=1 koi-xT zik2 +λkAxk1, where Aij = 1 if i = j; -1 if j = i + 1; and 0 otherwise.

We set n = 100↪ 000↪ d = 500, λ = 0▷1◁pn, and a minibatch size b = 100. Figure 3 shows the objective value and testing loss versus CPU time, with different ⇢'s. As can be seen, ⇢⇤ in Proposition 3 outperforms the other choices of ⇢.

5 Conclusion

This paper proposed a non-trivial integration of SVRG and ADMM. Its theoretical convergence rates are as fast as existing variance-reduced stochastic ADMM algorithms, but its storage requirement is much lower, even independent of the sample size. Experimental results demonstrate its benefits over other stochastic ADMM methods.

Acknowledgments

This research was supported in part by the Research Grants Council of the Hong Kong Special Administrative Region (Grant 614513).