A New Neural Kernel Regime: The Inductive Bias of Multi-Task Learning
Authors: Julia B Nakhleh
Joseph Shenouda
Robert D Nowak
Venue: NeurIPS 2024 poster (2024)
Keywords: neural networks
weight decay
multitask learning
regularization
kernels
Primary area: learning_theory
TL;DR: We prove that for multi-task ReLU neural networks trained with weight decay, the solutions to each individual task are related to solutions in a reproducing kernel Hilbert space.

Abstract: This paper studies the properties of solutions to multi-task shallow ReLU neural network learning problems, wherein the network is trained to fit a dataset with minimal sum of squared weights. Remarkably, the solutions learned for each individual task resemble those obtained by solving a kernel regression problem, revealing a novel connection between neural networks and kernel methods. It is known that single-task neural network learning problems are equivalent to a minimum norm interpolation problem in a non-Hilbertian Banach space, and that the solutions of such problems are generally non-unique. In contrast, we prove that the solutions to univariate-input, multi-task neural network interpolation problems are almost always unique, and coincide with the solution to a minimum-norm interpolation problem in a Sobolev (Reproducing Kernel) Hilbert Space. We also demonstrate a similar phenomenon in the multivariate-input case; specifically, we show that neural network learning problems with large numbers of tasks are approximately equivalent to an $\ell^2$ (Hilbert space) minimization problem over a fixed kernel determined by the optimal neurons.

A New Neural Kernel Regime: The Inductive Bias of Multi-Task Learning
Julia Nakhleh
Joseph Shenouda
Department of Computer Science
Department of Electrical and Computer Engineering
University of Busconsin-Madison Madison, WI
University Wisconsin Masconsin-Madison
Madison, WI
jnakhleh@risc..e
j jshenouda@wise.
Robert D. Nowak
Department of Electrical and Computer Engineering
University of Maaconsin-Madison
Madison, WI
rdnowak@visc.cm
Abstract
This paper studies the properties of solutions to multi-task shallow ReLU neural network learning problems, wherein the network is trained fit dataset with minimal sum of squared weights. Remarkably, the solutions learned for each individual task resemble those obtained by solving kernel regression problem, revealing a novel connection between neural networks and kernel methods. It is known that single-task neural network learning problems are equivalent to a minimum norm interpolation problem in a non-Hilbertian Banach space, and that the solutions of such problems are generally non-unique. In contrast, we prove that the solutions to univariate-inpur multi-task neural network interpolation problems are almost always unique, and coincide with the solution to minimum-nome interpolation problem in a Sobolev (Reproducing Kernel) Hilbert Space. We also the multivariate-inpu case; specifically,
demonstrate a similar phenomenon we show that neural network learning problems with large numbers of tasks are approximately equivalent to an l2 (Hilbert space) minimization problem over a fixed kernel determined by the optimal neurons.
1 Introduction
This paper characterizes the functions learned by multi-output shallow ReLU neural networks trained with weight decay regularization, wherein each network output fits different "task" (i.c., different set of labels on the same data points). We show that the solutions to such multi-task training problems can differ dramatically from those obtained by fitting separate neural networks each task individually. Unlike standard intuitions Caruana (1997) and existing theory [Bn- David and Schuller (2003); Maurer et al. (2016) regarding the effects and benefits of multi-tass learning, our results do not rely on similarity between tasks.
We focus on shallow, vector-valued (multi-output) neural networks with Rectified Linear Unit (ReLU) activation functions, which are functions fe IRd IRT of the form
K
fo(x) =
Σ
Uy ( x ba)_ + Ax +
(1)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

where (+)+ max + is the ReLU activation function and wA E RR, d E R", and by E R are the imput and output weights and bias of the hthh neuron. K is the number of neurons and T denotes the number of tasks (outputs) of the neural network. The affine term Azr + is the residual connection (or skip connection), where E Rxxx and E TR."" The set of all parameters denoted by 0 = (L0g, wy,, by ) k=1 A.c).
Neural networks are trained to fit data using gradient descent methods and often include a form of regularization called weight decay, which penalizes the E² norm of the network weights. We consider weight decay applied only to the input and output weights of the neurons- nno regularization is applied to the biases or residual connection. This is a common setting studied frequently in past work Savarese jet al. (2019); Ongie al.] (2019); Parhi and Nowak (2021). Intuitively, only the input and output weights not the biases or residual connection affect the "regularity" of the neural network function as measured by its second (distributional) derivative, which why makes sense to regularize only these parameters, Given set of training data points (æ11. y1),.- ... (æN, yN) E Rd x R. and fixed width] K N2, we consider the weight decay interpolation problem:
K
min
10x12 + | 1 subject to fo(w:) yia i= I,...,N. N.
By homogeneity of the ReLU activation function (meaning that (ax)+ a(z)+ for any 2 0). the input and output weights of any ReIUU neural network can be rescaled as un,; + un./ /|/r/ ||2 and 4% + Uk |/ without changing the function that the network represents. Using this fact, several previous works Grandvalet] ( [ Grandvalet and Canu (1998); Neyshabur et al. (2013); Parhi and
Nowak 2023); Shenouda et al. (2024) note that problem 2 is equivalent to
K
min
|elll,, subject to {[|well2 = =1]21, fo(x.) = yi, i i= 1.,,..,AA N
(3)
in that the minimal objective values of both training problems are the same, and any network fo which solves (2) also solves 33. while any So which solves (3) also solves (2) after rescaling of the input
and output weights. The regularizer Ex= kml |/2/|12 is reminiscent of the multi-task lasso Obozinski jet al.) (2006). has recently been shown to promote neuron sharing in the network, meaning that only a few neurons contribute to all tasks Shenouda et al. (024))
The optimizations in 2 and (3) are non-convex and may have multiple global minimizers. As an example, consider the single-tase task, univariate dataset in Fig. I For this dataset, (3) has infinitely many global solutions [Savarese et al. (219)) Ergen and Pilanci (202I): Debarre al. (2022): Hanin (2021). ). Two of the global minimizers are shown in Fig. 1] In some scenarios, the solution on the right may be preferable to the one on the left, since the interpolation function stays closer to the training data points, and hence is more adversarially robust by most definitions Carlini et al. (2019). Moreover, recent theoretical work shows that this solution has other favorable generalization and robustness properties Joshi et al. (2024). Current training methods, however, might produce any one of the infinite number of solutions, depending on the random initialization of the parameters as well as other possible sources of randomness in the training process. It is impossible to control this using existing training algorithms, which might explain many problems associated with current neural networks such as their sensitivity to adversarial attacks. In contrast, as show in this paper, training network to interpolate the data in Fig. aalong with additional interpolation tasks with different labels almost always produces unique solution, given by the (potentially preferable) interpolation depicted on the right. This demonstrates that the solutions to multi-task learning problems can be profoundly different than those of single-task learning problems.
The main contributions of our paper are:
Uniqueness of Multi-task Solutions. In the univariate setting (d 1) we prove that the solutions to multi- task learning problems with different tasks almost always represent a unique function, and we give a precise condition for the exceptional cases where solutions are non-unique.
By an argument similar to the proof of Theorem of Shenouda et al. (2024). J as long as K > N2, problem
3 is well-posed and attains the same minimal objective value (regardless of which K 2 2V2 is chosen). Therefore, in this work, we always assume that K is some fixed value larger than N²
2

---

