Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs

Summary

The paper provides a connection of the convex program for gated ReLU networks to multiple kernel learning model with a weighted data masking feature map. Additionally, the paper provides a theoretical analysis of the predictive error of the proposed kernel algorithm.

Strengths

The paper provides a new framework that employs multiple kernel learning which is a convex reformulation of neural network training process, the new framework is better able to explain the remarkable performance of neural networks than the neural tangent kernel perspective, which requires the infinite width limit assumption.

Weaknesses

As I am not familiar with multiple kernel learning and group lasso, I feel that I am not able to fully identify the weakness in this paper. I will give a borderline rating with a low confidence score.

Questions

No.

Rating

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

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Summary

This work considers a convex formulation of a finite-width regularised two layer ReLU network and interpretations as multiple kernel learning. This then is related to the neural tangent kernel. 
The convex formulation considers cones of parameters with fixed activation along with a bound O(n^d). The gated ReLU further decouples the activation region from the linear function. A main conclusion is that while the NTK of the gated ReLU does not take labels into account, optimal Multiple Kernel Learning can.

Strengths

* The work deals with a relevant problem of understanding the optimization problem of neural networks beyond the infinite width setting. * The work gives an overview of different perspectives about ReLU networks, particularly previous work on convex programs, group lasso, multiple kernel learning, and NTK, which are interesting as they could facilitate further perspectives. * The work discusses convex formulations of gated ReLU networks from a perspective of multiple kernel learning.

Weaknesses

* The article indicates that previous works have considered training dynamics with infinitesimally small learning rates on networks in the infinite width limit. It would be indicated to comment on works covering small width [1,2], or works that discuss NTK more independently of the width [3], or works that investigate the dynamics of finite-width networks using NTK [4]. 

 * [1] E et al. A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics. 
 * [2] Su and Yang. On learning over-parameterized neural networks: A functional approximation perspective.
 * [3] Liu et al. On the linearity of large non-linear models: when and why the tangent kernel is constant. * [4] Bowman and Montufar. Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regime. * I missed a more explicit discussion of how the presented work is significantly different from or significantly advances in relation to prior works on convex formulations of ReLU networks, particularly the sequence of works [1,2,…]. * [1] Ergen and Pilanci. Convex geometry and duality of over-parametrized neural networks. * [2] Pilanci and Ergen. Neural networks are convex regularizers: exact polynomial time convex optimization formulations for two layer networks. * A more explicit connection between the presented analysis and the result of training a neural network would have made this a stronger contribution. Particularly, the conversion of gated ReLU to ReLU should be discussed more explicitly in the main part of the document. The theoretical discussion of fixing the kernel or improving the weights seems to focus on the training error with a more explicit discussion of generalization error missing. Figure 1 and the first experiments seem to be on toy examples. The experiments on UCI data compare NTK vs iteratively reweighed least squares but seem to be missing comparison with the trained network as well as reporting training accuracy.

Questions

* Please clarify the intended notation for w^{(+)} and w^{(-)} or why (11) should have the same expressive power as (1). Concretely, (11) is a signed sum of 2m ReLUs, whereas (1) is a sum of just m ReLUs. For d=2 and m=1, (11) can represent functions which have 4 linear regions, whereas any function represented by (1) has at most 2 linear regions.

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

* The work seems to consider minimal complete gate sets. * The work does not appear to include observations into overfitting or generalisation.

Summary

The paper studies gated ReLU networks with L2 regularization. The authors show that this model is equivalent to Multiple Kernel Learning with group lasso, which is a convex optimzation problem. Thus L2 regularized gated ReLU networks is equivalent to learning the NTK according to a Lasso objective and then fitting the data with the resulting learned NTK. In contrast, in the NTK limit the model fits the data with the initial NTK, which is in general not optimal w.r.t. to the optimization procedure defined previously.

Strengths

The article is well written and studies the important question of whether DNN can be interpreted as a kernel learning model. The theoretical results appear to be correct, and the numerical experiments illustrate the theory well.

Weaknesses

