Sparsity by Redundancy: Solving $L_1$ with a Simple Reparametrization
Authors: Liu Ziyin
Zihao Wang
Venue: Submitted to ICLR 2023 (2023)
Keywords: L1
sparsity
feature selection
deep learning
landscape

Abstract: We identify and prove a general principle: $L_1$ sparsity can be achieved using a redundant parametrization plus $L_2$ penalty. Our results lead to a simple algorithm, \textit{spred}, that seamlessly integrates $L_1$ regularization into any modern deep learning framework. Practically, we demonstrate (1) the efficiency of \textit{spred} in optimizing conventional tasks such as lasso and sparse coding, (2) benchmark our method for nonlinear feature selection of six gene selection tasks, and (3) illustrate the usage of the method for achieving structured and unstructured sparsity in deep learning in an end-to-end manner. Conceptually, our result bridges the gap in understanding the inductive bias of the redundant parametrization common in deep learning and conventional statistical learning.

Under review as a conference paper at ICLR 2023
SPARSITY BY REDUNDANCY: SOLVING L1 WITH A SIMPLE REPARAMETRIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We identify and prove a general principle: L1 sparsity can be achieved using re- dundant parametrization plus L2 penalty. Our results lead to a simple algorithm. spred, that seamlessly integrates L1 regularization into any modern deep learning framework. Practically, we demonstrate (1) the efficiency of spred in optimizing conventional tasks such lasso and sparse coding, (2) benchmark our method for nonlinear feature selection six gene selection tasks, and (3) illustrate the usage of the method for achieving structured and unstructured sparsity in deep learning in an end-to-end manner. Conceptually, our result bridges the gap in understand- ing the inductive bias of the redundant parametrization common in deep learning and conventional statistical learning.
INTRODUCTION
In many fields, optimization an objective function with respect to an L1 constraint is of fun- damental importance (Santosa & Symes, 1986; Tibshirani, 1996; Donoho, 2006; Sun et al., 2015; Candes et al., 2008). The advantage of the L1 penalty is that its solutions are sparse and thus highly interpretable. While non-gradient techniques like interior point methods Li-reuularized problems, gradient-based methods are favored by practices due to their scalability on large-scale problems and simplicity of implementation (Schmidt al., 2007; Beck & Teboulle, 2009). However, previous algorithms are mostly problem-specific extensions of gradient descent and highly limited the scope of applicability. remains an important and fundamental open problem of how to optimize a general nonconvex objective with L1 regularization. The foremost contribution of this work to propose method for solving arbitrary nonconvex objectives with L, regularization. The proposed method is simple and scalable. The proposed method does not require any special optimization algorithm: can be solved by simple gradient descent and can be boosted by common training tricks in deep learning such as minibatch sampling adaptive learning rates. One can even apply common second-order methods such as Newton's 's method or the LBFGS optimizer. The proposed method can be implemented in any standard deep learning framework with only a few lines of code and, therefore, seamlessly leverages the power of modern GPUs.
be applied to solve
In fact, there is large gap between L1 learning and deep learning. A lot of tasks, such as feature selection, that based methods work well cannot be tackled by deep learning, and achieving spar- sity in deep learning is almost never based on L1. This gap between conventional statistics and deep learning is perhaps because there is no method that efficiently solves general L1 penalty in general nonlinear settings, not mention incorporating such methods within the standard backpropagation- based training pipelines. Our result, crucially, bridges this gap between classical L1 sparsity with the most basic deep learning practices.
The main contributions of this work are
1. Identification and proof of a general principle: L1 penalty is the same as a redundant parametrization plus weight decay, which can be easily optimized with SGD;
2. Proposal simple and efficient end-to-end algorithm for optimizing L1 regularized loss within any deep learning framework:
3. A principled explanation of known and discovery of unknown mechanisms in the standard deep learning practice that leads low-rankness and sparsity.

---

Under review as a conference paper at ICLR 2023
2 RELATED WORKS
L1 Penalty. is well-known that the L1 penalty leads to a sparse solution (Wasserman, 2013). For linear models, the objectives with L, regularization are usually convex, but they not easy to solve because the objective becomes non-differentiable exactly at the point where sparsity is achieved (namely, the origin). Previous literature often proposes special algorithms for solving the L1 penalty for specific task. For example, lasso finds sparse weight solution for linear re- gression task. The original lasso paper suggests a method based on the quadratic programming algorithms (Tibshirani, 1996). Later, algorithms such as coordinate descent (Friedman et al., 2010) and least-angle regression (LARS) (Efron et al., 2004) have been proposed as more efficient alterna- tives. One major problem of the coordinate descent algorithm is that it scales badly the number of parameters increases and is difficult to parallelize. Yet another line of work advocates the iterative thresholding algorithms for solving lasso (Beck & Teboulle, 2009), but it is unclear how ISTA could be generalized to solve general nonconvex problems. This optimization problem also applies to the sparse multinomial logistic regression problem (Cawley et al., 2006), which relies on diagonal second-order coordinate descent algorithm. Another important problem is the nonconvex I -pparee coding problem. This problem can be decomposed into two convex problems, and Lee et al. (2006) has utilized this feature to propose the sign-feature algorithm. Our work tackles the problem of L sparsity from completely different angle. Instead of finding an efficient algorithm for special L1 problem, we transform any L1 problem into a smooth problem for which the simplest gradient descent algorithms have been found efficient.
Redundant Parameterization. Previously, the fact that L1 penalty is equivalent to Le with redun- dant parametrization has been discovered in various restricted settings. Grandvalet (1998) showed that La penalty in an arbitrary system is approximately equivalent to an adaptive quadratic penalty where each parameter comes with an independent learnable weight decay strength. Rennie & Srebro (2005) and Hastie et al. (2015) study the effect of the same parametrization on the classic matrix factorization problem and suggest its extension to different loss functions. Hoff (2017) studied this reparametrization in the context of linear and generalized linear models. Poon & Peyré (2021) and Poon & Peyré (2022) study the problem in case of a convex and lower semicontinuous loss function. A preliminary work pointed out the connection between a fully connected neural network with T2 and group lasso Tibshirani (2021). ). All these previous works lack two essential components of our proposal: (1) the application of the theory deep learning practice and (2) the proposal that such an equivalence means that simple SGD can solve the L1 penalty.
Sparsity in Deep Learning. One important application of our theory is the understanding and achieving any type of parameter sparsity in deep learning. There are two main reasons for introduc- ing sparsity to the model. The first is that some level of sparsity often leads to better generalization performance; the second is that compressing the models can lead to more memory/computttiin efficient deployment of the models (Gale et al., 2019; Blalock et al., 2020). However, none of the popular methods for sparsity in deep learning is based on the I, penalty, which is the favored method in conventional statistics. For example, pruning-based methods are the dominant strategies in deep learning (LeCun et al., 1989). However, such methods are not satisfactory from a princi- pled perspective because the pruning part is done in separation from the training, and it is hard to understand these pruning procedures actually optimizing.
MAIN RESULT
Consider a generic objective function I(Vg,, V2) that depends on two sets of learnable parameters V. and Va. where the subscript s stands for "sparse" and d stands for "dense". Often, we want to find sparse set of parameters V, that minimizes L. The conventional way to achieve this is by minimizing the loss function with an L1 penalty of strength 2x:
min L(V. Va) + 2xl|/Val11. Va
(I)
Under suitable conditions for L. the solutions of L(Vs, Va) will feature both (1) sparsity and (2) shrinkage of the norm of the solution V., and thus one can perform variable selection and overfitting avoidance at the same time. A primary obstacle that has prevented a scalable optimization of Eq. (1) with gradient descent algorithms is that it is -in-iffferentialee exactly at the points where sparsity is achieved, and this optimization problem only has efficient algorithms when the loss function belongs to restrictive set of families. See Figure 1.
2

