Explicit Group Sparse Projection with Applications to Deep Learning and NMF
Authors: Riyasat Ohib
Nicolas Gillis
Niccolo Dalmasso
Sameena Shah
Vamsi K. Potluru
Sergey Plis
Venue: Accepted by TMLR ()

Abstract: We design a new sparse projection method for a set of vectors that guarantees a desired average sparsity level measured leveraging the popular Hoyer measure (an affine function of the ratio of the $\ell_1$ and $\ell_2$ norms).
Existing approaches either project each vector individually or require the use of a regularization parameter which implicitly maps to the average $\ell_0$-measure of sparsity. Instead, in our approach we set the sparsity level for the whole set explicitly and simultaneously project a group of vectors with the sparsity level of each vector tuned automatically.
We show that the computational complexity of our projection operator is linear in the size of the problem.
Additionally, we propose a generalization of this projection by replacing the $\ell_1$ norm by its weighted version.
We showcase the efficacy of our approach in both supervised and unsupervised learning tasks on image datasets including CIFAR10 and ImageNet. In deep neural network pruning, the sparse models produced by our method on ResNet50 have significantly higher accuracies at corresponding sparsity values compared to existing competitors. In nonnegative matrix factorization, our approach yields competitive reconstruction errors against state-of-the-art algorithms.

