Penalising the biases in norm regularisation enforces sparsity

Summary

This work considers a single hidden layer ReLU network $f_\theta: \mathbb{R} \rightarrow \mathbb{R}$ with biases in the hidden layer as well as skip connections. In this context the representational cost $R(f)$ required to interpolate a function $f: \mathbb{R} \rightarrow \mathbb{R}$ is studied, which is defined as the infinimum of the 2-norm of the network parameters such that $f_\theta = f$. Following prior work and in order to consider the larger space of functions that can be approximated to an arbitrary degree by such finite width networks, (potentially) infinite width networks can be parameterized by a measure on the unit sphere, allowing the representation cost to be recast as the total variation of this measure such that $f_\mu = f$. Unlike prior work, the the bias terms of the hidden layer are included in the norm penalty. As a result of this, for a univariate Lipschitz function $f$ the representation cost is the total variation of $\sqrt{1-x^2}f''$ instead of just $f''$ when the bias terms are not included. Given a training sample $(x_i, y_i)_{i=1}^n$ the minimum-norm (with respect to the the total variation of $\sqrt{1-x^2}f''$) of interpolators $f$ such that $f(x_i) = y_i$ are studied. In Theorem 2 it is shown that the minimum-norm interpolator in this context is unique, which is not necessarily the case when the bias terms are not included. Furthermore, assuming the data is such that the linear interpolation between any consecutive set of 6 points is neither convex or concave, then in Theorem 3 it is shown that the minimum norm interpolator has a minimal number of kinks.

Strengths

This work builds on prior work by studying the impact of including the bias parameters in the 2-norm parameter regularization term. In particular, the min-norm interpolator in this context is unique and the results also suggest including the bias terms perhaps encourages the network towards finding sparser network solutions in terms of the number of kinks or bumps. The work appears technically sound however I did not thoroughly read the appendices. The paper is also well written and structured. The contribution appears tangible if somewhat incremental.

Weaknesses

1. One of the key findings over prior works is that regularizing the bias terms encourages a simpler interpolating function with only a few kinks. However, this relationship is only proved in a restrictive data setting where the linear interpolation between a small number of consecutive points is neither convex or concave. This feels like quite a restriction, furthermore, from the discussion lines 427-432 of the supplementary material, it seems at least experimentally that when the data does contain convex or concave regions then the minimum norm interpolator and sparsest interpolators are not really related. Therefore I wonder whether this takeaway is really a general principle or more a quirk only exhibited in a highly specific setting. 2. The setting, i.e., univariate data, the necessity for skip connections whose parameters are not included in the penalty is also restrictive, albeit in line with other works. The focus on studying the min-norm interpolators also does not capture learning. 3. Another minor comment I would have is that the statement to the effect of ``the most important factor behind generalization is the norm of the parameters" in the introduction is a bit strong in my opinion. I would argue the jury is still out on this, in practice one can fairly often train a network with no explicit regularization and it can do fine and there is also a line of work suggesting implicit regularization cannot be explained in terms of norm minimization, see e.g., https://arxiv.org/pdf/2005.06398.pdf, https://arxiv.org/abs/2012.05156.pdf.

Questions

1. Does one observe learning a smoother function, i.e., one with less kinks or bumps experimentally when the bias term is included versus not included and how does this vary with say the regularization parameter as well as the smoothness of the target function? 2. If one considers deeper networks or multivariate inputs or a different loss function etc. is there still evidence of a tendency towards learning a function with fewer bumps when bias terms are included in the penalty? 3. Empirically simulating across a number of trials what is the distribution of the learned function look like? Does it concentrate around the minimum norm interpolator? 3. In general how sensitive are the findings of this work to say to changes in network architecture (e.g., different activation function), moving to higher dimensional inputs, changing the loss function from squared error to cross-entropy say?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

A brief discussion of limitations is provided in the conclusion avenues for future work are identified. I cannot foresee any negative societal outcomes from this work.

Summary

This paper studies the representational cost of a toy ReLU MLP with a single hidden layer, and a scalar input. The main result of the paper is that, when regularizing both the weights and the biases, the minimum cost functions are min norm interpolators which are also sparse (defined in the paper as having the minimal number of kinks). When the bias is not regularized (as in the standard weight decay), the minimum cost functions are not necessarily sparse.

Strengths

Overall i enjoyed reading this paper. Its main strengths are: 1. Very well written, and positioned relative to prior work. 2. A rigorous, clean result, albeit on a very toyish model 2. A novel result that is somewhat surprising and non-trivial.

Weaknesses

The main drawbacks of the paper are: 1. The studied model is very simple, even for a theory paper (1D input) 2. Its not clear whether the main conclusion of the paper has any bearing in practice. Therefore, its impact might be restricted to the theoretically inclined. These drawbacks are somewhat nitpicky though, and i do not see a reason not to accept it.

Questions

Although the sparsest interpolator is not the only solution when the bias is not regularized, we do see (figure 3b) that standard weight decay does produce sparse (almost sparsest) interpolators. Is it possible that in practice the effect of regularizing the bias is not that pronounced?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Limitations are adequately addressed

Summary

The paper addresses two main questions: (1) Can the parameters' norm be understood in terms of a quantity that is more insightful from a functional analysis point of view? (2) What kind of functions are learned when minimizing the empirical loss, either with an explicit or implicit regularization of the parameters' norm? The paper provides an answer to these questions for univariate functions when the bias parameters are regularized. It shows that penalizing the bias terms enforces sparsity and uniqueness of the estimated function, which does not hold without penalization of the biases. The paper provides a theorem (see Theorem 1) that states the representational cost of a function is given by the total variation of its second derivative, weighted by an sqrt(1 + x^2) factor. This weighting does favor sparse estimators when training neural networks.