---

Under review as a conference paper at ICLR 2023
2.0.5
1.6
2-1.3
1356
00
100
-43
-05
+10
-10
Figure 1: Landscape comparison of the original L1 regularized loss the Le regularized redundant parametrization. With the redundant parametrization, the loss becomes smooth and differentiable. The reparametrization introduces one additional minimum but is entirely henign because the two minima are iden- tical and just mirrors of each other and converging to either achieves an equivalent performance. Left: the original Id In loss for I (w- c)² jwo. Mid: reparametrized loss with 0.5. Right: c= 1.5.
The following theorem is the first main theoretical result of this work, deriving a precise equivalence of Eq. (1) with a redundantly parameterized objective.
Theorem 1. Let aB x² and
(U.,,, L(U @ W. + + +|]]
(2)
Then, (U, V.W. is global minimum of Eq. (2) if and only if (a) |UA = |Wal for all i and (b) (U a W. Va) is global minimun of Eq. (1).
The subscript sr stands for "sparsity by redundancy". When L is n-time differentiable, the objective Ler is also n-time differentiable. One can thus apply simple gradient- based optimization methods to optimize this alternative objective when I itself is differentiable. When L. is twice-differentiabe one can also apply second-order methods for acceleration. As an example of L,, consider the case when I is baining-set-dependerr loss function (such as in deep learning), and the parameters V, and Va are learnable weights nonlinear neural network. In this case, one can write Ler as
1 Σ ((u(()))))))) + al|UT| + A|IP
where w = (U, W, Va) denotes the total set of parameters we want to minimize, and (I), 3/)) are data point pairs of an empirical dataset. It is intuitive to solve this loss function with popular training methods of deep learning. The L2 regularization can be implemented efficiently as weight decay as in the standard deep learning frameworks. As we discussed, this equivalence in the global minimum has been pointed out by previous works in various restricted settings (Rennie & Srebro, 2005; Hoff, 2017; Poon & Peyré, 2021). However, the equivalence motivate an application of SGD to it because gradient descent is local, and if there are many bad minima induced by this parametrization, SGD can still fail badly.
the global minimum is insufficient to
An important is thus where this redundant parametrization ind has made the optimization process more difficult or not. We now show that it does not, in the sense that all local minima of Eq. (2) also corresponds to local minima of the original loss and vice versa. Thus, the redundant parametrization cannot introduce new bad minima to the loss landscape.
Theorem 2. (U, (T) is a local minimum of Eq. (2) if and only (f) V U &&W W is local minimum of Eq (1) and (b) JU:] = [Wa
This proposition thus offers partial theoretical explanation to our empirical observation that the optimization of Eq. (2) is no more difficult (and often much easier) than the original L-rreuularized loss. A corollary of this theorem is that if is convex (such as in Lasso), then every local minimum of Lys are global. 1 This theorem directly motivates the application of stochastic gradient descent to any problem that SGD has been demonstrated efficient for, and this theoretical justification is lacking in the previous works.
In more general scenarios, one is interested in structured sparsity, where a group of parameters is encouraged to be sparse simultaneously. It suffices to consider the case when there is a single group because one can add L1 recursively to prove the general multigroup case:
L(V., Va) v/V//2-
(4)
The following theorem gives the equivalent redundant form.
'This is reminiscent of the classical result the deep learning loss landscape (Kawaguchi, 2016).
3

---

Under review as a conference paper at ICLR 2023
Theorem 3. Let aB 6² and
L Lu, W, = L(W. + + 31|WW1.
(5)
Then, (u, W.) is a global minimum of Eq. (2) if and only if (a) lu] = [Wlle for all i and (b) (wW, Va) is global minimum of Eq. (1).
Namely, every Lı group only requires one additional parameter to sparsify. Note that recursively applying Theorem and setting W to have dimension 1 allows us to recover Theorem 1.² The above theory leads to the simple algorithm given in Algorithm I and 2. Let be the number of groups, this algorithm adds m parameters to the training process. As a consequence, it has the same complexity as the standard deep learning training algorithms such as SGD because it at most doubles the memory and computation cost of training and does not incur additional costs for inference. For the ResNet18/CIFARR 10 experiment performed, each iteration of training with spred takes roughly 30% more time than the standard training, much lower than the upper bound of 100%.
Algorithm spred algorithm for parameter sparsity
Input:
loss function LV,,, V2), parameter Vs, Va. L1 regularization strength 2x Initialize W. U
Solve (with SGD, Adam, LBGFS, etc.) minw;u,y, L(U @ W.) + + ||01|])
Output: V = uW
Algorithm spred algorithm for structured sparsity
Input: loss function L(V,, Va), parameter Va, Va. L1 regularization strength 2x Initialize W, u Solve minw, L(uW, V&)+ + <<[W n²) Output: V uW
Two implementation caveats. First of all, there are multiple ways to initialize the redundant param- eters W and U. One way is to initialize W with, say, the Kaiming init., and U' to be of variance 1. The other way is to give both variables the same variance by, e.g., taking the squared root of the standard initialization methods. Secondly, even if one only wants to add L, to one layer, one should also add a small weight decay to all the other layers to prevent the model from diverging.
4 APPLICATIONS
In this section, we demonstrate the applications of our theory and algorithm to a series of classic tasks with both fundamental and practical importance. We first show that our algorithm is highly scalable algorithm for solving lasso in comparisons to classical lasso algorithms such coordinate descent and LARS. We also illustrate an application of suggested method to the sparse coding prob- lem. Lastly, we propose general method for performing nonlinear feature selection with neural networks (and, more generally, with ensembles nonlinear models) and demonstrate its power for nigh-dimensional tasks such as gene selection.
4.1 A SCALABLE ALGORITHM FOR LASSO
We first test the effectiveness of the proposed algorithm for the lasso problem. We emphasize that we do not claim that the proposed method to be the state of the art method for solving lasso. fact, it cannot be. This is because SGD is generic optimization method that works any differentiable problem and, by the no free lunch theorem, it certainly cannot outperform methods that are specially designed for the problem of lasso, which often take advantage of the convexity of the objective. If a SOTA performance is desired, the readers are advised to use the standard methods, such as the method proposed in Johnson Guestrin (2015), Massias et al. (2018), or Bertrand al. (2022). This section validates the following simple claim: the proposed method can achieve the correct sparsity in undl-snnerto classical problems, and does not perform badly in comparison to the default baselines of the field.
Note that when L. is linear regression objective, the loss function is equivalent the group lasso.
4

---

