Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs
Authors: Rajat Vadiraj Dwaraknath
Tolga Ergen
Mert Pilanci
Venue: NeurIPS 2023 poster (2023)
Keywords: neural tangent kernel
NTK
ReLU activations
neural networks
gated ReLU
convex optimization
kernel
multiple kernel learning
MKL
group lasso
iterative reweighting
group norm
TL;DR: We interpret convex reformulations of ReLU networks as multiple kernel learning and show that the NTK cannot perform better than the optimal MKL kernel on the training set, and also obtain the optimal MKL kernel from the NTK by iterative reweighting.

Abstract: Recently, theoretical analyses of deep neural networks have broadly focused on two directions: 1) Providing insight into neural network training by SGD in the limit of infinite hidden-layer width and infinitesimally small learning rate (also known as gradient flow) via the Neural Tangent Kernel (NTK), and 2) Globally optimizing the regularized training objective via cone-constrained convex reformulations of ReLU networks. The latter research direction also yielded an alternative formulation of the ReLU network, called a gated ReLU network, that is globally optimizable via efficient unconstrained convex programs. In this work, we interpret the convex program for this gated ReLU network as a Multiple Kernel Learning (MKL) model with a weighted data masking feature map and establish a connection to the NTK. Specifically, we show that for a particular choice of mask weights that do not depend on the learning targets, this kernel is equivalent to the NTK of the gated ReLU network on the training data. A consequence of this lack of dependence on the targets is that the NTK cannot perform better than the optimal MKL kernel on the training set. By using iterative reweighting, we improve the weights induced by the NTK to obtain the optimal MKL kernel which is equivalent to the solution of the exact convex reformulation of the gated ReLU network. We also provide several numerical simulations corroborating our theory. Additionally, we provide an analysis of the prediction error of the resulting optimal kernel via consistency results for the group lasso.

Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs
Rajat Vadiraj Dwaraknath Stanford University rajatvd@stanford. edu
Tolga Ergen LG Al Research tergen@lgresearch..t
Mert Pilanci Stanford University
pilanci@stanf ord. edu
Abstract
Recently, theoretical analyses of deep neural networks have broadly focused on two directions: 1) Providing insight into neural network training by SGD in the limit of infinite hidden-layer width and infinitesimally small learning rate (also known as gradient flow) via the Neural Tangent Kernel (NTK), and 2) Globally optimizing the regularized training objective via cone-constrained convex reformulations of ReLU networks. The latter research direction also yielded an alternative formulation of the ReLU network, called a gated ReLU network, that globally optimizable via efficient unconstrained convex programs. In this work, interpret the convex program for this gated ReLU network as Multiple Kernel Learning (MKL) model with weighted data masking feature map and establish connection the NTK. Specifically, we show that for a particular choice of mask weights that do not depend on the learning targets, this kernel is equivalent the NTK of the gated ReLU network on the training data. A consequence of this lack of dependence on the targets is that the NTK cannot perform better than the optimal MKL kernel on the training set. By using iterative reweighting, we improve the weights induced by the NTK obtain the optimal MKL kernel which equivalent to the solution of the exact convex reformulation of the gated ReLU network. We also provide several numerical simulations corroborating our theory. Additionally, we provide an analysis of the prediction error of the resulting optimal kernel via consistency results for the group lasso.
1 Introduction
Neural Networks (NNs) have become popular in various machine learning applications due their remarkable modeling capabilities and generalization performance. However, their highly nonlinear and non-convex structure precludes an effective theoretical analysis. Therefore, developing theoretical tools to understand the fundamental mechanisms behind neural networks is still an active research topic. To tackle this problem, [1] studied the training dynamics of neural networks trained with Stochastic Gradient Descent (SGD) in a regime where each layer has infinitely many neurons and SGD uses an infinitesimally small learning rate, i.e., gradient flow. Thus, they related the training dynamics of neural networks the training dynamics of fixed kernel called the Neural Tangent Kernel (NTK). However, [2] showed that neurons barely move from their initial values in this regime that neural networks fail to learn useful features from the training data. This is in contrast their finite width counterparts, which are able to learn predictive features in practice [3]. Moreover, [4, 5] provided further theoretical and empirical evidence to show that existing kernel approaches are not able to explain the remarkable performance of finite width networks. Therefore, although NTK and similar kernel based approaches enable theoretical analysis unlike standard finite width networks, they fail to explain the effectiveness of finite width neural networks that are employed in practice.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Recently series of papers [6-15] introduced an analytic framework to analyze finite width neural networks by leveraging certain convex duality arguments. Particularly, they showed that the standard regularized non-convex training problem can be equivalently cast as finite dimensional convex program. This convex approach has two major advantages over standard non-convex training: (1) Since the training objective is convex, one can find globally optimal parameters of the network efficiently and reliably unlike standard nonconvex training which can get stuck at a local minimum, and (2) As show in this work, class of convex reformulations can be interpreted as instance of Multiple Kernel Learning (MKL) [16] which allows us to characterize the corresponding finite width networks by learned dependee kernel that can be iteratively computed. This is in contrast to the infinite-wide width kernel characterization in which the NTK stays constant throughout training.
Notation and Preliminaries. In the paper, we use lowercase and uppercase bold letters to denote vectors and matrices respectively. We also use subscripts to denote certain column or element. We denote the identity matrix of size k x k as Ig. To denote the set {1,
.......,, .,,,,,..,11 n), we use [n). We also use I|-Ilp and I|-II to represent the standard lp and Frobenius norms. Additionally, we denote 0-1 valued indicator function and ReLU activation as {or 2 0} and (x) = max(2; zz, 0}, respectively.
In this paper, we focus on analyzing the regularized training problem of ReLU networks. Particularly, we consider a two-layer ReL.U network with m. neurons whose output function defined as follows
771
321
f(x,0):=
Σ
x" w
(2) Wj
Σ j=l
(1fx x
(1) wj 2
00 x" w. (1) w
(2)
j=1
where w(th) E Re and w/ are the jth hidden and output layer weights, respectively and 0 {(wf)) : m0 د represents all trainable parameters. Given a training data matrix X Raxd and target vector y RR, we minimize the following weight decay regularized training objective
2
m
min ((
Σ Xw ()
w
(2)
y
+
W 1
110 110
(2)
j=1
where À O is the regularization coefficient. We also O(X,0)
プド= (Xw(t)
(2)
for
convenience. We discuss extensions to generic loss and deeper architectures in appendix.
Our Contributions.
section 4, we show that the convex formulation of the Gated ReLU network is equivalent to Multiple Kernel Learning with a specific set of Masking Kernels. (Theorem 4.3).
In section connect this formulation to the Neural Tangent Kernel by showing that the NTK is a specific weighted combination of masking kernels (Theorem 5.1).
In Corollary 5.2, we show that on the training set, the NTK is suboptimal when compared to the optimal kernel learned by MKL, which equivalent to the model learnt by our convex Gated ReLU program.
section 6, we also derive bounds on the prediction error of this optimal kernel and specify how to choose the regularization parameter À (Theorem 6.
2 Convex Optimization and the NTK
Here, we briefly review the literature on convex training and the NTK theory of neural networks.
2.1 Convex Programs for ReLU Networks
Even though the network in (1) has only two layers, previous studies show that (2) is a challenging optimization problem due to the non-convexity of the objective function. Thus, local search heuristics such as SGD might fail to globally optimize the training objective [17-20]. To eliminate the issues associated with the inherent non-convexity, [7] introduced an exact convex reformulation of (2) as

---

the following constrained optimization problem
P
(2D; I)Xw; ;; 2 0
min W.W.
Σ
D. w()
(1wwill2 + ([w)ll2)
Vi, (3)
(2D; I)Xw; 2 0
where D; E Dx are n x n binary masking diagonal matrices given by p:= [Dx] and
xx:=
= {diag (1 (Xu 2 0}) u E
(4)
The mask set Dx be interpreted the of all possible ways separate the training data X by hyperplane passing through the origin. With these masks, we can characterize a single ReLU activated neuron on the training data follows: (Xw;) diag (1 (Xw, 2 ) Xw; D,Xw; provided that (2D, I,, Xw: 2 O. Therefore, by enforcing these cone constraints in (3), we maintain the masking property of the ReLU activation and parameterize the neural network as a linear function of the weights, thus make the learning problem convex. We refer the reader to [6] for more details.
Although (3) is convex and therefore eliminates the drawbacks associated with the non-convexity of (2), it might still be computationally complex to solve. Preciscly, worst-case upper-bount on the number of variables is O(n"), where r = rank(X) S min (n, d}. Although this is still significantly better than brute-force search 2 ReLU patterns, it could still be exponential in the dimension d. To mitigate this issue, [8] proposed a relaxation of (1) called the gated ReLU network
fg (x, 0)
Σ
1 11 gj 2 0) x" W (1) w
(5)
where G:= {g is set of gate vectors that are also optimized throughout training. Then, the corresponding non-convex learning problem is follows
min W(),w(a)
m diag (1 (Xg, 2 0}) Xw 3j
(2)
Σ j=1
122
( (1)) + +ww (2)
(6)
By performing this relaxation, decouple the dependence between the indicator function and the linear term in the exact ReLU network (1). To express the equivalent convex optimization problem corresponding to the gated ReLU network, we introduce the notion of complete gate sets.
Definition 2.1. A gate set G is complete with respect to a dataset X. if the corresponding set of hyperplane arrangements covers all possible arrangement patterns for X defined in (4), iee,
{diag (1 {Xg; 2 0}) gg E Dxx
Additionally, G is minimally complete if [G] [Dx p.
Now, with this relaxation, [8] showed that the optimal value for (6) can always be achieved by choosing G to be a complete gate set. Therefore, by working only with complete gate sets, we can modify (6) to only optimize over the network parameters (!)) and (2)
m Σ
372
min (O),w()
diag (1g) 0}) Xw, 11) (2)
(1)
+ +wm
(7)
Additionally, [21] also showed that we can set p without loss of generality. Then, [8] showed that the equivalent convex optimization problem for (6) and also (7) in the complete gate set setting is
min I D.X.: yy + |will2.
(
Notice that (8) is least squares problem with group lasso regularization [22]. Therefore, this relaxation for (3) can be efficiently optimized via convex optimization solvers. Furthermore, [8] proved that after solving the relaxed problem (8), one can construct an equivalent ReLU network from a gated ReLU network via a convex optimization based procedure called cone decomposition. We discuss the computational complexity of this approach in Section E of the supplementary material.

---

2.2 The Neural Tangent Kernel
Previous works [1, 5, 23, 24] characterized the training dynamics of SGD with infinitesimally small learning rates on neural networks in the infinite-width limit, i.e., as m + co, via the NTK. [25, 26] also present analyses in this regime via a miea-fieeld approach. In this section, we provide brief overview of this theory and refer the reader to [1. 27, 28] for more details. The main idea behind the NTK theory is to approximate the neural network model function f (x, 0) by linearizing it with respect to the parameters A around its initialization 0g:
f (x, 0) = f (x, 0n) + Vof (x, 0o)" 00)
The authors of [1] show that if f is a neural network (with appropriately scaled output), and pa- rameters 0 initialized as i.idd standard Gaussians, the linearization better approximates f in the unfinitewwitth limit. We can interpret the linearized model f as kernel method with feature map given by Φ (x) Vof (x, 0o). The corresponding kernel induced by this feature map is termed as the NTK. Note that this is a random kernel since it depends on the random initialization of the parameters denoted as d-- The main result of [1] in the simplified case of two-layer neural networks is that, in the infinite-width limit this kernel approaches fixed deterministic limit given by (xx x') == E [V 0o) VVo (x', oo)]. where i corresponds to the parameters of a single neuron. Furthermore, [1] show that in this infinite limit, SGD with an infinitesimally small learning rate is equivalent to performing kernel regression with the fixed NTK.
To link the convex formulation (8) with NTK theory, we first present a scaled version of the gated ReLU network in (5) as follows
Sa (x. 0) /2m
[ (1x"8: 2 20 (xx"""")) wf
(9)
the next lemma, we provide the infinite width NTK of the scaled gated ReLU network (9). Lemma 2.2. The infinite width NTK of the gated ReLU network (9) with i.idd gates sampled as
gj ~ N (0, Ia) and randomly initialized parameters as w; ~ NN, Ia) and w ~ N (0, is
H (xxx)):= 2x
1 ((T -aarcoos π
arcoos
x | |xx)
1 xxx
(10)
Additionally, we introduce reparameterization of the standard ReLU network (1) with 0 = Rd which can still represent all the functions that (1)
{(w) (+) can 5 1- with w)
fxxx0) 0) :=
Σ ( 3=1
( (x"w5"))
(11)
22m
Lemma 2.3. The gated ReLU network (9) and the reparameterized ReLU network (11) have the same infinite width NTK given by Lemma 2.2.
Next, we present an equivalence between the gated ReLU network and the MKL model [16, 29].
3 Multiple Kernel Learning and Group Lasso
The Multiple Kernel Learning (MKL) model [16, 29] is an extension of the standard kernel method that learns an optimal data-dependent kernel as convex combination of set of fixed kernels and then performs regression with this learned kernel. We provide brief overview of the MKL setting based on the exposition in [30]. Consider a set of kernels given by corresponding feature maps Φi : IRd + R.d Given n training samples E Bxd with targets y E RT, we define the feature matrices on this data by stacking the feature vectors as ④. = (xx(x]] )r. (<x)x,))))
Ruxd, o A convex combination
Then, the corresponding n x n kernel matrices are given by K,
of these kernels can be written as K (n) == Σ K; where 7 E Ap = {n 1" 1, 17 0) is set of weights in the unit simplex. By noticing that the feature map corresponding to K (n)
All the proofs and derivations presented in the supplementary material.

---

is obtained by taking weighted concatenation of Φ; with weights vT,, we can write the MKL optimization problem in terms of the feature matrices as
min 7EAp.VEER
E VT y
(12)
where À > 0 is regularization coefficient. For set of fixed weights n, the optimal objective value of the kernel regression problem over is proportional to y" ""E= v;;K; + AI,))_y up constant factors [16]. Thus, the MKL problem can be equivalently written as the following problem
min 7EA,
yd (²( y.
(13)
In this formulation, can interpret MKL finding the optimal data-dependent kernel that can be expressed as a convex combination of the fixed kernels given by K. In the next section, we link this kernel learning formulation with the convex group lasso problem in (8).
3.1 Equivalence Group Lasso
We first show that the MKL problem in (12) can be equivalently stated as a group lasso problem.
Lemma 3.1 (116, 291). The MKL problem (12) is equivalent to the following kernel regression problem using uniform combination of the fixed kernels with squared group lasso regularization where the groups are given by parameters corresponding to each fach map
P
P
2
min W.ER%
4 W;
y
|willa
(14)
We present short derivation of this equivalence. Using the variational formulation of the squared group -m-rrmm [31]
P
P [;
l2
(wslly
l1|
min nEAP
7)
we can rewrite the group lasso problem (14) as a joint minimization problem over both the parameters w and regularization weights as follows
w: l
Σ W
min nEAp
min w;ER4.
7/
Finally, with change of variables given by = note that the MKL problem (12) is also equivalent to the following standard group lasso problem
w we recover the MKL problem (12). We
min W. W.ER
Σ P W.
wwll22
(15)
This is due the fact that squared and standard group lasso problems have the same regularization where w" is the solution to (14).
paths [31], (14) and (15) equivalent when À
Σ |
3.2 Solving Group Lasso by Iterative Reweighting
Previously, we used variational formulation of the squared group -norm to show equivalences to MKI. Now, we present the Iteratively Reweighted Least Squares (IRLS) algorithm [32-35] to solve the group lasso problem (15) using the following variational formulation of the group fnonr [34]
w = min MERE 2
1
Σ
| + m
5

---

Based on this, we rewrite the group lasso problem (15) as the following minimization problem
[ 1
min min nER W.ERd,
Σ D W.
+
2 1=1
7//
Since the objective is jointly convex in (17, w). it can be solved using alternating minimization [33]. Particularly, note that the inner minimization problem w; is simply a & regularized least squares problem with different regularization strengths for each group and this can be solved in closed form
W 2
min W.
Σ p.W:
(16)
%/
The outer problem in v is also directly solved by setting 1/: || |w,ll2 [34]. To avoid convergence
issues and instability around 77 0, we approximate the reweighting by adding small positive constant e. We use this procedure solve the group lasso formulation of the gated ReLU network (8) by setting & = D,X. A detailed description is provided Algorithm 1. For further details regarding convergence, we refer the reader to [32-34].
Algorithm Iteratively Reweighted Least Squares (IRLS) for gated ReLU and ReLU networks
1: Set iteration count i 0
2: Initialize weights 7)
3: Set : D,X, D. Dx
4: while not converged and k S max iteration count do
5: Solve the weighted la regularized least squares problem:
+ w 2
[w(1)] (1) J.
argmin
Σ
P
W;
(k)
{wit.
1=1
(b++1)
6: Update the weights: ?
+
7: Increment iteration count: ls <- k +1
8: end while
9: Optional: Convert the gated ReLU network to ReLU network (see Section E for details)
4 Gated ReLU as MKL with Masking Kernels
Motivated by the MKL interpretation of group lasso, we return to the convex reformulation (8) the gated ReLUU network. Notice that this problem has the same structure as the MKL equivalent group lasso problem (15) with a specific set of feature maps that we define below.
Definition 4.1. The masking feature maps o)- Rdd Rd generated by fixed set of gates G are defined as (x)
{xT'g g; 2 0}* x.
These feature maps can be interpreted as simply passing the input unchanged if lies in the positive halfspace of the corresponding gate vector g i.c., x' g 2 O, and returning zero if the input does not lie in this halfspace. Since diag (1 (Xg, 2 0}} E Dx, V gj E holds for an arbitrary gate set G, we can conveniently express the corresponding feature matrices of these masking feature maps on the data X in terms of fixed diagonal data masks as $ D,X, where D, diag (1 (Xg, 2 0})- Similarly, the corresponding masking kernel matrices take the form K, D2XX'D Note that for an arbitrary set of gates, the generated masking feature matrices on X may not cover the entire set of possible masks Dx. Additionally, multiple gate vectors can result in identical masks if diag (1 (Xg; 2 0)) = diag (1 (Xg, 2 0}) for * j leading to degenerate feature matrices.
However, if we work with minimally complete gate sets as defined in Definition 2.1, we can rectify these issues.
Lemma 4.2. For minimally complete gate set G defined in Definition 2.1, I, we can uniquely associate gate vector gi to each data mask D; E Dx such that D diag (1 {Xg. 2 0}), (p).

---

Consequently, for minimally complete gate sets G. the generated masking feature matrices Vi E [p] can be expressed as $; D and the masking kernel matrices take the form K; D,XX"D, In the context of the gated ReL.U problem (7), since G is complete, we can replace it with minimally complete subset of G without loss of generality since [21] showed that increasing m beyond p cannot reduce the value of the regularized training objective in (7). We are now ready to combine the -KL-group lasso equivalence with the convex reformulation of the gated ReLU network to present the following characterization of the nonconvex gated ReLU learning problem.
Theorem 4.3. The non-conver gated ReLU problem (7) with a minimally complete gate set G is equivalent performing multiple kernel learning (12) with the masking feature maps generated by g
P Σ VI D, -y
min 7EAR.V.ER
1sll2
This theorem implies that the gated ReLU network finds the optimal combination of linear models restricted to the different masked datasets D:X generated by the gates. By optimizing with all possible data maskings, we obtain the best possible gated ReLU network. From the kernel perspective, we have characterized the problem of finding an optimal finite width gated ReLU network learning data-dependent kernel and then performing kernel regression. This is in contrast to the NTK theory where the training of an infinite width network by gradient flow is characterized by regression with constant kernel that is not learned from data. We further explore this connection below.
5 NTK as a Weighted Masking Kernel
We now connect the NTK of gated ReLU network with the masking kernels generated by its gates. Theorem 5.1. Let Kg (îi) E Raxx be the weighted masking kernel obtained by taking convex combination of the masking feature maps generated by minimally complete gate set 9 with weights given by πi; = Pidiag (I {Xh 2 0}) = D.] where h (0, Ia) and let H E gaxn be the infinite width NTK of the gated ReLU network (10) evaluated on the training data, i.e., the t5 entry of H is defined as H.y: (x,,, x,). Then, Kg (7) H.
A rough sketch of the proof of this theorem is to express the matrix H as an expectation of indicator random variables using the definition of the NTK [1]. Then, by conditioning on the event that these indicators equal the masks D., we can express the NTK as convex combination of the masking kernels K, The weights end up being precisely the probabilities that are described in Theorem 5.1. A detailed proof is provided in the supplementary material.
This theorem implies that the outputs of the gated ReLU network obtained via (16) with regularization weights 7 on the training data is identical to that of kernel ridge regression with the NTK.
Corollary 5.2. Let w be the solution (16) with feature matrices D. D,X and regularization
weights iJ = P(diag (1 [Xh 2 0}) = Dj) where h ~ NO0 Ia) and let ý H(H + AIm)-'y be the outputs of kernel ridge regression with the NTK on the training data. Then, Σ. D,Ww, y
Since G is minimally complete, the weights in Theorem 5.1 satisfy El= 1 1. In other words, 7 E Ap. Therefore, we can interpret Theorem 5.1 as follows - the NTK evaluated on the training data lies in the convex hull of all possible masking kernels of the training data. So H lies in the feasible set of kernels for MKL using these masking kernels. By Theorem 4.3, we can find the optimal kernel in this set by solving the group lasso problem (8) of the gated ReLU network. Therefore, we can interpret solving (8) as fixing the NTK by learning an improved data-dependent kernel.
NTK). Note that the weights r do depend on the training data X. but do not depend on the target labels Since MKL learns the optimal kernel using both X and y, the NTK still cannot perform better than the optimal MKL kernel on the training set. Thus, we fix the NTK.
Remark 5.3 (Suboptimality
6 Analysis of Prediction Error
In this section, we present an analysis of the in-sample prediction error for the gated ReI.U network given in (5) along the lines of existing consistency results [36, 37] for the group lasso problem (8).
7

---

Group lasso objective, =001
Learned functions
4 10
1.0
IRLS with random inits
3 10
IRLS with NTK init
Optimal
0.0
Group Lasso
NTK weights
Gradient Descent
KRR with NTK
-0.5
Training dats
20
-1.0
0
2
4
0
8
-2
lteration
Figure 1: Plot of objective value of problem (8) which is solved using IRLS (algorithm 1) for toy 1D dataset with n = 5. The iterates are compared the optimal value obtained by solving (8) using CVXPY (blue). Notice that the solution (16) with regularization weights given by the NTK weights 7 from Theorem 5.1 (green) sub-optimal for problem (8), and running IRLS by initializing with these weights (red) converges to the optimal objective value. We also include plots of IRLS initialized with random weights (black). The right plot shows the corresponding learned functions. The blue curve shows the output of the solution the group lasso problem (8) after performing a cone decomposition to obtain a ReLU network. The dashed curve shows the output of running gradient descent (GD) ReLU network with 100 neurons. The green curve the result of kerell ridge regression (KRR) with the NTK. We observe that our reweighted kernel method (Group Lasso) produces output that matches the output of the NN trained via GD. In contrast, NTK produces an erroneous smooth function due to the infinite width approximation.
We assume that the data generated by noisy ReLU neural network model y f(X 0*) + where f is the ReLU network defined in (1) with true parameters 0" and the noise is distributed as N (0, I.)). By the seminal universal approximation theorem of [38], this model is able to capture broad class of ground-truu truth functions by using a ReLU network with enough neurons. We can transform 0* to the weights w in the convex ReLU model and write f(X, 0*) = Σ D,Xw,. We denote by w the solution of the group lasso problem (8) for the gated ReLU network with an additional factor on the loss to simplify derivations,
W argmin W:ERd
Σ D,W, -y +
|will2-
(17)
2
We now present our main theorem which bounds the prediction error of the gated ReLU network obtained from the solution below.
Theorem 6.1 (Prediction Error of Gated ReLU). For some let the regularization parameter in (17) be to ||| p/n. Then, with probability at least - we have
1 fo - f(x 03) -
||
< 2A
w
where (x D,Xw, are the predictions of the gated ReLU network obtained from w.
The proof closely follows the analysis of the regular lasso problem presented in [37], but extend to the specific case of the group lasso problem corresponding to the gated ReLU network and leverage the masking structure of the lifted data matrix obtain simplified bounds.
Experiments
Here, we empirically corroborate our theoretical results via experiments on several datasets.?
We provide additional details in Section B.

---

Group Lasso objective Student- setting 0.0C1
7x
8x
10
IRLS with random inits
6x100
6x 10
Optimal
NTK weig
10
5x
Iteration K
Iteration
Figure 2: Plot of the group lasso objective in the student-teacher setting with d 5. Training data is generated using a teacher network with width m = 10. The NTK weights vj are estimated using Monte Carlo sampling, and again sub-optimal. IRLS initialized with these weights successfully fixes the NTK and converges to the optimal weights.
Table 1: Test accuracies for UCI experiments with 75% 25%
ID datasets. For the ID experiments in Figure 1, we add a second data di- mension with value equal to 1 for all data points to simulate a bias term in the first layer of the gated ReLU network. Also, in this case we can enumerate all 2n data masks D, di- rectly. We use the cone decomposi- tion procedure described in [8] ob- tain ReLU network from the gated ReLU network obtained by solving (8). We also train 100 neuron ReLU network using gradient descent (GD) and compare the learned output func- tions the right plot in Figure 1. Ex- act details can be found in the supple- mentary material.
training-test split. Our approach achieves either higher or the same accuracy for 26 out of 33 datasets.
Dataset
NTK
Ours (Alg 1)
acule-in/ inttemminlammmatioonn
120
1.000
1.000
acute-nephritis balloons blood
120
6
1.000
1.000
16
0.75
0.75
breast-cancer
286
0.417
0.625
breast-cane cancer- siiceerwisc-proe wisc-prog
699
9
0.96
0.966
caanust-aacer-wisee wisc-diug
560
30
0.965
0.915
breast-cancer-wine wancer-wisc-proe
33
0.7
congressional voting
435
16
0.266
0.266
coun-benche sunar-mines--rock mines-rocks
208
60
0.635
0.712
appdita
690
15
0.838
0.844
cylinder-bands
0.773
echocardiogram
131
10
0.758
0.788
fertility
100
9
0.76
0.76
huberrnan-survival
306
3
0.481
0.532
heart-hungarian
12
0.743
Student-teacher setting. We gen- erate the training data by sampling X (0, In) and computing the targets y using a fixed, randomly ini- tialized gated ReI.U teacher network.
hepatitis
155
19
0.923
0.897
ilpd-indian-liver
583
9
0.432
0.555
ionosphere
351
33
0.955
0. 0.966
mammographic
0.783
0.792
molec-biol-prumee
106
57
0.63
0.815
musk-1
476
166
0.782
0.866
oocytes_trinee .rixapterus_mmcllu__22 parkinsons pima
912
25
0.781
0.759
In Figure 2, n = 10, d = 5, and we use teacher network with width m = 10, with gates and parameters randomly drawn from independent standard multivariate Gaussians. To solve the convex formulation (8), estimate Dx by randomly sampling unique hyperplane arrangements.
22
0.939
768
0.552
0.599
pittsburg-bride bridges-T-OOR- T-OR-D planning
102
7
0.731
0.846
182
12
0.435
0.543
statlog- gaalog-australianccrede
14
gernin-credit statlog-heart
1000
24
0.512
0.576
270
13
0.779
0.765
tic-tac-toe trains
958
9
1.0
1.0
29
0.667
vertebral-column- 2clases
310
0.821
0.731
Computing the NTK weights 7j. The weights induced by the NTK are given as in Theorem 5.1 by î = Pidiag (1 (Xh 2 0}) D, where Ao(0, Ia) is standard multivariate Gaussian vector. These probabilities can be interpreted either as the orthant probabilities of the multivariate Gaussians given by (2D, I,,) Xh or as the solid angle of the cones given by {u E Rdd (2D, I,) Xu 2 0}. Closed form expressions exist for d = 2, and [39, 40] present approximating schemes for higher dimensions. We calculate these weights exactly for the ID example presented Figure 1, and estimate them using Monte Carlo sampling for the student-teacher example in Figure 2.
Higher (or same) accuracy
14/33
26/33

---

Fixing the NTK weights by IRLS. We solve (16) with D = D,X and regularization weights given by the NTK weights 1 obtain the solution W. We use efficient least squares solvers from [41, 42]. By Theorem 5.1, this corresponds to choosing the weights yt in the MKL. problem (13) such that the resulting kernel matrix is equal to the NTK matrix H. We find the exact solution of the group lasso problem (8) using CVXPY. Comparing the optimal value of the group lasso problem (8) with the objective value of w (given by the green line) in Figures and 2, we observe that the NTK weighted solution is sub-optimal. This means that H is not the optimal kernel that would be learnt by MKL (which is expected since H has no dependence on the targets y). By applying IRLS initialized with the NTK weights, we fix the NTK and find the weights of the optimal MKL kernel. In Figures and 2, we observe that IRLS converges to the solution of the group lasso problem (8) and fixes the NTK.
UCI datasets. We compare the regularied NTK with our IRLS algorithm (Algorithm 1) on the UCI MI. Repository datasets. We follow the procedure described in [43] for n S 1000 to extract and standardize the datasets. We observe that our method achieves higher (or the same) test accuracy for 26 out of 33 datasets (see Table 1 for details) while the NTK achieves higher (or the same) test accuracy for 14 datasets which empirically supports our main claim that the IRLS procedure fixes the NTK. Details of the experiments can be found in Section of the supplementary material.
Discussion and Limitations
In this work, explored the connection between knite-width theories of neural networks given by convex reformulations and infinite-width theories of neural networks given by the NTK. To bridge these theories, we first interpreted the group lasso convex formulation of the gated ReLU network as multiple kernel learning model using the masking kernels generated by its gates. Then, we linked this MKL model with the NTK of the gated ReLU network evaluated the training data. Specifically, we showed that the NTK is equivalent to the weighted masking kernel with weights that depend only on the input data X and not on the targets y. We contrast this with the MKL interpretation of the gated ReLU network which learns the optimal data-dependent kernel using both X and y. Therefore, the NTK cannot perform better than the optimal MKL kernel. To fix the NTK, we improve the weights induced by it using the iteratively reweighted least squares (IRLS) scheme to obtain the optimal solution of the group lasso formulation of the gated ReLU network. We corroborated our theoretical results by empirically running IRLS on toy datasets.
While our theory is able link the optimization properties of the NTK with those of finite width networks via the MKL. characterization of group lasso, we do not derive explicit generalization results on the test set. Applying existing generalization theory for kernel methods [44, 45] to the MKL. interpretation of the convex reformulation could be a promising direction for future work.
Finally, although studied fully connected networks in this paper, our approach can be directly extended to various neural network architectures, e.g., threshold/binary networks [46], convolution networks [47], generative adversarial networks [48], NNs with batch normalization [49], autoregres- sive models [50], and Transformers [51, 52].
Acknowledgements
This work was supported in part by the National Science Foundation (NSF) CAREER Award under Grant CCF-2236829, Grant DMS-2134248 and Grant ECCS-2037360 2037304; in part by the U.S. Army Research Office Early Career Award under Grant W91 Precourt Institute; and in part by the ACCESS -AI Chip Center for Emerging Smart Systems through InnoHK, Hong Kong, SAR.
in part by the Stanford
10

---

References
[1] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[2] Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable program- ming. arXiv preprint orXiv:/812.07956 2018.
[3] Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy. and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. Advances in Neural Information Processing Systems, 33:5850-5861, 2020.
[4] Boris Hanin and Mihai Nica. Finite depth and width corrections the neural tangent kernel. In International Conference on Learning Representations, 2020.
[5] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. In Advances in Neural Information Processing Systems, pages 8 8139-8 394-814,,222 2019.
[6] Tolga Ergen and Mert Pilanci. Convex geometry and duality of over perapaaameterie neural networks. Journal of Machine Learning Research, 22(212):1-63, 2021.
[7] Mert Pilanci and Tolga Ergen. Neural networks convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pages 7695-7705 PMLR, 2020.
[8] Aaron Mishkin, Arda Sahiner, and Mert Pilanci. Fast convex optimization for two-layer relu networks: Equivalent model classes and cone decompositions. arXiv preprint t:Xiv:2202.013311 2022.
[9] Arda Sahiner, Tolga Ergen, John M. Pauly, and Mert Pilanci. Vector-output relu neural network problems are copositive programs: Convex analysis of two layer networks and polynomial-tine algorithms. In International Conference on Learning Representations, 2021.
[10] Tolga Ergen and Mert Pilanci. Convex geometry of two-layer relu networks: Implicit autoen- coding and interpretable models. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4024 4033, Online, 26-28 Aug 2020. PMLR.
[11] Tolga Ergen and Mert Pilanci. Convex duality and cutting plane methods for over-parameterized neural networks. In OPT-ML workshop. 2019.
[12] Tolga Ergen and Mert Pilanci. Convex programs for global optimization of convolutional neural networks in polynomial-tine In OPT-ML workshop, 2020.
[13] Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3004-3014, PMLR, 18-24 Jul 2021.
[14] Yifei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have zero duality gap. In The Eleventh International Conference on Learning Representations, 2023.
[15] T. Ergen and M. Pilanci. Convex optimization for shallow neural networks. 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 79-83, 2019.
[16] Alain Rakotomamonjy, Francis Bach, Stéphane Canu, and Yves Grandvalet. Simplemkl. Journal of Machine Learning Research, 9:2491-2521, 2008
[17] Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. arXiv preprini arXiv: (tte::7030099555 2017.
[18] Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
[19] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference Machine Learning, pages 4433-4441 PMLR, 2018.
11

---

[20] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-lan layer neural networks with landscape design, 2017.
[21] Yifei Wang. Jonathan Lacotte, and Mert Pilanci. The hidden convex optimization landscape of regularized two-layer reLU networks: exact characterization of optimal solutions. In International Conference on Learning Representations, 2022.
[22] Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Sociery: Series (Statistical Methodology), 68(1):49-67) 2006.
[23] Lei Tan, Shutong Wu, and Xiaolin Huang. Weighted neural tangent kernel: A generalized and improved network-induced kernel. arXiv preprint arXiv:2103. 11558, 2021.
[24] Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent achieve arbitrarily small test error with shallow relu networks, arXiv preprint arXiv: 12292, 2019.
[25] Lenaic Chizat. Sparse optimization measures with over-parameterized gradient descent. Mathematical Programming, 194(1-2):487-33, 2022.
[26] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665- E7671, 2018.
[27] Rajat Vadiraj Dwaraknath. Understanding the neural tangent kernel. https:// rajatvv.github.io/
2019. Accessed: 2022-05-17.
[28] Simon Du and Wei Hu. Ultra-wide deep nets and the neural tangent ker- nel (ntk). https://blog..l http:/gwwm.mmmm.....///////////
seree--nets-and--ee the-
seural-tangent-kereete
2019. Accessed: 2022-05-17.
[29] Francis R Bach, Gert RG Lanckriet, and Michael Jordan. Multiple kernel learning, conic duality, and the smo algorithm. In Proceedings of the twenty-first international conference on Machine learning, page 6, 2004.
[30] Francis R Bach. The "eta-trick" reloaded: multiple kernel learning, 2019. Accessed: 2022-05-
17.
[31] Francis R Bach. Consistency of the group lasso and multiple kernel learning. Journal of Machine Learning Research, 9(6), 2008.
[32] Ingrid Daubechies, Ronald De Vore, Massimo Fornasier, and C Sinan G üntürk. Iteratively reweighted least squares minimization for sparse recovery. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 63(1):1-38) 2010.
[33] Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, et Optimization with sparsity-inducing penalties. Foundations and Trends@ in Machine Learning, 4(1):1-106, 2012.
[34] Julien Mairal, Francis Bach, and Jean Ponce. Sparse modeling for image and vision processing. arXiv preprint 1411.333 2014.
[35] Francis R Bach. The "eta-trick" or the effectiveness of reweighted least-squares. www.cceeeeteeeeeeeeeeeeeeeeeeeee -ttpo/////B7-/// trrittriiko or- the- wffectiveness-ott reweighted- least- www.eeesaasssseeeeeeeaeaa 2019. Accessed: 2022-05-17.
nttps://francisbet
[36] Han Liu and Jian Zhang. Estimation consistency of the group lasso and its applications. In Artificial Intelligence and Statistics, pages 376-383, PMLR, 2009.
[37] Peter Bühlmann, Sara van de Geer, Peter Bühlmann, and Sara van de Geer. Theory for the lasso. Statisties for fiigh-Dimensionll Data: Methods, Theory and Applications, pages 99-182, 2011.
[38] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 255)335-336, 1989.
[39] Dario Azzimonti and David Ginsbourger. Estimating orthant probabilities of high-dimensional gaussian vectors with an application to set estimation. Journal of Computational and Graphical Statistics, 27(2):255-
2018.
[40] Peter Craig. A new reconstruction of multivariate normal orthant probabilities. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 70(1):227-243, 2008.
12

---

[41] Christopher C Paige and Michael A Saunders. Lsqr: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software (TOMS), 811):33-71, 1982.
[42] David Chin-Lung Fong and Michael Saunders. Lsmr: An iterative algorithm for sparse least- squares problems. SIAM Journal on Scientific Computing, 33(5)2950-2271,, 2011.
[43] Manuel Fernández- Dellgad, Eva Cernadas, Senén Barro, and Dinani Amorim. Do need hundreds of classifiers to solve real world classification problems? Journal of Machine Learning Research, 15(90):3133-3181 2014.
[44] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: Hypercontractivity and kernel matrix concentration, Applied and Computational Harmonic Analysis, 59:3-84, 2022.
[45] Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Generalization bounds for learning kernels. International Conference on Machine Learning, 2010.
[46] Tolga Ergen, Halil I. Gulluk, Jonathan Lacotte, and Mert Pilanci. Globally optimal training of neural networks with threshold activation functions. In The Eleventh International Conference on Learning Representations, 2023.
[47] Tolga Ergen and Mert Pilanci. Implicit convex regularizers of cnn architectures: Convex optimization of two- and three-layer networks in polynomial time. In International Conference on Learning Representations, 2021.
[48] Arda Sahiner, Tolga Ergen, Batu Ozturkler, Burak Bartan, John M. Pauly, Morteza Mardani, and Mert Pilanci. Hidden convexity of wasserstein GANs: Interpretable generative models with closed-form solutions. In International Conference on Learning Representations, 2022.
[49] Tolga Ergen, Arda Sahiner, Batu Ozturkler, John M. Pauly, Morteza Mardani, and Mert Pilanci. Demystifying batch normalization in reLU networks: Equivalent convex optimization models and implicit regularization. In International Conference on Learning Representations, 2022.
[50] Vikul Gupta, Burak Bartan, Tolga Ergen, and Mert Pilanci. Convex neural autoregressive models: Towards tractable, expressive, and theoretically backed models for sequential forecasting and generation. ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3890-3894, 2021.
[51] Tolga Ergen, Behnam Neyshabur, and Harsh Mehta. Convexifying transformers: Improving optimization and understanding of transformer networks. arXiv, 2022.
[52] Arda Sahiner, Tolga Ergen, Batu Ozturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Unraveling attention via convex duality: Analysis and interpretations of vision transformers. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 99050-19088. PMLR, 17-23 Jul 2022.
[53] Kaare Brandt Petersen, Michael Syskind Pedersen, al. The matrix cookbook. Technical University of Denmark, 7(15):510, 2008
[54] Erling D Andersen and Knud D Andersen. The mosek interior point optimizer for linear programming: implementation of the homogeneous algorithm. In High performance opti- mization, pages 197-232. Springer, 2000.
[55] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[56] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[57] Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. In Marina Meila and Tong Zhang, editors, Proceedings the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2993-3003. PMLR, 18-24 Jul 2021.
[58] Tolga Ergen and Mert Pilanci. Path regularization: A convexity and sparsity inducing regular- ization for parallel relu networks. arXiv preprint arXiv:2 10.00544 2021.
13

---

Supplementary Material
Table of Contents
A Proofs and Theoretical Results
14
A.1 Proof of Lemma 2.2
14
A.2 Proof of Lemma 2.3
15
A.3 Proof Lemma 4.2
A.4 Proof of Theorem 4.3
16
A.5 Proof of Theorem 5.1
16
A.6 Proof of Corollary 5.2
16
A.7 Proof of Theorem 6.1
17
B Experimental Details
C Generie Loss Functions
19
D Extensions to Deeper Networks
20
E Cone Decomposition
20
E.1 Computational Complexity
21
A Proofs and Theoretical Results
A.1 Proof of Lemma 2.2
The gradient feature map of (9)
1x gi 2 0} x w
1 V2m
(xT gm 2 0) xw'! (1)
Vefg (x
1 [x T g1 2 0) wi
(x gm 2 0} u
(2)
The finite width random NTK given by Hm.o.g (x, x')== = Vofe (x. 0)¹²" Volg (x'
Hm.o.g (x)
[1x" 2 2 gj 20] xxTw/! 11)
(wff1) x x
2m
By the Law of Large numbers since gy, wj w are iid, Hm.o.g (x, x') converges in probability the expectation of the quantity in the sum as m oc. We denote this infinite limit by (x, x'). Therefore.
(1)
(2)
1 _E 1(x" 2 1200 g 82 xT xx (()) (w)2) 2 x" |. H (x,x')
where g N (0. (1) AO Ia). w (0, Using E (1012))2
xx (1) w(l) = xT x' and the linearity of expectation, we get
H (x,x' = 2 22
(18)
14

---

To evaluate the expectation of the product of the indicator random variables, we condition on one of the indicators being equal 1.
E [ g 2 0}]
= fx x 0) 1 g = -2 2 0] = 1
2 B [x"g 2 0) 82
The conditional expectation is the probability of the event that x2 g 2 0 given that x" g 2 0. This can be geometrically seen as the ratio of л minus the angle between x and x' to T. So, we get
1
x x3xx'
E 1 {x 2 03 g 2 0.
arccos
2
||x||2 ||x'|12
Combining this with (18) yiclds the desired result.
A.2 Proof of Lemma 2.3
The gradient feature map of (11) is
x w (+) 20,x x
1 x" mm
(+) 2 0 x
1 22m
Veft (x
1 x" w 1
(-) 2 0
- 1 { x² x"wn" wm 2 0
The finite width random NTK given by H
(x, x'):= Voli (x, 0)² Volr (x is
m
H (x,x))
(+) 2 0) 1 f x w (+) 2 0) x-x+
2m
x w 2 0 wf w (-) 2 20)xx(
20
By the Law of Large numbers since w (+) the expectation of the quantity in the sum as m + xc. We denote this infinite limit by H" (x, x'). Therefore.
w are iid, H 0 (x, x') converges in probability to
H (x, x') E
w
2 0) { x" w(() 20())
1 x w/ 0) 1 fx w 0) x"xx,
where w(+) ~ N (0, la) and w(-) ~ NO,, Ia). Since w(+) and w(-) are i.i.d., we can combine the expectations to get
H" (xxx)= =E 1 {1xxx x w (+) 2 1 w(+) 2 x
Comparing to (18), we get the desired result.
A.3 Proof of Lemma 4.2
Since G is complete, V E [p] 3gg E G such that diag (1 (Xg: 2 0)) = D.. Additionally, these gates g: are unique since diag (1 (Xg: > 0}) * diag (1 (Xg; 2 0}) = g: + gg. Therefore, there is subset gates G of size p that are uniquely associated to each mask D,. Since G is also minimally complete, this subset must be G and this proves the lemma.
15

---

A.4 Proof of Theorem 4.3
By Lemma 3.1, the MKL problem given by
2
min MEAp.
D.v y
v
equivalent to the group lasso problem (14). Additionally, (14) is also equivalent to the standard group lasso (15) since they have the same regularization paths. Since g is minimally complete, (7)
(which is equivalent to (6) in the minimally complete gate set setting) is equivalent to the group lasso problem (15) and this proves the theorem.
A.5 Proof of Theorem 5.1
The weighted masking kernel given by
Kg (7) Σ D,
(19)
Now, the NTK matrix H can be written as (using (18)),
H E (( [diag (1 (Xg 2 0}) xx diag (1) (Xg 2 0})]
We condition the events that diag (1 [g 0}) D; v E [p). Since Dx covers all possible data maskings D,, we know that Dp=1 [diag (1 [Xg 2 0)) D = 1. Therefore,
H
E V(LLa [DxX" D, diag (1 [Xg 2 0}) Dj P diag (1 [Xg 2 0}) D.]
D x, (diigg (1 [Xg 2 0}) = =D:..
Plugging in ij P diag (1 (Xg 2 0}) D and comparing (19), get that Kg (Π) HH and this proves Theorem 5.1.
A.6 Proof of Corollary 5.2
First, we define a single combined masked data matrix X Ruxpd as follows
X = D D,X.-. D,X] D.X...D,....
We also define diagonal regularization weighting matrix R Rpddxpd follows
R diag (m la
izla 1al);
where 1a is a d-dimensional all-1s row vector. Now, we can rewrite (16) with +, = D,X and
regularization weights 7 as
2 Xw - y11 +
min WERRd
R 2 w
(20)
Setting the gradient of the convex objective in (20) to O, we get the following equation for the solution w,
2X T' Xw y)) v) + 2XR 2 0.
16

---

Solving for w, we get
w = (x"*+ + AR X"y
By applying the matrix inversion lemma [53], we can rewrite this
w RX (XRX*' + AIn)
Now, we notice that
Σ D X -XRXT (XRX² + AIn) y.
(21)
Additionally, observe that XRX = E DxXDD = H where the last equality is by Theorem 5.1. Plugging this into (21), we get
D,Ww, = +
and this proves Corollory 5.2.
A.7 Proof of Theorem 6.1
We begin with the optimality of w.
p Σ
p
D y
W 112 S
Σ D
X w -y
+
|w] 1l1
n
n
i=1
By plugging in the model y D. D,Ww, + we simplify this to
i Σ D (w: D.
w;) -
+
| lla - -1el1 +
l|
We expand the square on the LHS and obtain the following bound on the prediction error
P DDX (w, w)) +1
P
D (w: w()
w ll2 llwell2)
7
n
1
P
V^
|| T 1 I|: - willz + Σ (llwill2 w
where we used Cauchy-Schwarz inequality in the second step. Now, since D; are diagonal matrices
with either 0 or 1 on the diagonals, we can immediately say that "D,' l S i 11....;2. p. As a consequence, we get
| le' /'x] l for all
1
D.X (w, wi)
T
X
- + w:
(I|w3 l12 - 1|w.l12)
1=1
1=1
2
2 x
||2
+
>
I 1l +
2
- x x
>
Σ
|wall /
can get rid of the second term, namely ( [ 2 >) E W/ll and obtain a bound on the prediction error that does not depend on w. To this end, notice that e T is multivariate Gaussian with mean 0 and covariance a² 2x"X. We now present standard concentration result for the norms of Gaussians in the lemma below,
where we used the triangle inequality in the second step. Now, if X
||
17

---

Lemma A.1. Let z be d-dimensional multivariate Gaussian with mean O and covariance matrix Σ. We have
-2²
PP |||z|12 2
exp
21r (Σ)
Applying Lemma A.I to X,
X, we get
22
P [[]e"X]]] X = 2 1
2e 2=
t0 (r(xr(XxX) in the statement of theorem, get
Plugging in 2 A where A
n
P
X 11
Therefore, by choosing 1 2e 2//8, Consequently, have
to xxxxxx
we have that 2 ||exX|12
A with probability at least
"
2 2A
1
P Σ D.X (w; -w;)
w
n
2
with probability at least 2/8 which completes the proof.
A.7.1 Proof of Lemma A.1
Since the norm of Gaussian vector does not change by applying a rotation, we know that ||A2/=u|| and ||z||| have the same distribution where A is the matrix of eigenvalues from the spectral decom- position Σ QAQ and N (0, Ia). Now apply standard Chernoff bound argument. We
have for some s > 0,
P Al
PP
2
2
|| ||
> 6a2
nTd E [oVAluull
$ e
2c
I1
2012
2.12.
By optimizing the bound over s, get
P
||||a1 13/2 =
2 2exp
-2²
< 2exp
-22 2tr ΣΣ)
2 A
Finally, using PP [|2/|2 S 2] =1 P
[l|z|12 > 2] gives the result.
B Experimental Details
Hyperplane Arrangements for 1D example. In the ID example in Figure 1, the data matrix X is in R=x2, i.c. the dimension d 2. This is because set the second component of cach input to be exactly equal to 1 to simulate a bias the neural network. Though the datapoints some structure which allows us enumerate all hyperplane arrangements Dx easily. Specifically, the datapoints all lie on the line y = in the zy plane, so the hyperplanes that separate them always separate them into two contiguous segments. Therefore, by sorting the datapoints according their first component, we can directly enumerate all 2n hyperplane arrangements.
in I they have
Nonconvex ReLU network. For the black dashed line in Figure 1, we trained two layer ReLU network with 100 hidden neurons using the standard weight decay regularized objective with gradient descent using learning rate of 0.01 for 200000 epochs.
18

---

Convex program solver specifications. For directly solving the group lasso problem (8), we used CVXPY with the MOSEK solver [54]. For the l regularized least squares problems (16). we used iterative methods with an efficient matrix-vector product implementation to avoid explicitly constructing the large combined masked data matrix X. Specifically, we used the LSQR and LSMR methods as described in [41, 42]. The experiments were run locally on a MacBook Air 2020 version with the Apple MI chip.
UCI Machine Learning Repository. Here present details for the experiments on several real datasets from the UCI Machine Learning Repository [55]. We follow the procedure described in [43] for n < 1000 to extract and standardize the datasets. For these experiments, we use the 75% 25% ratio for the training and test set splits. We use the squared loss and tune the regularization parameter À for both NTK and our approach by performing a grid search over the set (10-5, 10= 10-3, - 10-2, 10-1, 10", 10 As shown in Table I, our method achieves higher (or the same) test accuracy for 26 datasets out 33 datasets while standard NTK achieves higher (or the same) test accuracy for 14.
C Generic Loss Functions
Here, we prove that the analysis with squared loss presented the main paper can be extended to arbitrary convex loss funetion. Let consider the following regularized two-layer ReLU network training problem with an arbitrary convex loss function L (..-)
min wOw,wa
Σ
(ww!))
(2) w
y
+
(w + (w(2)pp)
(22)
j=1
Then, as shown in [7], the corresponding gated convex reformulation of (22) is
p D. -y v) + w
:= min L W:
(23)
In order to realize the emergence of kernel characterization in the case of arbitrary loss function, we use Lagrange duality. Particularly, since (23) a convex optimization problem and Slater's conditions holds as proven in [7, 8), we equivalently represent (22) the following dual problem
P
max L (z,
s.l.
|zz |x' DJ D2X112 S X, Vi E [p]
(24)
where L yz) is the Fenchel conjugate of C y) defined as [56]
C² y) = max z C (v.y).
We then form the Lagrangian for (24) as follows
[(2, 0.)) -L" (z,y) +
ai () - 10-1222' |2=,,x11>>>
1=1
= =- (2,y) + Σ
04 (A -x'"DXX''
i=1
= -- (z,y) +
Σ 0r (X - x² K,2)
1=1
where a; 2 0 is the Lagrange multiplier for the inequality constraint. Based on the representation above, the dual problem in (24) can be written as
P max min L" (v.y) + E a4 (A x" K,z) 0,20
(25)
Thus, similar to (12), the problem (25) can be globally optimized with alternating minimization [33, 35].
19

---

D Extensions to Deeper Networks
In this section, we generalize the kernel characterization of two-layer ReLU networks presented in the main paper to deeper architectures. We first note that most prior works convex reformulation of ReLU networks studied only two-layer ReLU networks, e.g., [6-10], since the non-convex interaction of multiple nonlinear layers hinders the convex analysis deeper networks. However, recent follow- up studies [13, 57, 58] showed that the analysis can be extended to arbitrarily deep networks, Based on this recent results, below we briefly explain how one can extend our kernel characterization to three-layer networks. By following the convex reformulations in [57, 58), we have the following gated ReLU training problem for three-layer network
P2 D
P1
P2
min Wiy
Xw y
w
(26)
where the hyperplane arrangements for the first and second ReLU layers, i... denoted as D
D
and D
(2) } E D are defined as follows
D {diag (1 (Xu 2 0}) IR and pi:= |
(27)
D = { diag (x((XU))) (2) 2 o0) u Rdxmy ( RT and p2: |D
Then, following the derivations Section 4, we can conveniently express the corresponding feature matrices of these masking feature maps on the data X in terms of fixed diagonal data masks as (2) X. Similarly, the corresponding masking kernel matrices take the form K.j = "D
Pi
D X (' ((3)) The same interpretation also extends to arbitrarily deep networks and yields more complicated feature map due to the interaction of multiple hyperplane arrangement matrices, e.g., D D
D
E
Cone Decomposition
Here, we briefly review the cone decomposition concept introduced by [8]. We first note that (3) is the exact convex reformulation of the standard non-convex regularized training problem in (2). However, as mentioned in the main paper. the number of constraints (3) can be prohibitively large, precisely can be (nn)), and consequently prevents solving the exact convex optimization problem especially for large scale datasets. To remedy this issue, [8] proposed the unconstrained formulation (8), but, this relaxation corresponds to another neural network architecture called gated ReLUU network in (5). Although this relaxation breaks dependence between the arrangements and preactivations of a ReLU activation, [8] proved that once the gated ReLU network training problem in (8) training problem is solved, one can construct a solution for the ReLU network model in (1). This procedure named as cone decomposition and we provide details regarding the implementation steps below.
Let us assume that we solve the gated ReLU network training problem in (8) and denote the optimal solution as {w; ) Then, since each D,Xw² can have both negative and positive entries (due to the absence of nonnegativity constraint) ), we need decompose D,Xw; into two separate cones to maintain nonnegativity property of a ReLU activation. We formulate this decomposition step as the following convex optimization problem
(2D: - I, Xv; 2 0 min Valll + ||u/||2 s.t. D,XW; DAX(V, -u), (2D: Xu; 0" V..u;
(28)
After solving the convex optimization problem in (28) for all i E [p]. We declare the optimal solutions, (v7, uj { as a solution to exact ReLU model (1). Thus, instead of directly solving the convex reformulation with extremely large number of constraint in (3), we first solve the relaxed gated ReLUU problem in (8) and then map the solutions the proper cones to enforce the nonnegativity property of the ReLU activation.
20

---

E.1 Computational Complexity
Although [8] reduce the computational complexity by eliminating the constraints in the convex optimization problem in (3), the number of variables, denotes as p, can still be exponentially large in feature dimension However, there are multiple ways to remedy this issue.
We can change the architecture. Particularly, we can replace fully connected networks with convolutional networks. Then, since CNNs operate on the patch matrices {X+]o=1 instead of the full data matrix X, where X E Ru and h denotes the filter size, even when the data matrix is full rank, i.e., r min(n,, d), the number of hyperplane arrangements p is upperbounded as p S O(n*). where r. == max, rank(X,) I h < min d). For instance, let us consider a CNN with x 3 filters, then r. I independent of n, d. As consequence, weight sharing structure in CNNs dramatically limits the number of possible hyperplane arrangements and avoids exponential complexity. This also explains efficiency and remarkable generalization performance of CNNs in practice.
We can also use sampling based approach where one can randomly sample a tiny subset of all possible hyperplane arrangements and then solve the convex program with this subset. Thus, although the resulting approach is not exact, the traiming complexity will not be exponential in d anymore. The experimental results Appendix show that this approximation fact works extremely well, specifically resulting in models that outperform the NTK in 26/33 UCI datasets as detailed in Table
21


Reviews:
[{"review_id": "eGnKBew57j", "reviewer": "Reviewer_98L1", "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.", "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?\n2. 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?\n3. 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?", "limitations": "See weakness", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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.\n\nThe 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:\n\n1. 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.\n2. 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.\n3. 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.\n4. 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.\n5. 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and comments. We hope that you would consider increasing your score if your concerns are adequately addressed. We have addressed the issues related to generalization in the global response. Please see our responses to your other specific queries below.\n\n$\\textbf{Activation functions:}$\nWe note that the convex reformulations can be extended to other activation functions. Particularly, for all piecewise linear activations (including ReLU, leaky ReLU, absolute value or binary activations), the same analysis hold except that the structure of the gates (diagonal matrices $\\mathbf{D}_i$) changes. We also want to emphasize that the same analysis can also be applied to smooth activations such as sigmoid or tanh but in those cases the computational complexity can be slightly higher due to the increase in the required number of gates/diagonal matrices.\n\n$\\textbf{Kernel methods}$\nWe are not sure exactly what you mean by the statement that even deep neural networks can expressed in a feature map format. Previous works (apart from the NTK) characterizing deep neural networks establish equivalence to a kernel method by freezing all the weights except for the last layer, effectively resulting in a random features model. The NTK is another kernel characterization, but requires the neural network weights to be in the lazy regime with infinite or large width (where the weights do not change much from initialization). The kernel characterization we present in this work differs from these previous approaches by studying the finite width regime where the weights need not be close to initialization, and the kernel is learnt from the data. \n\n$\\textbf{Simplex constraint:}$\nNote that the change of variables argument merely establishes equivalence of problem (12) and the problem described in lines 163-164. We would like to point out that both problems contain the simplex constraint. This constraint, and the weight variable $\\eta$ can be eliminated by applying the variational formulation of the squared group $\\ell_1$ norm, which is presented in lines 161-162. This allows us to convert the standard $\\ell_2$ regularization in the problem between lines 163-164 to the squared group lasso regularization without the weights $\\eta$ in problem (14). This is the main result of Lemma 3.1. A further result is the equivalence between $\\textit{squared}$ group lasso and the standard group lasso, which is presented in problem (15). \n\nTheorem 4.3 is the result of a chain of equivalences between various optimization problems (proof in the supplement). We present them here again as a summary. (7) is the standard non-convex learning problem for the gated ReLU network. Prior work showed that this is equivalent to the group lasso problem (15). This is also equivalent to the squared group lasso problem (14). Lemma 3.1 then connects (14) to the MKL problem (12). The crux of the argument is as follows: the MKL problem optimizes over parameters $\\mathbf{w}$ as well as weights $\\eta$ over the kernels, with $\\eta$ constrained to be in the simplex, and the parameters $\\mathbf{w}$ having standard $\\ell_2$ regularization (this is problem (12)). Using the variational argument in the proof of Lemma 3.1, we can completely eliminate the kernel weight variable $\\eta$ (along with its simplex constraint), by replacing the standard $\\ell_2$ regularization with a squared $\\textit{group lasso}$ regularization, which is exactly problem (14). \n\n$\\textbf{Regarding Regularization}$\nYes, the results extend to non-regularized version by taking the limit $\\lambda \\to 0$ and following the regularization path of the solution. Additionally, we use the regularized objective to avoid issues related to overfitting, leading to better generalization performance in practice.\n\n$\\textbf{Why IRLS?}$\nThe motivation behind introducing IRLS is that the solution obtained by the NTK can be expressed as one instance of an iterate in the IRLS algorithm, allowing us to directly obtain the optimal MKL solution by initializing with the NTK solution.\n\nComputationally, each iteration of the IRLS method involves a simple least squares regression problem that has a closed form solution which can be computed using very efficient direct and iterative methods. Additionally, state of the art iterative methods like preconditioned conjugate gradient -- specifically LSQR and LSMR [1, 2] that we use for solving these least squares problems can be efficiently parallelized and implemented with GPU acceleration [3].\n\n[1] - Paige, Christopher C., and Michael A. Saunders. \"LSQR: An algorithm for sparse linear equations and sparse least squares.\" ACM Transactions on Mathematical Software (TOMS) 8.1 (1982): 43-71.\n\n[2] - Fong, David Chin-Lung, and Michael Saunders. \"LSMR: An iterative algorithm for sparse least-squares problems.\" SIAM Journal on Scientific Computing 33.5 (2011): 2950-2971.\n\n[3] - Huang, He, et al. \"An MPI-CUDA implementation and optimization for parallel sparse equations and least squares (LSQR).\" Procedia Computer Science 9 (2012): 76-85."}, {"review_id": "2hLrAb0ggL", "reviewer": "Reviewer_NJAL", "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.", "questions": ".", "limitations": ".", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "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.\n\nTherefore, 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": ".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the positive feedback and accurate comments, and greatly appreciate the time taken by them to review our work. We are encouraged to know that you believe that our main insights warrant an acceptance. "}, {"review_id": "vxQp8btSN3", "reviewer": "Reviewer_Tkhd", "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.", "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.\n\nIf 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.", "limitations": "As already mentioned, the authors should be clearer about the two following possible issues:\n- 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.\n- That the optimization is not unique outside the training set.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nThe 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.\n\nAnother 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and comments. We have addressed the issues related to complexity in the global response. Please see our responses to your other specific queries below.\n\n$\\textbf{Regarding the objective}$\nWe would like to clarify that one of the main results of our work is that the MKL optimization problem with group lasso is indeed equivalent to the standard non-convex training with L2 regularization loss. Thus, this cost was not designed from the perspective of the NTK, but instead was obtained by deriving an equivalent convex reformulation, which we also show captures the loss function from performing kernel ridge regression with the NTK. \n\nWe thank the reviewer for raising this point, and we will revise our wording in the final version to be clearer when describing the suboptimality of the NTK."}, {"review_id": "pZTZzHt5qC", "reviewer": "Reviewer_nJAh", "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.", "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.", "limitations": "* The work seems to consider minimal complete gate sets. \n* The work does not appear to include observations into overfitting or generalisation.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The work deals with a relevant problem of understanding the optimization problem of neural networks beyond the infinite width setting. \n* 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. \n* 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].   \n    * [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.  \n    * [2] Su and Yang. On learning over-parameterized neural networks: A functional approximation perspective.  \n    * [3] Liu et al. On the linearity of large non-linear models: when and why the tangent kernel is constant. \n    * [4] Bowman and Montufar. Spectral Bias Outside the Training Set for Deep Networks in the Kernel Regime. \n* 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,…]. \n    * [1] Ergen and Pilanci. Convex geometry and duality of over-parametrized neural networks.\n    * [2] Pilanci and Ergen. Neural networks are convex regularizers: exact polynomial time convex optimization formulations for two layer networks. \n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the feedback and comments. We hope that you would consider increasing your score if your concerns are adequately addressed. We have addressed the issues related to generalization in the global response. Please see our responses to your other specific queries below.\n\nWe greatly appreciate the reviewer for pointing out the references that study the NTK in the finite but large or small width regimes. We will include a discussion of this related work in the final revision of our work. However, we would like to point out an important distinction between our kernel characterization and the works which study the NTK in various width regimes. Specifically, based on our understanding, the works you reference still analyze the NTK in the regime where the weights do not much from initialization (the lazy regime), and the kernel is not learned from the data. On the other hand, our MKL kernel characterization does not require the weights to stay close to initialization, and the optimal kernel is learned from the data.\n\nThe significant contribution in relation to prior works on convex formulations is to connect these reformulations to the MKL perspective, which further reveals a connection to the NTK theory, allowing us to show that the convex reformulation leads to a new kernel characterization of gated ReLU networks that applies beyond the lazy regime (which is required for the NTK theory to hold).\n\n$\\textbf{Training accuracy results}$\nIn the paper, we present experimental results that showcase the $\\textit{generalization}$ performance of the gated ReLU model compared to the NTK. For completeness, we also present here the $\\textit{training}$ accuracies for the UCI datasets, which we will add to the final revision of the paper. Note that, as a consequence of Theorems 4.3 and 5.1, we expect that our kernel always outperforms the NTK on the training set, which is exactly what we observe in the table below:\n\n**We note that our aim is to minimize the regularized training objective which includes not only the training loss but also the regularization term. And then during the validation process, we made a grid search for the regularization coefficient $\\beta$ and included the results with the best test accuracies (generalization performance) for both models. Therefore, it is normal to have some training accuracy below 100%.**\n\n**Training accuracies by training on standard $\\ell_2$ regularized loss**\n\n| Dataset Name                              | NTK | **Ours** |\n|-----------------------------------|---------|---------|\n| acute-inflammation                | 1.000   | 1.000   |\n| acute-nephritis                   | 1.000   | 1.000   |\n| balloons                          | 1.000   | 1.000   |\n| blood                             | 0.841   | 0.957   |\n| breast-cancer                     | 0.799   | 0.986   |\n| breast-cancer-wisc-prog           | 0.975   | 1.000   |\n| breast-cancer-wisc-diag           | 1.000   | 1.000   |\n| breast-cancer-wisc-prog           | 0.973   | 1.000   |\n| congressional-voting              | 0.752   | 0.791   |\n| conn-bench-sonar-mines-rocks      | 1.000   | 1.000   |\n| credit-approval                   | 0.868   | 1.000   |\n| cylinder-bands                    | 0.766   | 1.000   |\n| echocardiogram                    | 0.888   | 1.000   |\n| fertility                         | 0.960   | 0.920   |\n| haberman-survival                 | 0.821   | 0.991   |\n| heart-hungarian                   | 0.850   | 1.000   |\n| hepatitis                         | 0.931   | 1.000   |\n| ilpd-indian-liver                 | 0.808   | 1.000   |\n| ionosphere                        | 0.939   | 1.000   |\n| mammographic                      | 0.845   | 0.950   |\n| molec-biol-promoter               | 1.000   | 1.000   |\n| musk-1                            | 1.000   | 1.000   |\n| oocytes_trisopterus_nucleus_2f    | 0.830   | 1.000   |\n| parkinsons                        | 0.884   | 1.000   |\n| pima                              | 0.837   | 1.000   |\n| pittsburg-bridges-T-OR-D          | 0.908   | 0.987   |\n| planning                          | 0.809   | 1.000   |\n| statlog-australian-credit         | 0.571   | 1.000   |\n| statlog-german-credit             | 0.828   | 1.000   |\n| statlog-heart                     | 0.881   | 1.000   |\n| tic-tac-toe                       | 0.978   | 1.000   |\n| trains                            | 1.000   | 1.000   |\n| vertebral-column-2clases          | 0.892   | 1.000   |\n\nOur kernel achieves a higher train accuracy on 32/33 datasets, which is to be expected. The discrepancy in one of the datasets can be attributed to the approximation of subsampling a set of hyperplane arrangements.\n\n\n\n\n\n$\\textbf{Clarification about reparameterized ReLU network}$\nWe would thank the reviewer for bringing up this point. Indeed you are correct that the model (11) can be more expressive than (1), so we will modify the wording to \"... can represent the same or more functions as (1) ...\". Note that this does not affect the significance of our results, since the motivation behind introducing this reparameterization is to study an equally sized model (with $O(m)$ neurons) that can be obtained from a ReLU network (1) with $m$ neurons that has the same NTK as the gated ReLU network.\n\n$\\textbf{Minimal gate sets}$\nIndeed for the theoretical results to go through, we require that the gate set be complete. However, in practice we observe that sampling gates to obtain a subset of all possible hyperplane arrangements performs very well, so the approach is computationally feasible. Additionally, as discussed in the global response, the number of arrangements $p$ can be significantly reduced by subsampling or using a CNN architecture.\n"}, {"review_id": "Hnjzh3CPTC", "reviewer": "Reviewer_UwLS", "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.", "questions": "No.", "limitations": "Yes.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:
We would like to thank all the reviewers and the AC for taking the time to review and assess our work.

We are encouraged to know that the reviewers believe that our findings are valuable and our main insights are sufficiently novel. We also appreciate that the reviewers found the paper well written and lucid, as clarity of presentation is important to us.
 
In this global response, we address some of the common queries and concerns brought up by the reviewers.

$\textbf{Regarding Generalization:}$

We would like to emphasize that the focus of this paper is on optimization of neural networks with a standard regularized training objective. Indeed, theoretically studying the generalization properties of the MKL kernel and convex reformulations is a very interesting direction for future work, but the focus of our theoretical results in this work is on the training performance. **With regards to generalization, we present empirical results that indicate that our convex MKL formulation also achieves better test performance than the NTK formulation on multiple datasets (Table 1 for UCI datasets, and the learned functions in Figure 1 for toy datasets).**


$\textbf{Complexity arising from number of hyperplane arrangements/kernels:}$ 

There are multiple ways to avoid high computational complexity as detailed below. 

* First, one can use a sampling based approach where one can randomly sample a tiny subset of all possible hyperplane arrangements and then solve the convex program with this subset. Thus, although the resulting approach isn't exact, **the training complexity won't be exponential in  any of the problem parameters anymore**. The experimental results in Section 7 show that this approximation in fact works extremely well, specifically resulting in models that outperform the NTK in 26/33 UCI datasets. 

* Second, we can change the architecture. Particularly, we can replace fully connected networks with convolutional networks. Then, since CNNs operate on the patch matrices $\\{\mathbf{X}_b\\}\_{b=1}^B$ instead of the full data matrix $\mathbf{X}$, where $\mathbf{X}\_b \in \mathbb{R}^{n \times h}$ and $h$ denotes the filter size, even when the data matrix is full rank, i.e., $r=\min (n,d)$, the number of hyperplane arrangements $p$ is upperbounded as $p \leq \mathcal{O}(n^{ r_c})$, where $r_c:=\max_b \mathrm{rank}(\mathbf{X}_b)\leq h \ll \min(n,d)$. For instance, let us consider a CNN with $3 \times 3$ filters, then $r_c \leq 9$ independent of $n,d$. As a consequence, weight sharing structure in CNNs dramatically limits the number of possible hyperplane arrangements and avoids exponential complexity. This also supports the observed efficiency and remarkable generalization performance of CNNs in practice.


Meta-review: The theoretical results in this paper are correct and interesting, which reveal whether DNN training can be interpreted as kernel learning. The authors need to polish and improve the paper according to the reviewers' suggestions in the revision.
Decision: Accept (poster)