Published in Transactions on Machine Learning Research (10/2022)
Explicit Group Sparse Projection with Applications to Deep Learning and NMF
Riyasat Ohib
riyasat ohib Sgotech. edu
TReNDS Center, Georyia Institute of Technology
Nicolas Gillis
nicolas, gillis Gumons.ac.b
University of Mons
Niccolò Dalmasso
niccolo. www.mmmmmssmmpcmssee.c.oo
J.P. Morgan Al Research
Sameena Shah
samenna.shad@jjpmccase.comm
J.P. Morgan AI Research
Vamsi K. Potluru
J.P. Morgan Al Research
Sergey Plis
s. s.m. wm..lis@gmail..com com
TReNDS Center
Reviewed on OpenReview: https: opw.r/veewwwweeeeoooee weteeeewweeee//eeee forum? id- jIrDeNjdpe
Abstract
We design new sparse projection method for set of vectors that guarantees desired average sparsity level measured leveraging the popular Hoyer measure (an affine function of the ratio of the & and &2 norms). Existing approaches either project each vector individually or require the use of a regularization parameter which implicitly maps to the average to- measure of sparsity. Instead, in our approach we set the Hoyer sparsity level for the whole set explicitly and simultaneously project a group of vectors with the Hoyer sparsity level of each vector tuned automatically. We show that the computational complexity of our projection operator is linear in the size of the problem. Additionally, we propose a generalization of this projection by replacing the & norm by its weighted version. We showcase the efficacy of our approach in both supervised and unsupervised learning tasks on image datasets including CIFARIO and ImageNet. In deep neural network pruning, the sparse models produced by our method on ResNet50 have significantly higher accuracies at corresponding sparsity values compared to existing competitors. In nonnegative matrix factorization, our approach yields competitive roconstruction errors against stato-of-the-art algorithms.
1 Introduction
Sparsity is crucial property in signal processing and learning representations, exemplified by breakthroughs in compressed sensing (Donoho, 2006; Candès et al., 2006), low-rank matrix approximations (d' Aspremont et al., 2007) and sparse dictionary learning (Aharon et al., 2006; Hoyer, 2004). A natural advantage of sparseness is that it diminishes the ellects of random noise since it suppresses arbitrary combinations of measured signals (Donoho, 1995; Hyvärinen, 1999; Elad, 2006). The norm a natural measure of sparsity but directly optimizing for it typically NP-hard. In practice, f--nrr is typically used as a proxy for obtaining sparse solutions. This is similar to the LASSO problem (Tibshirani, 1996) in the regression setting where one constrains the number of non-zeros in the solution which can be accomplished explicitly

---

Published in Transactions on Machine Learning Research (10/2022)
constraint or implicitly through fi-norm regularization. However, this necessitates the search over the regularization parameter which corresponds to the solution with the user-defined sparsity.
In this paper, we design a new sparse projection method for a set of feature vectors {or E "R to achieve a desired average sparsity level that is measured using the sparsity measure introduced by Hoyer (2004). For x + and n > 1, the Hoyer sparsity of x is defined as follows
vn |
sp(x)=
vn E [0.
(1)
We have that sp(x) 0 > | |z
|x(+) = b for all j and for some constant b, while sp(x) =1 > | = 1. We refer to Section 2.1 for more detail on this measure. In summary, given a set of vectors {a E -= and a desired average sparsity level & E [0, I], we will compute a set of vectors {a, E E_ that are closest to fa E R- for each (see Section 3 for the details), while the average Hoyer sparsity of the vectors r larger than 8, that is, 1 Ex=1spp(zg 2 8.
This projection is inspired by the work of Thom al. (2015) in which each feature vector &; is independently projected, and used for sparse dictionary learning. Although range of approaches exist to induce sparsity, this particular measure has been shown to enjoy many attractive properties (Hurley & Rickard, 2009) while also being very amenable for optimization. The key difference with our projection from previous works by Potluru et al. (2013); Thom el al. (2015) is that the feature vectors achieve an average largel sparsity level: some may end up dense, while others extremely sparse based on the problem. Therefore, our approach has three main advantages:
1. Only one sparsity parameter has to be chosen, namely s E 1].
The sparsity levels of the projected vectors are automatically tuned to achieve the desired average sparsity; hence, allowing these vectors have different sparsity levels.
3. Our projection has more degrees of freedom and consequently will generate sparse feature vectors that are closer to the original ones.
Our novel projection operator will rely on duality and Newton's method to compute the unique solution under mild assumptions. This new approach to project a set of vectors could be used in numerous applications where more than one sparse vector has to be learned, c.g., in dictionary learning (Thom et al., 2015) and sparse low-rank matrix approximations (d' Aspremont et. al., 2007). In this paper, we will explore our novel projection operator in the settings of pruning deep neural networks and sparse non-negative matrix factorization (NMF).
1.1 Related Work
Projection onto the & ball, and onto the intersection of é1, la balls bybbll projections have a rich history in the literature and in particular have been considered earlier by Gafni & Bertsekas (1984). Recent versions are optimal with run times linear in size of the input (Duchi et al., 2008; Condat, 2016). Projections onto the intersoction of L, ball constraints was introduced by Hoyer (2004) and subscquently addressod in series of works by Yu el al. (2012); Potluru el al. (2013); Thom et al. (2015); Liu el al. (2019), resulting in essentially the same optimal run times shown in the & settings. Note that none of the approaches above can directly handle the group sparsity problem that arises in Sparse NMF and neural network models.
Sparse NMF In nonnegative matrix factorization, an input data matrix Y E m is approximated by a low-rank matrix Y = XH where X E RT and H E RIX", and r is the factorization rank. The most popular formulation of NMF uses the Frobenius norm to evaluate the quality of the solution as follows:
min XeRmxr, He Y - -XHI
(2)
such that X 2 0 and H 2 0.
2

---

Published in Transactions on Machine Learning Research (10/2022)
Many algorithms have been proposed to tackle this problem such as by Kim & Park (2007) and Potluru et al. (2013). Most of them use an alternating strategy optimizing X for H fixed and then H for X fixed, since the corresponding subproblems are convex; see Section 5.1 for more detail.
In practice, it is particularly useful to have sparse X and/or H to take prior information into account, leading to more robust, identifiable and more interpretable decomposition (Hoyer, 2004). We will discuss detail sparse NMF formulations in Section 5.1.
Neural Network Pruming It has been known since the 1980s that a significant number of parameters can be climinated from neural networks without appreciable loss in accuracy (Janowsky, 1989; LeCun et al., 1990; Reed, 1993). It is indeed an attractive proposition to prune such large networks for real-time applications especially, on edge devices with resource constraints. Pruning large networks could substantially reduce the computational demands of inference when used with appropriate libraries (Elsen et al., 2020) or hardwares designed to exploit sparsity (Pool et al., 2021; Cerebras, 2019). In recent times, the Lottery Ticket Hypothesis (Frankle & Carbin, 2019) was proposed that details the presence of sub-networks within a larger network, which are capable of training to full accuracy in isolation. This resulted in renewed interest in sparse deep learning and model pruning (Renda et al., 2020; Chen et al., 2020; 2021) and more recently in the arca of sparse reinforcement learning (Arnob et al., 2021; Sokar et al., 2021). There are a range of techniques in the literature to prune deep neural networks and find sub-networks at various stages of training: techniques that prune before training (Lee et al., 2019; Wang et al., 2020), during training (Zhu & Gupta, 2018; Ma et al., 2019) and after training (Han et al., 2015). The most common among these techniques to prune the network after training using some sort of predefined criterion that captures the significance of the parameters of the network to the objective function. A range of classical works on pruming used the second derivative information of the loss function (LeCun et al., 1990; Hassibi et al., 1993). Perhaps the most intuitive of these approaches is magnitude based pruning, where following training, a subset of the parameters below some threshold is pruned and the rest of the parameters are retrained (Han et al., 2015; Guo et al., 2016), and regularization based methods ( (Yang et al., 2020; Ma et al., 2019; Louizos et al., 2018; Yun et al., 2019) which induces sparsity in the network during the optimization process.
However, we still lack a way to introduce sparsity in the layers of the network which is both controllable and interpretable. For example, in the case of regularizer imposed sparsity in neural networks (Yang et al., 2020), there is no way to relate the regularization weight with the actual sparsity of the result. Moreover, in practice we have to tune the regularizer weight differently for each task and architecture, Hence form of a grid search for that parameter is unavoidable, which is costly both in terms of time and resources.
1.2 Contributions and Outline
Our contributions can be summarized as follows:
1. We define a novel grouped sparse projection (GSP) with single sparsity parameter (Section 2).
We provide an efficient algorithm (linear in the size of the problem) to compute this projection, based on the Newton's 's method (Section 3).
We extend our approach to perform weighted grouped sparse projection using the weighted & norm (Section 4 and Appendix C).
2. We evaluate GSP on sparse NMF and pruning deep neural network tasks (Section 5).
For NMF, GSP competes with state-of-the-are methods on an image dataset and outperforms them on a synthetic dataset (Section 5.1).
In pruning deep neural networks, GSP achieves higher accuracies at corresponding sparsity values compared to competing methods on the CIFAR10 datasct. On the Imagenet task, it outperforms a range of pruning methods in terms of sparsity versus accuracy trade-off (Section 5.2).
GSP can also recover competitive accuracy with single projection of large pre-trained models followed by finetuning, altogether skipping the training with regularization phase. (Section 5.3).
Please check the appendix for detailed proofs, implementation details, and additional experiments.
3

---

Published in Transactions on Machine Learning Research (10/2022)
Notation We denote R" the set of n-dimensional vectors in R, R = fz x 22 where means that the vector is component-wise nonnegative, [ = [0) and R0,++ = R ((} where 0 is the vector of zeros of appropriate dimension. For I E IR"", we denote sign(æ)) the vector of signs of the entries of | the component-wis wise absolute value of the vector 2, [x]+ max(0, x) the projection onto the nonnegative orthant, x(() the ith entry of x, ||ar|lo the number of nonzero entries of x, that is, the Eo norm, ||ا|| = E (a()))
the 4 norm of z, and || V x0i)² the &g norm of 2. We also denote the component-wise product wetween two vectors, that is; 2 == x 200 = =(1) x(i)v(1) Vi, 1 the vector of all ones of appropriate dimension, and [1,r]] {1, r..
2
Background on Projection with the Hoyer Sparsity Measure
In this section, we define the problem of sparse projection and formulate the sparse projection task for single vector.
2.1 Hoyer sparsity measure
Given a vector E R", meaningful way to measure its sparsity is to consider the Hoyer sparsity defined in (1). A main advantage of sp(x) compared to || is that sp(x) is smooth except on a set of measure zero, namely when x(i) = O for some i, since ||æ|]] is not smooth at these points. However, it is continuous everywhere except at the origin, I = O, where it is not defined. Moreover, when considering only the nonnegative orthant, that is, z E RT, then sp(z) is smooth everywhere except at the origin, since ||=||| 1 for x 2 0. As we will see in Sections 2.2 and 3, see in particular (4) and (GSP), one can restrict the search space to the nonnegative orthant which makes sp(x) even more convenient to work with. Those crucial properties that allows one to project efficiently onto the set of vectors of a given Hoyer spansity (Thom et al., 2015). Note that sp(x) is invariant to scaling, that is, sp(x)= = sp(ax) for any # O.
Another useful property of sp(x) is its nonincrcasingness under the soft thresholding operator: Given a vector x and a parameter À 2 0, the sofl-thresholding operator is defined as
st(z, A) = sign(x) o - [|]+-
This property will be particularly useful later when deriving our novel projection of a set of vectors. Note that for A between the largest and second largest entry of |z], st(x,, A) is 1-sparse with sp (st(2, A)) = 1, honce sp (2, 2)) is constant. Interestingly, for x x= b1 for some constant b, it not possible lo sparsily x (because we cannot differentiate between its entries) and st(x, is constant for all X < Note that while the 4n norm can also be used directly as a sparsity measure (Bolte al., 2014; Pock & Sabach, 2016), it does not enjoy some of the nice properties of the Hoyer-sparsity measure; see Appendix A.1, Hurley & Rickard (2009) and Thom et al. (2015) for more detailed discussions.
2.2 Single Vector Sparse Projection
Let us first present the sparse projection problem for a single vector, along with reformulation that will be uscful to project a set of vectors. These derivations are similar to that of Hoyer (2004); Potluru et al. (2013); Thom et al. (2015). Given e Ry and a sparsity level 8 E [0, 1], the sparse projection problem can be formulated as follows
min ||e - 2||2 such that sp sp(x) 2 s. ZER
(3)
Let us use the change of variable az, with = || 0 and ||||| 1. Note that sp(z) sp(ax) = sp(x) since sp(.) is invariant to scaling. Hence does not appear in the sparsity constraints. Moreover, can be optimized casily. By expanding the & norm we have:
a" = argmin azl12 = x0x c),
since ||/||| 1. For a" > 0, have
||c aa'r 1 = ||cl 1103-2200
-0=x=" c (a²)² =|co12 -m=Fc)²
4

---

rs and Published in Transactions on Machine Learning Research (10/2022)
We notice that the sign of the entries of be chosen freely since the constraints not inftuenced by flipping the sign of entries of x. This implies that, at optimality,
the entries of x will have the same sign as the entries of c, and
a 0 since c + and 0. Therefore, (3) can be reformulated as
max x cl =ERo
(4)
such that
||||| 1, 2 0 and sp (x) 2
In fact, the optimal solution of (3) is given by = (Ic|=x²) sign(c) o x", where xf is an optimal solution of (4). Although this reformulation is relatively straightforward, it was not present in the literature, as far as we know.
3 Grouped Sparse Projection (GSP)
We extend the argument of Section 2.2 a set of vectors and present our novel approach grouped sparse projection.
3.1 Formulation of the Problem
Let {a E (R be a set of non-zero veclors. The main goal of sparse projection is to find set of non-zero unit-norm vectors {a, E Rg J that has an average target sparsity larger than a given E [0, 1]. Mathematically, let X {a; E By E [1 : x, 2 0, |xlll = IV.. We propose the following novel grouped sporse projection problem:
max X
of lcal such that
Σ sp (a;) 2 8.
(GSP)
The main reason for the choice of this formulation is that it makes GSP much faster to solve. In fact, as for (3) that was studied by Thom al. (2015), we will be able to reduce this problem to the root finding problem of a nonincreasing function in one variable. In particular, using the objective function minx Eiulls - z;112 (or
Ee );]l²) would not allow such an effective optimization scheme.
Remark 3.1 (Abuse of terminology). The solution to the problem (GSP) is not projection, as it does not provide point within set closest in some norm to a given point. However, for simplicity, and since it extends the projection in the case of single vector, see (3) and (4), we abuse the terminology and refer to (GSP) as a projection.
Let reformulate GSP focusing the sparsity constraint: have
Σ sp (2,)
n
|allla
rs,
14
T4
7
where we used the fact that ||> for all the feasible set X. Denoting ke Ei=1
yn: vai-1
8, - GSP can be reformulated as follows
max
x [cll
such that
3.1 x; S his
(5)
We used || 1T x, since x, 2 0. Note that the maximum of (5) attained since the objective function is continuous and the feasible set. is compact (extreme value theorem).
5

---

Published in Transactions on Machine Learning Research (10/2022)
3.2 Lagrange Dual Formulation
In order lo solve (5), follow slandard dual approach, similarly done by Thom et al. (2015) for the projection of a single vector. However, our derivations are rather different because the vectors to be projected share the same Lagrange dual variable, while we need to carcfully treat the case when some of the vectors are projected onto a 1-sparse vector. Let us introduce the Lagrange variable μ 2 0 associated with the constraint Ei=1 (3,1% S lig. The Lagrange dual function with respect to f given by
of clll 1 Σ B,x (EB,eT1 Kis
((p) max Σ
max
2 (lcal (Bpll) + pkg.
(6)
The dual problem given by min (()). The optimization problem to be solved to compute A(H) is separable in variables xt's 's and consequently be solved individually for each 2;. Let us denote 2;[p] the optimal solution of (6). For each i, there are two possible cases, depending on the value of μc:
|al p3,1 > 0: the optimal xı[a] given by
||||| - 113:1
st([ea). 1433,)
x
[|ad p/3 1]
[t(( (1::)
This formula be derived from the first-order optimality conditions. Note that this formula is similar to that of Thom al. (2015). The difference is that the 2,'s share the same Lagrange variable /a.
2. |a| --,, < O: the optimal 2ı[p]] is given by the 1-sparse vector whose nonzero entry corresponds to the largest entry of |e|- 11,11, that is, of les- Note that if the largest entry of |ed is attained for several indexes, then the optimal 1-sparse solution of is not unique. Note also that this case coincides with the case above for μ in the interval between the largest and second largest entry of c.
3.3 Characterizing the Optimal Solution x;144]
Let ji be the smallest value of μ such that x[]i]] are all 1-sparse. There are three scenarios based on the value of μ: (a) μ = 0, (b) p 2 j and (c) 0 < ft.
(a) For μ O, we have r,[0]]
|c.1 If x0 is feasible, that is, E. x,1 S kg, then it is optimal Tcalla-
since the error of GSP is zero: this happens when the es's are already sparse enough and do not need to be projected.
(b) For a 2 i, all xz(ā are all 1-sparse so that 1 [
hence
g(ū)=
Σ 8r ka
i=1
Σ 1=1
n
+
m4
1=1
(7) The value ji is given by the second largest entry among the vectors |c:l/3,'s. In fact, if is larger than the second largest entry of |ca], then æı|μ is 1-sparse. Note that the largest and second largest entry of vector |cj| are equal, then 9(4) is discontinuous, This is an unavoidable issue when one wants to make vector sparse: if the largest entries are equal to one another, one has decide which one will be to zero. (For example, [1, 0) and [0. 1] are equally good 1-sparse representation of [1, 1).)
- - 0.

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm GSP(fc E R" 1=,,
1: input: {c E R" 1/ the average sparsity E [0, 1I. the accuracy the parameter E [1/2,1)
2: output: {z E " |==1 with average sparsity in [a - e, +
3: μ= =0, P i1 μ¹ = 0, =
while 19(4")
re do
pold n³*
:² = -1++ + k-g(μ")
Newton's step
g'(m")
if 1²² [1 then n²= - μ+ツ end if
Bisection method if Newton's step fails D> Update feasible interval
8:
if (((")) 00 then == μi else μ = n end if
if M μ> n and lpold μ²1 (1 -1) then
10:
D If feasible interval is not reduced use bisection again end if
11:
if g(x")) > then == else μ
D> Update feasible interval
12:
end if
13:
A= A
>> Update diameter A
14: if A <<e and 11" ul < cp" for some μ E then
15: break;
D D contains the set of discontinuous points, stop GSP
16: end if
17: end while
18: return 27
[lcll xe:]] sign(c;) o x. 2,(u"|V=1 D Compute rs[1²]] (see Section 3.2) and return projections
(c) For 0 < 1 ni, the constraint is active at optimality and we need to find the value μ such that
sl4) = Σ x - k. = 0,
that is, find root of g()). Theorem 3.2 guarantees that the solution μ² is unique in this setting, and Corollary 3.3 proves the respective projection =1p²]= [=][n").... ....) "xTT4") [x]]] is also unique.
Theorem 3.2 (Uniqueness of μ*). The function g(n) is strictly decreasing for < < n. Hence, it is not disconlinuous around g(1) = 0 and allains a unique rool p²
Proof sketch. The function g(u) is continuous as it is continuous function of I(H), which is contimuous Hence, it suffices to show that g' (p) < 0 for 0 < p Tt. See Appendix C.3 for a detailed derivation in more general case.
Corollary 3.3 (Uniqueness of projection x²). the largest entry of each [c,) is attained for only one entry, the projection x æ|n*] is unique.
Proof skelch. -= and p > n., x(u)) is unique provided the largest and second entry of each |es are not equal (see Section 3.3). For μ A, since the optimal μ² is unique it suffices prove [ı[4]] is a one-to-one mapping, i.c., that if x; (11)) (p22) then μn /22- Detailed derivations shows that 24[44] is one-to-one mapping unless all entries of are equal, which is in contrast with the assumption (see Appendix B). J
[1,r]. Once the optimal 4² and the respective projections xx[x²]] are computed, one can retrieve the sparse projections via 2 ((eg)")r,(<"))) sign(c)) xg[=*]] for
3.4 Implementation and Computational Cost
In order to compute the dual variable μ4, which leads to the desired average Hoyer sparsity for the vectors =/[al's, we resort to a standard approach compute the root of the nonlincar function, g(p), namoly Newton's method which has quadratic convergence (given that we are sufficiently close root, and that the function is sufficiently smooth). Because g(u) not smooth everywhere, have implemented the bisection method

---

Published in Transactions on Machine Learning Research (10/2022)
fallback procedure, which guarantees the algorithm's computational complexity to be upper- bounded by O(N log N). The use of bisection is necessary if Newton's method either goes outside of the current feasible interval [u, pid containing the solution μ²¹ or stagnates locally and does not converge (although we have not observed the latter behavior in practice). This a a standard textbook strategy in numerical analysis.
Algorithm 1 summarizes the GSP algorithm. The main computational cost of GSP to compute g(v) and g' (p) each iteration, which requires ((N) operations where N = -i== n4. Most of the computational cost resides in computing the zu(u]'s and some inner products. The total computational cost is O(t)), where is the number of Newton's 's method iterations, hence making GSP linear in the size of the problem. In practice, we observed that Netwon's method converges very fast and does not require many iterations t (see Appendix A.4 for a synthetic data example with vectors of dimension n, = 1000, in which Newton's 's achieves convergence in t = 4 iterations or less). In our experiments we have observed that using Newton's method with initial point 1 = 0 performs well, which in line with the results of Thom et al. (2015), as points where the function is not differentiable typically form a set of mcasure zero (Kummer al., 1988). The reason choose l 0 as the initial point is because g(u) decreases initially fast (all entries of x;; corresponding to nonzero entry of are decreasing) while it tends to saturate for a larger μ. In particular, we cannot initialize I at values larger than j since g(H) is constant (g) 0) for all 2 p.. Finally, we have included a method to detect discontinuities, corresponding to situations when the largest entries of the oj 's are not unique. In that case we require GSP to return a J such that g(u + qu) < 0 < g(u eut), where é is a desired accuracy (which in practice can be set to E c= =0=
4 Weighted Grouped Sparse Projection
In some settings, one may want minimize a weighted sum of the entries of the ss that is, Ei of x; S k for some W; R.. This amounts to replacing the --norm in the sparsity measure sp(.) by weighted & norm. We introduce the notion of weighted sparsity: For vector Ry and given 18 we define
|| ||
(x)
l la
E [0. 1],
(8)
| min, wi)
where W diag(w). We the weighted sparsity in (8) to define the w-sparse projection problem of the set of vectors {cp E I Her Let {w, E 1 He be the nonzero nonnegative weight vectors associated with the q'ss. Given a target average weighted sparsity sw E [0, 1], we formulate the weighted group sparse projection (WGSP) problem as follows:
max
x [cel
such that
Σ SPi, (xx² 2 Sw
(WGSP)
We have included properties of the proposed weighted sparsity, along with full derivation of the WGSP problem, the optimal solutions and experiments in Appendix C.
5 Experiments
In this section, we evaluate the utility of GSP in two applications: sparse NMF and deep learning network pruning. The goal is to evaluate the effect of performance at desired sparsity in the unsupervised and supervised setting.
5.1 gspNMF: Projection-baser Sparse NMF
As explained in Scction 1.1, the standard NMF problem is formulated as in (2). As studied in detail in the recent book by Gillis (2020), the most widely used and efficient algorithms for NMF are block coordinate descent algorithms, and two of the most popular and effective ones are the following:
A-HALS updates alternatively the columns of X and the rows of using closed-form solution (Gillis & Glineur, 2012),
8

---

Published in Transactions on Machine Learning Research (10/2022)
2. NeNMF updates alternatively the full factors X and H. The update of each factor requires to solve convex non-negative least squares problems that NeNMF solves approxinately using few steps of Nesterov fast gradient method (FGM), an optimal first-order method (Guan et al., 2012).
Sparse NMF enforces an additional sparsity constraint X and our GSP leads to natural sparse NMF formulation: given average sparsity level for the columns of X, 8, solve
min XeRmxr,
||Y - XH
(9)
such that X 0, 222 and Σ sp (X((,))) 2s,
where X(; k) is the kth column of X. To solve (9), we use the same update as A-HALS for H as it is not affected by the sparsity requirement. For updating X, we adapt the update of NeNMF (Guan et al., 2012) by replacing the projection onto the nonnegative orthant with GSP; we refer this new sparse NMF algorithm as group sparse projection NMF (gspNMF). Note that our feasible set not convex, hence FGM is not guaranteed to converge. However, use a restarting scheme and keep the best iterate in memory. We compare gspNMF with
The same algorithm where the projection performed column-wise with the columns constrained to have the same sparsity level, as done by Thom al. (2015). This algorithm solves the same problem (9) where the last constraint is replaced by sp (X(:,)) 2 for all k. We refer to this algorithm cspNMF.
A-HALS with l penalty described by Gillis (2012) that uses the formulation
min XERMX HER
Y XHI + Ae [x(;,))ll
(10)
k=1
such that X 0, H H 0, and [X((;,))l = 1 for & E [1,r].
where the & penalty parameters for each column of X, Ag's, are automatically tuned to achieve the same desired to sparsity level"; see the code provided by the author. We refer to this algorithm as & A-HALS.
We compare all algorithms in terms of error per ileration. Since all algorithms have almost the same computational complexity per iteration", we believe it is fair and more insightful to compare these five algorithms with respect to the itcration number. In all experiments, we perform 500 itcrations (updates of X and H) of each algorithm. See Appendix for details about the experimental parameters and datasets used.
gspNMF on synthetic data We first perform experiments on synthetic data sets where W and are generated randomly, with W having about 50% of its entries equal to zero, and with setting m and r 10; see Appendix D.1 for the details. We note an interesting finding: if gsPNMF is given the sparsity of an exact factorization, it converges to exact solution much faster than A-HALS and NeNMF. In other words, gspNMF is able to use the prior information to its advantage. Although A-HALS and NeNMF are less constrained, as they solve (2) instead of (9), they converge significantly slower. From Figure we observe
expertt
100
AAtthough & A-HALS does not use the same sparsity measure as MF and cspNMF, these two measures are close to one another in most cases. For example, in the synthetic data experiments (see below), we will generate n-dimensional vectors using the Gaussian distribution and setting the negative entries to zero. Such vectors have an expected to sparsity of 50%. Generating 100 such vectors, their average Hoyer sparsity is 48.31% 1 while their average fo sparsity is 49.9%.
2The main computation cost resides in computing YHT (resp. YX) when updating X (resp. H) which requires ((mar) operations. gspNMF and cspNMF slightly more expensive because of the projection step, although this is not the main computational cust (the projection cost is lincar in and r). For example, on syuthetic data sets for sufficiently large (see below), gFpNMP and csPNMF took on average the same computational time than NcNMF and A-HALS (in fact, for some with 10 g8PNMF surprisingly slightly faster than NeNMF and A-HALS, due inaccuracy accounting for the computational time).
9

---

Published in Transactions on Machine Learning Research (10/2022)
10
100 IIY-XHIII Omin ) /IIII
100 IIY- XHII JIYI
10
10
A-HALS
NeNMF
2
--HAALS
10
gapNMF
A-HALS
NaNMF
CSONMF
AA-HALS
A---ALS 0.7
12pNMF
gepNMF
2spNMF
CspNMF 0.7
10
100
lterations
300
500
10
Iterations
10
10a
Comparison of NMF and sparse NMF algorithms. On the left: Average relative error 100 IY [ r-mmin obtained with different NMF algorithms over 50 synthetic data sets. On the right: Average
Figure 1:
||
relative error in percent to which the lowest error minn obtained among all algorithms and all initializations is subtracted (hence the error should go to zero for the best algorithm), that is, 100 Y Emiin over 10 random initializations the CBCL data set with = 49.
that NMF performs better than A-HALS, which in turn outperforms NeNMF. gspNMF reduces the error towards zero much faster, although having a higher initial error as is more constrained.
Since cspNMF more constrained, it is not able to perform as well as gspNMF. This illustrates the significant benefit of using an average sparsity instead of a single sparsity level for all columns of X. For similar reasons, 21 A-HALS performs worse as it attempts to achieve the same given sparsity level for all columns of X.
gspNMMF on CBCL facial image data We test our method one of the most widely used datasets in the NMF literature, the CBCL facial images used in the seminal work by Lee & Seung (1999) with 49. NeNMF and A-HALS for NMF (2) generate solution with average Hoyer sparsity about 70%. We run the sparse NMF techniques with sparsity set at 85%, hence we expect sparse NMF to have higher approximation errors but have higher sparsity. Using 10 random initializations, Figure 1 reports the evolution of the average relative error. In this case, gspNMF performs similar to the ttate-of-the-ar algorithms, cspNMF and & A-HALS, because the columns of X have similar sparsity levels. We include the basis elements obtaincd by each different methods in Fig 5 of Appendix-D.2.
5.2 Pruning Deep Neural Networks with GSP
We evaluate performance of GSP in pruning each layer of modern convolutional neural network using fixed value of the sparsity parameter s. Although we chose to prune each layer with the same sparsity to simplify the comparison, GSP can casily be used with different sparsity levels for parameters of different layers, providing fine control over the sparsity of the network.
To simplify comparison with related work we express the sparsity of the pruned network in terms of the number of zeroed parameters instcad of sp(x) (1). Since sp(æ) is a differentiable approximation of the &u norm, applying GSP with sparsity to layer of the network pushes fraction of the parameters to zero near zero, thus retaining interpretability of the parameter
We run experiments on the CIFAR-10 (Krizhevsky et al., 2009) dataset with the VGG16 model and on the ILSVRC2012 Imagenet dataset (Russakovsky et al., 2015) with the ResNet50 model (He et al., 2016) For the fully connected layers, we project the connections in each layer separately, with a target sparsity s. This ensures the weights of that particular layer have sp(x) = s. For the convolutional layers, we project each & filter treating each as a vector x; E R² in our formulation, where n cx h2 and the number of input channels. All the filters in a particular layer are projected at once.
The code available at
10

---

Published in Transactions on Machine Learning Research (10/2022)
VGG16 on CIFAR 10
Model Sparsity
Methods
80%
85%
90%
95%
97%
Dense Baseline
92.82 %
Random Pruning
83.7%
82.75%
81.56 %
78.18%
76.3%
Magnitude Pruning (Han et al,, 2015)
92.78%
92.74%
92.5%
91.41%
10%
DeepHoyer (Yang el al., 2020)
91.23%
91.2%
91.42%
91.447%
91.51%
GSP
92.37%
92.28%
92.39%
92.32%
91.92%
Table Test Accuracy of pruned VGG16 16 network using GSP vs random pruning and other pruning methods for sparsity varying the 80% to 97% range.
We test two pruning strategies using GSP. The first strategy consists in projecting the layers of a model every specified number iterations, then pruning the weights post-training followed by finetuning of the surviving weights we call this Snddccod-SSP" training. In the second strategy, we start with a pretrained model, project the layers once, and finetune the model. The second approach skips the sparsity inducing training phase, which is requirement for popular regularization-basse based sparse techniques. We denote this approach singlo-shot GSP'
Table reports the test accuracy of induced-GSP at different sparsity levels against (a) random pruning, which randomly selects (1 - s) fraction of the model weights and retrains them, (b) magnitude pruning, where the top s) fraction of the parameters are selected post-training and retrained and (c) DeepHoyer (DH, Yang al. 2020), a hegf-performance regularization- based pruning technique. GSP clearly outperforms random pruning and finds out important connections in the network. While magnitude pruning performs slightly better than GSP at lower sparsity levels, GSP achieves comparable and higher accuracies in the sparsity region > 90%. Finally, GSP achieves higher accuracy than DH throughout the different sparsity levels tested. We note that since DH requires a regularization parameter to be tweaked using naive search, we trained upwards of 60 models to achieve the reported performance. This quickly becomes infcasible for training ImageNet level lasks without using significant resources.
-2.5
Accuracy A %
-5.0
-7.5
GSP
SynFlow
Magnitude
-10.0
DeepHoyer
SNIP
GraSP
-12.5
ThiNet
NISP
DCP
-15.0
50
90
Sparsity %
Figure 2: Accuracy change relative the dense model at different levels of sparsity for multiple state-of-tho the--rtt network pruning techniques applied to ResNet550 on the ImageNet dataset. Values towards top-right are better. Notably, GSP provides superior sparsity vs accuracy tradc-off.
11

---

Published in Transactions on Machine Learning Research (10/2022)
ResNet50 ImageNet Testing pruming techniques on the ImageNet dataset (Russakovsky et al., 2015) is becoming standard in the field of model compression as it is a large-scale complex dataset. Therefore, we test the efficacy of GSP on the ImageNet dataset and compare it with a range of pruning techniques from the literature. We compare against regularization-base basee (Yang et al., 2020), magnitudo-basel (Han et al., 2016); and structure-based pruning (Luu et al., 2017; Yu et al., 2018; Zhuang et al., 2018). We also test GSP against pruning at initialization techniques by Lce et al. (2019); Wang et al. (2020); Tanaka et al. (2020), that have the added benefit of training a sparse model but the disadvantage of having almost no training information to guide pruming. We project the layers of Res-Net50 model with GSP every fixed iterations and subsequently prune the parameters identified by our method according to set sparsity values. Pruning a network is a trade-off between sparsity and accuracy. Hence, in Figure 2 we report the sparsity and accuracy of GSP against other pruming techniques. We observe that even at relatively high sparsity levels, GSP competes with and outperforms all pruning techniques we compared with, dropping only 0.41, 1.43 and 2.2 percentage points at 70, 80, 85 and 90 percent sparsity respectivcly.
5.3 Single Shot Network Pruning
GSP can also be utilized to generate sparse models by a single projection stop instead of repeated projections throughout the training process. Thus, we can first take a pretrained model, project the model once layerwise with our choice of sparsity, and finally finetune the surviving connections. We refer to this approach as "Single-Shot GSP" This is in contrast to popular regnlarization--aaed techniques of Yang et al. (2020) and Ma et al. (2019) which need to train with the regularizer first, then prune the weights and finally finetune the surviving weights to generate the final sparse model. The ability to project pretrained model directly without going through a regularized training phase would be an attractive ability to have, e.g. in transfer learning.
Table 2 shows the accuracy and sparsity value of induced GSP and single-shot GSP against DeepHoyer (DH) on the Res.eet-56 and ResNet-110 architectures and tested on the CIFAR-10 Dataset. The drop in accuracy compared to their respective basclines is reported well. Noticeably, single-shot GSP performs comparably or better than DH. Particularly, a higher sparsity of 85.75% with the same accuracy drop of 0.42% compared to DH. For the ResNet-1100 architechlure, we find that even with a higher sparsity of 85.90% we achieve lower accuracy drop compared to DH. Subsequently, even after pushing the single-shot GSP sparsity to 90.72%, the accuracy drop was only 1.17%, still lower than DH's 1. 1.24% at 83.94% sparsity. This result even more salient as DH relies on an extra aparsity-inducing regularizer phase with 164 epochs of training to first induce sparsity, and then pruncs the model with a threshold followed by finetuning for similar number of epochs. In contrast, we use a preset. sparsity value for GSP, project a pretrained model once, and finetune the surviving weights.
notice that for the ResNet-56 architecture, single-shot GSP achieves
Summary of the numerical experiments We have shown that GSP in the NMF application performs competitively with state-of-the-art approaches on image data sets without the need to tune the sparsity parameters and outperforms them on syuthetic and sparse data sets In deep network pruning, the use of GSP leads to sparser and more accurate networks hout extra training time needed to tune sparsity parameters. On ImageNet data with ResNet50 model GSP outperforms a large number of existing approaches. It also demonstrates superior performance when used for single-shot pruning.
6 Conclusion
We proposed novel grouped sparse projection algorithm which allows us to project a set of vectors to a set of sparse vectors whose average sparsity is controlled via single interpretable parameter. This parameter should be carefully chosen by the user to obtain a good tradeoff between the sparsity of the projected vectors and how well they approximate the original input vectors; see, c.g., Table 1 and Figure 2 in the context of pruning deep neural networks. We provided theoretical guarantees for the uniqueness of the solution of the dual problem which is also shown to correspond to the uniqueness of the primal solution. Additionally, we proposed an efficient algorithm whose running time is shown to be linear in the size of the problem. We demonstrate the efficacy of the projection in two important learning applications, namely in pruning deep
12

---

Published in Transactions on Machine Learning Research (10/2022)
Methods
Architecture
Spansity%
Accuracy%
Drop %
Induced GSP
R6sNet-56
88.33
92.04
1.09
DII
ResNet-56
84.64
92.71
0.42
Single-shot GSP
ResNet-56
85.78
92.71
0.42
Induced GSP
Resuet-110
95.18
92.67
0.95
DH
RosNet-110
83.94
92.76
1.24
RosNct-110
85.90
92.86
0.76
Single-Shot GSP
RosNet-110
90.72
92.45
1.17
Sparsity vs drop in accuracy for ResNet-56 and ResNet-110 for single-shot and induced GSP (our algorithms) in comparison to DeepHoyer (DH) in the CIFAR-10 dataset. GSP with single projection produces a model with comparable or better sparsity vs accuracy trade-off than full pipeline of DeepHoyer's regularized training and finetuning, The best sparsity-accurac trade-off compared to DH are reported in bold.
Table 2:
neural networks and sparse non-negative matrix factorization and validate it on wide variety of datasets. However, projection is not limited to the listed applications and could also be used in dictionary learning, sparse PCA, and in different types of neural network architectures. We expect the proposed group sparse projection operator to have wide applicability given the interpretability of the sparsity mcasure, practical efficiency of the projection, and strong theoretical guarantees.
Acknowledgement
We thank the action editor and the three reviewers for their insightful comments that helped us improve the paper significantly.
This study was in part supported by NIH MH129047, NIH DA040487, NIH MH121885 and NSF 2112455.
Nicolas Gillis acknowledges the support by the Fonds de la Recherche Scientifiquu FNRS and the Fonds Wetenschappelijk Onderzock Vlanderen (FWO) under EOS Project no 0005318F-RG47, and by the Francqui Foundation.
Niccolò Dalmasso, Sameena Shah and Vamsi K. Potluru at the time of publishing are at JP Morgan AI Rescarch. This paper was prepared for information purposes by the AT Research Group of JPMorgan Chase & Co and its affiliates ("J.P. Morgan"), and is not a product of the Research Department of J.P. Morgan. J.P. Morgan makes no explicit implied representation and warranty and accepts no liability, for the completeness, accuracy reliability of information, or the legal, compliance, financial, tax or accounting effects of matters contained herein. This document is not intended as investment rescarch or investment advice, or a recommendation, ofler or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction, and shall not constitute a solicitation under any jurisdiction or to any person, if such solicitation under such jurisdiction such person would be unlawful.
References
Aharon, M., Elad, M., and Bruckstein, A. K-SVD: An algorithm for designing overcomplete dietionaries for sparse representation. IEEE Transactions on signal processing, 51(11):4311-4222 2006.
Arnob, S. Y., Ohib, R., Plis, S., and Precup, D. Single-shot pruning for offline reinforcement learning. ar preprint ar Xic:21112 15579, 2021.
Beck, A. and Teboulle, M. fast iterative shrinkage-tlreesooking algorithm for linear inverse problems. STAM Journal on Imaging Sciences, 2(1):183 202, 2009.
Bolte, J., Sabach, S., and Teboulle, M. Proximal alternating lincarized minimization for nonconvex and nonsmooth problems. Math. Program., 146(1-2):459 494, 2014. doi: 10.1007/110107-013-0000011
Candès, E., Romberg, J., and Tao, T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEFF Transactions Information Theory, 52(())489-5))) -509, 2006.
13

---

Published in Transactions on Machine Learning Research (10/2022)
Cerebras. Wafer Scale Engine: Why We Need Big Chips for Deep Learning. http:://cerebrrs.net//bugg cerebras-wafer-scate scale- wwwpr-eaeeeeeeeeeeeeeeeeeee
-ewe---e-------s---------------- -orp-s-oo-de-e--ernnnneee 2019.
Chen, T., Frankle, J., Chang, S., Liu, S., Zhang, Y., Wang, Z., and Carbin, M. The lottery ticket hypothesis for pre-trained bert networks. Advances in neural information processing systems, 33:15834-15844 2020.
Chen, T., Frankle, J., Chang, S., Liu, S., Zhang, Y., Carbin, M., and Wang, 7. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pottern Recognition, pp. 16306-16316, 2021.
Condat, L. Fast projection onto the simplex and the l ball. Mathematical Programming, 158(1):575 585, 2016.
d' Aspremont, A., El Ghaoui, L., Jordan, M., and Lanckriet, G. A direct formulation for sparse PCA using semidefiiite programming. STAM Review, 49(3))434-446) 2007.
Donoho, D. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289 1306, 2006.
Donoho, D. L. De-noising by soft-thresholding. IEEE transactions on information theory, 41(3):613-627, 1995.
Duchi, J., Shalev-Shwarz, S., Singer, Y., and Chandra, T. Efficient projections onto the e--ball for learning in high dimensions. In Proceedings of the 25th international conference on Machine learning, pp. 272 279, 2008.
Elad, M. Why simple shrinkage is still relevant for redundant representations? information theory, 52(11):5559-5556 2006.
IEEE transactions on
Elsen, E., Dukhan, M., Gale, T., and Simonyan, K. Fast sparse convnets. In Proceedings of the IEEE/CT /VF conference on computer vision and paltern recognition, pp. 14629 14638, 2020.
Frankle, J. and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Gafni, E. M. and Bertsekas, D. P. Two-metric projection methods for constrained optimization. SIAM Journal on Control and Optimization, 22(6):936-964, 1984.
Gillis, N. Sparse and unique nonnegative matrix factorization through data preprocessing. Journal of Machine Learning Research, 13(Nov):3349 3386, 2012.
Gillis, N. Nonnegative Matrix Factorization. SIAM, Philadelphia, 2020.
Gillis, N. and Glineur, F. Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization. Neural compulation, 24(4):1085 1105, 2012.
Guan, N., Tao, D.,, Luo, Z., and Yuan, NcNMF: An optimal gradient method for nonnegative matrix factorization. IEEE Transactions on Signal Processing, 60(6):2882 2898, 2012.
Guo, Y., Yao, A., and Chen, Y. Dynamic network surgery for efficient DNNs. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS'16, pp. 1387-1395, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
Han, S., Pool, J., Tran, J., and Dally, W. J. Learning both weights and connections for efficient neural networks. arxiv preprint ar Xiv: 02626, 2015.
Han, S., Mao, H., and Dally, W. J. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In Bengio, Y. and LeCun, Y. (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Hassibi, B., Stork, D. G., and Wolfi, G. J. Optimal brain surgeon and general network pruning. In IEEE international conference on neural nebworks, pp.
TEEE, 1993.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEFE conference computer vision and pattern recognition, pp. 770-778, 2016.
Ho, N.-D. Nonnegatine Matriz Factorization Algorithms and Applications. PhD) thesis, Université catholique de Louvain, 2008.
Hoyer, P. O. Non-negative matrix factorization with sparseness constraints. Journal of machine learning research, 5(Nov):1457 1469, 2004.
Hurley, N. and Rickard, S. Comparing measures of sparsity. IEEE Transactions on Information Theory, 55 (10):472344744 2009.
Hyvärinen, A. Sparse code shrinkage: Denoising of nongaussian data by maximum likelihood estimation. Neural compulation, 11(7):1739 1768, 1999.
Janowsky, S. A. Pruning versus clipping in neural networks. Physical Review A, (9(1))66600, 1989.
Journée, M., Nesterov, Y., Richtárik, P., and Sepulchre, R. Generalized power method for sparse principal component analysis. Journal of Machine Learning Research, 11(Feb):517-553, 2010.
Kim, and Park, H. Sparse non-negative matrix factorizations via alternating non-regaatvityy-cosstraaad least squares for microarray data analysis. Bioinformatics, (3(12))14455 149-- 2007.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Kummer, B. al. Newton's method for non-differentiable functions. Advances in mathematical optimization, 45(1988):114-122 125,, 1988.
LeCun, Y., Denker, J. S., and Solla, S. A. Optimal brain damage. In Advonces in neural information processing systems, pp. 598 598-605, 1990.
Lee, D. and Seung, H. Learning the parts of objects by non-negative matrix factorization. Nature, 401 401 (6755): 788, 1999.
Lee, N., Ajanthan, T., and Torr, P. H. S. Snip: Single-shot network pruning based on connection sensitivity. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Liu, H., Wang, H., and Song, M. A unified approach for projections onto the intersoction of l and lg balls spheres. arXio preprint arXiv:111 1. 0.994,, 2019.
Louizos, C., Welling, M., and Kingma, D. P. Learning sparse neural networks through tn regularization. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Conada, April 30 May 3, 2018, Conference Track Proceedings, 2018.
Luo, J.-H., Wu, J., and Lin, W. Thinet: A filter level pruning method for deep neural network compression. In Proceedings of the IEEE international conference on computer vision, pp. 5058 5066, 2017.
Ma, R., Miao, J., Niu, L., and Zhang, P. Transformed 4 regularization for learning sparse deep neural networks. Newral Nelworks, 119:286 298, 2019.
Pock, and Sabach, S. Inertial proximal alternating linearized minimization (ipalm) for nonconvex and nonsmooth problems. SIAM Imaging Sci., 944: 1787, 2016. doi: 10.1137/16M1064061.
Pool, J., Sawarkar, A., and Rodge, J. Accelerating Inference with Sparsity Using the NVIDIA Ampere Architecture and NVIDIA TensorRT. https://developer oppr mwwdiaiiicmmmmmm www.ia.co./blog//eeeeeeeeeeeeeee httpa/////////c/cleeeriiigggggg/ inference- wi sth-sppasitt--uiinge wwwpr/ussiniaame-aaanneeeee
2021.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Potluru, V. K., Plis, S. M., Roux, J. L., Pearlmutter, B. A., Calhoun, V. D., and Hayes, T. P. Block coordinate descent for sparse NMF. In Bengio, Y. and LeCun, Y. (eds.), 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Conference Track Proceedings, 2013.
Reed, R. Pruming algorithms-a survey. IEEE transactions Neural Networks, 4(6):740-747, 1993.
Renda, A.; Frankle, J., and Carbin, M. Comparing rewinding and fine-tuning in neural network pruning. arXiv preprint 0rx: 02389, 2020.
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, L. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), (15(3)2211-2555 2015. doi: 110007/s11663-05-00166666
Sokar, G., Mocanu, E.,, Mocanu, D. C., Pechenizkiy, M., and Stone, P. Dynamic sparse training for deep reinforcement learning. arXiv preprint arxiv;2106. 04217, 2021.
Tanaka, H., Kumin, D., Yamins, D. L., and Ganguli, S. Pruning neural networks without any data by iteratively conserving synaptic flow. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Newrul Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020.
Thom, M., Rapp, M., and Palm, G. Efficient dictionary learning with pparseness-enforee projections. International Journal of Computer Vision, 114(2-3):168-194 2015.
Tibshirani, R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267 288, 1996.
Wang, C., Zhang, G., and Grosse, R. B. Picking winning tickets before training by preserving gradient flow. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Yang, H., Wen, W., and Li, H. Deephoyer: Learning sparser neural network with differentiable scale-invariant sparsity measures. In 8th International Conference on Learning Representations, TCLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Yu, A. W., Su, H., and Fei-Fei, L. Efficient euclidean projections onto the intersection of norm balls. Tn Proceedings of the 29th International Conference Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26- July 2012. ieml.ec / Omnipress, 2012.
Yu, R., Li, A., Chen, C.-F., Lai, J.-H., Morariu, V. I., Han, X., Gao, M., Lin, C.-Y., and Davis, S. Nisp: Pruning networks using neuron importance score propagation. In Proceedings of the IEFE Conference Computer Vision and Pattern Recognition, pp. 9194 0194-9203, 2018.
Yun, J., Zheng, P., Yang, E., Lozano, A., and Aravkin, A. Trimming the & regularizer: Statistical analysis, optimization, and applications to deep learning. In International Conference on Machine Learning, pp. 7242 7251. PMLR, 2019.
Zhu, M. and Gupta, S. To prune, or not to prune: Exploring the efficacy of pruning for model compression. In 6th International Conference on Learning Representations, ICLR 2018, Voncowver, BC, Canada, April 30 May 3, 2018, Workshop Track Proceedings, 2018.
Zhuang, Z., Tan, M., Zhuang, B., Liu, J., Guo, Y., Wu, Q., Huang, J., and Zhu, J. Discrimination-avann aware channel pruning for deep neural networks. arxiv preprint Xrx:o:1810, .. 1 11809, 2018.
16

---

Published in Transactions on Machine Learning Research (10/2022)
Appendices
A Hoyer Sparsity Measure and Grouped Sparse Projection
A.1 The Hoyer Sparsity Measure
In section 2.1 we discussed the Hoyer sporsity measure (Hoyer, 2004) for a given vector æ E R" and for x + 0 and n > 1, we defined the sparsity of æ as
sp(x) = VT a
E [0, 1).
(11)
The above measure has the following properties, which we list here for completeness:
We have that sp(x) = > ||||| = v < s(i) = for all i and for some constant b, while sp(x) = + ||0||o = 1, where ||æ||o counts the number of nonzero entries of x.
One of the main advantage of sp(x) compared to | is that sp(x) is smooth over Rn apart from a mcasure-zero set, i.e., when z = 0 or z<i) 0 for any i. For example, with this mcasure, the vector [1, 10-1001,10 10- is sparser than [1, 1, 0], which makes sense numerically as [1, 10-6, 10-6) is very close to the 1-sparse vector [].
sp(x) is invariant to scaling, that is, sp(r) sp((xr) for any + 0. 1
Note that for any two vectors and 2, sp(w) sp(2)
Note also that sp(x) is not defined at 0, nor for 1.
is non-increasing under the soft thresholding operator: Given a vector and parameter 2 0, it. defined as st(x, A) sign(x) o | where is the component-wis multiplication, and [+] is the projection onto the non-negative orthant, that is, max(0..).
A.2 Comparison to typical formulations
We discuss how the GSP formulation compares with two typical approaches sparsify set of vectors:
The most popular method to make set of vectors sparse is arguably to use & penalty terms, solving
Σ lc Σ/1c
min
2 A111zila
REER LISiS
for which the solution is given by the soft thresholding operator, . = st(c,, 1 Asiss This is widely used in algorithms for compressed sensing and for solving inverse problems (in particular, to find sparse solutions to an underdeternined linear system); see, e.g., Beck & Teboulle (2009). The use l penalty to obtain sparse factors in low-rank matrix approximations is also arguably the most popular approach; see, e.g., Kim & Park (2007); Journée al. (2010).
The main drawback of this approach is that the parameters A; needs to be tuned to obtain a desired sparsity level, As we noted, our projection resolves this drawback.
Using the method of Thom et al. (2015) that projects a vector onto vector with a desired level of sparsity, that is, solves (3), we could either project each vector e; independently but then we would have to choose a priori the sparsity level of each projection Iz. We could also project the single
vector [ei; "giegi...ee)) E R "i stacking the c,'s on top of one another. However, some vectors c:
17

---

Published in Transactions on Machine Learning Research (10/2022)
could be projected onto zero, which is not desirable in some applications; for example, in low-rank matrix approximation problems this would make the matrix with x; s as its columns rank deficient. More pertinently, in the scenario of learning sparse deep models, stacking all the layers together and projecting them this way would result in the projection of all the parameters of layer onto zero, also known as layer-collapse (Tanaka et al., 2020), which makes the model untrainable.
A.3 Properties of g(u) and edge cases
In section we discussed that the optimization problem to be solved to compute E(p) in (6) is separable in the variables xys, and that it can be solved individually for each 24. We denoted the optimal solution of the (6) with siju] and noted that there are two possible cases, depending on the value of μ. We noted that unless the solution for f is feasible (which can be checked easily), we need to find the value of f such that.
g(m) Σ 3.1 3.1xauul k. = 0,
that is, we need to find a root of g(u) (if 1 > j then the zs[u] are all 1-sparse).
In section-3 we explored possible ways to find this root of g(u), including using bisection and Newton's 's method. The reason to use bisection is mostly to avoid points of difeeeeferattialllity and local stagnation of Newton's method because of discontinuity. The discontinuous points be pre-computed and corresponds to the largest entries of the q's when they not uniquely attained. We have denoted DD the set of discontinuous points of s()) in Algorithm 3: if discontinuous point is encountered, the algorithm returns such that g(H + Ep) < 0 < g(p ([u--e] eq). Note that the accuracy e does not need to be high in practice, say 0.001, since there will not be a significant. difference between a vector of sparsity 8 and sparsity 8 + 0.001.
Finally, we also provide a fast vectorized GPU-compatible implementation of the Algorithum 1 in Py Torch along with the supplementary materials, where we parallelly project all the vectors together for application in deep neural networks. Since, the Newton's method converges quickly (sce Table 3), empirically observed fast execution of the the projection of deep networks.
A.4 Computational Cost
As detailed in Section 3.4, the computational cost of the algorithm is O(tN), where N N n, and t is the number of iterations in Newton's method. The computational cost per iteration is therefore linear in the size of the problem. In practice, we observed that Netwon's method converge very fast and does not require much ilerations, as showcased by the following synthetic data example. Let us take = 1000 for all ie [1, 100] and generate each entry of the e using the normal distribution N(0, 1). For each sparsity level, we generate 100 such data points and Table 3 reports the average and maximum number of iterations needed by Algorithm 1. In all cases, it requires less than 4 iterations for a target accuracy of e 10-4.
8g
8 = 0.7
8 = 0.8
s 0.9
$ = 0.95
0.99
Average
20.86%
3.88
3.78
3.98
3.75
3.77
Maximum
21.01%
4
4
4
4
4
Table 3: Average and maximum number of iteration for Algorithm 1 to perform grouped sparse projection of 100 randomly generated vectors of length 1000, with precision = 10-4, The column su gives the average and maximum initial sparsity of the 100 randomly generated vectors x,,s
B Grouped Sparse Projection
In this section we detail the calculations in the proof of Corollary 3.3.
Proof. If p=p=00 0 and μ > fi, the projection unique provided the largest and second entry of each |c:| are not equal (see Section 3.3). For μ < n. since the optimal J² is unique it suffices to prove an [r] is one-to-one
18

---

Published in Transactions on Machine Learning Research (10/2022)
mapping, ie., that if ss[mr] zı[p2] then μ41 A2- As noted in Section 3.2, when |c| - 1,,,1 S the solution vi[n] is unique corresponding to the largest entry of |cal - as long as the largest entry is unique.
We now analyse the last scenario, in which |cy| ,4 > 0 (with 0 < < p.). For simplicity of notation, we assume all indexes j of the vector |ca] are active, i.e. [ca - p3, > 0 Vj. The derivations would follow in an analogous way the case of some indexes being zero-d out, with sums and norms only including the active indexes. Let's consider μt, #2 such that M1, 14, and consider the j-th index of xi[un] and x; x;[ug] respectively.
=i(mi]() = (i)
|c,(i]| 11 |c(1]] - 4225
|||e|] - 11B:l12 |||al - M23ill2
(1c(1)) 110--11 1114)2 - (la) 1223) 123;)) = (1c(5) 22 3,) - 11.,)² 11111)
lc:(i)² + m?33 - 2)a(1)) (11a113 - - - 2228ilcil =
P233 -21c (11.1++ + 2/13//cs/7e))
((()) - + 2e
37 1a -τ)) + 2p 12 mi)
+ +2la())llo(((3(()22>->) m1) 2ppp)))))))))))) -22) =
(n3 Mt) [4()))n - [|c
(12)
( - p2) |c: P1o - -160)/ a22a =0
(n3 15) (c(j))n - |al2 + 2p1 p2) (l((0)))) ||c]]]]
(13)
+ (M -22) |c00)) | lc -0
(M1 p2)
|| - n 22 + [n++M2882
+23; |40)% (alll
(A)
(B)
(C)
For the equation above to be equal to zero, given (11 42. > 0, cither the terms (A) = (B) = (C) =
or #l = 122- Note that if (A) and (B) are equal 0 then (C) 0, hence we just need to check when
(A) = (B) We have that:
{ (A) (A)=0 0 - f a(j) 1a(0)nn ||all= -
(G)) || /a
-B)=0
|c(0i = Iall
This implics the vector &; needs to have all entries equal to the same value in every active index j. As by assumption this cannot be case the largest entry of & needs to be unique and distinct - we have that #1 u2 and we have proved that [n] is a one-to-one mapping.
C Weighted Grouped Sparse Projection
C.1 Weighted Sparsity
In section 4 we introduced the notion of weighted sparsity: For vector Ry and given E R following
||1|| Walli |
sp.. (I)
[0, 1], where W diag(w) (w)
(14)
||l||2 min, wiii
Let make some observations about this quantity
19

---

Published in Transactions on Machine Learning Research (10/2022)
We have
|
max l
[Wyll
and
min w(i) = min [Wlll, Ivll==
which implies the fact that sp.. E [0, 1] for any
For w = 1, we have ||W(+))l = II(-)II,, ||w]22 = v and min, w(1) = 1 so that sp(.) = spp (-).
(x) = if and only if x is 1-sparse and its non-zero entry corresponds to (one of)) the smallest.
entry w. Therefore, a vector æ can be 1-sparse but have low weighted sparsity (p) the corresponding entry of is large.
||>|]| is norm if and only w > 0, which we do not require in this paper but use this notation for simplicity.
This notion of weighted sparsity allows to give more or less importance to the entries of x to measure its sparsity. For example, having w(j)) means that there no need for =(j) to be sparse (that is, close or equal zero) as it is not taken into account in sww (3), while taking w(j) large will enforce z(j) be (close to) zero if (x) is large (that is, close to one). In the remainder of this paper, we will say that vector x is w-sparse if it has large weighted sparsity (x). The following example provides a potential application of projecting a set of vectors onto w-sparse vectors.
C.2 Weighted Group Sparse Projection
We defined the w-sparse projection problem of the set of vectors fcr E R in (WGSP), where fw; E H== was the nonzero nonnegative weight vectors associated with the g's with a target average weighted
sparsity sn E [0.
As for 5, the maximum of (WGSP) is attainod. Similarly, as for (5), we can derive formula for x, depending the Lagrange variable μ associated with the inequality constraint:
1. For |cil p3 wa E 0, we have
[|cal M3
ad[a] =
||[ca] 1 m
2. For |cal p.0"' wi S 0, Zz [u]u]] is 1-sparse. The nonzero entry of 23[M] corresponds to the largest entry of |c,1 - 1, w, In this case, since the entries of w, might be distinct, this non-zero entry does not necessarily correspond to the largest entry of |cj] and may change as increases. In particular, for p large enough, the nonzero entry of zılua] will correspond to the smallest entry of wi.
We need Ei= 37" uf [ [u[u]] to be smaller than ky, that is,
Iw (M) = Σ 3.hh of x.[m]] knt" 5..
1=1
If gu (0) < 0, then <=[0] than ). Otherwise, the constraint will be active and we need to find a root n² of (4). Unfortunately, as opposed to GSP, the function (w) is not necessarily strictly decreasing for js sufficiently small: when - 1c,1-,,,,"v w; < and as μ increases, the u-sparsity of c; may change abruptly as the index the maximum entry of |c - 1137 wi may change as μ increases. In that case, the term correspouding to e in gw) is piece-wise constant. For example, let e = [4, 1] and w; = [2, 1], we have
Jccl ||||
Tc: optimal and the problem solved (the 0z's 's have average w-sparsity larger
For 8 E (1, (x.(())) ssp ([1, 0)) Vō-1 0.19.
/
For 8 2, sp. (I: (p.. 0, 1)) = 1. However, when |G| 11 wi & 0 for some i, (p) is strictly decreasing.
20

---

Published in Transactions on Machine Learning Research (10/2022)
Figure 3: Basis elements obtained with sparse NMF (left) and weighted sparse NMF (right).
C.2.1 Example Application on Facial Images
Let consider the case when the 2; 's represent set of basis vectors for (vectorized) facial images. Tn this case, one may want these basis vectors to be sparser the edges since edges are less likely to contain facial features; see, e.g., Ho (2008). Let us illustrate this on the ORL face data set (400 facial images, each 112 by 92 pixels). Each column of the input data matrix Y represents a vectorized facial image, and is approximated by the product of XH where X and H are nonnegative. Each column of W is a basis elements for the facial images. We first apply sparse NMF with average sparsity of 60% for the colurnss of basis matrix X. The basis elements are displayed on the left of Figure 3.
Given basis image 112 by 92 pixcls, define the weight of the pixel at position (i.j) with = 5 in Chapter 6 of Ho (2008). The further away from the middle of the image, the more weights we assign to the pixel so that the basis images are expected to be sparser on the edges. According to these weights, the average weighted sparsity of the sparse NMF solution is 89% (in fact, we notice that most basis images are already relatively sparse on the edges). Then, we run weighted sparse NMF (WSNMF) with average weighted sparsity 95%. The basis elements are displayed on the right of Figure 3. We observe that, as expected, the edges are in average even sparser compared the unweighted case (note that the only WSNMF basis element that is not sparse on the edges, the third image, has darker pixels in the middle of the image to compensate for the relatively lighter pixels on the edges). This is confirmed by Figure 4 which displays the average of the columns of the squared error for both solutions, that is, it displays the average of the columns of the squared residual (Y - XH)², The residual of WSNMF is brighter on the middle of the image (since the basis elements are less constrained to be sparse in this area) and darker at the corners. fact, most of the error WSNMF concentrated in the four corners.
Observe also that the basis elements of WSNMF are denser: in fact, the (unweighted) sparsity of WSNMF is only 50%. The relative errors, that is, [Y-XH||e for both approaches are similar, 20.34% for sparse NMF and 20.77% for WSNMF.
[
21

---

Published in Transactions on Machine Learning Research (10/2022)
Figure 4: Average squared error obtained with sparse NMF (left) and WSNMF (right) -the darker, the higher the error.
C.3 Theoretical Results
We now provide theoretical proofs for the solutions of the problem 4, as well as proof Theorem 3.2 for GSP. Lemma C.1 provides proof for the solution of the dual problem for general weighted sum of x æ[μ]], from which both results follow.
Lemma C.1. Let w E R8 and x E IR4. Let also [a(T) w x1>]] where
x yw $ 0, that is, i < 5 = max, w(y) then
z(i)
[x 7w]
x|>| = [ --w] + l12
Otherwise x1>1] is 1-sparse vector, with its nonzero entry equal to one and at position j E argmax, x(1)= -w]().
For 0 S. <, falr) is strictly decreasing, unless x is mulliple of w in which case it is constant. Por r 2 5, sa()) is nonincrensing and piece-wise conslant.
Proof. The case 2 y is straightforward since fa(7) wj for argmax, (a(j) - >ww())) as 7 increases, the selected wy can only decrease since w 2 O.
Let us now consider the case 0 S 7 R. Clearly, fz(7) continuous since it is a lincar function of æh>] which is continuous, and it is differentiable everywhere except for y a(j for some j. Therefore, it suffices to show that f'()) is negative for all 7 A =(3) Note that f()) strictly decreasing if and only if ())()) is strictly decreasing for any constants C1, C2 > 0. Therefore, we may assume without loss of generality (w.loog.) that ||l||2 = (replacing w by w/|lw][2) We may also assume w.l.o.g. that x yw otherwise we restrict the problem to xJJ where J(7) = (z]) (w(s) 0} since f depends only on the indices in in the case 7 < 5. Under these assumptions, have
z(i)
w (x yw)
wT x 7 || ywo 12
f(7)
|| ywll2
since ||m|| = TTu. w 1, and
f(() -||x - -ool + (w x - 7) w (x 700)11 yw0
||
ywl 2
-||x
ywl
(w Fx )2
yw]
22

---

Published in Transactions on Machine Learning Research (10/2022)
It remains to show that || ywl1 1B (w - 7) implying (n) < 0. We have
- - = ||:|| 2yw² T xr + t2
and
(w x - x)² = =(w" x)² - 2yw' + 7² which gives the result since |' x|| |||||||ا||| = ||œ||2 for a not a multiple of w.
Proof of Theorem 1. The proof follows from Lemma C.1 by sctting w = 1 and noting that g(4) Em (B,p) - -ss Note that since w(f) = Vj, the index of the maximum element remains the same.
Corollary C.2. The function Iw (11) = Ei= wf xels4] - kg as defined above is nonincreasing. Moreover, if [eal - 133 wi & 0 for some i, it strictly decreasing.
Proof. This follows from Lemma C.1 since (w( = Ei (3, k."
Therefore, as opposed to g(H), (w) could have an infinite number of roots μ*, However, the corresponding 24(1") is unique so that non-uniqueness of μ is irrelevant. Morcover, this situation rather unlikely happen in practice since it requires |cl (41-p3,mme we for all i at the root of (w(p)) hence it requires 8h to be close to one (that is, knr to be large). Similarly as for 9: Iw will be discontimuous at the points where els) max, 3,,,(3) is not uniquely attained: as y increases, the two (or more) last non-zero entries of xy sy[n]] become zero simultaneously. Finally, to solve WGSP, we can essentially use the same algorithm as for GSP, that is, we can easily adapt Algorithm to find a root of 9u (1).
D Sparse NMF: Experiment Details
In this section, we provide experiment parameters and details for the sparse NMF experiments.
D.1 Synthetic data sets
For the experiment on synthetic data, we take m = n = 100 and r = 10. We generate each entry of X using the normal distribution with mean 0 and variance and then set the negative entries to zero, so that X will have sparsity around 50%. We generate each entry of H using the normal distribution the interval [o, 1]. To run gspNMF and cgspNMF, we compute the average sparsity of the columns of the true X and use it input. We generate 50 such matrices, and use the same initial matrices for all algorithms, which were generated using the uniform distribution for each entry. In Figure 1 of the paper, we reported the evolution of the average of the relative error oblained by the different algorithms among the 50 randomly generated matrices.
D.2 Image data set
For this set of experiments we test on the widely used data set in the NMF literature, the CBCL, facial images. This dataset consists 2429 images of 19 x 19 pixels, and was used in the seminal paper by Lee & Seung (1999) with r = 49. We run the sparse NMF techniques with sparsity 85% Using 10 random initializations, Figure (in paper) reports the evolution of the average relative error, and Figure displays the basis elements obtained by different mothods.
E
Deep Network Pruning with GSP: Experiments, settings and hyperparameters
E.1 Experiments on CIFAR-10
We use the CIFAR-10 dataset (Krizhevsky et al., 2009) to train and test the VGG16, Resnet-56 and Resnet- 110 models for experiments. The CIFAR-10 dataset accessed through the dataset APT of the torchvision
23

---

Published in Transactions on Machine Learning Research (10/2022)
Figure 5: Basis elements obtained with NcNMF (top left), PSNMF with sparsity 0.85 (top right), & A-HALS with sparsity 0.85 (bottom left), ePSNF with sparsity 0.85 (bottom right).
package PyTooch. We performed the standard preprocessing on the data which included horizontal flip, random crop and normalization on the training set. With the CIFAR-10 dataset we perform two different types of experiments. First, perform experiment with layerwisc induced GSP integrated with the training phase. We also perform single shot pruning with single projection of the model weights followed by the finetuning phase in section 5.3.
For the experiments with intermittent projections during the training phase, we project the weights of the VGG16 model using GSP with sparsity level s, perform a forward pass on the projected weights and finally update the model parameters using backpropagation every 150 iterations for 200 epochs, starting from epoch 40. We reduce the learning rate by factor of 0.1 at the milestone epochs of 80, 120 and 160. Next, we set the fraction of the lowest parameters of the model to zero. At this point the model is sparse with layerwise hoyer sparsity of However, since project intermittently and with hoyer sparsity being differentiable approximation to the to norm, we then prune the surviving weights that are close to zero or zero, kceping the largest 3 fraction of the parameters, where & is the final sparsity of the model. We fix these pruned parameters (do not train them) with a mask. Finally, we finetune the surviving parameters for 200 epochs with a learning rate of 0.01 and dropping the rate by 0.1 in the same milestones the sparsity inducing run. In the case of single shot GSP, we take a pretrained model, make a single projection of the layers with a sparsity and then prune and finetune the model with similar parameters above.
24

---

Published in Transactions on Machine Learning Research (10/2022)
E.2 Experiments ImageNet
In these set of experiments, use the ImageNet dataset (Russakovsky el al., 2015) to train and test the Resnet-50 model for our experiments. ImageNet is augmented by normalizing per channel, selecting patch with a random aspect ratio between 3/4 and 4/3 and a random scale between 8% to 100%, cropping to 224x224, and randomly flipping horizontally.
For the experiments with induced-GSPp we project the weights of the ResNet50 model in similar technique to the experiments performed with the CIFAR-10 dataset. We first project the layers of the model using GSP with = 0.80, perform forward pass the projected weights and finally update the model parameters using backpropagation every 500 iterations for 120 epochs. We start the projection of the model from epoch 40 and keep projecting every 500 iterations till the final epoch. In both the cases of CIFAR-10 and ImageNet we choose the iteration interval of projection in such a way so that there are projections per epoch. We reduce the learning rate by a factor of 0.1 at the milestone epochs of 70 and 100. Next, we set the fraction of the lowest paramcters of the model to zero. We next prune the surviving weights that are close to zero or zero, keeping the largest 1 fraction of the parameters, where is the final spansity of the model. Finally, finetune the surviving parameters for 140 epochs with learning rate of 0.001 and dropping the rate by 0.1 in the same milestones as the inducing-GSP run.
25


Reviews:
[{"review_id": "yda0YTGvZn", "reviewer": "Reviewer_Ycco", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper addresses the sparse learning problem which is important for efficient large-scale and also interpretable machine learning. The paper discusses relevant prior works in the literature adequately. The writing is fine (up to a point before the main methodology), although there are parts missing details. It is interesting that the method can avoid the cost of searching for the optimal regularization parameter and tunes the level of sparsities over a set of vectors quite automatically, although the authors don’t seem to analyze more about how it helps in terms of interpretable feature learning. The single-shot GSP is interesting provided that it does not require the sparsity-inducing optimization step and this can be quite significant from the compression point of view.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper develops a sparse projection method called Grouped Sparse Projection (GSP) by which a set of feature vectors can be learned to be sparse. The problem is formulated as a sparsity inducing optimization based on the Hoyer sparsity measure. The approach develops further into a dual problem such that the sparsity parameter can be set for a group of vectors without having to learn individually for each vector, in which the authors use Newton’s method to compute $g(\\mu)$ and $g'(\\mu)$. The authors also provide some variants to fit some different scenarios such as weighted GSP or single-shot GSP. The method is evaluated on nonnegative matrix factorization and neural network pruning tasks and achieves competitive results to the alternative approaches.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* Section 1 makes a point about the contribution in a high-level view, but misses some technical details about the proposed methodology.\n“Projections” in Subsection 1.1 appears to be incomplete, sounds arbitrary, or doesn’t really deliver much insight into how it is related to the proposed work.\n“Contributions” in Subsection 1.2 needs to discuss how Newton’s method is being used.\nAlso include that the problem is being solved in the dual, and how this is related to the sparsity parameter.\nDiscuss how significant it is to have the characterization of the optimal solution (that is on the uniqueness).\nThe proposed method “group sparse projection” is quite vague as it can refer to any existing prior work on group sparsity.\n\n* Section 2 (Background on sparse projection) is a good place to discuss background material, but has a lot of room for improvement.\nSubsection 2.1 doesn’t quite work as “problem definition”; instead it explains what is the Hoyer measure and its properties (continuing in the appendix); rather it is defined in Subsection 2.1 where the authors explain the sparse projection as an optimization problem; this section needs organizing.\nThis section needs to provide more explanations on how the soft thresholding operator has to do with the sparse projection and the Hoyer measure to fill the gap in the background materials.\nPerhaps move “Notation” here from the introduction.\n\n* Section 3\nDiscuss why the problem has to be re-formulated and solved in the dual, perhaps with the link to the sparsity parameter.\nDiscuss why Newton’s method is necessary and the background on Newton’s method including the initialization, bisection method, etc.\nDiscuss what it means to have nonzero x (as in the case for neural networks; as opposed to the nonnegative matrix factorization) for the proposed method.\nPerhaps also discuss how it compares to the sparse group Lasso (this can be put in the previous sections).\n\n* Section 5\nProvide a lot more details on the baselines of NMF. It is not clear whether or not the speedup gain in the convergence comes from the proposed idea of group sparsity or Newton’s method; when it is compared to NeNMF.\n\n* Other technical details\nDiscuss in detail how one sets the desired sparsity level both in the algorithm and for experiments.\n\n-- After authors' response\nI have read the authors response and the update made on the manuscript. My major concern was on clarifying the methodologies, and I think the authors have made quite significant (and positive) changes as to improving the paper.", "broader_impact_concerns": "No concerns I have.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2xxXcNnoih", "reviewer": "Reviewer_AMJx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength\n1. The paper brings up important research question on performing explicit sparse projection with group sparsity constraint, and provides an effective solution\n2. The derivation on the GSP problem formulation and solution is solid\n3. The paper shows convincing experimental results on the effectiveness of the proposed method\n4. The paper is well written and easy to follow\n\n### Weakness\n1. The theoritical contribution needs further clearification. From the description of Section 3.1 and 3.2 seems like the formulation and solution of GSP borrowed technique from the cited (Thom et al., 2015) paper. As this theortical derivation serves the main contribution of this work, it is suggested to clearly identify which part of the formulation or solution is derived from (Thom et al., 2015), and what is unique for the proposed method. Something worth discussing would be (1) if the technique of converting Hoyer to L1 by normalizing the L2 norm in problem formulation is novelly proposed, and (2) what is the major difference in solving for group projection vs. single vector projection?\n2. This work mainly focus on using Hoyer measure for sparsity constraint. Meanwhile it would also be possible to use L1 (group LASSO) or L0 (magnitude pruning) as explicit sparsity constraint for the GSP problem, which will lead to simpler and more efficient solutions. It's suggested to explicitly discuss and compare with these schemes. ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides an explicit group sparsity projection method based on the Hoyer sparsity measure. Specifically, the paper makes the following contributions:\n\n1. This paper provides a clever formulation of the group sparse projection problem with explicit sparsity control with the Hoyer measure, making the problem faster to solve\n2. This paper theortically derives an efficienct algorithm to solve the proposed group sparse projection problem\n3. This paper provides emperical justification showing the proposed method is effective on both NMF and neural network pruning applications", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please refer to the two weakness points mentioned previously. Point 1 on the novelty is a critical issue needs to be addressed in the revision, while point 2 on the comparison would further strengthen the work.\n\nTypo: Section 2.2 line before Equ. (3) \"can formulated\" -> \"can be formulated\"", "broader_impact_concerns": "I don't see any potential concerns for this submission.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "q1M0UdGlVJ", "reviewer": "Reviewer_QiA9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strenghts** \n- Optimizing an average notion of \"sparsity\" based on the Hoyer index is interesting.\n- Numerical results seem to suggest benefits of their approach.\n\n**Weaknesses**\n- The manuscript is unclear, with contradicting notation throughout the paper.\n- Comparing methods are unclear (or in some cases not defined at all), making the interpretation of the results difficult.\n- Some statements are hand-wavy or exaggerated.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript proposes a group sparse projection algorithm based on the Hoyer index, which relates to the sparsity of a vector. In particular, the projection is defined with a constraint set that measures the average Hoyer index of a set of vectors. The manuscript proposes an optimization algorithm that optimizes the dual formulation, scaling linearly in the problem dimension. The authors compare their approach for sparse non negative matrix factorization as well as pruning of artificial neural networks' weights.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "**Main comments**\n\n**[Notation]** \nRespectfully, the paper does not look in a condition for review, as there are multiple inconsistencies in notation. For example, in the paragraph titled Notation the authors mention that they use $x(j)$ to denote the j-th entry in the vector $x$. *On the following sentence* they refer to the i-th entry in $x$ as $x_i$. These issues persist (and increase) throughout the paper: e.g. in Sect 3.3, point (a), the authors write $x_i(0)$ to denote *a vector*, as they seem to be referring to the i-th of $r$ vectors as a function of the scalar (Lagrange parameter) $\\mu$. It is very hard to follow the paper and understand what is being done with all these inconsistencies. Please, use conventional notation (using $e$ to denote a vector of all ones is *very confusing*). \n\n**[Definition of sparsity]** \nThe authors seem to argue (throughout the introduction) that their choice of sparsity measures (the Hoyer index) is more \"interpretable\" and that it does not need a parameter search to achieve a desired sparsity level. This is incorrect: a Hoyer measure of 0.5 does not imply that 50% of the entries will be zero, and if one desires 50% of zero entries one indeed needs to carry out a parameter search over the Hoyer measure. It is true that the Hoyer measure, sp(x), is nice in that sp(x) implies that the vector is fully dense, and sp(x)=1 implies that x only has 1 non-zero element. However, a similar conclusion can be drawn by using an $\\ell_1$ norm: if one computes the proximal of the $\\ell_1$ norm at a point $x$ with a penalty parameter of $\\lambda \\in [0,\\lambda_{max}]$, where $\\lambda_{max}=\\lVert x \\rVert_{\\infty}$ , then $\\lambda=0$ leads to no sparsity enforced, and $\\lambda = \\lambda_{max}$ leads to only 1 non-zero (maximal sparsity). In light of this, the \"benefits\" over and $\\ell_1$ to measure sparsity are unclear (and exaggerated). Please, do let me know if there's another benefit that I'm failing to see.\n\n**[Organization]**\nThe organization of the paper is unclear, and many things are undefined:\n* The introduction section is very short, and it would be beneficial for the reader to have an introduction to the use of sparsity in inverse problems and compression, as well as some background on the Hoyer measure.\n* The paragraph on *Projections* is very strange: \"projections\" is a mathematical operator that is much broader than what the authors mention in their paragraph. Perhaps the authors are rather referring to the use of regularization (either as projections or regularization) in inverse problems. I would include this in the Introduction.\n* The authors then present \"Sparse NMF\". Yet, their definition of the problem in Eq. (1) is not a sparse NMF problem, as there is no sparsity enforced at all. It is true that the authors mention at the end of that paragraph that \"In practice, it is particularly useful to have sparse X and/or H to have a more interpretable decomposition\". *(i)* enforcing sparsity is not just an ad-hoc practical trick, but has been largely studied theoretically. The benefit sparse components is not just \"interpretability\" but rather leading to statistical benefits. *(ii)* the authors never formalize what the sparse NMF problem is, as they never write any sparsely-regularized version of the problem in Eq. (1). This becomes problematic later in section 5.1 when the authors write \"As H is not affected by the sparsity requirement...\" : what sparsity requirement? up to this point, there's no sparse-enforcing term on either factor.\n\n**[Experimental results]**\n* The experimental section is unclear. Admittedly, part of this is likely because the presentation of the method is not fully clear (for the issues above), but also because the authors present and compare many methods that have not been formally defined, and so one does not know what these comparisons really mean. Importantly, some of these methods penalize $\\ell_1$ norms, some penalize Hoyer measures, and it's not very clear which ones do what. It'd be very useful to *define* the problems that each method solve (indeed, these were never defined).\n* When comparing methods that enforce sparsity in different ways ($\\ell_1$ and $sp$), is it not clear how the choices for these regularizers were done (i.e, what $\\lambda$, or what value of $s$), or how they were chosen. Were they optimized for each method independently? Were they set so that they all achieve the same level of effective sparsity (i.e. cardinality)? Without this information, it is hard to understand the meaning of these graphs (e.g. the lines that converge to an error of >0.1 might have parameters that enforce too much sparsity, thus resulting in higher errors). \n* The authors mention compare all algorithms in terms of error per iteration, \"Since all algorithms have almost the same computational complexity per iteration\", yet, the computational cost per iteration is not the same for the different methods (as per footnote 1). Thus, a comparison of runtime would also be appropriate here.\n* It is a bit strange that the sparsity percentages (on Table 2) have no decimal points.\n\n**[other main comments]**\n* The authors mention that the maximum of Eq. (5) is attained since the objective function is continuous and the feasible set compact. I am unsure this is true, since the problem seems to optimize over vectors different from the zero vector (indeed, see the problem (GSP)). Thus, $\\mathbb R^n_0$ is not compact.\n\n**[Typos and other errors]**\n* There are many typos throughout the manuscript. E.g., in the *Notations*, the paper have two different summations over the variable $i$, but use $j$ to index the summands. \n* In many equations (e.g. in GSP, eq 5, eq 6, among many other places) the authors write a maximum operator over the vectors $x_i$ as well as the indices $i$, i.e.: $\\max_{x_i,1\\leq i\\leq r}$. However, the argument of this operator has no index on $i$, because there is a summation from $i=1$ to $i=r$.\n* At the top of page 5, when \"reformulating\" their GSP problem, the authors are missing the $\\ell_2$ norms in their expressions for $sp(x_i)$.\n* The authors comment (Sec 2.1) that the Hoyer index is smooth. This statement is incorrect: first, this index is discontinuous (at x=0). Second, the $\\ell_1$ norm (and thus, $sp(x)$) is not smooth at points wherever any of the entries in $x$ are zero (even if the overall vector is non-zero). \n*  Consider including the constraint of $n>1$ in the definition in Sec. 2.1.\n* Denoting by $\\lVert x \\rVert_w$ the weighted $\\ell_1$ norm of $x$ is very confusing, as this is typically the notation used for weighted $\\ell_2$ norms. Consider using $\\lVert W x \\rVert_1$, where $W = \\text{diag}(w)$.\n", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers' initial comments were mostly cleared up after clarification and rewording.

- The usage of the word "projection" is clearly justified in the single vector case, section 2.2.  In the multi vector case, section 3 gives a well-defined operator, equation (GSP), but it's a bit vague whether it's a projection.  Projection in a linear algebra sense means idempotent (which your operation seems to be) but is defined for a linear operator and a domain that is a sub-space, which does not apply to your operator. In optimization, projection is often used in the sense of "best approximation" (with respect to some norm), as in Eq (3), but that's also unclear in the multi vector case. So maybe state in which precise sense the operation is a "projection", or possibly give it a different kind of name.

- The usage of \citet and \citep is not done correctly. See, e.g., https://bochang.me/blog/posts/latex/

- After equation 1, it's written iff "x(i) = b" but this should be "|x(i)| = b".  That same paragraph uses "i" to both index a component and a set of vectors; please use a different variable for the two meanings.

- "Note that while the l0 norm can also be used directly as a sparsity measure Bolte et al. (2014); Pock & Sabach (2016) although it does not enjoy some of the nice properties of the Hoyer-sparsity measure;"  This is not a complete phrase; remove the "while" or the "although" to make it complete.

- There are still other grammar issues, in addition to the ones I just pointed out. Since my job is not to copy-edit, I just request that the reviewers take another look at the manuscript to fix minor typos and grammar issues before they submit the final version.
Decision: Accept (poster)