Under review as a conference paper at ICLR 2023
1.0
optimal
10*
0.6-
1p 1predinn-100 9g
Lappe e Lantty
Time (oeci
20
spree 0.9
Spried
Zenu
0.4
seroklin 10013
0.7
10a-
0.0
10P
102 10* 10a
dimension
Figure 2: Performance of spred for solving lasso Left: The sparse ratio under different choices of spred agrees with the thcoretical optimum everywhere. Lasso: the closed-form solution. LI: LI regularized least square regression solved by gradient descent; sr: the proposed method. Right: Up to the time scale we can tolerate, using spred can be 100 times faster than the conventional algorithms. Using spred also allows us to solve L1 problems scales at least two orders of magnitudes much larger than what the conventional algorithms can afford.
We experiment with the following two settings. ID oulput and orthogonal inpul: In this case, the closed-form solution for lasso is known, and this allows us evaluate whether our method can reach the optimal lasso solutions or not. We compare with a naive gradient-descent baseline: directly applying gradient descent to the original lasso objective, denoted as L./ While one does not expect this method to work, it has been the popular way in deep learning to optimize the L1 penalty (for example, see Han et al. (2015) and Scardapane et al. (2017)). We choose both gradient descent and Adam optimizers to optimize spred, as well as the original LI regularized mean square error objective. The learning rate chosen from {1,0.1, 0.01, 0.001]. The final result is produced from the best setting. See Figure 2. When using Spred, trick to spead up training is to set threshold below which we set the parameter to zero at the stopping point." We test two levels of threshold. and both agree with the optimal solution at convergence. We also plot in Appendix A the time evolution of the sparsity at the two thresholds, and we see that they converge to the same value at roughly the same time scale. This can be used as a criterion for assessing the convergence of spred. We see that spred agrees with the closed-form solution for all sparsity levels and for two different levels of accuracy, while the naive gradient-basee based method never reached a sparse solution.
High- lighediimnsional Lasso. Now, we compare the optimization efficiency of spred with the coordinate descent and LARS solutions of lasso under different input and output dimensions. The coordinated descent solution of lasso is denoted as Lasso. The Least Angle Regression of lasso is denoted by LARS. See Figure 2-right. For spred, we report the time when the zero rates of the solution matrix hit 75%, 90%, and 100% of the zero rates of the converged solution. We note that there is no discernible difference in the training loss with the lasso objective for all three rates. Notably, the scaling of time complexity of spred is significantly better than lasso and LARS, which indicates the spred is particularly suitable for large-scale computation. While the time cost of running spred stays roughly constant
scale to larger problems, that of the coordinate descent scales d. At d = 10s, using spred is roughly 100 times faster than the two conventional algorithms. The fact that the convergence rate of gradient descent is insensitive to the dimension in many settings is well-known in the optimization literature, which is consistent with our observation.
Sparse coding. As a visual demonstration, apply the method to sparse coding (also known as dictionary learning) (Lee et al., 2006; Mairal et al.. 2009). The objective for sparse coding is
min | BS| k||SS|1. R.
(6)
where X E IddxNN is a set of N data points, B e Rdox is set of k bases, and S E R is a set of N codes that matches a subset of the bases to each data. Neuroscientifically; the bases learned in this way have been found to reproduce the Gabor filters that mimic the patterns learned in the human visual cortex (Olshausen & Field, 1997). Differ- ent from the lasso objective, this loss function is nonconvex and has spurred an interest in the optimization community to design efficient optimization methods to find solutions. One common strategy is to al- ternatively minimize B and because when fixing the other (Lee et al.,
Figure 3: Examples of the learned Gabor filters from natural images.
'In experiments, we note that precise zeros can still be achieved with SGD or Adam if we train little longer (but still within a reasonable time scale. Thus, our method, in principle, does not require threshold.)
5

---

Under review as a conference paper at ICLR 2023
Table 1: Prediction accuracy for gene selection task for cancer diagnosis and survival time prediction.
tasks are classification tasks. On average, each of these datasets contains 300 data points, each with 40000 feature dimensions, and labeled into 10 classes, See Table 2 for more description.
spred
Dataset
HSICLasso
MLP (WD)
MLP (LI)
fi only
fi and f'
GDS1815
11.62 = 0.29
0.56 + 0.22
7.75 0.55
19.31 + 0.70
GDS1816
13.68 = 0.06
0.31 # 0.13
7.12 0.75
1
18.75 + 0.77
GDS3268
30.69 + 0.44
3.03
15.90 = 0.81
25.90 +
2.68
GDS3952
45.61 # 0.52
14.92
17.92 0.92
37.00
46.76 1.55
GDS4761
42.63 = 0.51
50.79 + 2.48
12.62 # 1.78
60.26
2.37
57.63 + 2.09
GDS5027
23.51 # 0.10
2.55
0.48
15.47 0.98
30.37 0.97
30.95 0.94
Here, Gabor filters can only be learned when real sparsity is achieved. Otherwise, one would get chessboard-like patterns that simple PCA would obtain. See Appendix A.3 for the experimental details.
2006).
4.2 NONLINEAR FEATURE SELECTION
Previously. based feature selection for a general nonlinear model has been an open problem because of the lack of an efficient algorithm to solve it. Existing feature-selection methods based on L1 penalty are predominantly linear. The nonlinear methods are often kernel-based, where the nonlinearity comes from an unlearnable kernel. In this section, we demonstrate how the proposed method directly solves this open problem on a gene selection task (Shevade & Keerthi, 2003; Sun al., 2015). The common gene selection tasks contain feature dimension of order 10a 10 (the size of the human genome), and the number of samples (often the number of patients) is of order 102. These tasks can be seen "transpose" of MNIST and are the direct opposite of the tasks that deep learning is good at. Additionally, one indispensable part of these tasks is that we want to not only make generalizable predictions but also pinpoint the relevant genes that have a direct physio- logical consequence. For example, out of roughly 50000 genes of homo sapiens, we want to know which gene is the closest associated with, say, hemophilia such a requirement for interpretability is also challenging for deep learning. 'he solution to these tasks is of both scientific and practical importance. To the best of our knowledge, no deep learning method has been shown to work for these tasks (for review, see Montesinos-López, et al. (2021)). We compare with relevant baselines on public cancer classification datasets based on microarray gene expression features from the Gene Expression Omnibus, including two datasets on glioma (#1815, #1816), three on breast cancer (#3952, #4761, #5027), and one on ulcerative colitis (#3268). More detailed descriptions of the datasets are in the appendix.
While a general nonlinear model can capture unexpected nonlinear effects, linear models have been found to work reasonably well for these tasks. Thus, one would like to make feature selections based on linear and nonlinear models. Our method allows one to achieve this goal easily: we demonstrate how to perform feature selection with an ensemble of models using spred. Let (W"2)) and fr. (W"x) denote the two different models to be trained on loss function ff,, Here, we have explicitly written weight matrices W and 4 to emphasize that these two models start with learnable linear layer. The following parametrization allows one to perform Ln feature selection with both models:
EELL(SI(Wi( @ (W, (U xz)))] + > <II + I|W,112+ (IU1E)
where dim(U)- = dim(x), and Eg denotes averaging over the training set. Note that the input to the two models is masked by the same vector U: this is crucial; without U, we are just train- ing an ensemble of independent models, whereas U makes them coupled. Each U, is a redun- dant parameter, and this is equivalent to performing In penalty on W and WT together by The- orem 3. In the experiment, we let fi be simple linear regressor without bias and fn be three- layer feedforward network with the ReLU activation. For simplicity, we set the objective function L(fi, fn) (Wi( @ v) Entropy (CE) losses.
v)) to be the summation of two Cross CE(F,
See Table 1. Because the dataset size is small, for each run of each model, we randomly pick 20% samples as the test set, 20% the dev set for hyperparameter tuning, and 60% as the training set. For SGD-based models (MIP, Linear, Linear + MLPP), we stop the optimization when the accuracy on

---

Under review as a conference paper at ICLR 2023
10
0.8
ReUU
node sporsity
count
0.2
10
RCLU
SWiSn
0.00
0.01
0.02
0.03
10
10
10
magnitude
Figure 4: The feedforward structure of neural networks encourages sparsity of the neurons (nodes). Left: distribution of the norm of the row vectors (each corresponding to a hidden neuron) of the last layer of a net with ReLU activation at strong weight decay. Predominantly many nodes are either zero close to zero. Mid: node sparsity of ReLU and swish function of weight decay strength. We see that larger weight decay leads to higher and higher neurons being constantly zero. Right: the weight sparsity is linear function of the node sparsity, suggesting that the node sparsity can perfectly explain the existence of sparsity in the model.
the dev set is not increasing. The performance are averaged over 20 independent samplings of the datasets for comparison. We report the percentage of the majority class of each dataset to justify whether the models produce meaningful results. In table I, MLP contains one hidden layer of 4096 neurons. fn contains two hidden layers of 1024 neurons. spred models are optimized by SGD. The learning rate and k are both selected from {7e-1, 5e-1, 3e-1, le-1, 5e-2, 3e-2, 1e-2). Besides the deep learning methods, we also compare with HSIC-Lasso, conventional Li-aaeed non-linear feature selection method (Yamada et al., 2014), which has been standard method, and recent works have identified it as one of the best-performing methods for these tasks (Sun et al., 2015; Krakovska al., 2019).
We see that deep learning combined with spred achieves very good performance, outperformed by the conventional method on only one dataset. On the other hand, simply applying deep learning does not work on any of the datasets. This is expected for tasks whose dimension is far larger than the available number of data points because memorization can be too easy. Importantly, simply applying Ln to an MLP fails badly because gradient descent cannot find sparse solution and thus cannot prevent overfitting. This Besides the competitive performance of the proposed method, we note that for each experiment, each training with the proposed method is at least ten times faster than the existing methods. As discussed, this is due to the dimension- free efficiency of gradient descent and expected. To the best of our knowledge, this is the first time deep learning has been shown to work for a high-dimensional feature-selection task with so few data points. Designing better architectures that suit the task of gene selection will further boost performance. Our result is thus expected to greatly accelerate the exploration and incorporation of deep learning technology into this field.
SPARSITY OF DEEP NEURAL NETWORKS
This section is devoted to applying the theory and algorithm to deep learning. We show that our theory also directly contributes to our understanding of neural networks.
5.1 INHERENT NODE SPARSITY FULLY-CONNECTER LAYERS
Our theory suggests the existence of approximate I. regularization in some systems. For example, consider a model containing a term of the form vh(w), where h(w) = are 0(w2) ) a homoge- neous nonlinear function. Then, in the neighborhood of zero (where sparsity is achieved), this term expands to aow + O(w²). With a weight decay present, this approximate redundancy becomes an effective L, regularization and encourages sparsity.* This type of function appears very frequently in the context of deep learning as two consecutive layers.
We first consider a ReLU net with neurons 784 - 1000 be compactly written as fxx) ( where a is the nonlinearity and the effect of bias in incorporated into the definition of æ. is well-known that there is a rescaling symmetry in the
trained on MNIST. The model can
AIsso note how this expansion is consistent with strong weight decay.
7

---

Under review as a conference paper at ICLR 2023
model. Let h4 ReLU(W,()) -x) be the i-th hidden neuron. Then, the model can be written as f(z) = Σ bybbyj (2)
1000
R x))
(8)
where, for each j. 1/ and v/ are normalized vectors and ay (bj) are the norms of the columns (rows) original weight matrix w(2) (W())). This means that the loss function (for example, the cross entropy) with weight decay can be written as
Lottl Laa b, o2), ,0())) + [|]]||/++1b0/)
Thus, our theory can be applied to show that this loss function encourages node sparsity because a and are wise redundant parametrizations of the model, on which an L2 regularization is applied. Therefore, a key implication is : ReLU layers with L2 encourage L1 node spansity See Figure 4. We train the specified model with Adam for 50 epochs on MNIST with varying levels of R. We measure the degree of node sparsity (operationally defined as the number of columns of W(2) whose average parameter magnitude is smaller than 10 We also measure the function of the node sparsity as a function of the weight sparsity. A clear linear relationship suggests that the weight sparsity in the model is sufficiently explained by the node sparsities caused by the weight decay. We stress that this inherent node sparsity is quite general because it is approximately achieved for almost any activation functions. As an example, consider the swish activation (Ramachandran al., 2017): swishh (z, W)= == W x @ sigmoid( Wx). When the weight decay is strong, the parameters of the model will be close O, and so we can expand to the first order and extract the norm of the preceding layer: swiish (I, W) au bu swisshh (z, v). and, again, there is an effective L1 penalty on the norm of the weight matrices.
Note that node becoming sparse implies that the learned representation becomes low-rank. This result offers a direct and unified explanation of the recent observed phenomenon of neural collapses in supervised learning (Xu et al., 2022; Rangamani & Banburski-Fahee 2022; Ziyin et al., 2022), and posterior collapses in Bayesian deep learning (Wang & Ziyin, 2022), where the collapses happen when strong effective recond-order regularization (such as weight decay) is applied to the weights. This fact suggests that the regularization effect of weight decay is much stronger than previously understood. In case of node sparsity, single redundant parameter (the norm of row) is sufficient to regularize the whole row of the parameter and bias them towards zero. Previously, the equivalence of full connection with L, penalty has been noticed by Neyshabur et al. (2014) and Tibshirani (2021).
Our results advances these works in two regards: (1) the extension to the approximate form, which suggests that the existence of such sparsity is much more common than previously thought, (2) the proposal that this fact can be algorithmized to systematically achieve sparsity in deep learning, which we demonstrate in the next section.
5.2 COMPRESSION OF NEURAL NETWORKS
The proposed method also offers a prineipled way of performing network compression in deep learning. We experiment with unstructured weight sparsity for deep neural networks. Our method can also be used for achieving structured compression, which we leave to future work.' We simply apply spred to all the weights of ResNet in this section. Previous methods often rely on heuristics for pruning. For example, removing the weights with the smallest magnitudes from a normally trained network. However, the problem with such methods is that one does not know in principle the effect of removing such weights, even though they seem to work empirically. Our method is equivalent to L1 and has its theoretical foundation in both traditional statistics and Bayesian learning with a Laplace prior. The meaning of removing a parameter with magnitude e is clear: its removal from the model will cause the training loss increase by roughly sc. We also emphasize that the goal of this section is not to suggest that the proposed method is a competitive method for network pruning and compression because we are not proposing a new method after all: L1 is known to lead to sparsity, and our method is just a method for optimizing L, constraints. The performance of the proposed method can thus be no better than what simple L, constraint can provide. The thesis of this section is that when an efficient way to optimize L1 exists, it can perform as well as the existing methods that are not L based, and thus L, based strategies are really worth exploring by
'For example, applying a vector of filter masks the filters allows one to learn sparse set of filters.
8

---

Under review as a conference paper at ICLR 2023
mcdull.lyyar4. coigh.
ofer20
dfer100
20"
Reshee18 spead N
32
10
10
10'
101
10"
12
0.2
0.4
0.81
1.0
10" 12a
-00
201
107
12P
122 327 327
weights
Compression Ratio
Compressioo Ratic
Figure 5: Performance of L1 -based ResNet18 pruning CIFAR-10 10 and CIFAR-100. For both datasets, the estimated pareto frontier competitive against any known existing pruning methods. Left: Distribution of weight parameters in the largest convolution layer of ResNet18 trained on CIFARIO. Training with spred leads to a very sparse distribution without affecting test accuracy. Mid: CIFAR-10. The grey dotted line shows the estimated pareto fronticr by fitting sigmoid. Right: CIFAR-100.
the community. Prior to our work, many works have attempted to naively optimize the L1 constraint with SGD, but such approaches have been found to perform rather badly compared with non L1- based methods (Han et al., 2015). Our result thus implies that the reason why L1 has not worked well in deep learning up to today is due to a lack of good generic optimization method, not because L1 is inherently unsuitable for deep learning.
We first train model with and without spred both at K = 5e and compare the distribution of the weight. See Figure 5. Both models achieve the established accuracy of 93% while the training with spred leads to much sparser distribution. We now test the performance of I, for network pruning on CIFAR-10 and CIFAR-100. We resort to simple and established procedure that has been utilized since Han et al. (2015). We first train a ResNet18 with fixed sparsity regularization for 200 epochs with SGD, prune at different thresholds, and then finetune for another 20 epochs with Adam at a learning rate of 4 - 4. Our implementation of ResNet18 contains roughly 11M parameters, consistent with the standard implementation. See the mid (CIFAR- 10) and right panels (CIFAR-100). For both datasets, the training at x = 5e - recovers the standard performance of these models. For CIFAR1O, the model can be pruned up to 1000 compression ratio (cr, total parameter divided by the remaining parameters) without losing accuracy, consistent with the best previous results reported in (Tanaka et al., 2020). For CIFARI00, Tanaka et al. (2020) achieves 70% accuracy only at 18 cr, whereas the pruning with L1 achieves 70% accuracy at 1 10 cr, roughly a magnitude better in compression power. To the more extreme end, the proposed method drops to roughly 35% accuracy at 6500 cr, doubling the performance of the best-known result previously, which drops to 15% at similar 5500 cr (Tanaka et al., 2020). Our result thus promotes the use of Lı penalty in deep learning. Interestingly, the higher the k, the more suited the trained model becomes for a more aggressive pruning. k is thus a parameter worth finetuning if one wants to achieve the best pparsity-performen
tradeoff.
We also tried using the thresholds of the trained model as a mask, which we apply to a model at initialization, and similar performance to the finetuned model is obtained. Our result thus supports the lottery ticket hypothesis and can be used as an alternative method for obtaining a lottery ticket. In fact, the performance of the models thus obtained is much better than the results reported in the original lottery paper (Frankle & Carbin, 201 8) and in a following survey (Blalock et al., 2020). We stress our thesis: L1 can indeed work in the context of deep learning if we have an efficient way to optimize it.
DISCUSSION
In this work, we have established a principle that a redundant parametrization can lead to an implicit constraint towards sparsity. In essence, Our theory deals with the landscape of an Lz-regularized redundant parametrization. Our empirical result, in turn, shows that optimization with gradient descent on such redundant but smooth landscapes is both efficient and scalable and can be of great use in various problems. We also bridged modern deep learning with conventional sparsity learning with an L1 penalty, and we hope our work will stimulate more research at this intersection. For all problems we approached, we have applied L1 in the most straightforward way, and developing more sophisticated methods with L2 is certainly one promising future direction. A fundamental question that arises is why gradient descent can optimize such landscape so efficiently, and future research that answers this question should advance our understanding of the optimization of deep learning models..

---

Under review as a conference paper at ICLR 2023
REFERENCES
Amir Beck and Mare Teboulle. A fast iterative shrinkage-thresholldng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-2000 202, 2009.
Quentin Bertrand, Quentin Klopfenstein, Pierre-Antoine Bannier, Gauthier Gidel, and Math- urin Massias. Beyond II: Faster and better sparse models with skglm. arXiv preprint arXiv:2204.07826, 2022.
Davis Blalock,
Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Proceedings of machine learming and systems, 2: 2:129-146, 2020.
Emmanuel J Candes, Michael B Wakin, and Stephen Boyd. Enhancing sparsity by reweighted 11 minimization. Journal of Fourier analysis and applications, 14(5):877-905, 2008.
Gavin Cawley, Nicola Talbot, and Mark Girolami. Sparse multinomial logistic regression via
bayesian 1l regularisation. Advances in neural information processing systems, 19, 2006.
David I. Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4): 1306, 2006.
Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani. Least angle regression. The Annals of statistics, 32(2):407449, 2004.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint ar3iv:1803.03635, 2018.
Jerome Friedman, Trevor Hastie, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of statistical software, 33(1):1, 2010.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint (00.::/9900095772 2019.
Yves Grandvalet. Least absolute shrinkage is equivalent to quadratic penalization. In International Conference on Artificial Neural Networks, pp. 201-206. Springer, 1998.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint 151000151, 2015.
Trevor Hastie, Rahul Mazumder, Jason D Lee, and Reza Zadeh. Matrix completion and low-rank svd via fast alternating least squares. The Journal of Machine Learning Research, 16(1):3367-3402, 2015.
Peter D Hoff. Lasso, fractional norm and structured sparse estimation using a hadamard product parametrization. Computational Statistics & Data Analysis, 115:186-198, 2017.
Tyler Johnson and Carlos Guestrin. Blitz: A principled meta-algorithm for scaling sparse optimiza- tion. In International Conference on Machine Learning, pp. 1171-1179, PMLR, 2015.
Kenji Kawaguchi. Deep learning without poor local minima. Advances in Neural Information Processing Systems. 29:586-594, 2016.
Siker Kimbung, Anikó Kováes, Pär- Ola Bendahl, Per Malmström, Märten Fernö, Thomas Hatschek, and Ingrid Hedenfalk. Claudin-22 is an independent negative prognostic factor in breast cancer and specifically predicts early liver recurrences. Molecular oncology, 8(1): 199-129 2014.
Olga Krakovska, Gregory Christie, Andrew Sixsmith, Martin Ester, and Sylvain Moreno. Perfor- mance comparison of linear and non-linear feature selection methods for the analysis of large survey datasets. Plos one, 14(3)e02113884 2019.
Heather G LaBreche, Joseph R Nevins, and Erich Huang. Integrating factor analysis and transgenic mouse model to reveal peripheral blood predictor of breast tumors. BMC medical genomics, (1):1-14, 2011.
10

---

Under review as a conference paper at ICLR 2023
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Honglak Lee, Alexis Battle, Rajat Raina, and Andrew Ng. Efficient sparse coding algorithms.
Advances in neural information processing systems, 19, 2006.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning 2018.
based connection sensitivity. arXiv preprint
Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online dictionary learning for sparse coding. In Proceedings of the 26th annual international conference machine learning, pp. 689-696, 2009.
Mathurin Massias, Alexandre Gramfort, and Joseph Salmon. Celer: a fast solver for the lasso with dual extrapolation. In International Conference on Machine Learning, pp. 3315-3324. PMLR, 2018.
Osval Antonio Moótes,nos-López, Abelardo Montesinos-López, Paulino Pérez-Rodrríuuez José Al- berto Barrón-López, Johannes WR Martini, Silvia Berenice Fajardo-Flores, Laura S Gaytan- Lugo, Pedro C -Mancila,, and José Crossa. review of deep learning applications for genomic selection. BMC genomics, 22(1):1-23, 2021.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 141.66614, 2014.
Colin L Noble, Alexander R Abbas, Jennine Cornelius, Charlie W Lees, Gwo-Tzer Ho, Karen Toy, Zora Modrusan, Navneet Pal, Fiona Zhong, Sreedevi Chalasani, et al. Regional variation in gene expression in the healthy colon is dysregulated in ulcerative colitis. Gut, 57(10):1398 1405, 2008
Bruno Olshausen and David Field. Sparse coding with an overcomplete basis set: A strategy employed by vI? Vision research, 37(23):311-33325 1997.
Heidi S Phillips, Samir Kharbanda, Ruihuan Chen, William Forrest, Robert Soriano, Thomas D Wu, Anjan Misra, Janice M Nigro, Howard Colman, Liliana Soroceanu, et al. Molecular sub- classes of high-gret high-grade glioma predict prognosis, delineate pattern of disease progression, and resemble stages in neurogenesis. Cancer cell, 93)):577-733, 2006.
Clarice Poon and Gabriel Peyré. Smooth bilevel programming for sparse regularization. Advances in Neural Information Processing Systems, 34: 1543-155, 2021.
Clarice Poon and Gabriel Peyré. Smooth over-parameterized solvers for non-smooth structured optimization. arXiv preprint arXiv:2205.01385, 2022.
Aleix Prat, Giampaolo Bianchini, Marlene Thomas, Anton Belousov, Maggic CU Cheang, Astrid Koehler, Patricia Gómez, Vladimir Semiglazov, Wolfgang Eiermann, Sergei Tjulandin, et al. based pam50 subtype predictor identifies higher responses and improved survival outcomes in her2-positive breast cancer in the noah study. Clinical Cancer Research, 20(2):511-522 2014.
Prajit Ramachandran, Barret Zoph, and Quoc V. Le. Searching for activation functions, 2017.
Akshay Rangamani and Andrzej Banburski-Falie Fahey. Neural collapse in deep homogeneous classifiers and the role of weight decay. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 4243-4247, IEEE, 2022.
Jasson DM Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference Machine learning, pp. 713- 719, 2005.
Fadil Santosa and William W Symes. Linear inversion of band-limited reflection seismograms. SIAM Journal on Scientific and Statistical Computing, 1303-3077, 1986.
Simone Scardapane, Danilo Comminiello, Amir Hussain, and Aurelio Uncini. Group sparse regu- larization for deep neural networks. Neurocomputing, 241:81 2017.

