Efficient High-Dimensional Data Representation Learning via Semi-Stochastic Block Coordinate Descent Methods
Authors: Bingkun Wei
Yangyang Li
Fanhua Shang
Yuanyuan Liu
Hongying Liu
Shengmei Shen
Venue:  (2020)
Keywords: Sparse learning
Hard thresholding
High-dimensional regression

Abstract: With the increase of data volume and data dimension, sparse representation learning attracts more and more attention. For high-dimensional data, randomized block coordinate descent methods perform well because they do not need to calculate the gradient along the whole dimension. Existing hard thresholding algorithms evaluate gradients followed by a hard thresholding operation to update the model parameter, which leads to slow convergence. To address this issue, we propose a novel hard thresholding algorithm, called Semi-stochastic Block Coordinate Descent Hard Thresholding Pursuit (SBCD-HTP). Moreover, we present its sparse and asynchronous parallel variants. We theoretically analyze the convergence properties of our algorithms, which show that they have a significantly lower hard thresholding complexity than existing algorithms. Our empirical evaluations on real-world datasets and face recognition tasks demonstrate the superior performance of our algorithms for sparsity-constrained optimization problems.

Under review as a conference paper at ICLR 2020
EFFICIENT HIGH-DIMENSIONAL DATA REPRESENTA- TION LEARNING VIA ORDINATE DESCENT METHODS
BLOCK Co-
Anonymous authors Paper under double-blind review
ABSTRACT
With the increase of data volume and data dimension, sparse representation learn- ing attracts more and more attention. For high-dimensional data, randomized block coordinate descent methods perform well because they do not need to cal- culate the gradient along the whole dimension. Existing hard thresholding algo- rithms evaluate gradients followed by hard thresholding operation update the model parameter, which leads to slow convergence. To address this issue, we propose novel hard thresholding algorithm, called Semi-stochastic Block Coor- dinate Descent Hard Thresholding Pursuit (SBCD-HTP). Moreover, we present its sparse and asynchronous parallel variants. We theoretically analyze the con- vergence properties of our algorithms, which show that they have significantly lower hard thresholding complexity than existing algorithms. Our empirical eval- uations real-world datasets and face recognition tasks demonstrate the superior performance our algorithms for spansity-constrained optimization problems.
INTRODUCTION
In modern high-dimensional data analytics, where the variable dimension can be equal or even larg- er than the number of samples, sparse representation learning has become a mainstream method to explore the potential real model of the problem and provides statistically reliable results. has been applied to many diverse domains such as high-dimensional statistics (Bühlmann & Van De Geer, 2011), signal processing (Lai et al., 2013). and computer vision (Wright et al. (0088). Many sparse learning algorithms such as é nnorm convex relaxation methods (Negahban et al. 2009 Van de Geer cet al. 2008) have been proposed in the past few decades. In order to get a smaller estimation er- ror, Eo-norm constrained algorithms are more prominent than -n-orrm convex relaxation algorithms optimiza-
(Zhang et al. 2010). In this paper, we mainly focus on the following
tion problem:
min F(w) = 71 Σ f(w),, s.t., ||w|lo S
(1)
where F(w) is a finite-sum convex and smooth function, each function fi(w) is associated with the i-th sample. |uo]oo is the number of nonzero entries in variable w, and s represents the sparsity level. The goal of sparse representation learning is to recover w" based on the given data. Such a
formulation encapsulates plentiful important problems. including sparse graphical model learning
(Zhou et al. 2019). sparse linear/logistic regression (Blumensath & Davies
2009 Foucart 2011
Pati al. 1993] Bahmani et al. 2013). and low-rank regression (Rohde et al.
2011.
However, Problem ① is in general NP hard, which is caused by the non non-convexity of the sparsity constraint. makes us to obtain an approximate solution Problem ( One of the most widely used methods for solving this problem is the hard thresholding based gradient descent method. In recent years, sparse representation learning is becoming more common for large-scale and high- dimensional data. However, deterministic gradient descent hard thresholding algorithms such as fast gradient descent hard thresholding (FG-HT) (Jain et al. 2014 Yuan et al., (014)) have to compute the gradients of all component functions, which leads huge computing overhead. To address this issue, many stochastic hard thresholding methods have been proposed. For instance, Nguyen et al. (2017) proposed stochastic gradient descent hard thresholding (SG-HT) algorithm, whose

---

Under review as a conference paper at ICLR 2020
Table 1: Comparison of some properties of the hard thresholding algorithms for solving sparsity-constranned constrained problems. [B] is the mini-batch size of block coordinate descent methods, and is the number of coordinate blocks. Since the sparsity level s = (2(xs)") required in our algorithms (i.e., SBCD-HTP and its parallel variant, ASBCD-HTP) is much smaller than those of other algorithms (c.g. (2(xfs")) the condition number K3 in our algorithms is also smaller than R3 in other algorithms, where 3= ==20sks "++*" and ã= 20(xs
I (V (w"), U supppw' w²)
with s = =2(k3s") ") is support set.
Required value of
Gradient
Hard Thresholding
Statistical
Methods
Complexity
Complexity
Error
FG-HT
O ( (t))
(Ng log )))
O log(
SG-HT ()
(k3 log( (
SVRG-HT s)
((nn+Ng)logg
(Ng log()og))) ())
O
[
ASBCDHT (((2s=)
- O(n < )log( )
(Kg lo)()))
V[(w)))
SBCD-HTP (1aas))
O(nn+ + -=| ylog( ))
(log( ())
0(v3 VF (w0 (lx)
k
ASBCD-HTP )
O(n++ * log ())
(log( ())
0(v3 VF (w )oo)
S'BCD-HTP (K3ss)
O((n+ - log ())
(log( 2)) 0(v3 VF (w (occ)
gradient and hard thresholding complexities are both O(Ng lo)(t)) However, due to the stochastic sampling, SG-HT can only attain a sub-optimal estimation bound, as shown in Table [. which is inferior to those of deterministic gradient methods such as FG-HT. Another limitation of SG-HT is that it requires that the restricted condition number K3 should not be larger than 4/3, which makes SG-HT hard for solving high- nigh-dimenssonal representation learning problems.
Recently, many stochastic variance reduced methods (c.g.. SAG (Roux et al. 2012). SVRG (Jhnnson & Zhang 2013 and their accelerated variants such as (Defazio 2016; Allen-Zhu 2018 have been proposed to accelerate stochastic gradient methods for convex optimization. All these methods enjoy low per-iteration complexities comparable with stochastic gradient descent (SGD), and they also can attain improved convergence rates. By incorporating the variance reduction technique into sparsity- constrained optimization domain, Li et al. (2016b) proposed a stochastic variance reduced gradient hard thresholding (SVRG-HT) algorithm, which can converge more quickly and obtain a smaller timation error than SG-HT. Moreover, SVRG-HT allows an arbitrarily large condition number in its theoretical analysis similar to FG-HT (Yuan et al. 2014). The gradient oracle and hard thresholding complexities of SVRG-HT are (((++ log(? 5) and (rig logg ()), respectively. Nevertheless, it can not leverage the coordinate block to accelerate convergence. [Chen & Gul (2016) proposed an accelerated stochastic block coordinate gradient descent hard thresholding (ASBCDHT) algorith-
m. The gradient oracle complexity of ASBCDHT is O( ==( )og(()) which is superior to SVRG-HT, Moreover, ASBCDHT also has the hard thresholding complexity, OKK lo)( How- ever, the hard thresholding complexity of ASBCDHT still scales linearly with Kg. which is usually expensive for real-world sparse learning problems. For large-scale and high-dimensional data, Li et al. (1.166) also proposed the asynchronous parallel variant of SVRG-HT (called ASVRG-HT by utilizing multicore architectures. Although it makes each processor to evaluate a stochastic gradient update on a global parameter stored in a shared memory in an asynchronous and lock-free mode, ASVRG-HT attains the similar gradient and hard thresholding complexities as its general version (i.e.. SVRG-HT). Therefore, all the algorithms mentioned above have a linearly kg-dependent hard thresholding complexity. This motivates us to address the following key issue:
Can we design such algorithms that have -e--independent hard thresholding complexity and a lower gradient oracle complexity?
To answer the above problem, we propose efficient Semi-stochastic Block Coordinate Descent Hard Thresholding Pursuit (SBCD-HTP) algorithm and its sparse Asynchronous variant (ASBCD- HTP). The oracle complexities and statistical estimation error of the proposed algorithms and other hard thresholding methods are summarized in Table [ We highlight several theoretical advantages of the proposed algorithms over the ofte-oof-the-n methods as follows:
SBCD-HTP and ASBCD-HT -HOCD-HTPPPO substantially improve the restricted condition on the sparsity level i.e., 8 = == ((gss") while most related algorithms such SVRG-HT require ==
2

---

Under review as a conference paper at ICLR 2020
The statistical estimation error of both our algorithms is better than those of FG-HT, SVRG-HT and ASBCDHT, as our algorithms have a smaller sparsity level s ==[{Ks==) and thus have a smaller cardinality, i.c., 8 = 2s s" This makes the restricted condition number K3 of SBCD-HTP smaller than other algorithms. Moreover, the statistical error of our algorithms is also smaller than that of SG-HT (i.e., - I [Vfi(("") )l) due the large magnitude of (w=")l (Zoou et al. 2018b).
Both SBCD-HTP and ASBCD-HTP enjoy a kg-iindependent hard thresholding complexity, which significantly better than the state-of-the-art hard thresholding algorithms. That is, the hard thresh- olding complexity of our algorithms is Ka times lower than that of FG-HT, SG-HTT SVRG-HT and ASBCDHT with (((xxs')) +s. Since both our algorithms have a significantly lower hard thresholding complexity, they are more suitable for handling large-scale sparse representation learn- ing problems, especially for high-dimensional data.
For constry-c problems, the gradient oracle complexities of both SBCD-HTP and ASBCD-HTP (or S²BCD-HTP) are much lower than those of the state-of-the-an hard threshold- ing algorithms, and that of BCD-HHT is similar to ASBCD-HTP under conditions the delay. Actually, the gradient oracle complexity of B'BCD-HTP is better than SBCD-HTP when we deal with sparse data sets, since S'BCD-HTP only evaluates the common nonzero point of the random sample and the sampled block. Furthermore, their gradient oracle complexities are significantly lower than those of ASBCDHT and SVRG-HT, and much lower than that of FG-HT, since they require a smaller sparsity level & = [((E3)*) and also have a smaller value of K3 with X = 22 +* compared with the restricted condition number Kiz used in other hard thresholding algorithms (Zhou iet al. 2018b).
2 RELATED WORK
In this section, we briefly discuss the relevant research to our work, which beyonds the sparsity- constrained optimization domain. Traditional gradient descent is computational expensive at each iteration, and stochastic gradient descent has low per-iteration complexity while obtaining large variance in estimating. Thus, many stochastic variance reduced algorithms (Defazio et al. 2014]
Roux et al. 2012 Shlale-SShwartz & Zhang (013) [Shang et al. 2018 Johnson & Zhang] 201 3) and their variants (Schmidt et al.] [201]] KoKneeyy et al. 2013 Xiao & Zhang [0144] Hamnah et al. (018))
have been proposed. The stochastic variance reduced methods very promising for many machine learning problems including sparse learning problems.
In contrast to gradient descent methods, coordinate descent algorithms have received increasing at- tention due to their successful applications in high dimensional problems (Breheny & Huang 2011 Friedman al. 2007). Among them, randomized block coordinate descent (RBCD) updates block of coordinate with respect to the entire training instances. The per-iteration cost is significant- ly lower than gradient descent, while still has a relationship with n component functions. Some stochastic block coordinate descent (SBCD) algorithms such as (Dang & Lan 2015 Xu & Yin, 2015 Konečný et al. 2017) were proposed. Such algorithms compute the stochastic gradient with respect to a random sample restricted to one randomized coordinate block. Therefore, these algo- rithms randomly sample a block of features and data instances at each iteration. However, they can only achieve a sublinear convergence rate (Zhang & Gu 2016). Recently, some mini-batch random- ized block coordinate descent algorithms such as (Zhao et al. 2014; Wang & Banerjee, 2014) were proposed to accelerate the convergence of stochastic block coordinate gradient descent. Our work studies over the above research by considering a proposed algorithms enjoy lower computational complexity in both gradient evaluation and hard thresholding computation while obtaining linear convergence performance. Moreover, its sparse and asynchronous variants are also proposed to deal with sparse high-dimensional data.
optimization problem. The
3 PRELIMINARIES
Throughout this paper, we use w" to denote the optimal solution of Problem I and its optimal sparsity level is s* with |=" Ilo s* ||l||| is the Euclidean norm for vector w E Rd and || is the largest absolute entry in w. The hard thresholding operation HT(w, s) preserves the s largest entries of w in magnitude for vector and the rest entries are set zero. We use supp(w) to denote the support set of w., i.e., the indices of its nonzero entries. Given an index set I, we define I as the complement set of I, and uz Rdd where [Uz]j= u Uj if j E I and [uz], =0 if j $ T. Given an integer
3

---

Under review as a conference paper at ICLR 2020
Algorithm Semi-stochastic Block Coordinate Descent Hard Thresholding Pursuit (SBCD-HTP)
Input: Number of outer-loops R, number of inner-loops step size 17, sparsity level s. Initialize: w0 1: for 0, 0..,.... ..... R do
2: w. 1 w" VF(T)= = = E Vf(()) = supp(ū);
3: fort= 0,....,, m do
4: Randomly sample mini-batch B from [n] uniformly;
5: Randomly sample a block je from [k:] uniformly, and S U
6:
Vsg(w") = [8] Enes Vsfi.(w)) Vsst. (w) VsF(w);
7: w'+1 wt V)gg((")
8:
end for
9: 8+1 = (T s);
10: end for
Output: ãR.
1, we define [n] = {1.... .n.. For set B, we denote its cardinality by [B]. Moreover, the common notations of (2.)) and (.) to characterize the asymptoties of two real sequences.
Throughout the analysis, make important assumptions the objective function, which commonly used in the analysis of hard thresholding algorithms (Li et al., 2016b] [Shen & Li] [017] Chen & Gu 2016 Gao & Huang] 2018). In high-dimensional sparse learning, the per-iteration hard thresholding operation can be tine-consuming or even more expensive than gradient computation.
Thus, we also take the complexity of hard thresholding into our consideration.
Assumption (Restricted Strong Convexity) differentiable function F(-) restricted P strongly convex at sparsity level 8, if there exists uniform constant Ps > such that for any w, w' E Rd with w|l w'llo S 5, we have
F(w) F(w') (VF(w'), w w/)
Pz w|w w/11
Assumption 2 (Restricted Strong Smoothness) For any i E [n], the differentiable function fi(.)) is restricted p -strongly smooth at sparsity level 5, if there exists a uniform constant p > 0 such that for any w. w' E Rd with || w' Ilo I 8, we have
f(w)) fwww) - (Vi(ww),
w/) < P f/ w 112
Moreover, the restricted condition number is defined as: K3 = / / P Since the complexity of one hard thresholding operation is linear with d, which is similar to a computational cost of a stochastic gradient, define the hard thresholding complexity metric for hard thresholding algorithms.
Definition (Hard Thresholding Complexity) hard thresholding operation, a vector is fed into HT(.)) 8) and then the oulpui HT(w, 8) is obtained.
Both gradient oracle and hard thresholding complexities can more comprehensively reflect the over- all computational cost of first-order hard thresholding algorithms. Therefore, their per-iteration cost dominated by both the gradient evaluation and hard thresholding operations.
We also define the optimization error and statistical error to clearly understand our theoretical results.
Definition (Optimization Error and Statistical Error) The optimization error is the difference which will decrease with the increasing iterations. A statistical error is the (unknown) difference between the retained value and the true value.
This means that the optimization error will decrease to zero when the number of iteration is quite large. However, statistical eπror will still work during the optimized process. Therefore, the larger the statistical error, the more difference to the true value.
4

---

Under review as a conference paper at ICLR 2020
4 SEMI-STOCHASTIC BLOCK COORDINATE DESCENT HARD THRESHOLDING PURSUIT
In this section, we propose novel Semi-stochastic Block Coordinate Descent Hard Thresholding Pursuit (SBCD-HTP) algorithm, and also theoretically analyze its convergence properties.
4.1 OUR SBCD-HTE ALGORITHM
The proposed SBCD-HTP algorithm is summarized in Algorithm ! In each outer-loop, we select a snapshot point ti and compute its full gradient VF In each inner-loop, we uniformly and randomly select a mini-batch samples B and block of coordinates Gje- where je E 21, k), (G....9.
Ge } is partition of all the d coordinates and is divided uniformly at random. We usually set 10 in our experiments. Note that, different from ASBCDHT, in line 5 we set to be a union set of the support set of snapshot point w and Gj.- In this way, the coordinate of the support set S which includes the possibly optimal coordinates can be updated, and thus this can reduce the error caused by randomness. Moreover, SBCD- HTP enjoys the dual advantages of randomized block coordinate descent and semi-stochastic gradient descent to optimize the objective as shown in line 6. Note that we perform the hard thresholding operation in only the outer-loop, which is different from all existing hard thresholding algorithms. Performing hard thresholding operations with high frequency or prematurely in inner-loop will make the gradient information lost, which is the main reason for slow convergence and low accuracy of existing hard thresholding sparsity- constriic algorithms. Our hard thresholding algorithm not only guarantees the sparsity model parameters, but also uses the full dimensional information without the interference of hard thresholding operations to update model parameter wt Our theoretical analysis and experimental results show that SBCD-HTP has a faster convergence rate and more accurate results.
We have to clarify the difference between the proposed SBCD-HTP and ASBCDHT in Chen & Gu (2016) for clear improvements. There are mainly two changes: a) we design bigger support set with the union of the sampled block Gū with the one the current support of the snapshot point since the current support of snapshot point contain the most related optimized information, while that of Chen & Gu (2016) only use the sampled block. b) we move the hard thresholding operation outside of the inner-loop. since the truncated function (hard thresholding) may loss many information and bringing higher complexity. Moreover, the asynchronous variant of SBCD-HTP is also proposed in this paper optimize the sparse problem | in the sparse data. This is the first to design this type of algorithm in sparse learning field, and the theoretical proof is also provided.
4.2 CONVERGENCE ANALYSIS
We first analyze the convergence behavior of SBCD-HTP. The main result summarized in the following theorem, whose proof is provided in Section C
Theorem Suppose F(w) is P5 -strongly convex and each function f.(w) is p -strongly smooth with parameter 3 = 2s s". Let K3 Pz_ and the sparsity level s 2 [(nss"). In addition, assume 1,, the number of inner-loops m 2 1800ks, and the number of blocks
that the learning rate r 5
48p7
k ==10, then the convergence rate 2rmp; (1-w) problem ( the output of Algorithm satisfies
+ (I-w)
8p. minnnnni BB) < }.2 For the sparsiny-constrained
E[F(w0") [ww") ( - +
F(wx))
17
(w 11
(4)
where ī- supp( HT (V (w) 2s)) ) supp(w=)) and w 8p 1
[S
Theorem shows that SBCD-HTP enjoys a linear convergence rate for solving sparsity-constrained problem In order ensure that the linear converging term in Eq. (4 satisfies (+)")(((")
F(w")] we can obtain the following corollary.
Corollary Suppose the conditions in Theorem hold. To achieve ([) -FFF("")-F((")) S c,
the gradient oracle complexity of SBCD-IITP is O(n+ k log( +)), and its hard thresholding complexity is (log(?))
5

---

Under review as a conference paper at ICLR 2020
This corollary is inferred under the high-dimensional condition, Actually, the worst condition of the gradient oracle complexity of SBCD-IITP is O( + 2 log(t)) (o((()) Due to the small sparsity level & required in our Theorem 1 and the overlaps between 93, and G, we can obtain the gradient oracle complexity ((nn+ Ka & l) for SBCD-HTP.
Remark 1
Table summarizes the properties of some hard thresholding methods. Compared with the gra- dient oracle complexities FG-HT (Yuan et al.) 2014) and SVRG-HT (Li et al.) (016b) (i.e., Onnng log(2)) and ( log( () respectively), SBCD-HTP has much lower oracle complex-
ity. For ASBCDHT (Chen & Gu. 2016), whose gradient oracle complexity is O(n++ [8) log( )),
the gradient oracle complexity of SBCD-HTP is ((n * log())) and is much lower than AS- BCDHT, as Rig of SBCD-HTP is usually comparable to even smaller than those of others (note that s in ==+++s is required to be smaller than others as shown below). Moreover, SBCD-HTP allows =((kss*), which is considerably superior to the condition of ((< required in other hard thresholding algorithms such as (Zhou et al. 2018b). In particular, with the same parameter settings of (B] and k, the gradient oracle complexity of our algorithm outperforms ASBCDHT. SBCD-HTI also attains a lower hard thresholding complexity than the state-of totth--r- hard thresholding method- s. That is, the hard thresholding complexity of SBCD-HTP is (log( which Ki re-independent and is significantly lower than those of other methods. This is significant improvement on hard thresholding complexity. Theorem immediately implies the following results.
Corollary 2 Suppose the conditions in Theorem hoold The output of Algorithm 7 satisfies
El|"" w0'l= S 2(4) F ( - F(w*)]
(-
29 (-w) Vil
(5)
P5
The right-hand side of Eq. (5) consists of two terms. The first term is the optimization error, which approaches zero with the increase of r. The second term corresponds to the statistical error, which is proportional to v VF One can also observe that the statistical error bound is better than those of FG-HT and ASBCDHT, since in the statistical error O(v VF(w") has a smaller cardinality (i.e.. 21((xs"*) + while existing algorithms require larger sparsity level s' = [(e33s") and have a larger cardinality. Therefore. compared with other existing algorithms, SBCD-HTP enjoys smaller statistical error, especially for the problems with a large restricted condition number. It is usually better than the error bound O VF + +
+I| (F"FF""")) III with 5= ==20((x (x2ss*) in SVRG-HT. Moreover, the error bound of SBCD-HTP much smaller than that of SG-HT (guuyen al. 2017) (i.e., O Σ (f(""))))) since the magnitude of the individual gradient norm [V]( w )
can still be relatively large (Zhou et al. 2018b).
ASYNCHRONOUS VARIANT OF SBCD-HTP
In this section, we propose the serial sparse and asynchronous parallel variants of SBCD-HTP for high-dimensional sparse data sets. Our Asynchronous Sparse Semi-stochastic Block Coordinate Descent Hard Thresholding Pursuit (ASBCD-HTP) algorithm is summarized in Algorithm 2 The main difference between ASBCD-HTP and SBCD-HTP is sparse approximate gradients in Ma-- nia et al. 2017 Zhou et al., 2018a). In order to perform fully sparse updates, we use a diagonal matrix D re-weigh the dense fully gradient (W.) The entries of D are the inverse probabilities of the corresponding coordinates belonging to uniformly sampled support T; of sample iç. Let P., be the projection matrix for the support Ti,, we can get D,, since D,, = P., D. Then we can find that E.,,D,,VE VF ( VFF
In this setting, we can compute the full gradient VF(w) also in a parallel way. order to reduce thread interference and fully utilize the sparsity of datasets, we restrict the sparse gradient Vyy( Vn((ū]r; to the intersection set of S and Ti, and obtain Vsg([w)r, Specifically, each thread of ASBCD-HTP computes sparse approximate gradient independently and then atomically write this gradient to the shared variable w'. Note that Sparse variant of SBCD- HTP (S'BCD-HTP) can be viewed as the single-thread version of ASBCD-HTP, which has linear convergence and the same oracle complexity as ASBCD-HTP. The detailed description and analysis of BCDD-HTP is listed in Section Next we give the main theoretical result of ASBCD-HTP.

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Asynchronous Sparse SBCD-HTP (ASBCD-HTP)
Input: The number of outer-loops R, number of inner-loops step size 1), sparsity level s. Initialize: T
1: for 0, R do w" G supp w and VF(ū)=
2: wh
= - Vf. (T);
//computed in parallel
3: t=0; U: //inner loop counter
4: compute the while loop in parallel
5: while 1 m do
6: Randomly sample from [n] uniformly, and randomly sample ji from [k] uniformly;
7:
T, suppoort of sample às and = t t-1;; 1; //atomic increase counter t
8:
S= G [ū] ;= inconsistent read of shared variable [ū"]] [ū"]T., Veg(( [1) Vsli ([w)n,) )- Vsli, ([w)x,,) + D., V Fw)); w s.,, Isn,, VV /latomic write
9:
10:
11: end while
HT s);
13: end for
Output: R
Theorem Suppose F F(w) is P3 -strongly convex and each function (:w) is p -strongly smooth with parameter 28 s" Let Kig oh and the sparsity level 2 ((Rzs*). We assume that 120kg,, the number of blocks k 10 and (iee, the linear speedup condition). Then for the sporsity-constraiee problem 77. the gradient oracle and hard thresholding complexities of Algorithm 2 are
Ps
the step size 17
the number of inner-loops 60pt'
S min 5//3 2kgg
280
v
O ((n ks/k)log(1// log(1/e)) and O (log(1/e)),
where denotes the maximum number of concurrent threads (Mania al. 2017 and A max Pý. which is a indicator to measure the sparsity of datasets (Leblond et al. 2017).
Theorem 2 jimplie that ASBCD-HTP BCD-HTTP can still obtain similar gradient oracle com- plexity and hard thresholding complexity SBCD-HTP while obtaining linear speedup ratio. Compared with ASVRG-HT et al. 2016a), ASBCD-HTP has a much lower gradient complexity, i.e. O((r+~ x log !) for ASBCD-HTP complexity, ASBCD-HTP Kg times lower than ASVRG-HT, which significant improvement in the asynchronous setting. Since ASVRG-HT has to compute hard thresholding operations at each inner-loop. the practical performance may be worse, especially for high-dimensional data. We also show this improvement by empirical evaluations.
(((++ag)) log !) for ASVRG-HT. For hard thresholding
EXPERIMENTS
In this section, we evaluate the performance of SBCD-HTP, S'BCD-HTP and ASBCD-HTT for solving sparse linear regression and sparse logistic regression real-worid datasets. All the dense algorithms were implemented in MATLAB, while the sparse and asynchronous algorithms were implemented in C++ and executed through MATLAB interface for fair comparison. We also test the performance for face recognition tasks. The detailed information is described in Section F Since there is no ground truth on real-world datasets, we run all these baselines sufficiently long until I|w"" - - ||/||=""] < 10 and then we use the minimum F(w") as the approximate optimal value F* for sub-optimality estimation our experimental results Zhou al. (2018b).
6.1 DENSE ALGORITHMS
We ran the experiments of all the dense algorithms on a PC with an Intel i7-7700 CPU and 32GB RAM. We compare SBCD-HTT with several state-of-the-art conssity algorithms. in- cluding FG-HT (Yuan et al. 2014). SG-HT (Nguyen et al.] 2017). SVRG-HT (Li et al.) (0166), ASBCDHT (Chen & Gu 2016) and FNHTP (Chen & Gu 2017). The detailed descriptions of the

---

Under review as a conference paper at ICLR 2020
L/0 GLD
Cr matt
Los Los
SE-T
SG
9
SP-5ECC-11 177
CPU
Sumber Clecciv
CEUTIme
news20
(b) revi-train
Figure I: Comparison of all the hard thresholding algorithms for solving sparse logistic regression problems. In each plot, the vertical axis shows the objective value minus the minimum, and the horizontal axis is the number of effective passes over data (left) or running time (seconds, right).
SG-TT
G- 564f
2541 70077
SRRAT
120 CPU Time
Sunae thchce Pasces
Sunber
Pasces
CPU Time 31
news20
(b) rev I-vi-train
Figure 2: Comparison of all the hard thresholding algorithms for solving sparse linear regression problems.
algorithms and datasets are provided in Section F We set the sparsity level s 200 for real-word datasets. For the number of inner-loops, we set 2n for SBCD-HTP and ASBCDHT, m for SVRG-HT as suggested in (Li al. 2016b] Chen & Gu 2016) and 1000 (sparse linear regres- sion)/3000 (sparse logistic regression) for FNHTP. We also set the batch-size of FNHTP to and that of ASBCDHT and SBCD-HTP to 5. For the block coordinate descent methods, we set the number of coordinate blocks & to 10. All the algorithms are tuned to their best performance.
We report the performance of all the algorithms in terms of both effective passes and CPU time. More experimental results presented in Section[F) Figures and show that for both sparse linear regression and sparse logistic regression problems, our algorithm converges significantly faster than the baseline algorithms in terms of both effective passes and CPU time. The main reason is that use all the information of gradients, while the related algorithms use less information caused by too frequent and premature hard thresholding operation in each inner-loop.
6.2 ASYNCHRONOUS ALGORITHMS
We ran the experiments of all the asynchronous algorithms PC with an Intel Xeon(R) Gold 5120 CPU and 64GB RAM. We compare our sparse and asynchronous algorithms with several state- of-the-art algorithms, including ASG-HT, ASVRG-HT and A SBCD-HT (asynchronous variant of ABSCDHT). For the algorithms, we set the number of threads to 20.
We only report the performance of all the algorithms in terms of CPU time since the performance in terms of effective passes is similar to the dense case. More experimental results are reported in Section F Figure shows that ASBCD-HTP and S*BCD-HTP significantly outperform than other algorithms. Moreover, ASBCD-HTP has a faster convergence performance than BCCCD- be- cause of asynchronous parallel acceleration. There are three main reasons for the advantages of our ASBCD-HTP: a) We get the set S from the support set of snapshot point 인 and Gj. In this way, the coordinate of the support set which appears as the possible optimal solution can be updated, and thus reducing the error caused by randomness. b) Because we put the hard thresholding operation in each outer-loop, the computation cost per thread of our algorithm at each inner-loop is less, while each thread of the baseline algorithms has a hard thresholding operation, which is expensive espe- cially for high-dimensional datasets. c) Our algorithm updates w" with all information of gradients, while the baseline algorithms update w" with less information caused by too frequent and premature hard thresholding operation in each inner-loop. We also evaluate the improvement of asynchronous parallel by running the same passes with different numbers of threads. We calculate the speed-up
8

---

Under review as a conference paper at ICLR 2020
Parco
SAttber ICECOmm
(a) real-sim
(b) news20
(c) rcv -train
(d) rov 1-test
Figure 3: Comparison of ASG-HT, ASVRG-HT, ABBCCD-H, BCBCD-HT and ASBCD-HIE D-HP for solving
sparse logistic regression problems. The four asynchronous parallel algorithms (i.c., ASG-HT, ASVRG-HT, A ABSCCD-T and ASBCD-HTP) run on threads.
10 Mumber Trrwaaee
CRU Time
CPU Tree K0
Nunder STTAweEE
(a) -eest
(b) real-sim
Figure 4: Speedup evaluation revi-test and real-sim. Left: Evaluation of objective function gap in terms of CPU time for ASBCD-HTP with different threads. Right: Speedup ratio with respect the number of threads.
ratio based on the rumning time of a single thread. From Figure 4 we can see that our ASBCD-HTP accelerated by nearly linear ratio.
CONCLUSION
In this paper, we proposed an efficient semi-stochastic block coordinate descent hard thresholding pursuit (SBCD-HTP) method for sparse representation learning. We proved that SBCD-HTP attains the gradient oracle complexity of O((n + (= log( and the hard thresholding complexity of (log(())) respectively, which an improvement over the existing algorithms. Moreover, we also presented the sparse and asynchronous parallel variants of SBCD-HTP. As far we know, algorithms are the first to use the full information gradient to update. This an improvement on sparse representation learning because be easily extended to other sparse learning algorithms.
REFERENCES
Z. Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. JMLR, 18 (221):1-51, 2018.
Sohail Bahmani, Bhiksha Raj, and Petros T. Boufounos. Greedy sparsity-constrained optimization. JMLR, 8411, 2013.
Thomas Blumensath and Mike E Davies. Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal., 2763):66--274 2009.
Patrick Breheny and Jian Huang. Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection. The annals of applied statistics, 5(1):232, 2011.
Peter Bühlmann and Sara Van De Geer. Statistics for high-dimensional data: methods, theory and applications. Springer Science & Business Media, 2011.
Jinghui Chen and Quanquan Gu. Accelerated stochastic block coordinate gradient descent for spar- sity constrained nonconvex optimization. In UAI, pp. 132-141, 2016.
Jinghui Chen and Quanquan Gu. Fast Newton hard thresholding pursuit for sparsity constrained nonconvex optimization. In SIGKDD, pp. 757-766, 2017.

---

Under review as a conference paper at ICLR 2020
Cong D Dang and Guanghui Lan. Stochastic block mirror descent methods for nonsmooth and stochastic optimization. SIAM Journal on Optimization, 25(2):856 1816,8888222 2015.
A. Defazio. A simple practical accelerated method for finite sums. NIPS, pp. 676-684, 2016.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances neural information processing systems, pp. 1646-1654, 2014.
Simon Foucart. Hard thresholding pursuit: An algorithm for compressive sensing. SIAM J. Numer. Anal. 4966))2533-26633 2011.
Jerome Friedman, Trevor Hastie, Holger Höfling, Robert Tibshirani, et al. Pathwise coordinate optimization. The annals of applied statistics, 1(2):002-322, 2007.
Hongchang Gao and Heng Huang. Stochastic second-order method for large-scale nonconvex sparse learning models. ICCA, pp. 2128-2134, 2018.
Athinodoros S. Georghiades, Peter N. Belhumeur, and David J. Kriegman. From few to many: Illumination cone models for face recognition under variable lighting and pose. IEEE Trans. Pattern Anal. Mach. Intell., 23:643-660. 2001.
Robert Hannah, Fei Feng, and Wotao Yin. A2bed: Asynchronous acceleration with optimal com- plexity. 2018.
Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high- dimensional m-estimation. NIPS, pp. 685-693, 2014.
Ric Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, pp. 315-323, 2013.
Jakub Konečný, Jie Liu, Peter Richtárik, and Martin Takáč. Mini-batch semi-stochastic gradient descent in the proximal setting. IEEE Journal of Selected Topics in Signal Processing. 10(2): 242 255, 2015.
Jakub Konečný, Zheng Qu, and Peter Richtárik. Semi-stochastic coordinate descent. optimization Methods and Software, 32(5):993-1055, 2017.
Ming-Jun Lai, Yangyang Xu, and Wotao Yin. Improved iteratively reweighted least squares for unconstrained smoothed \ell.q minimization. SIAM Journal Numerical Analysis, 51(2):927- 957, 2013.
Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien. ASAGA: asynchronous parallel SAGA. AISTATS, pp. 46-54, 2017.
Xingguo Li, Raman Arora, Han Liu, Jarvis Haupt, and Tuo Zhao. Nonconvex sparse learning via stochastic optimization with progressive variance reduction. arXiv preprint arXiv:1605.0271,, 2016a.
Xingguo Li, Tuo Zhao, Raman Arora, Han Liu, and Jarvis Haupt. Stochastic variance reduced optimization for nonconvex sparse learning. In ICML., pp. 917-925, 2016b.
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM J. Optim., 27(4):2202-222) 2017.
Sahand Negahban, Bin Yu, Martin Wainwright, and Pradeep K Ravikumar. A unified framework for high- high-dimensional analysis m-estimmaors with decomposable regularizers. In NIPS, pp. 1348 1348-1356, 2009.
Yurii Nesterov. Introductory Lectures Convex Optimization A Basic Course, volume 87 of Applied Optimization. Springer, 2004.
Nam Nguyen, Deanna Needell, and Tina Woolf. Linear convergence stochastic iterative greedy algorithms with sparse constraints. IEFE T. Inform. Theory, (3(11):6869-688) 2017.
10

---

Under review as a conference paper at ICLR 2020
Yagyensh Chandra Pati, Ramin Rezaiifar, and Perinkulam Sambamurthy Krishnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proc. Conf. Signals, Systems and Computers, pp. 40-44, 1993.
Angelika Rohde, Alexandre Tsybakov, et al. Estimation of high-dimensional low-rank matrices. Ann. Statist., 39(2)8877-30, 2011.
Nicolas Le Roux, Mark W. Schmidt, and Francis R. Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In NIPS, pp- 2672-2680, 2012.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83-112, 2017.
Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, I4(Feb):567-59, 2013.
Fanhua Shang, Kaiwen Zhou, James Cheng, Ivor W. Tsang, Lijun Zhang, and Dacheng Tao. VR-SGD: A simple stochastic variance reduction method for machine learning. CoRR, ab- s/1 1/1802.0993,, 2018.
Jie Shen and Ping Li. A tight bound of hard thresholding. JMLR, 18(1):7600-7691 2017.
Sara A Van de Geer al. High-dimensional generalized linear models and the lasso. Ann. Statist,, 36(2):614-64,, 2008.
Huahua Wang and Arindam Banerjee. Randomized block coordinate descent for online and stochas- tic optimization. CoRR, abs/1407.0107, 2014.
John Wright, Allen Y Yang, Arvind Ganesh, Shankar Sastry, and Yi Ma. Robust face recognition via sparse representation. IEEE transactions on pattern analysis and machine intelligence. 31(2): 210-227, 2008
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduc- tion. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
Yangyang Xu and Wotao Yin. Block stochastic gradient iteration for convex and nonconvex opti- mization. SIAM Journal on Optimization, 25(3):1686-1711 17166 2015.
Xiaotong Yuan, Ping Li, and Tong Zhang. Gradient hard thresholding pursuit for sparsity- constrained optimization. In ICML, pp. 127-135, 2014.
Aston Zhang and Quanquan Gu. Accelerated stochastic block coordinate descent with optimal sampling. In Proceedings of the 22nd ACM SIGKDI) International Conference Knowledge Discovery and Data Mining, pp. 2035-2044. ACM, 2016.
Cun-Hui Zhang et al. Nearly unbiased variable selection under minimax concave penalty. Ann. Statist, (8(2)88894-9999 942, 2010.
Tuo Zhao, Mo Yu, Yiming Wang, Raman Arora, and Han Liu. Accelerated block coordinate descent method. In NIPS, pp. 3329-3337, 2014.
randomized
Shuai Zheng and James T. Kwok. Fast-and-light stochastic ADMM. In Proceedings of the Twenty- Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pp. 2407-2613, 2016.
Baojian Zhou, Feng Chen, and Yiming Ying. Stochastic iterative hard thresholding for graph- structured sparsity optimization. In ICML, pp. 7563-7573, 2019.
Kaiwen Zhou, Fanhua Shang, and James Cheng. A simple stochastic variance reduced algorithm with fast convergence rates. In ICML, pp. 5980-5989, 2018a.
Pan Zhou, Xiaotong Yuan, and Jiashi Feng. Efficient stochastic gradient hard thresholding. In NewrIPS, pp. 1988-1997, 2018b.
11

---

Under review as a conference paper at ICLR 2020
APPENDIX
A KEY LEMMAS
Lemma ([Jain al. 2014) For any index set I, any R and HT(,,)) : I2d Ie be the hard thresholding operator, which keeps the largest s entries (in magnitude) and sets the other entries equal to zero. Then for any w" IR.' such that I| llo S s", we have
17
(T, 8) wol1 -
1 11
Lemma 2 ((Li et al. 2016b) Let w² E TRd be the optimal sparse vector such that ||w* S s and (T) R Rdth be the hard thresholding operator, which keeps the largest entries (in magnitude) and sets the other entries equal to zero. Given > s" for any vector w E IRd, we have
2/8* Vs M|w w w=113
|H w0 S
Lemma (Nesterov)) 2004) For any given vector w. w RR,, suppose F(.) also satisfies RSC and RSS conditions, then the following inequality holds
[VF(w) - VF(ww)) - (F)(F(w) - F(w') + (VF(w'), w' - w)]-
f;(w) is p -strongly smooth with parameter 2s + s" I supp(w") supp((e") U Uuupp("" (1))), [B] is the batch size. For any w E Rd and the sample in E B, denote Vi, =
Lemma 4 Suppose F(w) PT -stonngl convex and each function fachfunction
VzSi (w0 ( -))(()((())) V ((w"((w)
we have
E
n
B
E VIl(ww) - Vzli(w") VzP('""))+++("') VzF(w')ll
B
B
LEB
Proof.
See Section
B.1 for the proof of Lemma
Lemma 5 Suppose F(w) is Pz -strongly convex and each function f((w) is P -troongyy smooth
with parameter 3 2s + 8* Let w² Rd be the optimal sparse vector with ||o*|lo s" I = supp(w") J supp((")) U supp("" ()" size. For any w², E Id and the sample is. denote Vsg(w") [e Enes Vssf,ww") (
1 is uniform constant factor, and [B] is the batch
VsF(W), then can bound BE] Vssz
(w0)l as follows:
1 k
n [
B|Vssr(w''11
< (165p (1+
[E[F((')
+ +1
B (n
π B
165p
[B -1 F(F F(w")])
Proof. See Section B.2 for the detailed proof of Lemma
Lemma 6 Suppose F(w) is P7 -strongly convex and each function fi(w) is -t-sronngyy smooth with parameter $ 2s + s*. Let w* Rd be the optimal sparse vector with ||w"|lo S s*. supp(u")Usuppp( (w" (usupp("*+1)) 5> 1 is a uniform constant factor, and Dm maxx==1.... ps
For any w², t E &dd and the sample i,, denote Vsg(w*) = Vsfi,ww) (s)a, + Dr, F(T) can bound (Vsgz(w")] follows:
El [Sgx(w"))
< (125p (F(w') F(w"(()))) (3+ - 1))
k
+ +248pp + 486p (D 1))[F()) (F F(w"))),
where pj is the probability that dimension j belonging to the support set of randomly sampling sample it.
12

---

Under review as a conference paper at ICLR 2020
Proof. See Section B.3 for the proof of Lemma 6
This lemma is different from other variance reduced results for sparsity-constrainn problem (Mania
et al. 2017 Johnson & Zhang 2013; Chen & Gul 2016; Shang al. 2018)). Since this variance
reduced approximate gradients introduce an approximate full gradient to make fully sparse update in cardinality constraint problem.
B PROOFS OF KEY LEMMAS
In this section, we prove three key lemmas.
B.1
PROOF OF LEMMA 4
Proof.
Let Vi,
(VIJi, (w²)
- VzF(w")). We have
1 Σ
1
E
U/c
E0
V/ VE
B
E
Σ
Via V4 +
E||pi|1
B
[B]
B
1/3 vy +
E B1pggl
(11)
1
1)
[
[3]
[18]
1
B|
E
2
+
E||u,|
[
1)
BB
1)
[B
n
[
E 14
B (n
This proof is similar to that of (Zheng & Kwok 2016).
B.2 PROOF OF LEMMA
Proof. It is obvious that the stochastic variance reduced gradient satisfies
1 -(Vi,tt')-VV... + VF(w).
(12)
B
Thus, Vg(w") is unbiased estimator of the full gradient VF(w"). Now, bound E Vzz(wii (w*)
For any E (1,2,-.. .nI, we define the following function
h (ww))= = f(w) f((w*) - (V.,"="), w - w²)
(13)
is easy to find that Vh;(w*) = 0, which implies that h,ww)) = min hw(w). For any vector w, have
0 = h,ww)) < min h, (w vVz((())
< min minh, (w(w)) 77 (w), Vzh((w)) + T²p=
|zh((w)]|
2
min (w.) - 7/ Vzh, (z) + n²p=
(14)
[Vzht(w]||
2
= =h((w
[w),(w))|
2p
where the second inequality follows from the RSS condition, and the second equality holds due to the fact that (Vha(w), Vzhx(w)) [1])) and the last equality holds due to the fact that
n Ps
minimizes the function. Then, we have
VzJi(w)- Vzf((w')] < 1 fi(w") (Vzfi(w"), w²))-
(15)
13

---

Under review as a conference paper at ICLR 2020
Since the sampling is chosen uniformly from {1,2, ,n), we have
El[Vif((w) VIJi(w))] )1
=F] - VIf(w")]
VIZi(w)) - VIIl(w")|l
(16)
- 2p [F(w) - =(w") - (VzF(w"), w=)l
< 2nz [F(w) - F (w=) + (VTF((" " w')l
< 46p; [F(w) F)
where the last inequality follows from the restricted strong convexity of F(w). And we use simple underlying consensus that there must exist uniform factor > 1 which makes the following inequality true:
((F(w) F(w")) 2 (Vz)(""), w=\l= +
P3 2
||0 w²1
This property is called the extended restricted strong convexity used in the following proof. There- fore, we have
1
E V
Vyg(w")|1
(Vzli(w") Vzlii VFF(w)
B
&EB
E
VI'fi(("') VZF(W*)) Vzff((w") + FzF(w*)
EE
+ +V (w=* VTF(w") V=F(w")
1
Vzfa(w) VzF(w) ( + VIF(w")
B
iE8
< 4E
Vifi (w") - VZF(w')) + V F (w*)
B
EB
+ 4E
VzF() Vzla + V F(ww)
B
1
(17)
+
V (w')
1
4
E
( VzF(w') - Vzf((w)) v>F(=*)|
B
+ B
V VzF(w) Vzfi(w)) + V (1"
1)
+ 4E
Vz (w))
Vz
+
B
< (4 +
13
[
1
+ 4
71
[
VTJ. - Vzfi(w")11
13 1)
- [B]
< 1168p (1 +
B[F((w) - + +4
[B
n B
+ 168
[ [[F( F[ww"]
where the first inequality follows from ||a + b + c S equality follows from Lemma the second inequality follows from E| Ex/ <
the third and (16)
14

---

Under review as a conference paper at ICLR 2020
and the last inequality follows from
16 Due to the fact that B| Vser (oer(w")1l <
where I = supp(w") w²) U supp( (*+
U supp( w") and = Gz. U suppl ) we have
[3]
B [sgr(w'))1 = (165p
]B(F(u²) F(w")) + +
k.
(B 1)
(18)
n [
+ 168p
| [n B[F( F(w"))),
where k is the number of blocks. Note that we take expectation with respect to randomized block in the above equation. This completes the proof.
B.3 PROOF OF LEMMA 6
Proof. By the definition Vg(w") = Vi, V VF(w), we have E(D,, VF(#) Therefore, Vg(w") is an unbiased estimator of Vf(w").
VF( (6)
Based on 16
we have the following result:
E
V VVg(w")11
F|| fi, (w') VzJi, (w) D, VzF(1)| (2
3 VIft. m VIfa, (w VzF(w) VIF(w")
+ VzF(w) Di, VI (i) 12
+ 3E V (w') Vzzi,
- 6E VI/i, VIfa, Vz V2F(w*)11
Vz) + 6E Vz - DVz
(19)
+ 3E VzJa, Vzíi, (w )11
VzF
< [(("') (3+ 12 - 1)) VzZ
+ +240pp + 480p (D2 ())
where the first inequality follows from b /
the second inequality
follows from || +
Bllww] with [IV ( VzJ4 (w") }] = VzF(w) VwF(w"), and EJ V VzJa 1 S
b||
< [|] 2||b 2 the third inequality follows from E||w Eurl2² < E
45p [F(w") F(w*) } with > which also satisfied for with
Since Dm
max. p.
we bound the VIF(w) DV.F(vi term as follows:
I1D 1) F (T)
Σ
P=1 24 |)
S (D2 F
(20)
(D2 1) VzF(w") + VzF(w")]1
< 2(D2 =) Vzf((w "=(( + 1)] Vz"")(
I 86p (D2 - F) F(w")) - F
Due to the fact that Bl[Vssr(w")]] )12 < [BI[V 112 we have
1 (128p [F(w") F(u (3 12 1))))=
E (wgr(w")))
k
(21)
+ +245pp 486p (D ()) F(w")))
where & is the number of blocks. Note that we take expectation with respect to randomized block in the above equation. This completes the proof.
C PROOFS OF THEOREM I AND COROLLARIES I AND 2
In this section, we give the detailed proofs of Theorem and Corollaries and 2 which can guar- antee the convergence properties of our SBCD-HTP.
15

---

Under review as a conference paper at ICLR 2020
C.I PROOF OF THEOREM 1
Proof. In this subsection, we provide the proof of Theorem 1. Let w = w² 11 Vsgx(w>) and I = "U"+"'"*+,, where I' supp(w"). I' supp("") (") and I++1 supp( 1oop(w++1) +1] Conditioning on w', we have the following expectation
El 2| - w=
Ellw" "/ssr((') - 11
Ellw" - w²1l + " Vsyr (1²)
2n/w² - w², VVsgI
27
S El|lw* - w0 + of 2 V S/l (w'') )12+
+ 1.
(w0" w VzF(w'))
2nd0
S E||w" w²11 11 + 7 E
VS9I (w)))1
(F(w") F(w*)]
h
1
[
(22)
S Ell
112 + K
(166p 17 (1+
[B 1) ]B[F(w() - F[w")]
+ 166p .72 11 [B]
F(w")] (n6(F(ww) F(w + 4n²
B(F(w) (
[[V>F("")1I
[B - 1)
k
1
n |B] ) 2no (B)))B(F(())) F(w")]
= =E]l/w - 112 + k
(1168p 1/ (1+
[B - 1) F + 4n² k
n [B]
+ 1666p
[VzF(w"))I
[B -
where the first inequality follows from the expectation with respect to randomized block, the second inequality follows from our extended restricted strong convexity in the proof of Lemma [ and the third inequality holds by Lemma 5 Notice that w w -- Summing (22 over
0, m 1 and taking expectation with respect to all randomness, we have
[B]
E E|I" 1T
w0 11 < El W -- w1 + ((168p) 17 mmmm1 + 1B - 1) 2mnd) - F(w")
k
n |
4n m
+ 165p n2m
B[F(w"
F ((w))) }) +
FzF((")II
BB (n 1)
k
(23)
Notice that the convergence property used here is similar to the proofs of the convergence results for many hard thresholding algorithms (Chen & Gu 2016
2017
Li al. 2016b).
Moreover, obtain
n [B]
E El/w w²1
El - w01 + k
(116pp mm
) 2mmn6)BB(((( - F(w"))
[ - 1)
n B
[[ F(w"))) + 4 m
+ 166p 12
E F
V>F((>>>|>
|B (m 1)
k
n |B|
= El w0 1|2 + k
((166p n m11+
B - 1) 2mn B(F - F(w"))
n B
-(165p² mm +
[F F(w
| (n
+ +168p 1/ m
n
[
[E| [[[((rr-1) - F(w)))) + 40pm
[VzF(w")II
|B (n 1)
h
n |B|
S El|10" -1 w0 112 + ((168p5 1 mm(11 (1
2mmn6)E(F((")) - F (w*)
[B - 1)
- -(166p; + 17 mm2 +
n
1
- 2mmo7)
P (d - s)
Ellw - =11
B
(n
20(d 8*)
B
(1 - F (w=")) + 4rj²m
+160p + 2m
E
|VF((">))
B (n
h
(24)
16

---

Under review as a conference paper at ICLR 2020
where the second inequality holds due to the fact that we have the following results: When F( F(w" > 0, by using Lemma 3 on wm and w", we have
1 VF(W") VF(W"))
(F(W""), wh ) S F F(w")) F(w"))
2p F(
(25)
(1 (1-o)[F(0))
where the last inequality holds due to the fact that we assume that there exists a constant factoro > 0 making this inequality true. Then by using the RSS condition, we have
F( F( S ((w") n" w")) +
w
"
112
(26)
P3 2
s (1 - FF - F(w"))
-r"
After simplification, we have F(ū") - F(wm) -
e
l0"
u='ll 11. Using Lemma
we have
2a
|/|
1000 w 11= 11Hle(m")) - " 1|? v
I 5r 1
w w=1
(27)
and
F ((w") - F(w 1 P5 s)
1|000 w w=
(28)
20 - s*)
When F( F) < O, we can omit - (165 1)² mm1 + (8((m-
n- 2mmj) F (wm)
directly since 165p m2mm(++
a-|B] [B((n-1) ) 2m1o is less than zero. Because this is the simple situation,
we only analyze the complex one in our whole proof. Therefore, we have the following inequality:
1 (1 1160p5 mmmm1 +
n |
(d (d (0) 5) 2mnrjo)
P 20 5*)
)Bl| -w=""""""" w=1
b
(n
< E| - w=112+
(1168p 172 mm m1 +
n1
|3|
2 - F(w")] (29)
k
[B - 1)
n2 [B]
F(w") + 4n7²m
+ 166p y/²11
B[F(
B n
Since T" = Hr (w ), i.e., w" is the best s-sparse approximation wm then we have the following result due to Lemma
8/8"
w" (1
u w=11 112
(30)
V
Let a = 1
2 Va
and by combining
29 and 30 we have
1 (1 + (160p (1
B
P (d 8)
2mnnn
BB -w""-ww"" 1=11
b
(n
2a (d 8*
11 - |B]
< <aEl@i
- 1=1
(160p5 mmm +
2mm1d (B(F)))B(FFTTT F(w")]
13
n [ + 166 nmm
| V 2
B[F -1) ((f'-"')F(""")
(1)
B3 n
k
<
20 B ( -
F(w*) 1
a k
(165 1) +
n
|B]
2m F(w"))
2nm
|B 1)
P3
n B
E BiF(w - -0w=F)()) + 2
+ 168p 17
[V
B -
k
(31)
where the last inequality follows from the RSC condition and the definition of Σ, i.c. ī = Supp(HT(VVF(en) 2s)) U supp(w").
17

---

Under review as a conference paper at ICLR 2020
Through proper simplification, have the following result:
B
(210176 166p3 11 mm
+
))B[F((") - F(w")]
B [n
(32)
2a + 168 17² ma
B
- + 4n
[VF(w=)]
B
B
P3
where the first term of the LHS of (31 is omitted due to the fact that the coefficient of [B] " w 1|
larger than zero, when 8p mn) (R-()=))) ma 6p (d-s)
n-1B
ak(d-s")
0, which be naturally have
satisfied under our parameter setting with k3s". Following from
32
2n
E[F(w") F(w")) S 3E[F(W (1 F(w")] "I+ + 8(1 w)
(33)
8p3 x(n-1B)) [-][1= and 8p 1 n- 11] By applying (33)
where ( Tymp, 6(1-w)
recursively,
then we have the following desired bound with 3 s 1/z <
B[F(W") - F[w"]] ( TEF((T)) - F(w" ) + 1
| [+
(34)
This completes the proof.
C.2 PROOF OF COROLLARY
Proof. We then give the proof for the statistical estimation analysis. Following from the RSC condition of F()), we have
Pz w=1
F(w") < F(w") + FV((")), w² ww)
(35)
2
Let ø = (F) 1T F(w*)) -- V (ww')) [w) Combining (34p and
35
we have
E F < F(w")
F( (VF(W"), w w
PJ
10
w
11
(36)
2
Using the duality of norms, we have w= ),
F ("""
w²) VVF I Ex w"Ih S v
1l w" "1-
(37)
Combining (36). 37 and |Eu|| < E| have
Pa (E 1 w=1l)² vs
FFww")
w=Il
(38)
2
Let E| w= From the above inequality, we solve the following quadratic function with
respect to a,
Ps 63 V V Iloo -
(39)
which yields the bound
2( )( (FFF)F(()))) - F(w*)]
2n
2 2/
V (w
w²1 11 I
V 1 [VF(w=)]
P3
(40)
2( rr ( (F F(w*))
( 2
2n
V
V=
P3
Pg
I-
This completes the proof.
18

---

Under review as a conference paper at ICLR 2020
C.3
BOUND 3 <
Now we show that we can guarantee that 3 < by providing the appropriate choices of constants with 7,, and m used in the theorem. More specifically, let I have
Cs
and [B] = 1, then we
P3
48
8p ( [3]) [3 w) 1)
8C3(n [B])
1
(41)
[I 1) 8C3
n
B
If 17 2 O with C2 $ C3. then we have
Pj
k
(42)
nomp, (1 w)
26mC2 3kms
we guarantee 48m02 6kx2
S 4- then we have
6kKz Catig.
m 2
(43)
8C2
60 C3 1 C4 1800, k 10 and 2, then we have 3 < 2- Note that the convergence rate 3 does not include a, therefore, the required value of k comes from the restricted constraint of the coefficient of ||"" w0ll which implys that s ((xzs").
where 8 1. If we choose C2
C.4 PROOF OF COROLLARY Proof.
BFF("")~ F(w") sct 1-w VVF(("")
(44)
Let @1. 02. be a non-negative sequence of random variables which is defined as
{ F((T)) - F(w") - 1V
27
= max
(45)
For fixed e >> 0, it follows from (34 and the Markov inequality,
P(e. 20) Eer
(4)"((("") F(w))]
(46)
For given Ç E (0, 1), let the right side of 46) be not greater than Ç. which requires
F(w") F(w*)
loga
(47)
Ec
Therefore, the result in (44) holds with probability least 1- Ç. Thus, we need (log(E)) outer iterations to get i" satisfyıng (44). Since within each outer-iteration, we need to calculate a full gradient and m stochastic variance reduced gradients with mini-batei size [B], the overall oracle A
complexity is O((n + x=(B]] log 4). Note that in high-dimensional region, the effect of support of snapshot point can be ignored. On the other hand, we only perform hard thresholding operation each outer iteration. Then we have
loga -
Log(? ()
(1lgg(2))
(48)
log(2)
Thus, the hard thresholding oracle complexity Olog( ()). This completes the proof.
D PROOF OF THEOREM OF SPARSE VARIANT
In this section, we theoretically analyze the convergence properties of our Serial Sparse SBCD-HTP BCD-HDT)
19

---

Under review as a conference paper at ICLR 2020
Algorithm Serial Sparse SBCD-HTP (SCBCD-HTP)
Input: number of outer-loops R, number inner-loops m. step size 1,, sparsity level s; Initialize: w"
for 0. 0,1,,.. ..... R
do
2: w0
w²
3: VF(@)
1 Ei= Vf((w);
4:
G = supp(u)) i);;
5:
for = O........ m do
6:
Randomly sample from 1, 2, .,,,,, n uniformly;
7:
Randomly sample je from 1, .,,2....k) uniformly;
8:
T, supportt of sample iz;
9:
S= S=gugj
10:
Vsg([w']T, Vsfi, (lw" Vsfi. V. + Dr, VsF(w);
w(+1 w [Vss((u))).
12: end for
w+11= HT("",s))
14: end for
Output: TR.
D.1 PROOF
Proof. We start with the iterate difference between w²+1 and w". By expanding iterate difference and taking expectation with respect to all randomness, we get
El| w"I 1 Ellw=* 1/ V (w²) w 11
I|wl w 1² 1/² VsgI (w")) 2nylE(V/SII(( (es((VSS"') w² -w²) (49)
I|w² - "² 112 7 V.sII (1))1 1| 2n (VZF(w"), v - -w'),
k
where the last inequality holds by the unbiasedness of the sparse gradient estimator Vgz(w") and the expectation with respect to randomized block. By using the P3 -sroongly convex condition, get the bound for F(w"), wn w²) as follows:
FV w w²) s F(w") F("")
P3 - I|u" w² 1/2 2
(50)
Due to the support set I, we need the extended RSC condition with d > 1, which has been intro- duced in the proof of Lemma 5] Based on this underlying consensus, (V")"""), w" w²).
obtain the bound for
(VZF(w')," - ww" s {(((w"))= F(w")).
(51)
Using Lemma have the following sparse variance gradient bound,
E (/ss((")))'" < (F - +3 12(D", - F)x))>
(52)
+ (245p 486p 1))[P(()) F(w")]),
By combining the above inequalities, we have
1|2 < l/ue* w w011 + + ( 2166
E Iw (+1
[I (wo²) F(w
k
< I|w" w011 w01 2pp - 2768 [F(w') - F(w"))
k
(53)
2012
(12p +24p (D2 - 1)) F(w"))
+ 2 k
(3 + 12(D2, 1)
20

---

Under review as a conference paper at ICLR 2020
where the second inequality holds by Lemma 6 Summing the above inequality over 0,-.. , and taking expectation with respect to all randomness in this epoch, we have
w0 112 2njmm(1 6mpp) [P(w0 F(wx))
w=
112
R
10
k
201j 2 m
(12p
+ 24pp (D - - F(w")]
(54)
k
n'm m
+
(3 + 12( 1))1
Using 28
we obtain
w=11 S Bli --= 21dm (1 6m [P((TT) - F(wo)]
B| 10""
w²1
h
P3 (d - 5)
+ 21pmm(1 6mp
2k:o (d 3*) 111e w=
(55)
2m k
(24pī + 48p D 1))[F((rr-1)) F(w"))
1
(3 + 12 m - 1))
k
Since W" (T ,),, i.e,, then we have following result,
w" is the best 8-sparse approximation of w" and due to Lemma
21dam
p (d - 8)
(1 6n [F((")) F(w")] } + (1 2nōm(1 6m
)1("" =w"112
k
2ko (d s*)
< <BEllW0 wt 11 mn
(24p 48p (D 1))(F(( - F(w")]
k
(3+ 12(2 1))l 12²ma
(56)
5np 2m
5 [(("-1)) F(w"))
(24p + 48p5 (D? 1))(F((-11) [Fww)]
P3
k
+ 1/ ma
(3 + 12 1))1 (z1
where a = 1+ 2 and we use P3 strongly convex of F(w) to bound || - w"l inequality. Through proper simplification, can obtain
in the last
---a-1
2nadm (1 61p (FF(") F(w")]
2a
(24p + 48pp (D 1))8r)mma [F( - F(w")]
(57)
P3
2 mm
(3 12(D,, 1))
k
where the second term of LHS of (56) is omitted due to the fact that the coefficient of EE| w" 1|2 larger than zero, when 6p mn)² my + ka(d=s") > 0, which can be naturally satisfied under our 5n. (d-s)
parameter setting with s 2 K Therefore, we can obtain the following result,
2ka (24 + 48(D2 1))dmapp"
ELF(W") F(w*)] s
[F(#0-1)- - F(w")]
2njdm (1-d@m(1-61pp3 61pp²)
(58)
(3 + 12(D2, 1))man?
[VF(w=)]13
2njōm((1 - 6np
21

---

Under review as a conference paper at ICLR 2020
where ī supp(w") U Usup( We define ç
3- 3+12(D2 -000--111 11)
V FF(==))12
28(1 28(1-6p5 n)
In order to obtain linear convergence rate, we have to bound
2kx + (24 48(D) - 1))8mapp 12
k
(12 24(D - 11))
< 1.
27adm(1 6n
(1) 6p 17 j0mp
1- 1-6p3n1
- (59)
we choose 11 5 48D9, then the second term of 33 will be less than 1
2 i.e.,
1-6p "
500D Kig with yj
2' As for the first term, when m Z
50 = and k = 10, we have
D
S 4. Thus, get the linear convergence for our serial sparse SBCD-HTP BC (n- 6of " pmmp HTP).
3 : [ F(w")) + E.
(60)
which means that the total gradient evaluation oracle complexity is O((n + log ?), and the hard thresholding oracle complexity ()) This completes the proof.
E PROOF OF THEOREM 2
this section, we analyze the convergence properties of the proposed Asynchronous Sparse SBCD- HTP (ASBCD-HTP). We first have specify the iterates labeling order used in our asynchronous analysis.
We use "After Read" labeling order (Leblond et al. 2017 in proof, which enjoys simpler analysis but requires the order of randomly sampling step to be an uniform distributed sample. In order give clear proof, adopt the "After Read" labeling order and make the following assumptions:
"After Read" labeling order:
1. Inconsistently read the iterate viy;
Increase iterates counter + and sample random sample 4--1;
3. Compute the update - -n> g
Atomic write update to shared variable coordinately.
The labeling order increases after Step 8 in A and thus the future perturbation not considered the effect of asynchrony in the current step.
Assumption 4
Assumption We assume that uniform distributed samples and the independence of the sample 4e+1 with w,.
Following (Leblond et al. 2017,
explicit the effect of asynchrony follows:
w. w =1 Σ G.Vg((.),
(61)
(t-T))
where wt is the t-th inner iteration solution. In the proof of Theorem we use w' to represent the temporary solution of the t-th iteration for clean representation. And G,, is diagonal matrix with entries in {0,+ +1]. This explicitly defines the coordinate perturbation from the past updates. Here, 7 denotes the maximum number of overlaps between concurrent threads. We also denote A
-l.xx_ Pi, which provides a measure of sparsity following (Leblond et al. 2017).
E.
PROOF
Proof. We analyze our asynchronous algorithm based on the "perturbed iterate analysis" frame- work (Mania et al. 2017) with "After Read" labeling order. By expanding the iterate difference and taking expectation with respect the sample 4,11, get
22

---

Under review as a conference paper at ICLR 2020
Bign |10
w=112 Eis4 1lee 1) V)VSOI(ur) w=1
= 11 w=1 + 17 Vagr [12) + 2n 1w0" - -w", VssI(()))
21
(62)
I llwe w0 112 + r Vsgr (1: (8; (1; +
Binps (w0 Wr: Vgz(w;))
k
+ 2ryB (we w' Vsgr((i)))
where Wi is the "perturbed" iterate with perturbation v and the last inequality follows from the expectation with respect to randomized block. We need to bound the term, 21y(w" Wo Vgr((;)) Since 1 is independent We we can write:
Biesi (w" Uh Vgz((ee) (w" Wi, Bis+s Vgr((.)) (w* Ur, VzF(i))).
(63)
We can use P -stong convexity bound of F(2)) with constant factor 1 as well as squared triangle inequality to get:
-(w: w., VF(()))) S -5(F(())) - F(w*)) P3 100 - w =1
(64)
1
|| w=11 $ 1100 w²11
2 211100 w0ll, (Ila b112 s 2||a|12 1 + 211813).
(65)
(w - w., VzF(w,)) S (((((())) - F Fww))) +
PE 2
liiee w Pz I|w0 w w1?
(66)
Then we make an identical deformation, and we have
MPa 211 E (w= úRF Vgz((.:)) S ?P3 Ei,,, 1110 1=1 + 2k
Ei,,, 1100 - w²11
k
A
(67)
2np5 (F(w))) - F(w")).
k
Putting all logether, we get the initial recursive inequity, written here explicitly:
a 1+1 (1
7P3
)a +1j B Be,,,
Vssr (1::) 112 +
7P3
Ri
1/
r0112
21:
k.
(68)
2115 E²
+ 2n (10g - w' (sgI(()))
k
where a² : B,,,,,11 1/ w" 2 and 6 E., [F F(w*)}
From Lemma in (eblond al. 2017), bound the asynchronous terms || ||1b:="'] w²11 (10 and (w.() as follows.
w
E(ú w., (iSz((0))) =1
EGG, (wg)( (s)z((.)) (ss
(KVVss((t_),ssozz(t.))) Vsg2((.)))
(69)
<1 Σ
E (V
B (s))(
#=(t- +)+
A
H-1
Σ
E [
E
V VsgI(1i))1 (1:))1
2
2
[=(+=T)+
23

---

Under review as a conference paper at ICLR 2020
Ellú
w²133 s
[(G Vsgr((u); G. (syr(
n,u
< 1
Σ
(s Gr V.Vsr(W.)))
(, +,
E [o 1)+
B| (s)r
(=
(+-++)
= = + v (T - 1)+
E VsSz(ww)l1
5 AT)
E (w,)))
(70)
where G. are d x d diagonal matrices whose entries in {0, +1}. Each update in dh is already in w'- this is the case of O. On the contrary, some updates might be late: this is the case of +1. Then by combining (68). (69) and 70.. we get
az+1 S (1
MP= )a + 1 2k
Σ
B (
(1))? - 2178 k el
+ V
Σ
(t(r-)
< (1
MP3
)a + 122C Br [ + u=(t-r)+
Big VSsI((u)) (1w)]
2no6 k
er,
2k
(71)
where C : 1+ VT and C2 = VĀ + 1ig C1. T represents the mawimum number overlaps
between concurrent threads. And A max .d Pj. which is measure of sparsity with 1/n s A S1.. 1.
Using Lemma 6 to bound the sparse variance term, the above inequality becomes
t++1_
S (1
7P3
)a¹ +
r2 k
(F(())(F((tt)
F(w")] + (24 + 48( 1))5p (F()) - F(w*))
2k
C22 (t-T))
2nd (v.))1
+ +33 12 1)) Zz[
Σ
E
e
k
k
< a' 12
2no(1
1o1)
Big V [iz
Et
+)+
+ (24pt + 48p (D'h -1) 8C'n²
122
+ (3+ 12(D 11) 11) k
[V>F(w>)
k
(72)
where ē = ( -(ww)) }}, et = ((.,) - F(w")). Note that we have ã = w = w Summing 72 over f = ..... m - and taking expectation with all randomness in this epoch, we get
a m < a
21jmm
(1 - 6p. mm +
PC k
Σ
E (1
k
u=
(t-
(73)
SmCin² r- + (3 + 12(D - 1)) C1
+ +24pp + +48p (D2 - 1))
VVF((")11
k
k
24

---

Under review as a conference paper at ICLR 2020
where am E 1m u= and a Blllw" == 11? term on the RHS of 73
Then we focus upper bounding the third
Σ
Bl| (ez((w)))
Ell Vir ( S Σ
B BllVVzz(us)]
1=1 u=(b-T)+
t=1 (12pg) ôme + 5m (24p 48p (Di - + m ((x
(74)
Substituting the above incquality into 73 we obtain
a a0 2nôm
5p mnn
k (1 6pp
Ci
(24 48 - 1))( G15
-))
k
Imm
(3 + 1) CC/ + k
(75)
Then we bring
28 into the above incquality, we have
S 27dm
a
(1 6p: TTT'2 + ()) - F(#") - F(W") F(w")]
k
+ p mn
(24 48
k
mm
+
(3 12 m - 1))(C + +Z2)VV
h:
S 0 27dm (1 - 6pppnp((C + Ci)) + 21 - 6p n(CC2 C1))
P p (d 8)
2k (d s*) a
p mu²
+
(24 48 - ()) +C)
k
Imm m
+ (3 + 12(D2, - () + +C2))/22(('"
k
(76)
where the second inequality holds since we use (8) and make proper simplification. Using Lemma we have
(1 - 211mmm - 6p 10t=n + C1)) p p= 8)
2ko - 5r) )a"
20 2-
2andm (1 np:pn((T( + Ci))E"
P3
k
(77)
adp mn?
ad
(24 48 1))((C2 + G))
k
anpm m +
(3 + 12 1))(Ci + +2)1 F(w")| 11
1 w 12, and 7 supp(w") U (F The first term of LHS of is omitted due to the coefficient of ā" is larger than zero, when ka(d-s") > 0, which can be naturally satisfied under our parameter kn. (d=s)
where 1 2
ā"
6p m(rC2 + Cn mn settings with s 2 rgs". Therefore, we obtain the following recursive incquality.
2ka adp
48(Dg, 1))(TC2 C1 -
E
n(7
(78)
m3 -) (VFFF.) [V
+ 20n0m(( - C(
25

---

Under review as a conference paper at ICLR 2020
We assume that the following settings has satisfied with the above constraint and then by choosing 120ng. 17
m
60p;
k = 10. we get
5 75(p% 72 (1 + 2(D - 1))(T(2+())
20 +
5
---- + [Vz
(79)
45(1 TO (TC Ci))
where ç = 1 -1)((+(++(i)
In order to ensure linear speed up. needs to satisfy the 28p n(TC2-C1))
following constraint,
0 75 1 (1 2(D - 1))(((2++()
20
1.
(80)
48(1 (rC2 Ci))
We assume that 37 > D and 6 10. then by simply setting S min
5v 2
2x2
the
VA
above constraint is satisfied with 0 < 0. 0.7538, which implies that the oracle gradient evaluation and hard thresholding oracle complexities are O(n + +)) log 4) and Olog(( {)), respectively. We can
simply infer the statistical estimation result before. Here, will omit this part. This completes the proof.
E.2 DISCUSSION ABOUT SPARSE VARIANCE BOUND
In the dense update case (i.e., Dm = 1), Lemma 6 is very similar to Lemma 5 when [ = 1. In the sparse update case, Lemma 6 highly correlates with the sparsity of datasets (x D ), which could be much loose in some extreme cases. Dm is very large (imaging dataset with some dimensions contain only entry among the samples, SBCD-HTP will be much smaller than that of SBCD-HTP. Our algorithms can still converge to the optimal solution up the statistical error. Actually, still open problem whether can have a tighter variance bound in the sparse update setting that is uncorrelated with Dm
Dm n), the step size of sparse (asynchronous)
F MORE EXPERIMENTAL RESULTS
Table 2: Summary of large-scale and high-dimensional datasets
Datasets
Data
Feature
Density
rev I-train
20,242
47,236
0.16%
revl-test
677,399
47,236
0.15%
real-sim
72,309
20,958
0.024%
news20
19,996
30,000
0.49%
E2006-TFIDF 16,087
80,000
1.54%
F.1 REAL-WORLD DATASETS AND EQUIPMENTS
We summarize the detailed information of all the real-world datasets in Table 2 including revl- train, Itvs- real-sim, news20 and E2006-TFIDE. All these datasets are provided in the LibSVM websitq"] The E2006-TFIDF dataset includes 16,087 training data points and 150,360 features.
https://www. wttp:/wwwwwwwww...oo...ptttt..wt cdu. http:/ttt...uutt////aaaaaa/aeee.
26

---

Under review as a conference paper at ICLR 2020
Instead of using all features, randomly select 80,000 features for training. As for the news20 dataset, we randomly choose 30,000 features for training.
F.2
BASELINE METHODS
We compare our serial dense SBCD-HTP method with the state-of-the-art methods:
Fast Gradient with Hard Thresholding (FG-HT) (Yuan et al. 2014): This method based on standard gradient descent step and combined with hard thresholding to solve sparsity-constraine problems.
Stochastic Gradient with Hard Thresholding (SG-HT) (guyyn et al. 2017 This method combines stochastic gradient descent with hard thresholding for solving large-scale sparsity-constrained problems.
Stochastic Variance Reduced Gradient with Hard Thresholding (SVRG-HT) (Li et al. 2016b): This method incorporates the variance reduction technique in (Johnson & Zhang 2013 into the hard thresholding algorithm improve the efficiency of stochastic optimiza- tion.
Accelerated Stochastic Block Coordinate Gradient Descent with Hard Thresholding (ASBCDHT) (Chen & Gul 2016): Block coordinate descent (BCD) is used for solving upansity-constrannee problems.
Fast Newton Hard Thresholding Pursuit (FNHTP) (Chen Gu 2017): This method tries to iteratively approximate the inverse Hessian matrix and combines a Newton algo- rithm with hard thresholding.
For the proposed Serial Sparse SBCD-HTP BCHHDDHH and Asynchronous sparse parallel SBCD-HTP (ASBCD-HTP) methods, we compare them with the following asynchronous parallel sparsity-consttraned methods:
Asynchronous Accelerated Stochastic Block Coordinate Descent Hard Thresholding (A'SBCD-HT): This algorithm is the asynchronous variant of ASBCDHT by using our parallel framework.
Asynchronous Stochastic Gradient with Hard Thresholding (ASG-HT): This method is an extension of SG-HT from serial dense setting to asynchronous sparse setting.
Asynchronous Stochastic Variance Reduced Gradient Hard Thresholding (ASVRG- HT) (Li et al. 2016a):: This method incorporates multicore structure to compute stochastic variance reduced gradient in a parallel way.
F.3 FACE RECOGNITION DATASETS
Although there are many datasets available for face recognition, we choose a common dataset (i.e. the Extended Yale B datahase (Georghiades al. (00T)). The Extended Yale B database contains 2,414 frontal-face images of 38 people under different controlled lighting conditions (Georghiades) al. 2001). For each individual, we randomly choose 26 images for training and 15 images for lesting.
F.4 EXPERIMENTAL SETUP
For each sparsity algorithm, the sparse level makes great difference to the solution of sparse representation, especially at different noise levels. Therefore, in order to approach the best performance of all these algorithms, we change the sparsity parameter within certain range for each algorithm. Thus, we can make sure that all these algorithms achieve the best recognition rates in the parameter setting. In all settings of the experiments, the images down-sampled to 32x30 32 pixels.
27

---

Figure 6: Mini-batch size in the convergence rate of SBCD-HTP algorithm for sparse logistic regression on Under review as a conference paper at ICLR 2020
Recognition Rate
Recognition Rate
0.6
0.4
SVRGGHT
0.4
ASBCDHT
SBCD-HTP
0.2
SVRG HT
0.2
ASBC DHT
SBCD-HTP
200
400
600
800
0
100
200
300
400
500
600
CPU Time (s)
CPU Time (s)
Yale B
Figure 5: Recognition rates of all the algorithms on the Extended Yale B with diffcrent levels of Gaussian noise:
9 0.3 (left) and 1 0.6 (right).
mini-batch [8|-1
mini-batch [B|-1
mini-batch |-3
mini-batch [8|-3
Log Objective Gap
mini batch [B|=5
Log Objective Gap
mini-batch [B|s
-2
mini-batch [8|77
mini-batch [B|-7
-3
-4
30 -0
-4
10
20
30
200
600
800
1000
Number of Effective Passes
CPU Time
(a) revl-train
revl-train data.
Based on the sparse representation- based classification algorithm (SRC) (Wright et al. 2008). series of processing operations are made to the above dataset. We first rescale the training matrix into [0.1] for the convenience of adding noise, and then add Gaussian noise with zero mean and standard deviation 0. Finally, we normalize the columns of the training matrix to have unit norm. The parameter settings of comparison algorithms for face recognition task are the same as those described in Section
F.5 RESULTS
We first measure the effect of mini-batch size [B] in the convergence of SBCD-HTP rev 1-train, as shown in F It obvious that the large mini-bateh batch size can accelerate the convergence rate and make SBCD-HTP obtain better solution. This result is exactly in line with theoretical analysis. However, when the mini-batch size is relatively large, it will deteriorate the performance of running time. One simply choose the mini-batch size 5 suggested in Figure
28

---

Under review as a conference paper at ICLR 2020
F.6 FACE RECOGNITION TASKS
Then, we compare the performance of some hard thresholding algorithms, including SVRG. HT and ASBCDHT, with SBCD-HTP for solving face recognition tasks the Extended Yale B dataset. As shown in Figure SBCD-HTP can achieve the best performance among these stochastic hard thresholding methods objective function efficiently but also obtain a better representative solution on real applications, which is consistent with our theoretical results as described Section 42 This result also shows that our SBCD-HTP has better generalization accuracy than other hard thresholding algorithms.
short time.
clear that SBCD-HTP can not only optimize the
FG-HT
-G.HT HT
SVRG HT
Log Objectve ap
ASBCOHT
Log Objective Gap
ASBCDHT
FNHTT
13
FNHTP SBCD-HTP
-SBCD-HTP
-6
-8
-10
-10
-12
-14
40
50
60
Number of ffective Passes
CPU Time
(a) E2006-TDIF
1:1
Log Objective Gap
Log Objective
-3
FG-HT
SG-HT
SGGHT
SVRG-HT
SVRG-HT
ASBCDHT
ASBCCHT
FNHTP
SBCD-HTP
SBCD-HTP
10
20
30
40
50
60
200
400
600
800
1000
Number of Effective Passes
CPU Time (s)
(b) real-sim
Figure 7: Comparison of all the algorithms for solving sparse logistic regression problems. In each plot, the
vertical axis shows the objective value minus the minimum, and the horizontal axis is the number of effective
passes over data running time (seconds).
F.7 LINEAR/LOGISTIC REGISTRATION
We show more practical evaluation results for sparse linear regression and sparse logistic regression problems. All hardware environment and parameter settings are the same as in Section 6 For SBCD-HTP, from Figures and we both sparse linear regression and sparse logistic regression, our algorithm converges faster than the baseline algorithms in terms of effective passes and running time. However, find interesting
to the same conclusion
did before, that is in
29

---

Under review as a conference paper at ICLR 2020
result, which is that for the E2006-TFIDF dataset, all the algorithms converge with high precision solutions, so that we have to use some methods to magnify their differences. Of course, our SBCD- HTP has the best performance, but the gap is not that big. We think that this is due to ease with which E2006-TFIDF dataset can be optimized, since this phenomenon does not occur on other datasets.
For BCBCD- and ASBCD-HTTE from Figure 9 our S HTP and ASBCD-HTP far exceed the baseline algorithms terms of running time. Therefore, we can confirmedly obtain the conclu- sion that our Sparse and Asynchronous algorithms outperform the state-of-the-art hard thresholding algorithms for sparse datasets. This is a significant improvement for hard thresholding algorithms to solve sparse learning problems in the high- sigh-dimensional asynchronous setting.
Log Objective Gap
SG-HT
FG-HT
Log Objective Gap
SG-HT
FG-HT
SVRG-HT
SVRG-HT
ASBCDHT
ASBCDHT
-2
SBCD-HTP
SBCD-HTP
50
Number ffective Passes
CPU Time
(a) E2006-TDIFT
Log Objective Gap
-2
Log Objective Gap
FG-HT
SSG-TT
SVRG-HT
FG
ASBCDHT
-SG-HT
FNHTP
SVRG-HT
SBCD-HTP
ASBCDHT FNHTP
SBCD-HTP
10
30
40
50
60
200
400
600
800
1000
1200
Number of ffective P Passes
CPU Time (s)
(b) real-sim
Figure 8: Comparison of all the algorithms for solving sparse linear regression problems.
F.7.1
UPPER BOUND
In order to conduct an experiment on the upper bound of Theorem 1. We first generate some n synthetic matrices X, each row of which is drawn independently from d-dimensional Gaussian distribution with mean and covariance matrix E dd The response vector generated from the model y= Xx" " +c, where w" Rd is the s* -saarse coefficient vector, and need generate the noise e drawn from a multivariate normal distribution N(0, o²1) with o² 0.01. The nonzero the interval [-1, 1). For
entries in wn sampled independently from uniform distribution the experiments, we construct the following synthetic data set: 5000, d = 10000, x 500,
and the diagonal entries of the covariance matrix Σ are 1, and the other entries to 0.1.
30

---

Under review as a conference paper at ICLR 2020
Log bjjcttvve Gap
Log Objectivv Ctiective Gap
A-SBCD-HT
ASBCDDHT
ASG-HT
ASG-HT
ASURG-HT
ASVRG-HT
3
5'BCD-HTP
HTP
ASBCD-HTP
ASBCD-TPP
000000
50
100
150
200
CPU Time
CPU Time (s)
(a) real-sim
(b) news20
Log Objective Gap
-2
Log Objective Gap
A-BBCD-H
A'5BCD-HT
ASGIHT
ASG-HT
ASVRG-HT
ASVRG-HT
S'BCD-HTP
STTCD-HTP
ASBCD-HTP
ASBCD-HTP
-4
2
0.5
1.5
10
(s)
CPU Time
(c) revl-train
(d) revl-test
Figure 9: Comparison of ASG-HT, ASVRH-HT, A'SBCD-HT, S'BCD-HTP and ASBCD-HTP for solving
sparse linear regression problems. The four asynchronous parallel algorithms (i.e., ASG-HT, ASVRH-HT,
A'SBCD-HT and ASBCD-HTP) run on threads.
We set the step-size y = 48ps and batch size [B] = 1 during our experiments. The upper bound then computed according to Theorem Under this condition, we obtain the result, as shown in Figure T0 As since the statistical error becomes the main factor. The convergence performance of SBCD-HTP always bounded below the black line, which demonstrates the correctness of our theorem.
that the upper bound converges faster at first and then it becomes slow
F.8 LINEAR SVM
In this subsection, we consider the sparsity-constrained L2-SVM problem (i.e., min, 2n EE (max(0. (0, w (((())()))))))))))))))))))))))) 20))) + ||]l|| subject to ||w||o I s), where (() is the known label and (+) is the given sample. We fix the regularization parameter À 10-4 The other parameters are also same to the above experiments. The objective value gap and running time of the baselines are provided in Figure [I] We can see that we also make similar observation as from the previous results. SBCD-HT performs the best among these considered baselines.
31

---

Under review as a conference paper at ICLR 2020
Bound SBCD-HTP
Log Objective Gap
10
20
30
40
50
60
Number of Effective Passes
(a) 5000, d = 10000, 500, s' 500
Figure 10: The upper bound of Theorem the convergence performance.
SG-HT SVRG-HT ASBCDHT
TG-HT SVRGG-T
Log Objective Gap
111
Log Objecive Gap
ASBCDHT
-
30
40
50
50
100
150
200
Number of Effective
news20
FG-HIT
FG-IT
SG-NT
SG
SVAG-IIT
Log Objectiv Gap
-2
ASBCCHT SRCD-HTP
Log Objective Gop
ASBCOKT
SBCD-HTP
33
-5
10
20
30
40
0
50
150
200
250
300
Number Effettive asses
CPU Time
(b) revl-train
Figure 11: Comparison of FG-HT, SG-HT, SVRH-HT, ASBCDHT and SBCD-HTP for solving sparse SVM
problems.
32


Reviews:
[{"review_id": "Hyg-tqxRtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a semi-stochastic block coordinate descent hard thresholding pursuit (SBCD-HTP) algorithm for solving l0 sparsity-constrained minimization with decomposable convex objective. The key idea is to introduce BCD into SVRG type of algorithm to speed up the convergence as well as the hard thresholding operation. The paper is well written and easy to follow. The theoretical analysis is strong, I think. However, my main concern of the paper is the experimental part.\n\n1. The test functions are simple (i.e. logistic and linear regression), and the data sets are simple as well. I'd like to see more experiments using more complex problems with more realistic data. \n\n2. There are two stronger assumptions in the paper, but they are never verified in the experiments. What else functions are following such functions? Any example?\n\n3. There are no validation experiments for Thm. 1. Are all the assumptions mild in practice? Is it possible to plot the upper bound in Eq. 4?\n\n4. I do not understand the usage of Def. 1.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkeUyj9z5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a new optimization algorithm for convex functions with sparsity constraints, based on hard thresholding to enforce sparsity. It is argued that applying hard thresholding in every step is the computational bottleneck of previous works based on hard thresholding, and the paper proposes a variant that alleviates previous works’ convergence problems. This is achieved by having an inner and outer loop in which the hard thresholding is applied only in the outer loop, and in the inner loop block coordinate descent is used  (ie. applying updates to only a subset of the solution’s variables). The paper shows that the convergence bounds of the algorithms compares favourably to previous hard thresholding algorithms convergence bounds, and empirical results show the effectiveness of the algorithm compared to previous ones.\n\nIt is always exciting to see improvements in optimization algorithms as they can lead to improvements in many different problems. Yet, I have the following concerns:\n-The algorithm is strongly based on previous optimization algorithms as the main difference with them is applying the hard thresholding less frequently. This sounds incremental and I think the paper could emphasize much more why this idea is a significant advancement over previous works.\n-The paper could make a better job motivating the sparsity constraints, as it cites papers from 10 years ago which are not representative of state-of-the-art.\n-The paper focuses on optimization time but not on generalization. Note that converging faster to the objective does not imply better generalization. I would have expected at least a discussion about this in the paper. Does the algorithm lead to better generalization accuracy or worse?\n-The proof contains an assumption that it is unclear that has been explained in the paper. In the supplementary material, after eq. 25, the factor sigma is being introduced and the paper says “we assume that there exists a constant factor sigma making this inequality true”. \n-Definition 1 does not really define hard thresholding. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJgRgt7j5r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "===== Update after author response\n\nThanks for the clarifications and edits in the paper.\n\nI recommend acceptance of the paper.\n\nOther comments:\nDefinition 1 in the updated version is still too vague (\"difference of what?\" -- function values? distance in norm between iterates?) -- this should be clarified.\n\n========\n\nThis paper considers the problem of sparsity-constrained ERM and asks whether one can design a variant of the stochastic hard thresholding approaches where the hard-thresholding complexity does not depend on a (sparsity dependent) condition number, unlike all previous approaches (Table 1). It proposes a method which combines SVRG-type variance reduction, with block-coordinate updates, leaving the hard thresholding operation outside the inner loop, to accomplish this goal. It provides a convergence analysis which significantly improves the previous best rates (by having both the sparsity level shat which is significantly lower (kappa_shat vs. kappa_stilde^2) as well as a condition number independent hard thresholding complexity (Table 1). An asynchronous and sparse (in the features) variant is also proposed, with even better complexity. Some standard experiments on sparse linear regression and sparse logistic regression is presented showing an improvement in both number of iterations as well as CPU time.\n\nI think the clarity of the paper should be quite improved (see detailed comment), hence why I think the paper is borderline, but I am leaning towards an accept given the significant theoretical improvements over the past literature (and positive empirical results), even though the algorithmic suggestion is somewhat incremental.\n\nThe proposed Algorithm 1 seems very close to the one of Chen & Gu (2016), the paper should be more clear about this. There seems to be mainly two changes: a) extending the support projection of the gradient to the union of the sampled block with the one of the support of the reference parameter wtilde (vs. just the sampled block in Chen & Gu (2016) and b) moving the hard-thresholding iteration outside of the SVRG-inner loop. These small tweaks to the algorithm yield a significant theoretical improvement, though.\n\n== Detailed comments ==\n\nClarity: the number of long abbreviations with only one letter change make it hard to follow the different algorithms; perhaps a better more differentiating naming scheme could be used. Moreover, I think more background on the sparse optimization setup should be provided in the introduction or at least in the preliminaries, as I do not think the wider ICLR community is very familiar with it (in particular, no cited paper was at ICLR). For example, define early the separation in optimization error and statistical error; and point out that F(w_t) might even be lower than F(w*) as the sparsity threshold s might be much higher than s*. This will make Table 1 more concrete and less abstract for people who not are not yet experts on this particular analysis framework.\n\n- Table 1: I would suggest to put the rate for S2BCD-HTP instead on the last row and mention instead that the rate for ASBCD is similar under conditions on the delay; as it is interesting to already have a better gradient complexity for S2BCD vs. SBCD.\n\n** Questions:  **\n1) In Corollary 1, how is the gradient oracle complexity defined or computed? And more specifically, how does one compare fairly the cost of doing a gradient update in Algorithm 1 on the *bigger set* S = Gtilde U G_jt vs. just G_jt for the Chen & Gu ASBCD algorithm? Is this accounted in the computation?\n\n2) In Figure 1, which \"minimum\" is referred to and how is it found? I suspect it is not F(w*) (as it could be higher than F(w_t)), i.e. it is *not* the minimum of (1) with s*. One natural guess is that it might be min_w F(w) s.t. ||w||_0 <= s, though I do not see any guarantee in the main paper that running the algorithm would make F(w_t) converge to such a value (i.e. all we know from Thm 1 is that F(w_t) might be within O(||nabla_Itilde F(w*)||^2) of F(w*) ultimately. Please explain and clarify!\n\n== Potential improvement ==\n\nThe current result in Theorem 1, which is building on a similar proof technique as the original SVRG paper, has the annoying property of requiring the knowledge of the condition number in setting the size of the inner loop iteration. I suspect that this is an artifact of using an outdated version of the SVRG algorithm. This has been solved since then by considering a \"loopless\" version of SVRG which implicitly defines the size of the inner loop in a random manner using a quantity *which does not depend on the condition number*. This was proposed first by Hofmann et al. [2015], and then re-used by Lei & Jordan [2016] and more recently by Kovalev et al. [2019] e.g. Note that Leblond et al. (2017) that you cited profusely also used this variant of SVRG. I suspect that this technique could be re-used in your case to obtain a similar result with a loopless variant (which also gives cleaner complexity results). (Though I only skimmed through your proof.)\n\nCaveat: the sensibility of the theory in the main paper seems reasonable, but I did not check the proofs in the appendix.\n\n= References:\n- Hofmann et al. [2015]: Variance Reduced Stochastic Gradient Descent with Neighbors, Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien and Brian McWilliams, NeurIPS 2015\n- Lei & Jordan [2016]: Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method, Lihua Lei and Michael I. Jordan, AISTATS 2016\n- Kovalev et al. [2019]: Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop, Dmitry Kovalev, Samuel Horvath and Peter Richtarik, arXiv 2019\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers reach a consensus to reject the current submission. 

In addition, there are two assumptions in the proof which seemed never included in Theorem conditions or verified in typical cases. 

1) Between Eq (16) and (17), the authors assumed the 'extended restricted strong convexity’ given by the un-numbered equation. 

2) In Eq. (25), the authors assume the existence of \sigma making the inequality true.

However those assumptions are neither explicitly stated in theorem conditions, nor verified for typical cases in applications, e.g. even the square or logistic loss. The authors need to address these assumptions explicitly rather than using them from nowhere.
Decision: Reject