Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
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.

Another 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.

The 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?
clarity,_quality,_novelty_and_reproducibility: Mostly clear, a few typos.
Quality: low, for aforementioned reasons.
Novelty: probably novel.
Reproducibility: reproducible, but the authors should follow the advice of Blalock et al. (which was cited) to make sure their results can be easily compared to other shrinkage methods.
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.
review_title: null

final_score: rating: 1: strong reject
review_content: 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.
strength_and_weaknesses: The results are transparently presented, and the paper is quite complete and easy to follow.

The connection between deep learning methods and classical Lasso problem is extremely simple but very deep and will probably be impactful in understanding DNN performances.

The numerical experiments are also convincing.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written.

The authors should provide the source codes for a better reproducibility.

The major concern of the paper is that the main result is known already. I refer to "Equivalences Between Sparse Models and Neural Networks" by Ryan J. Tibshirani, April 15, 2021. 
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.
Unfortunately, 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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). 
strength_and_weaknesses: Strengths of the paper:
- The core contribution is easy to understand and has theoretical justifications. The theorems and proofs are easy to follow. 
- Some interesting perspectives on sparse regularization are discussed.
--- The discussion on 5.1 giving the node sparsity perspective to weights decay is interesting. 
--- The compression results in Fig 5 are impressive. 

Weakness
- 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:
-- Proximal methods are popular for solving with L1 penalty. Need more clarity on why they aren't applicable for the problems considered. 
-- 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. 
-- Is problem (8) equivalent to group Lasso? Are there any discussions on comparison with Group Lasso, formulation-wise and computational-wise ?

Some open questions:
- 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 ?
- 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.

 

- (Minor) Typos / Notational inconsistencies
   -- 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
   --  Theorem 3 is not consistent with the problem (2), rather it applies to (4). 

clarity,_quality,_novelty_and_reproducibility: - the writing style is easy to follow, though it can do better with more consistent notations and formal definitions. 
- The main drawback, as discussed before, is the confusion between the perspective of the paper (modeling vs computational). The Baselines for computational comparisons (on the same problem as that of the proposed solution applies to) seem to be inadequate. 
- The core contribution, Theorems 1,2,3 are quite useful for studying L1 regularization. 

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.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper propose a reparametrization of the L1 loss to efficiently solve L1 penalized problems. 
Experiments are proposed on standard L1-penalized optimization problems and sparsity deep learning (network compression).
strength_and_weaknesses: Strength
The application to network compression seems interesting

Weaknesses
- 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.
- All the experiments **lack standard competitors**
- Section 4.1.authors compare to **gradient descent directly on the L1 loss** and LARS, which are known to not converge, or bing unstable. 
I 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].
- Section 4.2 simply has no quantitative results


[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).

[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

[3] Hoff, P.D., 2017. Lasso, fractional norm and structured sparse estimation using a Hadamard product parametrization. Computational Statistics & Data Analysis

[4] Poon, C. and Peyré, G., 2021. Smooth bilevel programming for sparse regularization. Advances in Neural Information Processing Systems

[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.

[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.

[7] Bertrand, Q., Klopfenstein, Q., Bannier, P.A., Gidel, G. and Massias, M., 2022. Beyond L1: Faster and Better Sparse Models with skglm
clarity,_quality,_novelty_and_reproducibility: Unfortunately the proposed idea is not new, and the experimental investigation is not properly done

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
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The overall contribution is to use a simple method for solving general L1 penalized objectives with gradient descent, using a redundant l2 penalty.
The reviewers agree that the idea proposed is not new, that the paper lack a proper literature review and that experiments were limited.
Hence I follow their choice to reject the paper.


justification_for_why_not_higher_score: The lack of novelty and the poor experiments comparisons are the main reasons.
justification_for_why_not_lower_score: The score is already quite low. Some experimental proposition seems to be of interests to some reviewers though (network compression).
Decision: Reject