---

Under review as a conference paper at ICLR 2023
Mark Schmidt, Glenn Fung, and Rmer Rosales. Fast optimization methods for 11 regularization: A comparative study and two new approaches. European Conference on Machine Learning, pp- 286-297. Springer, 2007.
Shirish Krishnaj Shevade and S Sathiya Keerthi. simple and efficient algorithm for gene selection using sparse logistic regression. Bioinformatics, 19(17):226-22553, 2003.
Yijun Sun, Jin Yao, and Steve Goodison. Feature selection for nonlinear regression and its appli- cation to cancer research. In Proceedings of the 2015 SIAM International Conference on Data Mining, pp. 73-81. SIAM, 2015.
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Pro- cessing Systems, 33:6377-653 2020.
Robert Tibshirani. Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
Ryan J Tibshirani. Equivalences between sparse models and neural networks. Working Notes. URL http:://www. stat. cmu. eduf ryanths/hpperr/pparxityyyuu pdf. 2021.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:20002.0377,,200 2020.
Zihao Wang and Liu Ziyin. Posterior collapse of linear latent variable model. arXiv preprint arXiv:2205.04009 2022.
Larry Wasserman. All of statistics: a concise course in statistical inference. Springer Science & Business Media, 2013.
Mengjia Xu, Akshay Rangamani, Andrzej Banburski, Qianli Liao, Tomer Galanti, and Tomaso Poggio. Deep classifiers trained with the square loss. 2022.
Makoto Yamada, Wittawat Jitkrittum, Leonid Sigal, Eric P Xing, and Masashi Sugiyama. High- dimensional feature selection by feature-wise kernelized lasso. Neural computation, 26(1):185- 207. 2014.
Liu Ziyin, Botao Li, and Xiangming Meng. Exact solutions deep linear network, 2022.
12