The paper studies gated ReLU networks as an approximation of ReLU networks, but a lot of either very similar or stronger results to the ones proven here are already proven for actual ReLU networks. In particular, [Francis Bach, Breaking the curse of dimensionality with convex neural networks, 2017], proves a similar convex reformulation, and though not explicitely stated, it can also be interpreted as a kernel learning objective (arguably this optimization over kernels is more obvious in [A. Jacot, E. Golikov, C. Hongler, F. Gabriel, Feature Learning in L2-regularized DNNs: Attraction/Repulsion and Sparsity, NeurIPS 2022] which generalizes Francis Bach's results to the deep case). Francis Bach also proves generalization bounds which are missing here. The only possible advantage of the gated ReLU setting is that the optimization might not be NP-hard as is argued in the paper (we know the NP-hardness of the equivalent reformulation of ReLU networks), though this relies on the fact that the number of required gates $p$ grows polynomially, which is not proven. Actually I think it is quite likely that optimization proposed in this paper is NP-hard as well. Another related problem is that the gated ReLU optimization is arguably `less unique' than the traditional ReLU, since the dates $g_i$ can always be changed without changing the activations on the training data, thus changing the learned function and kernel outside the training set. It appears that the solution proposed here is to arbitrarily choose a gate direction $g_i$ for each activation pattern on the training set, which is not ideal. Also this problem is not really addressed in the paper. Note that the same problem appear in ReLU networks though it seems less severe, since there can be case where you obtain uniqueness of the solution, in contrast it appears that there is never uniqueness with gated ReLU.

Questions

I also do not like how the authors say in the abstract and introduction that the NTK at initialization is suboptimal compared to the learned NTK, without clarifying w.r.t. to which cost. This could suggest that they prove that the learned NTK is better in terms of generalization, which is not proven. Rather the learned NTK is optimal w.r.t. to the MKL optimization with group Lasso, which is a very specific optimization introduced in this paper (and previous paper) as a reformulation of the L2 regularization loss. So in some sense the statement that the learned NTK is optimal in contrast to the initial NTK is a tautology, since it is w.r.t. to a cost that was designed to reflect the effect of learning. If we are instead talking about generalization, then we cannot say that the learned kernel is always better than the initial kernel, as there could be some form of `kernel overfitting'. This is the `no free lunch' theorem: there is no statistical model that is strictly better than another, each model is better under certain assumptions on the task. For example we already know that learning with a constant NTK is optimal if the true function $f^*$ is a Gaussian process with covariance equal to the limiting NTK, in such a setting, NTK learning would be detrimental. For these reasons, I ask the authors to be more specific when thay say that the learned kernel is optimal and initial NTK is suboptimal.

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

As already mentioned, the authors should be clearer about the two following possible issues: - That the reformulation may not be that much faster, because the number of required kernels $d$ one has to optimize over could be very large. It is therefore not clear that gated ReLU offer a significant optimization advantage over ReLU networks. - That the optimization is not unique outside the training set.

Summary

This work presents the insight that the convex formulation of training a gated ReLU network is an instance of Multiple Kernel Learning (MKL) techniques. This contrasts with the NTK limit, which becomes a single kernel learning in the infinite width limit. The main thesis is that the finite-width ReLU network is necessarily superior over the NTK limit, since MKL learning optimizes over all linear combinations over the multiple kernels, but the NTK limit corresponds to a single fixed linear combination of these kernels.

Strengths

The presentation and the contribution of this paper are very straightforward: (convexified gated ReLU) = (MKL). This main insight, in my view, the key and only non-trivial insight of this work. In my view, all other parts of this work are relatively straightforward consequences of this observation, and the experiments are minimal and compact. Therefore, in my view, the decision comes down to whether this single insight is a sufficient contribution to warrant a NeurIPS publication. In my view, it definitely is. How the hidden convex structure of NN approach compares with the NTK or the mean-field analysis was an important problem to tackle, and I find the insight of this work to be a very good start. (Although this paper doesn't yet deal with the mean-field analysis.) I recommend this paper be accepted.

Weaknesses

.

Questions

.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and 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

4 excellent

Limitations

.

Summary

This paper establishes the equivalence between shallow neural networks activated by ReLU and multiple kernel learning (MKL) through the convex reformulation of shallow neural networks into gated ReLU networks. By interpreting neural networks in this way, it becomes apparent that the network may not be able to attain the optimal MKL kernel on the training set. To address this issue, the authors propose an iterative reweighted method to solve the corresponding MKL problem, which has the potential to obtain the optimal MKL kernel due to its convex nature. Moreover, the authors conduct an analysis of the in-sample prediction error for the gated ReLU networks.

Strengths

Previously, a series of recent studies have demonstrated that (shallow) ReLU networks can be reformulated as a convex problem. This paper builds upon the previous work by establishing the equivalence between this network formulation and the mask kernel learning (MKL) model. This finding has the potential to offer valuable insights into comprehending the performance of neural networks during both training and testing stages. The paper is well-written, providing an ample and lucid introduction to various topics such as the convex formulation of neural networks, mask kernel learning, NTK, and other related subjects.

Weaknesses

The main contribution of this paper is to establish the equivalence between neural networks and multiple kernel learning (MKL) models. However, there are certain assumptions and setups in the paper that may limit the scope of their findings: 1. The convex formulation of neural networks appears to be applicable only to ReLU (or its variants) activation functions, as the cone constraints rely on the non-negativity of ReLU. Consequently, the results might be specific to ReLU and may not generalize to other activation functions. 2. Since the output layer of the neural network is fully connected, it can be expressed in a feature map format as f(x) = phi(x)^T v, which holds true even for deep neural networks. Thus, merely establishing equivalence to a kernel method may not sufficiently uncover the intricacies of neural networks. 3. In lines 164-167 of the proof for Lemma~3.1, the authors fail to explain why the simplex constraint can be eliminated through a change of variables. This omission could lead to confusion for readers. 4. Theorem 4.3 demonstrates that problem (7) can be reformulated in the form of MKL, but the original problem (7) does not include a simplex constraint. However, the authors do not address this discrepancy in the main theorem or the supplementary proof. 5. The results presented in section 6 do not offer further insights or explain the benefits of formulating the problem as convex optimization or considering it as MKL. This is because the authors solely analyze in-sample prediction, while previous research has shown that shallow ReLU neural networks can generalize well to various underlying distributions (e.g., see https://arxiv.org/abs/1901.08584).

Questions

1. What is the motivation behind using a regularized formulation? Do the main results (Theorem 4.3, Theorem 5.1, Theorem 6.1) hold for the non-regularized version with lambda set to zero? 2. Is it possible to extend the convex formulation to activation functions other than ReLU? If so, what would be the considerations and challenges involved in adapting the formulation to non-ReLU activations? 3. Given that the reformulation is convex, why do you suggest using the Iteratively Reweighted Least Squares (IRLS) algorithm instead of a commonly used convex problem solver? Are there specific benefits to using IRLS in this context? Furthermore, can you provide insights into the properties of the solution that IRLS converges to?

Rating

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

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

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

See weakness

Further Review Comments Based on Author's Rebuttal.

Thank you for the author's response. Having reviewed the rebuttal and comments from other reviewers, I have chosen to maintain my original score due to concerns regarding the applications and implications of this work. I remain unconvinced that the convex reformulation presented in this paper can be readily extended to activations beyond ReLU. As ReLU is also piecewise linear function, I find it lacking that the authors have not provided references or a brief explanation detailing the applicability of such analysis to smoother activations like sigmoid or tanh. Furthermore, neural networks can be considered as a kernel method whenever the output layer is linear. Thus, it is worth considering whether the reformulation and results still hold when the output layer is non-linear, rather than linear. My reservations extend to the empirical results as well. Essentially, [1] reveals that the behavior of neural networks under gradient descent aligns with the kernel gradient with respect to NTK. In the infinite-width scenario, NTK converges to the so-called limiting NTK [1, Theorem 1]. To ensure a fair comparison, numerical experiments should consider juxtapose trained neural networks (across varying widths) with MLK using the optimal MKL kernel obtained in this paper. Unfortunately, based on the provided code, it appears the authors treat MLK with the limiting NTK as the performance of NTK. I hesitate to deem this a fair comparison, as the limiting NTK can be employed in alternative machine learning models like SVM rather than being solely tailored to MLK, but NTK itself really depends on the training. Given my reservations arising from the experimental outcomes, the insights offered by the results in section 6 do not sufficiently underscore the benefits of formulating the problem via convex optimization or viewing it as MKL. Earlier research [2] has indicated that shallow ReLU neural networks exhibit commendable generalization to diverse underlying distributions. Consequently, my decision remains unaltered regarding the review score. [1] Jacot, Arthur, Franck Gabriel, and Clément Hongler. "Neural tangent kernel: Convergence and generalization in neural networks." NeurIPS 2018 [2] Arora, Sanjeev, et al. "Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks." ICML 2019

Response to rebuttal

I appreciate the authors responses, which clarify some of the concerns in my initial review and propose suggestions to improve the text. I have adjusted my score accordingly.