Figure 1:
Two solutions to ReLU neural network interpolation (blue) of training data (red). The
functions on the left and right both interpolate the data and both are global minimizers of (2) and (3)
and minimize the second-order total variation of the interpolation function PParhi and Nowak (2021).
In fact, all convex combinations of the two solutions above are also global solutions to both training problems.
Multi-task Training = Kernel Method (almost always). When the solution to the univariate weight decay problem unique, it is given by the connect-the-dee interpolant of the training data points: i.e., the optimal solution is linear spline which performs straight-line interpolation between consecutive data points in all tasks. On the support of the data, this solution agrees with the minimum-norm interpolant in the first-order Sobolev space H' reproducing kernel Hilbert space (RKHS) which contains all functions with first derivatives in L De Boor and Lynch (1966). In contrast, solutions the single-task learning problem are non-unique in general and given by minimum-nont norm interpolating functions in the non- non-Hilbertian Banach space BV2 Parhi and Nowak (2021), which contains all functions with second distributional derivative in L This shows that the individual task solutions to multi-task learning problem are almost always equivalent those of a minimum norm kernel interpolation problem, whereas single-task solutions generally are not.
Insights on Multivariate Multi-Tast Problems. We provide empirical evidence and mathematical analysis which indicate that similar conclusions hold in multivariate settings. Specifically, the individual task solutions to a multi-task learning problem are approximately minimum-nore solutions in particular RKHS determined by the optimal neurons. In contrast, learning each task in isolation results in solutions that are minimum-norm with respect to a non-Hilbertian Banach norm over the optimal neurons.
2 Related Works
Characterizations of ReLU neural network solutions: Hanin (2221: Stewart al. (2023)
characterized the neural network solutions to (2) in the univariate input/output setting. Boursier and Flammarion (203) showed that in the univariate input/output case, when weight decay is modified to include the biases of each neuron, the solution is unique. Moreover, under certain assumptions, is the sparsest interpolant (i.e., the interpolant with the fewest neurons). Our work differs from these in that we study the multi-task setting, showing that univariate-input multi-task solutions are almost always unique and equivalent to the connect-the-dots solution, which is generally not the sparsest, and is a minimum- multivariate setting more challenging, there exist some results under certain dataset assumptions Ardeshir et al.] (2023); Zeno et al. (2024) or by leveraging a convex reformulation Ergen and Pilanci (2021): Mishkin and Pilanci (2023) of
solution in Sobolev RKHS. While characterizing solutions to (2) in the
Function spaces associated with neural networks: For single-output ReLU neural networks, Savarese et al. (2019); Ongie et al. (2019) related weight decay regularization on the parameters of the model to regularizing particular semi-norm the neural network function. Ongic al.) (2019) showed that this semi-norm is not an RKHS norm, highlighting a fundamental difference between learning with neural networks and kernel methods. Parhi and Nowak (2021 2022 Bartolucci ct al. (2023): | Unser (2021) studied the function spaces associated with this semi-norm, and developed representer theorems showing that optimal solutions to the minimum-non -orm data fitting problem over
'Technically, BV contains all functions with second distributional derivatives in M, the space of Radon measures with finite total variation. M can be viewed as "generalization" of L (see Ch. 7.3, p.223 in Folland 1999)).

---

these spaces are realized by finite-width ReLU networks. Consequently, finite-width ReLU networks trained with weight decay are optimal solutions to the regularized data-fitting problem posed over these spaces. Function spaces and representer theorems for multi-output and deep neural networks were later developed in Korolev (2022): Parhi and Nowak (2022) Shenouda al. (2024).
Multi-Task Learning: The advantages of multi-task learning have been extensively studied in
the machine learning literature Obozinski et al. (2006, (210); Argyriou et al. (2006) 2008); Caruana (1997). In particular. the theoretical properties of multi-task neural networks have been studied in Lindsey and Lippl (2023); [Collin et al. (2024): [hhnoouaa et al. (2024). The underlying intuition in these past works has been that learning multiple related tasks simultaneously can help select or learn the most useful features for all tasks. Our work differs from this traditional paradigm as we consider multi-task neural networks trained on very general tasks which may be diverse and unrelated.
3 Univariate Multi-Task Neural Network Solutions
For any function f that can be represented by neural network ① with width K, we define its representational cost to be
K
R() = inf
12, subject to || ll2 = 1 Vk. f =
(4)
1=1
where 0 ((0), WR, b A, c). Taking an inf over all possible neural network parameters necessary as there multiple neural networks which can represent the same function. Solutions to (3) minimize this representational cost subject to the data interpolation constraint. This section gives precise characterization of the solutions to the multi-task neural network interpolation problem in the univariate setting (d = 1).
For the training data points (.1, V1)...., (IN. yN) E R x RT, let Vı denote the ht coordinate of the label vector ys. For each 1.... T, let D, denote the univariate dataset (x1 ye...... (IN, MNee) E R x R, and let
Di+ 1,t Vie
8st
(5)
Ti+1 32
denote the slope of the straight line between (fe) and (1i+1,9t+1z) 11) The connect-the-dots interpolant of the dataset D, is the function fD, which connects the consecutive points in dataset Dr with straight lines (see Fig. 2p. Its slopes on (=00, and [IN-1, are 81+ and SN-16s respectively. In the following section, we state a simple necessary and sufficient condition under which the connect-the-dots interpolation fo = , fD.) the datasets DI..... Dr. We also demonstrate that the set of multi-task datasets which satisfy the necessary condition for non-uniqueness, viewed as a subset of R. R''x,, has Lebesgue measure zero.
is the unique optimal interpolant of
This result raises interesting new connection between data fitting with ReLU neural networks and traditional kernel-based learning methods. Indeed, connect-the-dots interpolation is also the minimum-nome interpolant over the first-order Sobolev space H' ([=1, itself RKHS whose norm penalizes the T,2 norm of the derivative of the function. In particular, fo, agrees on [N] with the function f(xx) = -Ø 0zK(I,zz) whose coefficients oj solve the kernel optimization problem
min Oge ER
Σ k,a,k(I; 23), subject to Σ a (o,k(I;, 2T) Vit, i I...., N.
(6)
with the kernel -1- +x 21)+ + (2) x²) x')+ De Boor and Lynch 1966).
Therefore, our result shows that the individual outputs of solutions to (3) for T >> tasks almost always coincide on [41, with this kernel solution; for example, this occurs with probability one if contrast, optimal solutions to the (3) in the case 7= 1 are generally non-unique and may not coincide with the connect-the-dots kernel solution Hanin (002). We note that for T 1, our result consistent with the characterization
the task labels are sampled from an absolutely continuous distribution.
of univariate solutions to in Hanin (0022).

---

Di
D2
fp.
D3
fn.
fo.
.11
222
333
24 85
46
Figure 2: The connect-the-dots interpolant fo = , fD.) three datasets D1, D2, D3-
3.1 Characterization and Uniqueness
Our main result is stated in the following theorem:
Theorem 3.1. The connect-the-dots function fD always solution (3). Moreover, the solution to
problem 3 is non-unique if and only if the following condition is satisfied: for some i = 2..... N -2
the vectors
9-+1
Y
Yi
y:-1
81-1
(7)
I1+1
24
24
H4-1
and
Vi+2
Vs+1
V-+1
8++1
8:
(8)
2++2 Ti+1
Ii+1 24
both nonzero and aligned If this condition is not satisfied, then ID is the unique solution 3 Furthermore, as long as >> and N > 1, the set of all possible data points T1....,TN E TR. and . YN E HT which admit non-unique solutions has Lebesgue measure zero (as subset of RN
x RTXNN.
Corollary 1. If are sampled from an absolutely continuous distribution with respect to the Lebesgue measure RR. x TRNN then with probability one, the connect-the-doke function is the unique solution to
and N and the data points F1y-.., EN R and label vectors
y1..... YN E R.T
Remark 1. The proof of Theorem 3.1. which relies mainly on Theorem 3.2 describe below, also characterizes solutions of the regularized loss problem
N
K
mii Σ
C(fo(z;),,) y1) + Σ 1 subject to
|wa] = k= K
k=1
for input dimension = 1, any X O, and any loss function which is lower semicontinuous in its second argument. Specifically, any fo which solves (9) is linear between consecutive data points [r,, 2;+1] unless the vectors s; $:-1 and 8;+1 8; are both nonzero and aligned, where and y, = fo(xx).
8;
9i-1 1 9,
Previous works Shenouda et al. (2024) and Lindsey and Lippl (2023) showed that multi-task learning encourages neuron sharing, where all task encouraged to utilize the same of neurons or representations. Our result above shows that univariate multi-task training is an extreme example of this phenomenon, since fo can be represented using only N neurons, all of which contribute all of the network outputs. Therefore, in the scenario we study here, neuron sharing almost always occurs even the tasks are unrelated.
The full proof of Theorem 3.1 appears in Appendix A. We outline the main ideas here. Our proof relies the fact that any R -> IR. ReLU neural network of the form (1) which solves (3) represents continuous piecewise linear (CPWL) functions, where the change in slope of the 1"ll function at
the th knot is equivalent the hh entry of the fthh output weight vector (see Appendix A. for further detail). This fact allows us to draw a one-to-one correspondence between each knot in the function and each neuron the neural network. The proof relies primarily the following lemma:
Two vectors un and u2 aligned if ui || ||ui|||ua|| uz/l-

---

Lemma 3.2. Let f: +R be a function for which each output ft is CPWL and interpolates Di- Suppose that at some ī between consecutive data points, one or more of the outputs fo has a knot. Let in and i2 be the x-coordinates of the closest knots before and after 5. respectively. Denote the slopes of St around this interval in terms of 0t by, Ct and de as in Fig. 3 and let a, b, c, 8 E RRT be the vectors containing the respective values for each task.
Then removing the knot and instead connecting I; and I++1 by a straight line does not increase R(f). Furthermore, if a - b and b are not aligned, then doing so will strictly decrease R(f).
81 1 7
b, + 6
1/2
U1
b;
Ct
at
H2
Figure 3: The function output fa around the knot at R. where r 3 3-ية Each line segment in the figure is labeled with its slope. For any particular output t, it may be the case that ft does not have a knot at (in which case 6; = 0); does not have a knot at क (in which case dr = b, + dt); and/or does not have knot at 32 (in which case by -- c.).
Proof of Theorem 3.2
The contribution of these knots to R(J) is:
||5 + b all2 +
1 - ||0||2 + ||c - b b+ 75/(1 - -2)122
2 bb a - ||0||2 + 1-7 ||0||2 + ||c bll2
1- |||||
(10)
= |b a l2 + ||c
-ll2
where the inequality follows from the triangle inequality. This shows that taking 6, = 0 for all outputs, which corresponds to connecting λι and it with a straight line in all outputs, will never increase the representational cost of f. The triangle inequality used in (IO) holds with equality for some * 0 if and only if a b, b e, and g aligned with ||01|2 min bl|2, 1-r cl|2].
states that removing neurons which are located away from the data points and replacing them with a straight line will never increase the cost of the network, and will strictly decrease the cost unless a - b and b- - c are aligned. This result implies that the connect-the tereetttteeootts interpolant fo is always solution B since we may take any solution f of (3) and remove all knots from (resulting in the function (D) without increasing its representational cost. If 8; 8i-1 and 8:+1 8; are aligned for some
Theorem 3.2
2,..., - 2, we can view any interpolant on the interval { 4141] as an instance of Fig. 3 with a 8; b 8;, and c = 8 By Theorem 3.2 any CPWL. function with a knot at some point ž E (I,, 2;-1) can have the same representational cost as the connect-the-dow solution on this interval, only if a b and b are aligned.
We can also prove by contradiction that optimal solutions are unique on [x,, x++1] as long 8; - 8;-1 and 8i+1 - are not aligned. Suppose that there is some other optimal interpolant f which is nor the connect-the-dott solution fo on an interval [z,, #++1] for which s; - s:-1 and $;+1 s; are not aligned. Then apply the lemma repeatedly to remove all knots from fe which are not located at the data points, except for a single remaining knot at some between consecutive data points. If this knot occurs after .2 or before N I, the lemma implies automatically (again taking and 1)+1) that removing this knot would strietly decrease the representational cost of the function, contradicting optimality of f. To conclude the proof, it remains only to show that any optimal
8; b 8,,

---

interpolant of the dataset must agree with the connect-the-dots interpolant fo before 22 and after N-- the details of this argument appear in m[Appendix A.I As our theorem and corollary quantify, real-world regression datasets (which are typically real-valued and often assumed to incorporate some random noise from an absolutely continuous distribution, e-g. Gaussian) are extremely unlikely to satisfy this special alignment condition; hence, our claim that connect-the-dots interpolation is almost always the unique solution to (3
Multivariate Multi-Task Neural Network Training
In in(Section 3, we proved that univariate-input functions learned by neural networks trained multiple tasks simultaneously can be profoundly different from the functions learned by networks trained on each task separately. In this section, we demonstrate extension of this phenomenon to the multivariate-inpun case. Similar to the univariate case, the multivariate single-task weight decay regularized learning problem corresponds to norm-penalized learning problem in a non-Hilbertian Banach space, where solutions may be non-unigon con-unique Parhi and Nowak (202I). Indeed, FFiuuee 4 illustrates multivariate single-task dataset with multiple min-norm interpolants. In this section, show that, as in the univariate case, multivariate multi-task learning can produce solutions that are strikingly different from the corresponding single-task learning solutions. Moreover, show that the multivariate multi-task learning problem can also be related to a norm-penalized learning problem over an RKHS. Here we analyze neural networks of the form
K
f0(x)
Σ
un (w + bx)+
(1I)
where uy Edd-1, by TR, th E ETT and 0 = {ug, wk; b= Since the analysis in this section is not dependent on the residual connection, we omit for ease of exposition. We consider the multivariate-input, T-task neural network learning problem
N
min
C fo(xs)
1
(12)
for some dataset (I1, V1), (NN, UN) Rd RT, where L is any loss function which is lower semicontinuous in its second argument and separable across the T tasks, and K 2 22 (see"l).
To characterize the nature of the functions whose parameters solve 12) note that the optimal task
output weights vi.....,, U.k for (12) also minimize
K
J(V UR.) Σ
Vio
UKa
ik
+ A
Uks A
(13)
where o/e denotes the vector of with its 4hh element uh. excluded and E -R N a matrix whose i, 1ath entry is t (xr. un bb)=- Thus, J is the objective function of (12) with all parameters except for U.s..... UKs held fixed their optimal values. Note that if vi....., k. did not minimize J, they would not be optimal for (12).
We interested in analyzing the behavior of solutions to (1)) as the number of tasks T grows. Intuitively, T is very large, it it reasonable to expect that the optimal output weight et for an individual neuron & and task would be relatively small compared to the sum of the output weights vk, for tasks of 8. In this case, the 1.th term of the regularizer (22) would be approximately equal
|1o + (vf.)²
| (oioa)
110
(14)
2|
for any individual task s, where 1107 112 == E 1 (ut (uta) 22
The approximation above comes from the
Taylor expansion fx:) Vx22 2² c+
whose higher order terms quickly become negligible if < x & c. Notice that the right hand side of (14) is a quadratic function of which suggests that the regularization term of (13) resembles a weighted e² regularizer when uks is close to its optimal value -
7

---

The above reasoning can be made precise by observing that, in multi-task task learning problems, the order in which the tasks are assigned the network outputs is irrelevant. Therefore, we can assume the tasks are assigned uniformly at random to each of the networks outputs. This random assignment process induces a distribution on the training data (labels) for each output y.1.-... V.T. Under this assumption, the following are true with high probability as T grows (see Nakhleh et al. (2024). Appendix A.2 for further detail):
.lll. which implies that the remainder in the 1. The magnitude of uis is dominated by 1 quadratic Taylor series approximation tends zero.
2. | concentrates around the norm of the full vector of output weights || 2l,, which means that the Taylor approximation tends to the same quadratic function for all tasks.
more detailed analysis is given in the companion paper Nakhleh et al. 2024 here we informally state a theorem summarizing the main conclusion.
Theorem 4.1. Nakhleh et al. (2024)
For an individual task s, consider the objective
N
(E UKe) ==
Σ
L
Yio, Σ
l1et +
(15)
2 2/ 2/1221
1=
RES
KES
Then as T grows, the global minimizer v'a....,, u'ke of H. satisfies
[J v(ke) [ui......... (kk
(16)
with probability approaching one.
The theorem states that the solution the followed weighted e regularized problem
min
YisI
Uke
L
Yks Uks
(17)
2
KES
RES
where Ykk 1/1l ll2 is an approximate minimizer of increases. In contrast, when T 1, the optimization
13 with stronger approximation as T
min PL MK
Uk M
(18)
yields output weights which exactly optimal for 12 Note that the matrices 4 in (17) and V in
(18) are not the same, since they are determined by the optimal input weights and biases for (12).
which are themselves data- and lask-dependent. Nonetheless, comparing (17) and (18) highlights the different nature of solutions learned for (12) in the single-task versus multi-task case. The multi-task learning problem favors linear combinations of the optimal neurons which have minimal weighted e² regularization penalty. In contrast, the single-task learning problem favors linear combinations of optimal neurons which have minimal él penalty. Therefore, multi-task learning with large number of tasks promotes fundamentally different linear combination of the optimal features learned in the hidden layer.
To gain further insight, note that concentration of || lla around || implies that for large T:
Yks
7kk
|
(19)
(see Lemma 4.2 in Nakhleh al. (2024)).
) This reveals novel connection between the problem of minimizing (13) and a norm-regularize data fitting problem in an RKHS. Specifically, consider the miits-nimensional linear space
H.
UR v EK
(20)
'S denotes the of optimal active neurons for
A neuron 17(x) v(w" To +)+ is active if ||e||2
0.

---

where (x) = (wf + b, equipped with the inner product
(u) = Qu
(21)
where Q = diag 21 ..... 7x) As finite-dimensional inner product space, H is necessarily Hilbert space; furthermore, finite- ditien-iiiiiiilttyy of H. implies that all linear functionals (including the point evaluation functional) on H. are continuous. Therefore, H. is an RKHS, with reproducing kernel
<(2, x')
Σ v& (x) Qx) dx(x').
(22)
Note that indeed satisfies the reproducing property, that is, (ml, a), fiH = f(x) for any f e H and any æ. To see this, write
K
Σ Ont (x
Σ u2
(23)
H
We can view the term on the left as a function Iu E H where un = Q (x))) or (xx))=1sss this is equivalent to
K
1)(, = (gu. =(=))
Σ
(K0(x)= = f(x).
(24)
Finding a minimizer of H over R.K is thus equivalent to solving
arg min JEH
((yi..((x;)) + All
(25)
We provide empirical evidence for the claims presented in this section in Figure 4 on simple multi-variate dataset. First, we demonstrate the variety of min-norm interpolates to this dataset in a single task setting. In contrast, we show that the solutions obtained via multi-task learning with additional random tasks have less variability across different trials and are often much smoother than those obtained by single-task learning supporting our claim that these solutions are well approximated by solving a kernel ridge regression problem. We also verify that the optimization (15) a good approximation for 13
5 Conclusion and Discussion
We have shown that univariate, multi-task shallow ReLU neural networks which interpolate a dataset with minimal sum of squared weights almost always represent unique function. This function performs straight-line interpolation between consecutive data points for each task. This solution is also the solution min-nome norn data-fitting problem in an RKHS. We provide mathematical analysis case, and numerical evidence suggesting that a similar conclusion may hold in the mulvariate-ing as long as the tasks are sufficiently large in number. These results indicate that multi-task training of neural networks can produce solutions that are strikingly different from those obtained by single-task training, and highlights a novel connection between these multi-task solutions and kernel methods.
Future work could aim to extend these results to deep neural network architectures. We also focus here on characterizing global solutions to the optimizations ( and 33. Whether with gradient descent-based algorithms will converge to global solutions remains an open question: low-dimensional numerical experiments in (Sections 3 and 4 indicate that they do, but a more rigorous analysis of the training dynamics would be an interesting separate line of research. Fimally, while our analysis and experiments in Secciinn indicate that variate multi-task neural network solutions behave similarly to L regression over fixed kernel, we have not precisely characterized what that kernel is in the multi-input case as we have in the single-input case: developing such characterization is of interest for future work.
networks trained

---

(a) Solution to with T = (single-task training)
(b) Solution to 12
with T = 1
(c) Solution to 12 with T = 1
(single-task task training)
(single-task training)
(d) Solution 12 with T 101 (multi-task training)
(e) Solution 25
(RKHS approximation)
Figure 4: ReLU network interpolation in two-dimensions. The solutions shown were obtained with regularization parameter À Top Row Soolutioss single-task training: Figures 4a and 4c show solutions to ReLU neural network interpolation (blue surface) of training data (red). The eight data points are located at the vertices of two squares, both centered at the origin. The outer square has side-length two and values of at the vertices. The inner square has side-length one and values of at the vertices. All three functions interpolate the data and are global minimizers of (2) and when solving for just this task (i.e., T = 1). Due to the simplicity of this dataset the solutions in the first row were confirmed by solving the equivalent convex optimization to (2) developed in Ergen and Pilanci (20TT). Bottom Row Solutions to multi-task training: F Figure 4d shows the solution to the first output of a multi-task neural network with tasks. The first output is the original task depicted in the first row while the labels for other 100 tasks are randomly generated i.i.d from a Bernoulli distribution with equal probability for one and zero. Here show representative example;
the optimality
101
examples are depicted in inpppeddix B showing that this phenomenon holds across many runs. FFguree 4e shows the solution to fitting the training data by solving (55) over fixed set of features learned by the multi-task neural network with 7 100 random tasks. We observe that unlike the highly variable solutions of single-task optimization problem, the solutions obtained by solving the multi-task optimizations are nearly identical, one would have for kernel methods. Moreover, the solution obtained by solving (25) is also similar to the solution of the full multi-task training problem with all T 101 tasks.
10

---

References
N. Ardeshir, D. Hsu, and C. H. Sanford. Intrinsic dimensionality and generalization properties of the r-norm inductive bias. In The Thirty Sixth Annual Conference on Learning Theory, pages 1264-3303. PMLR, 2023.
A. Argyriou, T. Evgeniou, and M. Pontil. Multi-task feature learning. Advances in Neural Information Processing Systems, 19, 2006.
A. Argyriou, Evgeniou, and M. Pontil. Convex multi-task feature learning. Machine Learning, 73: 272-272, 2008.
F. Bartolucci, E. De Vito, L. Rosasco, and S. Vigogna. Understanding neural networks with re- producing kernel banach spaces. Applied and Computational Harmonic Analysis, 62:194-236, 2023.
A. Beck. First-order methods in optimization. SIAM, 2017.
S. Ben-David and R. Schuller. Exploiting task relatedness for multiple task learning. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, pages 567-580. Springer, 2003.
E. Boursier and N. Flammarion. Penalising the biases in norm regularisation enforces sparsity. Advances in Neural Information Processing Systems, 36:57795-57837 2023.
N. Carlini, A. Athalye, Papernot, W. Brendel, Rauber, D. Tsipras, I. Goodfellow, A. Madry, and
A. Kurakin. On evaluating adversarial robustness. arXiv preprint arXiv: /9X.::9900006705 2019.
R. Caruana. Multitask learning. Machine Learning, 28:41-75, 1997.
L. Collins, H. Hassani, M. Soltanolkotabi, A. Mokhtari, and S. Shakkottai. Provable multi-task representation learning by two-layer relu neural networks. In International Conference on Machine Learning, 2024.
C. De Boor and R. E. Lynch. On splines and their minimum properties. Journal of Mathematics and Mechanics, 15(6):953-966) 1966.
T. Debarre, Q Denoyelle, M. Unser, and J. Fageot. Sparsest piecewise-linear regression of one- dimensional data. Journal of Computational and Applied Mathematics, 406:1 14044, 2022.
Diamond and S. Boyd. Cvxpy: A eython-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(1):2909-299 -913, 2016.
Ergen and M. Pilanci. Convex geometry and duality of over-parameterized neural networks. Journal of Machine Learning Research, 22(212):1-63, 2021.
G. B. Folland. Real analysis: modern techniques and their applications, volume 40, John Wiley & Sons, 1999.
Y. Grandvalet. Least absolute shrinkage is equivalent to quadratic penalization. In ICANN 98: Proceedings of the 8th International Conference on Artificial Neural Networks, Skövde, Sweden, 2-4 September 1998 8, pages 201-206. Springer, 1998.
Y. Grandvalet and S. Canu. Outcomes of the equivalence of adaptive ridge with least absolute shrinkage. Advances in Neural Information Processing Systems, 11. 1998.
B. Hanin. Ridgeless interpolation with shallow relu networks in 1d is nearest neighbor curvature extrapolation and provably generalizes on lipschitz functions. arXiv preprint 100.:2.099.1900, 2021.
B. Hanin. On the implicit bias of weight decay in shallow univariate relu networks. 2022.
N. Joshi, G. Vardi, and Srebro. Noisy interpolation learning with shallow univariate relu networks. In International Conference on Learning Representations, 2024.

---

Y. Korolev. Two-layer neural networks with values in Banach space. SIAM Journal on Mathematical Analysis, 54(6):6358-633 6389, 2022.
W. Lindsey and S. Lippl. Implicit regularization multi-task learning and finetuning in overpa- rameterized neural networks. arXiv preprint arXiv:23 2023.
A. Maurer, M. Pontil, and B. Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81): 2016.
A. Mishkin and M. Pilanci. Optimal sets and solution paths of relu networks. In International Conference on Machine Learning, pages 24888-24922 PMLR, 2023.
Nakhleh, Shenouda, and R. D. Nowak. The effects of multi-task learning on relu neural network functions, arXiv preprint arXiv:2410.21696, 2024.
B. Neyshabur, R. Tomioka, and N. Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. International Conference on Learning Representations (Workshop), 2015.
G. Obozinski, B. Taskar, and M. Jordan. Multi-task feature selection. Statistics Department, UC Berkeley, Tech. Rep, 2(2.2):2, 2006.
G. Obozinski, B. Taskar, and M. I. Jordan. Joint covariate selection and joint subspace selection for multiple classification problems. Statistics and Computing, 20:231-252, 2010.
G. Ongie, R. Willett, D. Soudry, and N. Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference on Learning Representations, 2019.
R. Parhi and D. Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1-40, 2021.
R. Parhi and R. D. Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. SIAM Journal on Mathematics of Data Science, 4(2):464-489, 2022.
R. Parhi and R. D. Nowak. Deep learning meets sparse regularization: A signal processing perspective. IEEE Signal Processing Magazine, 40(6):63-74, 2023.
Savarese, I. Evron, Soudry, and Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
J. Shenouda, R. Parhi, K. Lee, and R. D. Nowak. Variation spaces for multi-output neural networks: Insights on mulli--ask learning and network compression. Journal of Machine Learning Research, 25(231):1-40, 2024.
L. Stewart, F. Bach, Q. Berthet, and J.-P. Vert. Regression classification: Influence of task formulation on neural network features. In International Conference on Artificial Intelligence and Statistics, pages 11563-11582 PMLR, 2023.
M. Unser. unifying representer theorem for inverse problems and machine learning. Foundations of Computational Mathematics, 21(4):941-96) 2021.
C. Zeno, G. Ongie, Y. Blumenfeld, N. Weinberger, and D. Soudry. How do minimum-norm shallow denoisers look in function space? Advances in Neural Information Processing Systems, 36, 2024.
12

---

A Proofs of Main Results
A.1 Proof of Theorem 3.1
Proof. We break the proof into the following sections.
Unregularized Residual Connection. We first discuss the utility of the unregularized residual connection in our analysis. Consider a single-input/outpu function f represented by a ReLU network fo R + R with unit norm input weights. Suppose fo includes two neurons,
1 (x) = vi (w1# + b1)+ and 7/2 (2( b2)+
with / b2/wy such that they both activate at the same location. We have the following two cases:
1. Same Sign Weights: If (g)) = sgn(w2), (w2), the neurons activate in the same direction and can be merged into a single neuron. This would reduce the representational cost without altering the function.
2. Opposite Sign Weights: If w1 1 and W2 -1, their sum can be rewritten using
x (z)+ (-z)+;
vn (x + b1) + v2(-x bi)+ = (u) - 22) + bi)+ (vi + 02) + bi).
The term (o) + (z) + b1) can be absorbed into the residual connection, again reducing the representational cost the function.
The residual connection allows conclude that for optimal networks solving (3), two neurons activate at the same location. This provides a one-to-one correspondence between slope changes in the function and neurons in the network. The same conclusion also holds for any T output ReLU network.
Therefore, any set of T continuous piecewise linear (CPWI.) functions with K slope changes or knots, at locations f...... Rx and slope changes jkr is represented, with minimal representational cost, by network of width K, where parameters satisfy -bp/wz. Ix and pkt W/. This correspondence enables us to analyze networks which solve (3) entirely using CPWL functions, treating "knots" and "neurons" interchangeably and using Ukrl to denote both the magnitude of the slope change at a knot and the magnitude of the output weight.
Connect-the-dots interpolation is always a solution to (3) Using Theorem 3.2 we proceed to prove Theorem 3.1] The objective function in (3) is cocrcive, moreover the interpolation constraint closed set due to the fact that neural networks are continuous with respect to their parameters. Therefore solution to (3) exists (Beck) 2017 Lemma 14). Let Sž denote the set of parameters of optimal neural networks which solve for the given data points, and let
S" = (f R R RT f(() = fz( Vo E R. 0 E Sg}
(26)
be the set of functions represented by neural network with optimal parameters in Sg- First, note that the connect-the-dooe interpolant fo is in the solution set S To see this, fix any f E S*, and apply Theorem 3.2) repeatedly to remove all "extraneous" knots (i.e., knots located away from the data points Ti,... N) from f. By [heorem 3,2, the resulting function-which is simply fa-has representational cost no greater than the original f, and since f had optimal representational cost, so does fD.
Conditions for non-unique solutions. number of solutions. For some = 2,..., 2, consider the two vectors
We first prove the conditions for which (3) admits infinite
y Hi
yi
y4-1
8, 8
(27)
Ti41
24
and
8, yl+2 Vs+1
3s+1 y
8:41
(28)
T442
Fi+1 24
13

---

41
b
by
b2
b2
by
by
(a) function with knot at 5 E (2),
(b) The function fo-
Figure 5: Left: a function which has a knot in one or more of its outputs at point 5 E (i1 T2). Right: the connect-the-dots interpolant fD. The representational cost of is strictly greater than that of fD.
and assume they are aligned. Then may view the function fo around the interval [T 25411 as an instance of Theorem 3.2 with a Si-1. b = 8;, and 8,+1. Fix some point å E (x441 and denote
1i+1 2i
Let ö be any vector which is aligned with b and ب (b c) and has smaller than both, and
let f IR > R. be the function whose output slopes on (ar j:) are given by ö and whose slopes on (Ø, 2i+1) are given by b -_ 5. Then by Theorem 3.2) R R(fD) and thus f E S" Since there are infinitely many 8's which satisfy the condition above to choose the solution to is non- non-unique in this case with infinitely many optimal solutions.
Necessary and sufficient condition under which fo is the unique solution. For the other direction of the proof, suppose that for any I,...,NN 1, the vectors 8; 8:-1 1 and 8,- 8; are not aligned, and assume by contradiction that there is some f E S" which is not of the form fD. This must have any knots on (-00, x1] or [a o0), since removing such knot would strictly decrease R(f) without affecting the ability of ff to interpolate the data, contradicting optimality of f. So it must be the case that / has an extraneous knot some ã which lies between consecutive data points an; and Ti+1. Let denote the function obtained by removing all extraneous knots from f except the one located at By Theorem 3.2 R(g)= S R(f).
Now, suppose the extraneous knot is between [z r++1] for i =, ,, 2. Since has no extraneous knots away from must be the case that agrees with fo on [x;- xz. and 1, We may view the behavior of g around the interval [z, x[+1] as an instance of Theorem 3.2 with S;-1. 8; and c 8;+1- By assumption, a b and b e are not aligned, so by Theorem 3.2 removing the knot at ã would strictly reduce R(g). This contradicts optimality of g, hence of f.
Finally, consider the case where the extraneous knot is the interval [x;, Z141] where i (the case = - follows by an analogous argument). Let a denote the vector of incoming slopes of æ1 Define
y/2 y1
y2
b
D2 21
I3 .2
Since g has no extraneous knots except for Z. the slopes of g coming out it are c. By optimality of g, it must be the case that b and b are aligned (otherwise and strictly reduce the representational cost of / by removing the knot at 7, a contradiction), which implics that sgn(a, b.) sgn(b. c,) for each f = 1, I....,I T. For any outputs t which have knot
invoke|Theoren Theorem 3.2 could invoke
14

---

at ë. this quantity is nonzero, in which case |c: bul < lc: az (see Fig. 5a Let 1..... .o be the indices the outputs which have a knot at it and let to + 1, ................................ T be the indices of the outputs which do not have knot at T. We may again invoke Theorem 3.2 to remove the knots from g. resulting in new function 9 (satisfying R(g)= 2 R(ğ)) which has slopes a coming into Iι, b between 21 and 22. and e coming out of 22. The contribution of these knots to R(ğ) is then given by:
1 a1
c1
b1
1i a1
+ C1
01
+
:
Dio
Co
Uto
bto - 0to
+ Coo bio
C1 01
Cta 0ta
1 b1
Cto
bto
but the last quantity is exactly the contribution of these knots to R(fD) (see Fig. 5bj. This contradicts optimality of g. hence of y and of f. The remainder of the proof is dedicating to showing that such datasets which admit non-unique solutions are rare when the data is randomly sampled from continuous distribution.
Datasets which admit non-unique solutions have Lebesgue measure zero. I 2 or N then fo is the only solution to (3) so focus on the case where N > 4. Suppose that for some i E , NN - 2]. the data points 24-1, Ia, 1441, T242 E IR and labels y;- yt, Vi+1. Vi+2 E IR? satisfy the requirement that
yi+1 yi
V:-1
yi+2 y/-1
yo+1
(29)
I++1
24
34
I4-1
T4+2
T++1
Ii+1
x2
for some w > O, where both vectors are nonzero. After some computation, this is equivalent to the requirement that
(I:+1 2.)yi-1-1111 w(x142 2241)04 + ((1 w) F441 + wrr42) w(x++1 2:)yi42
(30)
or equivalently
Ti+1 Di
0
yi Ui, 11+11 Vi+22]
W
Pi+1
=
(31)
Fj Di+1
T1+2
YERTx
F441 33
0zER!
for some w > O. In order for this requirement to be satisfied, it must be the case that Yaı = w az for some 0, or equivalently, that the matrix U Y(a,, ag] RTx2 has rank one. Since the rank of any matrix and its Gram matrix are equivalent, this is equivalent to requiring that UUT TTT has rank one, cquivalently (because T' 1), that det(UUT) observe that, based on the definition of the determinant and of the matrix U, the function deU(U a real-valued polynomial function of the variables Y; = [y--1. 1, ys, 3i+1. M442] E 7 and Ti-1, I4+1, 2,42 4 Therefore, as the zero set of a polynomial function (i.e. an algebraic variety), the set of all Y. = [35-1: Yi Wi+1, 7542] E 7'x4 and -;- 3i, T4+1, Ti42 E g for which del del(UUT) = has Lebesgue measure zero. This is true for any = 1...., N, so taking the union over i = 1, N. we have that the set of all possible data points ; ... aN E R and label vectors y yN E RT which admit non-unique solutions has Lebesgue measure zero (as a subset of RN x _ NN
0. Now
15

---

B Additional Experimental Results and Details
B.1 Numerical Illustration Theorem 3.1
We provide numerical examples to illustrate the difference in solutions obtained from single task versus multi-task training and validate our theorem. The first row in Fig. shows three randomly initialized univariate neural networks trained interpolate the five red points with minimum sum of squared weights. While all three of the learned functions have the same representational cost (i.e., all minimize the second-order total variation subject the interpolation constraint), they each learn different interpolants. This demonstrates that gradient descent does not induce a bias towards particular solution. The second row shows the function learned for the first output of multi-task neural network. This network was trained on two tasks. The first task consists of interpolating the five points while the second consists of interpolating five randomly generated labels sampled from standard Gaussian distribution. When trained to interpolate with minimum sum of squared weights we see that the connect-the-dots solution is the only solution learned regardless of initialization, verifying Theorem 3.1 This solution simultancously minimizes the second-order total variation and (on the interval [11 TN the norm in the first-order Sobolev RKHS ([ær ZN associated with the (x
kernel k(x, 2") the interpolation constraints.
(x x1)+ )+ + (x) x²)+
De Boor and Lynch (1966), subject to
-18
-18
-14
35
35
15
-05
-24
Figure 6: Top Row: Three randomly initialized neural networks trained to interpolate the five red points with minimum sum squared weights. Bottom Row: Three randomly initialized two-output neural networks trained to interpolate a multi-task dataset with minimum sum of squared weights. The labels for the first task are the five red points shown while labels for the second were randomly randomly sampled from a standard Gaussian distribution.
B.2 Additional Experiments from Section 4
All of our experiments the models with mean squared error loss and included the representational cost Σ |/ fow/l2 regularizer with À = le - 5 for the univariate experiments and À le - 3 for the multi-variate experiments. All models were trained to convergence. The networks were initialized with 20 neurons for the univariate experiments and 800 neurons for the multi-variate experiments. For solving (25 we utilized CVXPy Diamond and Boyd (2016).
carried out in PyTorch and used the Adam optimizer. We trained
Fig. 7
below provides additional experimental results to accompany the discussion in Section 4 The results demonstrate that observations from Section 4 are true setting across multiple random initializations of the network.
'The code for reproducing all numerical experiments can be found at https://githuu com/ Doeshenouda//fffectte-ttt..
16

---

(c)
(d)
(c)
(f)
Figure 7: We present three more trials of the same experiment from Section 4 The top row corresponds to the solution of the fist output of multi-task neural network with 7 101 tasks. The first task is the original (i.e. interpolating the red points), the other 100 are randomly sampled i.i.d from a Bernoulli distribution with equal probability for one and zero. The second row corresponds to the solutions obtained by solving (25). We see again that for the T = 101 multi-task neural network the learned function is consistent across multiple random initializations. Moreover, those solutions are also similar to the ones obtained by solving (25). These results suggest that with many diverse tasks the contributions of any one task on the optimal neurons are not significant.
B.3 High Dimensional Multivariate Experiments
In this section we provide additional experiments in higher dimensional setting to demonstrate how multi-task solutions can differ drastically from single-task. For these experiments we consider student-teacher model. In particular, we generated 25 random ReLU neurons with unit norm input weights w, E 12 for = I...., 25. These served as "teacher" neurons. We then generated a multi-task dataset {æ,, y: 2 where each w; e R and sampled i.i.d from standard multi-variate Gaussian distribution. The labels yi E 22 were then generated according to the teacher ReLU neurons, that is,
ya = (w? x::)-
Therefore, each task is generated by single-index model. We then trained 25 student single-output ReLU neural networks on each tasks as well as a 25-output multi-task ReLU neural network on all the tasks. Both were trained to minimize MSE loss and were regularized weight decay parameter of 1e - 4. All networks nearly interpolated the data with MSE value less than 1e Figure 10 plots the learned single task networks evaluated along a unit norm vector E R From the plots is clear that the single task networks recover the ground truth function (i.e. a single ReLU neuron) as it looks like ReLU ridge function in every direction. Moreover, observed average sparsity of five active neurons across all the trained single-output networks.
In the Figure 9 we also plot the output of the 1th function from the leanred multi-task network evaluated at the same w. this case, the functions look very different from single-index model and do not recover the ground truth data-generating function for the respective task. Figure 8 shows
17

---

Output Weight Sparsity Pattern for Multi-Task Network
Task weights
Neuron output weights
Figure 8: Sparsity pattern for output weight matrix of the multi-task student network. The h column in the matrix corresponds to the output weight of the 1tth neuron. We observe that each neuron either contributes to all the tasks or none.
the sparsity pattern of the weights for each neuron with roughly 150 neurons contributing to all the outputs.
18

---

1111
Figure 9: Multi-task solutions along the same direction w. Here fr denotes the tth output of the
multi-task network. We observe that unlike Figure 10 the functions do not look like ReLU ridge functions and have variation in multiple directions.
19

---

Figure 10: The 25 single-task networks evaluated along the same direction in Figure 9 Here fo denotes the tt single-task network trained on task according to the data generating function above. Here expect the single-tar task nets ReLU ridge functions. We note that these observations hold across different choices the one- mie-dimnniionl subspace w.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claims are supported by the theory/analysis and numerical experiments in Sections 3 and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations and future research directions which could address these limitations in Secction
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification: The assumptions of all theorems and analysis are stated, and detailed proofs are provided either in the main body of the paper in the appendix (in which case the relevant appendix section is clearly referenced within the paper).
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The relevant details needed to reproduce our (simple) numerical experiments are provided in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
22

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: Our experiments use only synthetically-genet geaella-egereeeddd data, and the procedure by which the data is generated is described in each case, so there is no real-workd data to share. The numerical experiments are also very simple to run and we judge that providing code for them is not necessary: using the details provided in Appendix B. they should be easy to manually reproduce.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 //nips.ccppullcc// Segguddds/oooSSuubnn
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification; All relevant training details reproduce the experiments are included in either the figures where the results are presented or in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our experiments are included to visually illustrate the types of functions learned by multi-task neural networks with weight decay regularization, and as such, do not report on error or other metrics since this not what these experiments are intended to highlight.
Guidelines:
23

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: Our experiments computationally very simple execute any computer architecture and do not require GPUs, so we judge that these details are not important to include.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our paper involves no human subjects, no real-world data (hence no privacy concerns), and no other negative societal consequences that we are aware of.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?

---

Answer: [NA]
Justification: Our investigation here is primarily theoretical and, while we hope our work will contribute toward developing stronger mathematical theory of deep learning (which may contribute toward the safety and robustness guarantees of machine learning at large), we are not aware of any direct application of our results here in a way that would have substantial societal impact.
Guidelines:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The computational packages used (PyToreh and CVXPy Diamond and Boyd (016)) are both open-source, and are explicitly mentioned and credited.
25

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
26

---

Justification:
Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
27


Reviews:
[{"review_id": "gRezbjws8O", "reviewer": "Reviewer_WQUb", "summary": "Using the piece-wise linear data interpolation problem, the authors in this paper studied the solution obtained in single task learning and that in multi-task learning where interpolation functions are jointly obtained for multiple problems. Both numerical and empirical results are provided to show that muti-task learning high likely leads to unique optimal solution with different initializations, while the solution resulted from single-task learning is very sensitive to initialization. In the paper, the analysis is done first for the case where the input is univariate; and it is latter extended to the case of multivariate.", "questions": "None", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The analysis is sound\n* The conclusions are interesting, providing another prospective of seeing the advantage of multi-task learning over single task learning.", "weaknesses": "* There is a typo in Eq. (3). There is f_{\\theta}(x_i)=x_i, the latter x_i should be y_i.\n* The analysis is done based on a toy problem that is very simple, requiring technically, only two layers of neurons with relu activation in the first layer and identity activation in the second. However, networks for practical applications are much more complicated. In my own experience, very different solutions are clearly observed while training deep neural networks in multi-task learning setting with different random initializations. These observations do not align with the conclusions in this paper. I guess the underlying causes can be complicated, involving multiple factors, for example, as the authors pointed out whether global optimal solution is reached during each training may be in question. My concern is that given large gap between the toy setting in this paper and practical applications of deep neural networks, the real impact of this work or its significance is quite uncertain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and positive score. Our analysis does focus on two-layer networks, but the conclusions of the multivariate analysis can be used to reason about the behavior of functions learned at layers within a deeper network.  A ReLU layer in a deep network can be viewed as a shallow network (with inputs coming from the previous layer and outputs going into the next layer).  If the outputs of this layer are sufficiently diverse, then the behavior can be similar to the kernel-like behavior indicated by our analysis.  We have now also included new experiments in higher dimensions beyond the Fig. 5 example (see the general response above).\n\nAlso, we agree that when training neural networks in multi-task settings, the solutions will not be exactly the same across different initializations, but this is not at odds with our results. In our setting, the input weights will depend both on the training data (collectively across all tasks) and the random initializations, but whatever input weights (and hence neurons) are learned, the output weights for each task are effectively minimizing a common weighted ridge regularization objective. We will update the language of the paper to make this point more clear.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ej6TPgtAcu", "reviewer": "Reviewer_Snxf", "summary": "The authors investigate the properties of solutions to multi-task shallow ReLU neural network training problems. It reveals a novel connection between neural networks and kernel methods, particularly focusing on interpolating training data while minimizing the sum of squared weights in the network. The findings highlight that while single-task solutions are non-unique and can exhibit undesirable behaviors, multi-task training leads to unique solutions with desirable generalization properties.", "questions": "1. In Equation (3), do you mean $f_{\\theta}(x_i)=y_i$ instead of $f_{\\theta}(x_i)=x_i$?\n\n2. What happens when $x$ is different in different tasks? Do your conclusions still hold?", "limitations": "The study is limited to shallow ReLU networks. Extending these results to other activation functions and deeper network architectures remains an open question.", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors offer a robust theoretical framework, providing new insights into how multi-task training in neural networks can lead to fundamentally different solutions compared to single-task training. This framework connects multi-task neural network solutions to kernel methods. It rigorously proves that under certain conditions, the solutions are unique and analogous to those in an RKHS.", "weaknesses": "1. The theorems show the difference between the single and multi-task solutions. However, the author's argument makes it hard to determine the difference between the 1-task and 2-task solutions.\n\n2. Although [1] used the neural tangent kernel (NTK) framework, different from the idea in this paper, [1] showed that overparameterized neural networks on $\\mathbb{R}$ is linear interpolation on the single task and it seems to be a generalization solution in the author's argument. This challenges the main contribution of this paper. \n\n3. Under the RKHS framework (kernel methods), the author should quantify the generalization ability, like the generalization error bound, if they want to claim \"the unique multi-task solution has desirable generalization properties that the single-task solutions can lack\".\n\n4. For the multivariate case, the exact nature of the kernel corresponding to the neural network solutions is not fully characterized. \n\nIf the authors can solve the above problems, I will consider raising the score.\n\n[1] Generalization Ability of Wide Neural Networks on \\mathbb{R}", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback, but it seems the reviewer has a **misunderstanding** about the results of our paper. Below, we address each of the comments individually.\n1. **[1-task vs. 2-task solution]** Our result does indeed demonstrate the difference in solution between learning 1 task individually versus 2 tasks jointly. The description in Theorem 3.2 of conditions under which multi-task solutions are non-unique holds for any T > 1. \n2. **[Relation to NTK]** Our results are based on established exact characterizations of the global minimizers of training neural networks with weight decay ([2], [1], [3], [4], [5], [6]). The global minimizers are non-unique in general, and in the univariate case, it is well known that the connect-the-dots solution is just one of (potentially infinitely) many solutions. **The NTK regime is a different, approximate analytical framework that relies on a number of assumptions which we do not employ in this work**. Namely, our analysis does not require that the learning rate be extremely small (\"lazy training\") or that the network have infinite width, both of which are necessary for the NTK regime and it is now well established that such assumptions are insufficient for explaining the success of neural networks ([8],[9],[10]]). Additionally, **the paper [7] cited by the reviewer does not address connections between neural kernel regime(s) and multi-task training/\"task augmentation,\" which is one of the main novel contributions of our paper**. Finally, the conclusions about the results in [7] seem to be incorrect, as **[7] states that the solutions are *almost* linear interpolation under additional assumptions on the data**. In contrast our result states that the solutions are **exactly** connect-the-dots linear interpolation with very weak assumptions on the data which are almost always satisfied.\n3. **[Generalization]** See the general response to all reviewers above. When we referenced generalization, we specifically meant to reference the \"tempered overfitting\" result in [3], which is specific to the univariate case.\n4. **[Multi-variate case]** The kernel will depend on the specific neurons learned in training, as indicated in the paper. These will depend on the training data collectively across all tasks and the random initialization of the training process. However, the function learned for each task will be a standard kernel solution in terms of this kernel. In contrast, training separate networks for each task will, in general, produce different solutions that cannot be viewed as kernel solutions. Specifically, the solutions to single-task training with weight decay effectively minimize the $\\ell_1$ norm of the output weights, as discussed in the paper and many of the referenced prior works.\n\nRegarding Question #2, this is an interesting setting, but our main focus in this paper is the standard multi-task learning scenario, in which all tasks share the same data points x.\n\n[1] Joshi, Nirmit, Gal Vardi, and Nathan Srebro. \"Noisy interpolation learning with shallow univariate ReLU networks.\" ICLR 2024.\n\n[2] Hanin, Boris. \"On The Implicit Bias of Weight Decay in Shallow Univariate ReLU Networks.\"\n\n[3] Ongie, Greg, et al. \"A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case.\" ICLR 2020.\n\n[4] Parhi, Rahul, and Robert D. Nowak. \"What kinds of functions do deep neural networks learn? Insights from variational spline theory.\" SIAM Journal on Mathematics of Data Science 2022.\n\n[5] Savarese, Pedro, et al. \"How do infinite width bounded norm networks look in function space?.\" COLT 2019.\n\n[6] Shenouda, Joseph, et al. \"Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compression.\" JMLR 2024.\n\n[7] Lai, Jianfa, et al. \"Generalization ability of wide neural networks on $\\mathbb{R}$.\"\n\n[8] Jacot, Arthur, et al. \"Feature Learning in $ L_2 $-regularized DNNs: Attraction/Repulsion and Sparsity.\" NeurIPS 2022\n\n[9] Arora, Sanjeev, et al. \"On exact computation with an infinitely wide neural net.\" NeurIPS 2019.\n\n[10] Damian, Alex, et al. \"Neural networks can learn representations with gradient descent.\" COLT 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "STNJibIjN8", "reviewer": "Reviewer_XF9Q", "summary": "The paper shows that multi-task training can benefit the single tasks, even if the tasks are unrelated. Assuming a particular setting of training a 2-layer neural network that finds a path norm interpolation solution on univariate data, the multi-task optimizer is unique and is given by the piecewise linear function that connects the training data points which coincides the minimum norm interpolant in a first-order Sobolev RKHS, whereas the corresponding single-task optimizer is non-unique and hence not the minimum norm interpolant with respect to any RKHS.", "questions": "- Assume an optimal solution does not contain a training point x_i as a knot. How can you transform this solution to the linear spline containing only the x_i as knots. Do all optimizers already contain all x_i as knots? Can x_i be introduced without increasing the representational cost? I do not see how this case is covered in the proof and would appreciate a clarification.\n- Is there an intuitive explanation when and why the multi-task solution improves the individual tasks too? In particular, does your example with all tasks except one being pure noise tasks induce some regularizing implicit bias or does this conclusion also hold for more typical multi-task settings where there is a significant amount of signal in each task, and differing amounts of alignment between them?\n- Practical data sets are not expected to be as symmetrical as the x_i in the 2-dimensional example of Figure 5. Is the non-uniqueness of single-task solutions less severe under continuous iid sampling of the x_i?\n- The results of Boursier and Flammarion (2023) indicate that regularizing the biases can make an important difference in the optimal solutions. Could your multi-task theory be extended to this case and would the solution also be sparsified compared to the current objective without bias regularization?", "limitations": "The implications and limitations to practically optimized neural networks, multi-dimensional data and tasks with varying degrees of alignment and anti-alignment should have been assessed, at least empirically.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The fact that a multi-task learning objective can induce a kernel regime, in cases where the single-task setting is non-unique, is to the best of my knowledge novel and interesting. The solution and presentation are clear and simple and correspond to the piecewise linear function that interpolates the training data. The theoretical argument that motivates the relevance for multi-dimensional covariates is solid and empirically verified by a minimal experiment. The related work is adequately cited.", "weaknesses": "While investigating the benefits of multi-task settings has great potential, I cannot recommend the paper for acceptance. The points and questions below specify important limitations that remain to be addressed and essential aspects of multi-task training that were not explored:\n\n- Question 1 below raises a potential gap in the proof.\n- A general claim that the multi-task solution improves upon the single-task solution - an essential narrative in the paper - can clearly not be made, and depends on the exact functional dependence between covariates x and labels y. Canatar et al. (2021) is one example of how the generalization error of (other) neural kernel regimes depends on the task alignment. In the provided example in Figure 5, the ground truth function is arguably ambiguous and it might also be desirable to reflect this uncertainty by being able to learn several reasonable solutions as the single-task solution does. At least a more detailed empirical evaluation in varying input dimension, varying task signal strength and alignment could have yielded valuable insights in the regard of uniqueness and generalization in various settings. Even under negative outcome, the results would have yielded important information about the practical implications and limitations of the univariate theory.\n- The implications and limitations for practical settings are unclear due to a lack of empirical evaluations. The experiments only include one task with signal and otherwise pure noise tasks (see questions 2 and 3 below), and at most cover 2 input dimensions with constructed symmetric data points.\n\n**Typos:** in lines 26, 146, 222, before 235: be be, eq (3): f_theta(x_i)=y_i\n\n**References:**\nCanatar, A., Bordelon, B. & Pehlevan, C. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. *Nat Commun* **12**, 2914 (2021).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful review of our work and for their feedback. Below, we address each of the comments individually.\n\n1. **[Clarification on Theorem 3.1]** We thank the review for this clarifying question about Theorem 3.1. Lemma 3.2 says that, given any solution which interpolates the data, we can remove all knots located away from the data points (\"extraneous knots\") without increasing the representational cost of the network. Removing these \"extraneous knots\" may introduce new knots at the data points which were not originally present, but Lemma 3.2 says that the total cost $R(0) = \\|b-a\\|_2 + \\|c-b\\|_2$ of the new solution  with knots at the data points (see Fig. 3) is no greater than the cost $R(\\delta) = \\| \\delta + b-a \\|_2 + \\frac{1}{1-\\tau} \\| \\delta \\|_2 + \\| c-b + \\tau \\delta/(1-\\tau) \\|_2$ of the original solution, which may or may not have knots at the data points. Therefore, the question does not present a gap in the proof. Please let us know if this clarifies the concern.\n2.  **[Generalization]** See the general response to all reviewers above. When we referenced generalization, we specifically meant to reference the \"tempered overfitting\" result in [3], which is specific to the univariate case.\n3. **[Experiments]** See the general response for details on new experimental results.\n\nRegarding questions:\n\n1. We address this question in the rebuttal to weaknesses above.\n2.  In the univariate case, the intuition is that multi-output weight decay regularization encourages neuron sharing across outputs ([6]) while also encouraging the weights of each output individually to be \"small,\" i.e., encouraging each output individually to be a min-norm univariate interpolant (which are characterized in [2]). In general, the only way to accomplish this is for each output to perform connect-the-dots interpolation, with the shared knots located at the shared data points. The multivariate case is more subtle. The example in Figure 5 was constructed specifically to illustrate the existence of multiple solutions with signficantly different \"directions\" of variation. We agree that it is difficult to argue that any particular one of these solutions is better, but the more symmetric solution obtained by multi-task training does stay closer on average to the data points (we verified this computationally). We used pure noise tasks here for illustration and convenience, but similar results are obtained if the multiple tasks are randomly perturbed versions of the two-squares task. Intuitively and more generally, since the multi-task solutions are approximately equal to the kernel solution, these functions will be weighted combinations of all neurons in the model and rarely strongly aligned with a subset of the neurons.  Thus, the multi-task solutions tend to be smoother and have more symmetry.\n5. In the new experiments conducted we do not rely on any special structure for the data samples. In this case we still observe a striking difference between solutions learned by multi-task task networks vs. single task networks trained individually.\n6. This is an interesting theoretical question for future work. Our initial experiments (not shown) indicate a similar kernel-like effect when regularizing biases in multi-task settings.\n\n[2] Hanin, Boris. \"On The Implicit Bias of Weight Decay in Shallow Univariate ReLU Networks.\"\n\n[6] Shenouda, Joseph, et al. \"Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compression.\" JMLR 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nQlxif7dhp", "reviewer": "Reviewer_aewJ", "summary": "This paper analyzes the solutions to a multi-task training objective that entails finding a two-layer ReLU network that interpolates all training data and has minimum l2 norm of the first- and second-layer weights, in the overparameterized setting in which the number of neurons is larger than the total number of training examples across tasks. In the case wherein the the data dimension is one (univariate case) and under a very weak task diversity condition, the paper proves that the solution to the multi-task training objective is unique and equal to the ``connect-the-dots’’ interpolator, which aligns with the solution to a particular kernel optimization problem with a certain kernel. On the other hand, prior results, as well as empirical results presented in this paper, show that the solutions to the analogous single-task training objective are not unique and may be overly-complicated, non-robust interpolators. The paper takes an initial step towards extending the univariate multi-task learning results to the multivariate setting with preliminary analysis and experiments suggesting that the multi-task solution is unique, unlike the single-task solutions.", "questions": "N/A", "limitations": "The authors have adequately addressed limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The writing is mostly clear and easy to follow.\n- The univariate result is interesting. Such a clear separation between the behavior of single-task and multi-task learning, with only a very weak assumption on the tasks, is arguably unprecedented in the literature to my knowledge, and is an important step towards explaining why multi-tasking can lead to more robust models. I checked the proof and did not notice any mistakes. \n- The paper studies a nonlinear model, whereas most existing characterizations of solutions to multi-task objectives are limited to linear models.\n- In the multivariate case, the provided intuitions are sound, and the experiments evince the validity of the approximations in the discussion and the uniqueness of solution.", "weaknesses": "- The most interesting results are limited to the univariate case. In the multivariate case, the analysis is not rigorous. Also, the conclusion that multi-tasking behaves like a kernel method is underwhelming because this kernel is unknown and depends on $\\mathbf{v}^*$ and $\\mathbf{w}_k^*$ and $b_k^*$ for $k=2,…,K$, and characterizing these reduces to the original problem of characterizing the solution(s) of the multivariate multi-task learning problem. Along this line, while the multivariate experiments are helpful for the reasons discussed above, they don’t help to characterize the kernel, and in particular they don’t show an analogous solution to the connect-the-dots solution for the univariate case.\n- In addition to being primarily focused on the univariate case, the results are limited to the setting in which the overparameterized networks are trained to exactly fit the training data, and all tasks have exactly the same input data, neither of which may be the case in practice.\n- More discussion could be given regarding why the fact that multi-task learning behaves like a kernel method is important/interesting, and why the kernel in the univariate case is conducive to generalization.\n- The optimization algorithm used in the experiments is not discussed. If the algorithm is gradient descent on the Lagrangian, then this suggests that the multi-task augmented loss is convex, and the single-task augmented loss is non-convex, which is possibly an important point that the paper is missing. Related, for the experiments showing that single-tasking with different initializations can lead to different solutions, it would be helpful to share the final values of the training objective, to confirm that all functions are global optima.\n\nMinor\n- Nit-picking, but the use of “unlikely” to describe the alignment of $\\mathbf{s}_i - \\mathbf{s}_{i-1}$ and $\\mathbf{s}_{I+1} - \\mathbf{s}_{I}$ is not quite correct because there is no assumed generative model for the data. Under many distributions, such alignment is very likely.\n- Related: I suggest that the authors refer to the condition that $\\mathbf{s}_i - \\mathbf{s}_{i-1}$ and $\\mathbf{s}_{I+1} - \\mathbf{s}_{I}$ are not aligned as a task diversity condition. If all the tasks are the same, it fails (which is an important sanity check that should be pointed out).  However, if the tasks have only a small amount of diversity in some sense, it holds. Previous studies of multi-task learning require some level of task diversity to learn generalizable models, e.g. [1,2,3,4].\n- Again, related:  there is a large body of work studying solutions found by multi-task learning and their generalization capabilities [1,2,3,4, etc.] that the paper does not address. Like the current paper, these works also require task diversity, so they are more related than the paper’s brief discussion suggests.\n- Citations should be changed to parenthetical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful review of our work and the concerns brought up. Below, we address each of the weaknesses brought up in a point-by-point manner.\n\n1. **[Multi-variate case]** The results for the multivariate case (which also apply to the univariate setting) are more of an approximate argument.  This is partially due to the fact that far less is known about the solution sets in the multivariate case (see e.g. [3],[4], [8]) compared the the complete characterization which is known for univariate solutions ([2]). The fact that multivariate solutions can also display variety in orientation, as evidenced in the example of Figure 5, hint at the potential richness of the solution sets. Under the iid task model used in our analysis, we believe that the approximations assumed in the analysis can be made more rigorous, which is of interest for future work. We disagree that the results are underwhelming. The fact that multi-task neural network training behaves like an $\\ell^2$ minimization over linear combinations of the learned neurons, whereas single-task training is equivalent to $\\ell^1$ minimization over the neurons, implies that the nature and properties of functions the functions learned by multi-task vs. single-task training can be profoundly different. This is, in our opinion, novel and interesting.\n\n2. **[Interpolation]** We note that the more approximate argument presented in the multivariate case (which also applies to the univariate case) characterizes non-interpolation training problems which minimize a data-fitting term plus a penalized loss (for any penalty strength). Neural network interpolation problems are also a setting of practical interest, since many overparameterized networks trained in practice are able to achieve zero or near-zero training error. Moreover, standard multi-task learning scenarios generally assume that all tasks share the same set of input data points, and these tasks are learned jointly, which is exactly the setup we consider.``\n\n\n3. **[Relevance of kernel regime]** The fact that multi-task learning behaves like a kernel method is important/interesting because it shows that the solutions to each task can be profoundly different compared to those obtained by training a separate network for each, even if the tasks are statistically independent as assumed in our analysis. In other words, multi-task training can have a major effect on the learned functions for each task even in situations where one might not anticipate such an effect. This insight may be valuable in practice, since this effect of multi-task training may be desirable or undesirable depending on the application. Regarding generalization properties, see the general comment made to all reviewers above.\n\n\n4. **[Non-convex objective]** As discussed in Appendix 8, all experiments except that in the bottom right of Fig. 5 are done by training multi-output neural networks using the Adam optimizer with MSE loss and weight decay parameter 1e-5 (univariate experiments) or 1e-3 (multivariate experiments). Because the data-fitting term is non-convex and lambda is very small, the resulting problem is always non-convex. For the experiments in Fig. 4 showing that multi-task training with different random initializations leads to the same solution, it is not necessary to check the objective values since we know a priori (by our result in Theorem 3.1) that the learned functions depicted in the figures are global minimizers. However, if it is helpful to the presentation, we can include these numbers. For the multi-variate experiments in Fig. 5 the global optimality of these solutions were verified using the convex neural networks approach in Tolga & Pilanci [8].\n\nRegarding the minor weaknesses: \n\n1. We agree that the use of the word \"unlikely\" here is imprecise since no distributional assumptions are given on the data/labels. We note that Corollary 1 (Appendix 7.2) of Theorem 3.1 implies that, if the task labels are sampled i.i.d. from an absolutely continuous distribution (e.g. Gaussian) and the number of tasks T is greater than 1, then those labels admit only the connect-the-dots solution with probability one. (This follows from Corollary 1 in Appendix 7.2.)  So for example, if the labels are given by ground truth values plus some additive Gaussian noise—even a small amount of noise—the unique multi-task solution is connect-the-dots. We will mention this explicitly and update the phrasing to be more precise.\n2. Agreed.\n3. We are unsure of what the reviewer is referring to for citations [1,2,3,4] but we can include some more discussion/mention of existing multi-task learning research which focuses on the benefits of unrelated tasks, and how our work relates to these upon the reviewers clarification.\n4. Agreed.\n\n[2] Hanin, Boris. \"On The Implicit Bias of Weight Decay in Shallow Univariate ReLU Networks.\"\n\n[3] Ongie, Greg, et al. \"A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case\" ICLR 2020\n\n[4] Zeno, Chen, et al. \"How do minimum-norm shallow denoisers look in function space?.\" NeurIPS 2024.\n\n[8] Pilanci, Mert, and Tolga Ergen. \"Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks.\" ICML 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## General response to reviewers
We thank the reviewers for their helpful feedback and careful review as well as the AC. 
Most reviewers agreed that our results are novel and provide new insights on multi-task learning with neural networks. In particular,
- Reviewer XF9Q noted that our main result is "to the best of my knowledge **novel** and **interesting**"
- Reviewer aewJ highlighted that our result "is arguably **unprecedented in the literature**" and "is an important step towards explaining why multi-tasking can lead to more robust models."

Here we provide a rebuttal to some of the common concerns across reviews.
___
### Clarified Claims on Generalization
Multiple reviewers raised concerns about the statement in our abstract that "the unique multi-task solution has desirable generalization properties that the single-task solutions can lack." We will remove this sentence from the abstract, as it does not describe our paper's main contribution(s), and generalization is not our main focus. **The main focus of the paper is to demonstrate the significant difference between single-task and multi-task solutions**, even when the tasks are statistically independent, and to highlight a novel connection between multi-task neural network training and kernel methods. Our intention in mentioning the "desirable generalization properties" was specific to the univariate case, in which the connect-the-dots univariate interpolant is known to exhibit "tempered overfitting" ([1]). Informally, this means that the connect-the-dots solution generalizes reasonably well, as opposed to other minimum norm solutions that can generalize arbitrarily poorly (see [1] for technical details of this result). We will update our language to clarify that this is the "desirable generalization property" being referenced, and that this is not a contribution or focus of our paper, merely a reference to an existing result which motivates why our work is interesting.

Several reviewers also noted that there is a typo in Equation 3: the correct expression should be $f_{\theta}(x_i) = y_i$, not $f_{\theta}(x_i) = x_i$.

### New Experimental Results
___
We have now included another experiment for the multi-variate setting that is higher dimensional and does not rely on the symmetric structure of the datapoints. 

In this experiment we generate $T=25$ random teacher networks with one random ReLU neuron. We then construct a multi-task dataset by evaluating the teacher networks on the same $n=25$ random samples $x_i \in \mathbb{R}^5$ sampled i.i.d from a Gaussian distribution. Next, we train 25 single-output student networks on each task individually with $K=200$ neurons and one multi-task network on all tasks simultaneously. 

The single-output networks learn very sparse solutions consisting of only 5-10 neurons for each task. In constrast the multi-task network consists of 155 active neurons and each active neuron contributes to all of the outputs of the network.
We plot the difference in the solutions obtained from training a student network on task $t$ independently of the rest vs. the $t^{\text{th}}$ output of the multi-task network along different directions in $\mathbb{R}^{5}$. We observe that the single-output student network trained on task $t$ learned the ground truth ReLU function and is a ReLU function in all directions. In contrast, for certain directions the $t^{\text{th}}$ output of the multi-task student network is very different from the single-output student network and is clearly not a ReLU function. This again supports our claim that the functions learned for each task via a multi-task neural networks can be very different from the function learned by a neural net trained on each task individually. Please see Fig. 1,  Fig. 2 and Fig. 3 in the attached PDF for the results.


[1] Joshi, Nirmit, Gal Vardi, and Nathan Srebro. "Noisy interpolation learning with shallow univariate ReLU networks." ICLR 2024.

Meta-review: This paper examines the properties of solutions to multi-task shallow ReLU neural network training problems. This paper focuses on the fact that solutions to multi-task problems can align with those of kernel methods, uncovering a novel link between neural networks and kernel methods. In particular the paper considers the problem of interpolating training data while minimizing the sum of squared weights in the network. It is known that functions resulting from such single-task training problems solve a minimum norm interpolation problem and that these solutions are generally non-unique. However, the multiple solutions can differ significantly and may display undesirable behaviors, such as making large deviations from the training data. In contrast, the authors claim that solutions to multi-task training problems are different. In univariate settings, the authors prove that the solution to multi-task training is almost always unique, and each individual task’s solution is equivalent to minimum norm interpolation in a Sobolev space. Additionally, the authors purport to show that a unique multi-task solution exhibits favorable generalization properties that single-task solutions may lack. Finally, the authors provide empirical evidence and mathematical analysis, demonstrating that multivariate multi-task training can yield solutions related to minimum-norm interpolation in a Hilbert space.

The reviewers liked the fact that the model is nonlinear and the writing is clear. They raised various technical concerns that seems to have been addressed. One reviewer raised concerns about novelty. I disagree with this assessment and recommend acceptance.
Decision: Accept (poster)