---

Under review as a conference paper at ICLR 2023
104
Lane
LMgS
Swool
Time 1683
8
Time Loed
101-
101
109
10%
10"1
1.0
1.7
10*
107
10'
dimenslon
dimension
1.00
Lava Galneo
10"
Leve
Tine (b0c)
Time (oec)
33760
10'
10'
10"1
10a1
10a
162
10
10a
10a
162
10
10a
dimemion
dimemius
Figure 6: Performance of spred across different values of From upper left to lower right:
2, 3, 4, 5. The main text contains the case when a = 1.
A EXPERIMENTAL CONCERNS
A.1 CONVERGENCE OF SGD ON spred LASSO
Figure presents the training trajectory under different value of a. We can see from the left subgraph of Figure 7 that L/ fails to produce the sparse solution even though the LI norm of the weight matrix almost identical to spred. When the a gets larger, our method significantly outperforms L/ because it achieves the highest sparse ratio but almost zero LI norm of the weight matrix.
A.2 spred LASSO FOR DIFFERENT REGULA RRIZAAIINIIION STRENGTHS
For completeness, we also compare spred with the baseline Lasso methods across different levels of regularization. See Figure 6. As the figure shows, our observation in the main text holds across different strengths of regularization.
A.3 SPARSE CODING
Our theory suggests straightforward solution using gradient descent. We parametrize by W V and replace the L1 norm with a corresponding weight decay for W and V respectively. This means that we optimize the following objective:
min X B(W V)Il2 < |IV112.
(10)
This objective is differentiable and the (stochastic) gradient descent method can be applied. We normalize B by its columns as in previous works. Additionally, found that normalization S by the rows significantly speeds up the training procedure. We let = 2048. We train S with simple stochastic gradient descent, and B is trained with the LBFGS optimizer, with batch size of 5000. The dataset consists of 2 x 10a pieces of 16 x 16 patches of images taken from natural scenes. See Fig. for a few examples of the found filter. The experiment finishes within 10 mins. Existing methods that are based on the lasso algorithm are found to be at least order of magnitude slower, consistent with our finding the previous section. Also, it is worth commenting that our method compatible with the alternative optimization schemes and one can simply replace the Lasso step with GD on the redundant parametrization to obtain acceleration when the dimension of S is high. The application of spred to this problem produces the correct Gabor filters shown in Figure 3. Again, this shows that sparsity can actually be achieved with gradient descent on the suggested optimization.
13

