Mask in the Mirror: Implicit Sparsification

Authors: Tom Jacobs, Rebekka Burkholz
Primary area: optimization
Keywords: Continuous sparsification, Implicit bias, Mirror flow, Time-dependent Bregman potential, Regularization, Rich regime

Abstract:
Continuous sparsification strategies are among the most effective methods for reducing the inference costs and memory demands of large-scale neural networks. A key factor in their success is the implicit $L_1$ regularization induced by jointly learning both mask and weight variables, which has been shown experimentally to outperform explicit $L_1$ regularization. We provide a theoretical explanation for this observation by analyzing the learning dynamics, revealing that early continuous sparsification is governed by an implicit $L_2$ regularization that gradually transitions to an $L_1$ penalty over time. Leveraging this insight, we propose a method to dynamically control the strength of this implicit bias. Through an extension of the mirror flow framework, we establish convergence and optimality guarantees in the context of underdetermined linear regression. Our theoretical findings may be of independent interest, as we demonstrate how to enter the rich regime and show that the implicit bias can be controlled via a time-dependent Bregman potential. To validate these insights, we introduce PILoT, a continuous sparsification approach with novel initialization and dynamic regularization, which consistently outperforms baselines in standard experiments.

Decision: accept (poster)
Reviewer scores: 5, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730356398241

thread_type:
official_review

<thread_object>
creator: reviewer_uabp

<content>
summary:
This paper studies the implicit sparse regularization of continuous specification. By studying the implicit bias of a specific mirror flow with a time-dependent Bregman potential, the authors propose a novel continuous sparsification method  "parametric implicit lottery ticket" (PILoT). The convergence and optimality is shown theoretically, and the effectiveness in real-world examples is demonstrated numerically.

strengths:
The paper is well-written and easy to follow. I didn't go through the proofs, but the illustrations make sense, and the technical contribution is solid.

weaknesses:
One point that might limit the significance of the conclusion is that the implicit regularization appears after the model fits the data perfectly (Theorem 2.3), which might not hold in reality.

questions:
The literature below is related but missed

* Vaskevicius et al, Implicit regularization for optimal sparse recovery, NeurIPS 2019.
* Li et al, Implicit Sparse Regularization: The Impact of Depth and Early Stopping, NeurIPS 2021.
* Zhao et al, High-Dimensional Linear Regression via Implicit Regularization, Biometrika 2022.
* Li et al, Implicit bias of gradient descent on reparametrized models: On equivalence to mirror descent, NeurIPS 2022.
* Li et al, Implicit Regularization for Group Sparsity, ICLR 2023.

Minor comments:
* .(dot) is missed for the leading bold text in Section 1.1
* Line 213, "(Ziyin & Wang, 2023)..." is not a sentence.
* Line 404, "return..." goes to the next line
</content>
</thread_object>

</thread>
<thread>
creation date:
1730713148573

thread_type:
official_review

<thread_object>
creator: reviewer_jfbc

<content>
summary:
In this paper, the authors focus on the problem of finding sparse neural networks. They propose a new method called PILoT based on theoretical analysis on simple diagonal linear networks. They use the insights gained from theoretical analysis to improve previous method called spred to introduce dynamic regularization strength and initialization scheme. Experiments are provided to show the improvement of the proposed method.

strengths:
-	Studying the sparsification of neural networks is an interesting research problem.
-	The proposed method that applies the idea of implicit/explicit regularization to pruning seems to be new.
-	The performance of the proposed method shown in experiments suggests that there is some improvement over the previous works.

weaknesses:
-	Many places are not very clear to me as a reader.
-	See questions section below.

questions:
-	In line 228, I was wondering why ‘’the potential $R$ attains its global minimum at the initialization $x_0$... In consequence, we would not promote actual sparsity’’. I’m confused about this. As many paper that authors cited, when initialization scale goes to 0, the final implicit regularization is $\ell_1$ norm that promotes the sparsity.
-	In Theorem 2.2, what is $\alpha_\infty$? Is it regularization $\alpha_t$ at time $t\to\infty$? If not, what does it mean? If so, it seems to me that $\alpha_t\to 0$ given the assumptions. This would make $\alpha_\infty=0$, which makes the statement very weird. Moreover, if $\alpha_\infty\neq 0$, then why $x_t$ would converge to a minimizer of $f$ given the existence of a regularization term.
-	In line 347, I wonder if authors could explain more on why eq (6) explains spred performs better than LASSO. I believe there are many classical algorithms that can solve LASSO better than just using gradient descent/gradient flow, and they may not have such problems.
-	In line 374, I wonder why $\beta=1$ is motivated by the discretization of the gradient flow. It is not clear to me what are the connections here.
-	In the proposed algorithm PILoT (Algorithm 1), I wonder why $\alpha_k$ should be increased when the sparsity $\|m_k \odot w_k \|_1\ge K$. Since decreasing $\alpha_k$ would promotes better sparsity, I feel $\alpha_k$ should be decreased in this case?
-	In experiments, what are the schedules of $\alpha_k$ that are used?


Typo:

-	Below eq (6), missing ( in expression of $a_t$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731039505963

thread_type:
official_review

<thread_object>
creator: reviewer_l22t

<content>
summary:
This paper studies the mirror flow of the time-dependent $L_2$-regularized optimization problem which is parametrized by masked weights $x=m\odot w$. The authors derive the corresponding Bregman potential for the mirror flow and prove a convergence result for quasi-convex loss functions. Inspired by the forms of the derived Bregman potential and the gradient flow, the authors propose PILoT, which takes (i) a strategy to control the strength of $L_2$-regularization dynamically and (ii) a initialization for $m$ and $w$ that enables sign flipping. Evaluations show that PILoT outperforms baselines on CIFAR 10 and CIFAR 100.

strengths:
* The theoretical result seems sound though I didn't check the proofs. 
* The Bregman potential offers insight on $L_1$ regularization effect. 
* The gradient flow also offers insights on why spred outperforms Lasso from the perspective of convergence rate. 
* I appreciate that the authors also develop an algorithm inspired by the theory.

weaknesses:
The writing is poor. Some notations are never explained, e.g., $m^2$ (though I can see that's the square of $L_2$ norm, but it is not the standard notation). The experiments are also a bit hard to read. Please see questions.

questions:
1. I found table 1 confusing. Why do all methods have duplicates in the table?
2. At line 227, why does $R$ attain its global minimum at $x_0$ when $R$ is $L_1$ norm?
3. At line 218, is there any formal result stating that explicit regularization would lead to a trade-off? I can see that implicit bias of the reparametrized optimization is helping achieve both sparsification and low loss, but does that imply an explicit regularization forces a trade-off?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731068861430

thread_type:
official_review

<thread_object>
creator: reviewer_cfhk

<content>
summary:
"Spred" is a recent algorithm that implicitly achieves sparse solutions through reparameterization. To understand why "Spred" outperforms LASSO, the authors analyzed its training dynamics using the mirror flow framework. They demonstrated that when the regularization term in "Spred" is time-dependent, it can smoothly transition between implicit L2 and L1 regularization. Building on this insight, they introduced PILoT, an approach that dynamically adjusts the regularization strength. Finally, the authors validated the effectiveness of PILoT through experiments on CIFAR-10/100 and ImageNet datasets.

strengths:
The theoretical analysis of the reparametrization with time-varying weight decay is solid and novel. It is valuable to first develop a deep theoretical understanding, which then serves as a basis for algorithmic improvements.

weaknesses:
**Major:**
- **Inaccurate and unclear writing**: The presentation in the paper could benefit from a substantial revision to improve clarity, particularly in the latter half of Section 1 and Sections 2, 3, and 5. Additionally, some inaccuracies need to be addressed. For example, the abstract states that "A key factor in their (continuous sparsification) success is the implicit L1 regularization induced by jointly learning both mask and weight variables." However, the discussion from Lines 54-65 suggests that this implicit L1 regularization is exclusive to the "Spred" algorithm, which utilizes reparameterization. The paper is currently difficult to follow, which is my primary concern.
- **Computation and memory costs of reparameterization**: The reparameterization approach proposed in the algorithm effectively doubles the number of parameters, resulting in increased computational and memory demands. However, this is not discussed in the paper.

**Minor:**
- **Figure 4's legend is confusing**: It would be clearer to rename "mw LRR" to "LRR with reparameterization" and "x LRR" to "LRR."
- **Unclear variables in Algorithm 1**: The variables "u_0" and "v_0" introduced in Algorithm 1 are not referred to in subsequent sections, leading to confusion about their purpose.

questions:
N/A
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies the implicit L_1 regularization (by optimizing a function of the form f(m \odot w) with regularizations on m and w) and discuss how this outperform explicit L_1 regularization. The main idea is that the training dynamics first gives an implicit L_2 regularization and then transitions to L_1 regularization over time. The analysis is based on mirror flow framework. Overall the reviewers think the paper provides interesting new insights on why implicit L_1 regularization works. The main concerns were on the clarity of the paper which has been partly addressed during the response period.