Strengths

- It is well-known that omitting the bias parameters of the NN makes the analysis easier. So, the fact that the bias terms are included is highly welcomed. There are interesting conclusions garnished from including the bias terms, such as the enforcement of sparsity. - The paper shows that the representational cost of a function is given by the total variation of its second derivative, weighted by an sqrt(1 + x^2) factor.

Weaknesses

- The work is only for univariate functions, mainly for ReLU NNs with skip connections, penalization terms (that are not common in practice), and continuous dynamics for training. Therefore, the theoretical study here may say very little about the answers to the manuscript's two main questions for practical NNs. However, I acknowledge that it may be extremely hard to do analysis when the setup is modified and the authors provide empirical evidence. - A skip connection is a useful architecture to make the analysis easier; however, whether it says anything about the NNs that are used in practice is unclear to me. The author says: "Since a skip connection can be represented by two ReLU neurons, it is commonly believed that considering a free skip connection does not alter the nature of the obtained results."; however, I am not aware of a theoretical statement that makes it precise in this setting.

Questions

1. I wonder if there is anything special to the weight sqrt(1 + x^2) from a higher level and how particular this result is to the setup considered in the paper, e.g., Relu, Skip connection, 1D setup, and one hidden neural network. 2. The definition of the parameter norm is the squared $\ell_2$ norm of all the {a_j}, {b_j}, and {w_j}. While in 1D, we can consider them as 3 different vectors, but in higher dimensions, I am not sure about viewing them as vectors is the correct way of defining the parameter norm. Also, when it comes to sparsity, one would compute the number of its nonzero elements, an alternative of which is the \ell_1 norm. Using the squared $\ell_2$ norm as a sparsity measure is an uncommon choice since a neural network can be non-sparse at all but with a very small parameter squared $\ell_2$ norm. 3. It is not immediately clear from the paper what type of function f being considered in the main result. It was said that the second derivative of f, i.e., f'' should be understood in terms of distribution, which I assume that non-smooth 1D functions are considered. Based on the 2nd definition of \bar{R}_1(f), f is restricted to those represented by a simple Relu NN. 4. It is written that the two \bar{R}_1(f) in Section 2.1 can be proven to be the same. Can the authors provide proof or pointing some references to it?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

There are some comments on the future directions of this work in the conclusion, but I am not sure they are classified as limitations of this work. Here is the main limitation in my perspective of the paper: 1. The analysis is restricted to a 1D setting with a very particular structure for the neural network. The weight sqrt(1 + x^2) is too particular, and I am not confident that one can return the same result with a slight change in the problem setup. 2. The implication of minimizing the TV norm of sqrt(1 + x^2) f''(x) is not well understood, and its link to sparsity promoting is not so clear.

Summary

This paper theoretically investigates the effect of regularizing bias parameters’ norm, mostly ignored or omitted in previous analyses, for univariate one hidden layer ReLU networks. It turns out that minimizing $L_2$ norms for both weights and biases corresponds to regularizing a functional norm defined as the total variation of the second derivative of the function modeled by the neural network with a weight of $\sqrt{1+x^2}$ factor, where the weight factor does not exist when regularizing only the weight norm. The minimal functional norm interpolator can be obtained from a proposed dynamic programming algorithm, and the uniqueness and sparsity properties of the interpolator are discussed. **Post rebuttal** I have increased my score to 5 from 4. I can appreciate the theoretical contribution, while the practical relevance still seems to be a weakness.

Strengths

- The paper analyzes the effect of bias norm regularization, which has not been considered much before, showing novel and original results. The effect is not trivial, and the regularization problem is identified as minimizing a functional norm with a weight factor, which leads to interesting uniqueness and sparsity properties of minimum norm interpolators. - Proofs are provided for most of the theorems and lemmas in a mathematically sound way. It is especially ingenious to prove the uniqueness and sparsity properties of the minimum norm interpolator by using a dynamic programming algorithm that obtains the interpolator.

Weaknesses

- The benefit of the considered sparsity regarding the number of a function’s kinks is unclear. Why would the number of kinks be important? Can it be used to explain generalization properties in any way? Also, the sparsity in terms of kinks seems quite different from the one considered in usual machine learning contexts, e.g., having zero values for most weights or representations except for a few. Maybe addressing these points and providing some intuitive explanations would be helpful to enforce the claim of the paper. - The condition for the minimum norm interpolator to be the sparsest interpolator is quite restrictive according to **Assumption 1**. Moreover, **Appendix A** provides an example of when the sparsest and minimal norm ones are largely different in the number of kinks. These points can lower the significance of the sparsity result. - Due to the weight factor of $\sqrt{1+x^2}$ in evaluating $\mathcal{F}_1$ norm from bias regularization, the shift invariance property of the norm disappears. Can this have any negative impact on using the function norm to explain the nature of a function? Also, the connection between this weight factor and the sparsity property regarding the number of kinks is not intuitive. Rather, it seems that containing this weight factor would make the location of kinks not far from zero.

Questions

In addition to the questions posed in the **Weaknesses** section, I have the following questions: - What would be the practical benefit of considering bias regularization? As far as I know, a common practice for applying weight decay in neural network training is only regularizing the weight norm. This method has already shown many empirical successes so far. **[Minor comments]** - How is the ‘activation cone’ defined in line 188? - Providing some explanations about deriving (5) would be helpful. - **Corollary 1** is corrected in **Appendix E.6**, and I think the corrected version should come to the main text.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

The limitations of the results are discussed in **Conclusion** and **Appendix A**. For other possible limitations, please refer to the weaknesses and questions above.