---

Under review as a conference paper at ICLR 2023
Zero rate (a = 0.11am)
Zero rate (a 1.00at.)
1.0
1.0
L1(10-F)
0.8
L1(10-12)
0.8
spred(10
Zero Rate
L1(10-9)
0.6
spred(10
0.6
L1(10 12)
spred/10-1)
0.4
spred(10-1F)
0.2
0.2
0.0
10
101
102
10a
10a
10a
107
10a
10a
10
Step
Step
Figure 7: The training trajectory of Lı and spred when a 0.3 (left) and a 2.3(right)
layerd, weree....oov..eeeig...
layer4, www.nw..ovvvv...ooo weightt
module.leyerd..k weight
Reste:1
18
Re
spred Reshetta
sp rdl Reshetia
Spred ResNet18
10'
165
105
201
104
10a
207
107
107
10"
101
10
10"
105
105
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.5
0.B
3.0
0.3
0.2
0.4
0.6
0.8
1.0
weights
weights
seiigts
Figure 8: (normalized) Parameter distribution of the three largest convolutional layers of ResNet18 trained on CIFARIO with SGD. The blue histogram shows the distribution of normal ResNet18 with weight decay strength x 10-4, which very dense. The orange shows the distribution of spred ResNet18 (also with 5 x 10 weight decay), which exhibits predominant peak at zero that includes more than 99.9% of all the weights parameter the layer. This shows that training even with very small value of regularization with spred already leads to parameter distribution that favors sparsity.
Table 2: Basic statistics of seven gene datasets.
Dataset
#features
#labels
#samples
#samples #features
GDSI815 (Phillips et al., 2006)
22283
15
400
1.79%
GDS1816 (Phillips et al., 2006)
22645
15
400
1.77%
GDS3268 (Noble et al., 2008)
44290
8
606
1.37%
GDS3952 (LaBreche al., 2011)
54675
8
324
0.59%
GDS4761 (Kimbung et al., 2014)
52378
7
91
0.17%
GDS5027 (Prat et al., 2014)
54675
468
0.86%
A.4 WEIGHT DISTRIBUTION OF A TRAINED RESNET
We show more results the weight distribution of trained ResNet18, with roughly 11M parame- ters in total. We plot the parameter distribution of the three largest convolutional layers, each with roughly 2.3M parameters. See Figure 8.
A.5 DETAILED DESCRIPTION THE FEATURE SELECTION TASK
See Table for the statistics of the datasets. The datasets are taken from the public datasets of Gene Expression Omnibus." The indices of the datasets the same the indices on GEO.
htttps: pettps::/xww.ndtr ncbi nlm. www.nih.ggoo.. www..googeee...oo.oo
14

---

Under review as a conference paper at ICLR 2023
80
80
Tpp-1 accuracy
Top-1 accurary
Random
Random
10
Magnitude
Magnitude
40
SNIP
SNIP
GraSP
20
GraSP
SynFlow
SynFlow
spred
spred
10a
10
10
10
10a
10"
10'
10a
compression
ratio
compressian ratio
Figure 9: Performance of the proposed method in comparison to the exisitng methods that allow for compression upto at least 1000 times. Left: CIFARIO. Right: CIFAR 100. This shows that Ln may be a very competitive and useful baseline for model compression in deep learning.
A.6 COMPARISON OF THE CIFAR EXPERIMENT WITH PREVIOUS RESULTS
In this section, we explicitly present the result for CIFARIO and CIFARIOR with previous results. As we have discussed in the main text, spred performs very favorably in comparison with the previous results. See Figure 9. Here, we compare with the a trivial baseline of randomly pruning the network parameters. The method of pruning by magnitude after training (Gale al., 2019; Blalock et al., 2020), SNIP (Lee et al., 2018), GRasP (Wang et al., 2020), and SynFlow (Tanaka et al., 2020). To the best of our knowledge, SynFlow the only other method that allows one to compress model upto 10th compression ratio on CIFARIO without becoming trivial.
B PROOF
B. PROOF OF THEOREM 1
For notational conciseness, we prove the case when this simpler case if we redefine both U and W by constant scaling, We first prove a lemma.
The case can be reduced to
Lemma 1. For all i, any local minimum of Eq. (2) satisfies
IU,1 U.|=lW.l
(11)
Proof. We prove by contradiction. Suppose not. Then there exists U", W and index i such that [U.] + [Wa] and they are a local minimum of L(U" @ W') L2 reg, where
La reg. <(|U |[]]
(12)
Now, consider an infinitesimal perturbation of the solution such that U, Uf[1 dz) and W; (1 - dz). straightforward to see that, by the definition of element-wise multiplication,
L(U" & W L(U & W).
(13)
Without loss of generality, we assume |U,| < [W&]. Now, because U: W,, the Le reg. term strictly reduces:
U + 2dz) + W (1 -dd)) U. W 2(U W dd
(14)
This means that U, and W2 cannot be a local minimum. The proof complete. O
The above lemma implies that to find the global minimum of Eq. (2), it suffices to minimize over the solutions such that Wil = |U&] for all i. The following lemma shows that the two loss function identical if restrict the domain where [W]] [U.]
Lemma 2. Let W @ U = V and [W] for all Then,
Typ (W,U) T.I.
(15)
15

---

Under review as a conference paper at ICLR 2023
Proof. When [W,] = [UA,
Lis = L(U@W) + 2x ΣV² [u²++ +w? w?
(16)
[.U @ W) + 2
(17)
= L(U @ W) + 2n: @ W
(18)
By definition, U @ W- =V V, and so this loss is, in turn equivalent to the following loss:
L(V) 2x||V|I1.
(19)
This finishes the proof. 0
Now, we are ready to prove the main theorem. To repeat, the main theorem states the following (when a= = B). Theorem 4. Let B= and
(U, L(U W.Va) + allui| B|
(20)
Then, (U, (U.W.V Eq. (1).
W.V) V2) a global minimum of Eq. (2) if and only if (U a W, Va) is a global minimum of
Proof. The theorem immediately follows from the combination of the previous two lemmas. D
B.2 PROOF OF THEOREM 2
To repeat, the theorem states the following.
Theorem 5. (U, W) is a local minimum of Eq. (2) if and only (f V U @ W is local minimum of Eq (1) and (b) [U,] [W
Proof. For both directions, we prove by contradiction. The forward direction is much easier to prove. Let (U, W) be a local minimum of Ter and suppose V is not local minimum of V. Then, one can infinitesimally perturb V such that V + de has smaller loss. This corresponds to perturbation in U and W under the constraint [&A] [Wa] By Lemma 2, Lys under this perturbation is also smaller than the unperturbed value. Thus, (U, W' is
local minimum a contradiction.
We now consider the backward direction. Let V be local minimum of L1A1 and suppose (U, U) is a local minimum of V. As Lemma shows, if we restrict the subspace where [U]]= [W,) there cannot be perturbation that leads to a lower loss value because in this subspace, Lys is equivalent TVV.. Thus, that (U, W) is not a local minimum implies that there exists perturbation day and daw such that (U dæy, W daw) ) has smaller loss value than (U, W). The loss function value
(21) such that I(U dzu)al # I(U 22 Now, we can construct a new parameter U' sign(U dæy) V(U dzu) & (W + daw)), W" = (W + daw) @ (W dzw). This transformation is also infinitesimall and leaves the term unchanged. However, strictly decreases the L2 term
L((U dzv) (W daw)) + K(IlU dærll IIW + dzw Lys (U
2 dzv) @ (W + daw )12 -|=x< |IU + dzwrl12 |[W d2wl12.
(22)
Thus, have constructed model such that | |W/| for all i, and with strictly smaller loss. By Lemma 2, this implies that V is not local minimum of Lr1- This is a contradiction. The proof complete.
C PROOF OF THEOREM 3
Theorem 6. Let a8 x² and
(sr LLW. Vo) +au + S||W1
(23)
Then, (u, W, Va) is a global minimum of Eq. (2) if and only if (a) ju] = |[]]] for all i and (b)
(wW, Va) is global minimum of Eq. (1).
16

---

Under review as a conference paper at ICLR 2023
The proof is similar to that of Theorem 1, and we thus only give proof sketch.
Proof Sketch. When |u| = ||W]22, it easy to check that the two loss functions agree in value. When lu] || one always find continuous transformation (rescaling and W simultaneously) of u and W such that the loss function is strictly reduced, and these points cannot be local minima. O
The proof also shows that every minimum of L,s corresponds to the local minimum in the original loss, consistent with Theorem 2. This result can be immediately generalized to the case of multi- group L1, where want apply L, (possibly with different strengths) different groups. This can be proved by simply induction on the size of the set of groups and using Theorem 3.
17


Reviews:
[{"review_id": "QDpRxX0Xso", "reviewer": "Reviewer_SaAB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new method for solving L1 regularized problems using redundant parametrization. Theoretical results show that the regularization on the redundant parameters is equivalent to L1 (overall, and group-wise). These results are then applied towards various use-cases ranging from simple models (Lasso) to deep NNs. Overall, the paper provides an easy way to solve with L1 penalty under various settings, though there are some aspects which need to be addressed (discussed later in this review). ", "summary_of_the_review": "Overall, the paper provides simple but useful ways to learn with L1 penalty. Different applications are discussed in the paper, though the focus might have been more towards computational comparisons. ", "strength_and_weaknesses": "Strengths of the paper:\n- The core contribution is easy to understand and has theoretical justifications. The theorems and proofs are easy to follow. \n- Some interesting perspectives on sparse regularization are discussed.\n--- The discussion on 5.1 giving the node sparsity perspective to weights decay is interesting. \n--- The compression results in Fig 5 are impressive. \n\nWeakness\n- It is confusing if the paper is focused on computational methods or sparse models. If it is the former, the discussions on comparisons should have been more comprehensive against other computational algorithms for the same problem considered. That does not seem very conclusive. Examples below:\n-- Proximal methods are popular for solving with L1 penalty. Need more clarity on why they aren't applicable for the problems considered. \n-- Figure 2 is a bit unfair because it does not include any of the proximal algorithms for lasso. This is true for the sparsity plot (2a) and the time splot (2b). Need a comparison with proximal gradient methods to make any recommendations from the plots. \n-- Is problem (8) equivalent to group Lasso? Are there any discussions on comparison with Group Lasso, formulation-wise and computational-wise ?\n\nSome open questions:\n- Why does the time complexity as given from Figure 2b independent of d for gradient methods ? isn't computation of the gradient itself linear in d ?\n- The results of sparse coding are not given in full (Both in the main paper as well as the Appendix). The baselines are not discussed well. Neither there are any quantitative comparisons.\n\n \n\n- (Minor) Typos / Notational inconsistencies\n   -- Theorem 1 discusses w.r.t U, W, V_d whereas Theorem 2 discusses only w.r.t U, W, even though both theorems discuss the solutions for the same problem\n   --  Theorem 3 is not consistent with the problem (2), rather it applies to (4). \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KzpDQ3Fvhq", "reviewer": "Reviewer_D7C8", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a very neat result: regularization with $\\ell_1$ penalty is equvalent to $\\ell_{2}^{2}$ penalty up to (over) reparametrization of the model parameter. This provides several insights on the origin of sparsity in trained neural network architecture. The authors exploit this connection to provide simpler and faster solver for Lasso optimization problem.", "summary_of_the_review": "The paper explores a nice connection between learning via overparametrized model and learning via sparsity. An explicit and fundamental correspondence between the two is established and allows for nice insights and algorithmic development for both.\nUnfortunately, the main result is already published more than a year ago. I encourage the authors to review the paper I mentioned above and reconsider the contributions.", "strength_and_weaknesses": "The results are transparently presented, and the paper is quite complete and easy to follow.\n\nThe connection between deep learning methods and classical Lasso problem is extremely simple but very deep and will probably be impactful in understanding DNN performances.\n\nThe numerical experiments are also convincing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CNo49-D9Z1", "reviewer": "Reviewer_5KD8", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper propose a reparametrization of the L1 loss to efficiently solve L1 penalized problems. \nExperiments are proposed on standard L1-penalized optimization problems and sparsity deep learning (network compression).", "summary_of_the_review": "The application to network compression might be interesting, but the idea is not new, the paper lack a proper literature  review, experiments should be more comprehesive", "strength_and_weaknesses": "Strength\nThe application to network compression seems interesting\n\nWeaknesses\n- IMO the paper clearly lack a proper literature review: **the proposed idea, called \"main results\", is not new** and has been studied for a long time in the machine learning community. Recent version of this idea, usually called variational formula, can be found in [1], [2] or [3]. Authors can also read the related work of [4] for a comprehensive review on the subject.\n- All the experiments **lack standard competitors**\n- Section 4.1.authors compare to **gradient descent directly on the L1 loss** and LARS, which are known to not converge, or bing unstable. \nI would suggest comparisons against working sets based solver such as blitz [5], celer [6] or skglm [7], and for multiple values of the regularization parameter, as it is done in [4].\n- Section 4.2 simply has no quantitative results\n\n\n[1] Rennie, J.D. and Srebro, N., 2005, August. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference on Machine learning (pp. 713-719).\n\n[2] Hastie, T., Mazumder, R., Lee, J.D. and Zadeh, R., 2015. Matrix completion and low-rank SVD via fast alternating least squares. The Journal of Machine Learning Research\n\n[3] Hoff, P.D., 2017. Lasso, fractional norm and structured sparse estimation using a Hadamard product parametrization. Computational Statistics & Data Analysis\n\n[4] Poon, C. and Peyré, G., 2021. Smooth bilevel programming for sparse regularization. Advances in Neural Information Processing Systems\n\n[5] Johnson, T. and Guestrin, C., 2015, June. Blitz: A principled meta-algorithm for scaling sparse optimization. In International Conference on Machine Learning (pp. 1171-1179). PMLR.\n\n[6] Massias, M., Gramfort, A. and Salmon, J., 2018, July. Celer: a fast solver for the lasso with dual extrapolation. In International Conference on Machine Learning (pp. 3315-3324). PMLR.\n\n[7] Bertrand, Q., Klopfenstein, Q., Bannier, P.A., Gidel, G. and Massias, M., 2022. Beyond L1: Faster and Better Sparse Models with skglm", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9k3n84SXqU", "reviewer": "Reviewer_GwGp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Another method for optimizing a loss function plus L1 penalty is proposed that splits each variable into a product and adds an L2 penalty to both terms. Experiments compare sparsity, computational efficiency and accuracy on some datasets.", "summary_of_the_review": "A nice (in some ways) and probably novel solution to optimizing an L1 regularized objective, but the method has drawbacks (doubling the number of variables, not producing exact sparsity), several relevant methods were not even discussed (Andrew & Gao, Lipton & Elkan) and the empirical evaluation is lacking in several respects.", "strength_and_weaknesses": "There has been so much work on L1 optimization over the last 15-20 years, it is difficult to keep track of it all. The proposed method is nice, in that it reduces the non-smooth objective to a smooth one that can be solved by any general method including stochastic methods. I vaguely remember seeing a method like this maybe ten years ago, certainly some methods which split the variables in two like this, and I'm a little worried that this has been discovered before. Have any other reviewers seen something similar? But I am not certain, so I won't hold it against the paper.\n\nAnother downside to working on a problem with so much prior work is that it is difficult to compare with everything. I can think of two uncited methods that have all the advantages of the proposed method without its two principle disadvantages, namely that it requires doubling the number of variables and that it does not set weights to exactly zero and therefore requires a pruning step. For smaller datasets, I would think a method like Orthant-wise L-BFGS should be at least as fast, maybe much faster. (That algorithm requires complete passes over the data, but converges in a relatively small number of steps and does produce exact sparsity.) For larger datasets, there is the method of https://arxiv.org/pdf/1505.06449v3.pdf that is stochastic, can be combined with accelerated stochastic methods like Nesterov acceleration, Adagrad/Adam, and also produces exact sparsity.\n\nThe empirical result section is lacking. In Figure 2 it is not surprising that unmodified stochastic algorithms applied to the L1 regularized objective do not produce sparsity (even *near sparsity* with parameters < 1e-6) because the non-differentiability at 0 will cause updates to hop over the value 0, unless the learning rate is extremely small. I don't understand the right half of figure 2: how is it possible that spred works equally fast on all input sizes? I hope the authors can explain that in the rebuttal. Table 1 only compares with unmodified SGD applied to the L1 objective, which as I said before should not be expected to work. The authors cite Gale et al. and Blalock et al. which discuss a wide variety of L1 algorithms-- some of these must be used as a baseline. At the very least, you have to compare to simple magnitude pruning which was shown in Gale et al. to be competitive to more complex methods. Also the benchmark tasks are small and outdated. Blalock created \"shrinkbench\", a modern test suite for shrinkage methods; it should be relatively easy to compare on those datasets, no?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject