A New Neural Kernel Regime: The Inductive Bias of Multi-Task Learning

Authors: julia  nakhleh
joseph  shenouda
robert d nowak
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 01:37:45

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 method, revealing a novel connection between neural networks and kernel methods. It is known that single-task neural network training problems are equivalent to 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 first-order Sobolev (reproducing kernel) Hilbert Space. We also demonstrate a similar phenomenon in the multivariate-input case; specifically, we show that neural network training problems with a large number of diverse tasks are approximately equivalent to an $\ell^2$ (Hilbert space) minimization problem over a fixed kernel determined by the optimal neurons.

Main paper: 
 introduction: 
 This paper investigates the nature of functions learned by training neural networks on multiple "tasks" (i.e., multiple sets of labels on the same set of data points) and contrasts these solutions with those obtained by training separate networks for each individual task. We show that the solutions of multi-task neural network learning problems can differ dramatically from the solutions to single-task problems, even if the tasks are unrelated to one another. Unlike standard intuitions Caruana (1997) and existing theory Ben-David and Schuller (2003) ; Maurer et al. (2016) regarding the effects and benefits of multi-task 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 f θ : R d → R T of the formEQUATIONwhere (•) + = max{0, •} is the ReLU activation function and w k ∈ R d , v k ∈ R T , and b k ∈ R are the input and output weights and bias of the k th neuron. K is the number of neurons and T denotes the number of tasks (outputs) of the neural network. The affine term Ax + c is the residual connection (or skip connection), where A ∈ R T ×d and c ∈ R T . The set of all parameters is denoted by θ := {v k , w k , b k } K 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 ℓ2 norm of the network weights. We consider weight decay applied only to the input and output weights of the neurons-no regularization is applied to the biases or residual connection. This is a common setting studied frequently in past work Savarese et al. (2019) ; Ongie et 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 is why it makes sense to regularize only these parameters. Given a set of training data points (x 1 , y 1 ), . . . , (x N , y N ) ∈ R d × R T and a fixed width1 K ≥ N 2 , we consider the weight decay interpolation problem:EQUATIONBy homogeneity of the ReLU activation function (meaning that (αx) + = α(x) + for any α ≥ 0), the input and output weights of any ReLU neural network can be rescaled as w k → w k /∥w k ∥ 2 and v k → v k ∥w k ∥ 2 without changing the function that the network represents. Using this fact, several previous works Grandvalet (1998) ; Grandvalet and Canu (1998) ; Neyshabur et al. (2015) ; Parhi and Nowak (2023) ; Shenouda et al. (2024) note that problem (2) is equivalent toEQUATIONin that the minimal objective values of both training problems are the same, and any network f θ which solves (2) also solves (3), while any f θ which solves (3) also solves (2) after rescaling of the input and output weights. The regularizer K k=1 ∥v k ∥ 2 is reminiscent of the multi-task lasso Obozinski et al. (2006) . It has recently been shown to promote neuron sharing in the network, meaning that only a few neurons contribute to all tasks Shenouda et al. (2024) .The optimizations in (2) and (3) are non-convex and in general, they may have multiple global minimizers. As an example, consider the single-task, univariate dataset in Figure 1 . For this dataset, (3) has infinitely many global solutions Savarese et al. (2019) ; Ergen and Pilanci (2021) ; Debarre et al. (2022) ; Hanin (2022) . Two of the global minimizers are shown in Figure 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. Moreover, recent theoretical work shows that this solution could have 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 neural network weights 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 we show in this paper, if we train a neural network to interpolate the data in Figure 1 along with additional interpolation tasks with different labels, then the solution is almost always unique and given by the (potentially preferable) interpolation depicted on the right. This demonstrates that multi-task learning can have a profound effect on the nature of neural network solutions.The main contributions of our paper are:Uniqueness of Multi-task Solutions. In the univariate setting (d = 1) we prove that the solution to multi-task training with different tasks is almost always a unique function, and we give a precise condition for the exceptional cases where solutions are non-unique. Multi-task Training ≡ Kernel Method (almost always). In the case that the solution to the univariate weight decay problem is unique, it is given by the connect-the-dots interpolant of the training 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 Parhi and Nowak (2021) .In fact, all convex combinations of the two solutions above are also global solutions to both training problems.data points: i.e., the optimal solution is a 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 solution to minimum-norm interpolation in a Sobolev reproducing kernel Hilbert space (RKHS) which contains all functions with first derivatives in L2 De Boor and Lynch (1966) . In contrast, solutions to the single-task training problem are non-unique in general and are given by minimum-norm interpolating functions in the non-Hilbertian Banach space BV 2 Parhi and Nowak (2021), which contains all functions with second distributional derivatives 2 in L 1 . This shows that the solution to each individual task in a multi-task solution is equivalent to that of a kernel method, whereas single-task solutions generally are not.Insights on Multivariate Multi-Task Problems. We provide empirical evidence and mathematical analysis which indicate that similar conclusions hold in multivariate settings. Specifically, with a large number of diverse tasks, the solutions for each individual task in multi-task learning are approximately minimum-norm solutions in a particular RKHS space 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.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 4.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 in 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 as long as it is clear that these goals are not attained by the paper. 
related works: 
 Characterizations of ReLU neural network solutions: Hanin (2021); Stewart et al. (2023) characterized the neural network solutions to (2) in the univariate input/output setting. Boursier and Flammarion (2023) 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 it is often the sparsest interpolator (in terms of the number of neurons). Our work differs from these as we study the multi-task setting, showing that the solutions are almost always unique and that they are the connect-the-dots solution, which is generally not the sparsest and corresponds to minimum norm interpolation over a particular RKHS space. While characterizing solutions to (2) in the multivariate setting is more challenging, there exist some results for very particular datasets Ergen and Pilanci (2021) ; Ardeshir et al. (2023) ; Zeno et al. (2024) .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 a particular semi-norm on the neural network function. Ongie et al. (2019) showed that this semi-norm is not an RKHS semi-norm, highlighting a fundamental difference between neural networks and kernel methods. Parhi and Nowak (2021, 2022) ; Bartolucci et al. (2023) ; Unser (2021) studied the function spaces associated with this semi-norm, and developed representer theorems showing that optimal solutions to the minimum-norm data fitting problem over 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 et al. (2024) .Multi-Task Learning: The advantages of multi-task learning has been extensively studied in the machine learning literature Obozinski et al. (2006 Obozinski et al. ( , 2010)) ; Argyriou et al. (2006 Argyriou et al. ( , 2008)) . Theoretical properties of multi-task neural networks in particular, have also been studied in Lindsey and Lippl (2023) ; Collins et al. (2024) ; Shenouda 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.k\s ∥ 2 concentrates around the norm of the full vector of output weights ∥v * k ∥ 2 , which means that the Taylor approximation tends to the same quadratic function for all tasks.A more detailed analysis is given in the companion paper Nakhleh et al. (2024) ; here we informally state a theorem summarizing the main conclusion. 2024) Suppose that y :1 , . . . , y :T are conditionally independent given x 1 , . . . , x N . For an individual task s, consider the objectiveH(v 1s , . . . , v Ks ) := N i=1 L y is , k v ks Φ ik + λ k ∥v * k\s ∥ 2 + v 2 ks 2∥v * k\s ∥ 2 (14)Then as T grows, the global minimizer v ′ 1s , . . . , v ′ Ks of H satisfiesEQUATION)with probability approaching one.The theorem shows that the solution to the weighted ℓ 2 minimization problemEQUATION)where γ ks := 1/∥v * k/s ∥ 2 is approximately optimal for the original objective ( 12), with stronger approximation as T increases. In contrast, in the single-task setting (T = 1), the optimizationEQUATION)yields output weights which are exactly optimal for (11). Note that the matrices Φ in 16 and Ψ in 17 are not the same, since they are determined by the optimal input weights and biases for (11), which are themselves data-and task-dependent. Nonetheless, comparing ( 16) and ( 17) highlights the different nature of solutions learned for (11) in the single-task versus multi-task case. The multi-task learning problem with independent tasks favors linear combinations of the optimal neurons which have a minimal weighted ℓ 2 regularization penalty. In contrast, the single-task learning problem favors linear combinations of optimal neurons which have a minimal ℓ 1 penalty. Therefore, multi-task learning with a large number of diverse tasks promotes a fundamentally different linear combination of the optimal features learned in the hidden layer.To gain further insight, note that because ∥v * k\s ∥ 2 concentrates around the norm of the full vector of output weights ∥v * k ∥ 2 as T growsEQUATION)This reveals a novel connection between the problem of minimizing ( 12) and a norm-regularized data fitting problem in an RKHS. Specifically, consider the finite-dimensional linear spaceH := f v = K k=1 v k ϕ k : v ∈ R K (19)whereEQUATION)whereQ = diag γ1 2 , . . . , γ K 2 .As a finite-dimensional inner product space, H is necessarily a Hilbert space; furthermore, finite-dimensionality of H implies that all linear functionals (including the point evaluation functional) on H are continuous. Therefore, H is an RKHS, with reproducing kernelEQUATIONwhere ϕ(x) is a vector containing the outputs of all K neurons (i.e., ϕ 1 (x), . . . , ϕ K (x)). Note that κ indeed satisfies the reproducing property: that is for anyEQUATIONThis shows that ( 16) is well approximated by solvingEQUATIONWe provide empirical evidence for the claims presented in this section in Figure 4 on a simple multi-variate dataset. First, we demonstrate the variety of solutions that interpolate this dataset in a single task setting. In contrast, we show that the solutions obtained via multi-task learning with additional random tasks are very similar and often much smoother than those obtained by single-task learning supporting our claim that these solutions are well approximated by a kernel method. We also verify that solutions to ( 23) is a good approximation for solutions which minimize (12).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 Section 5.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
univariate multi-task neural network solutions: 
 For any function f that can be represented by a neural network (1) with width K, we define its representational cost to beR(f ) := inf θ K k=1 ∥v k ∥ 2 s.t. ∥w k ∥ 2 = 1 ∀k, f = f θ (4) where θ = {v k , w k , b k } K k=1 , A, c. Taking an inf over all neural networks that realize f is necessary as there are 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 a precise characterization of the solutions to the multi-task neural network interpolation problem in the univariate setting (d = 1).For the training data points (x 1 , y 1 ), . . . , (x N , y N ) ∈ R × R T , let y it denote the t th coordinate of the label vector y i . For each t = 1, . . . , T , let D t denote the univariate dataset (x 1 , y 1t ), . . . , (x N , y N t ) ∈ R × R, and letEQUATIONdenote the slope of the straight line between (x i , y it ) and (x i+1 , y i+1,t ). The connect-the-dots interpolant of the dataset D t is the function f Dt which connects the consecutive points in dataset D t with straight lines (see Figure 2 ). Its slopes on (-∞, x 2 ] and [x N -1 , ∞) are s 1t and s N -1t , respectively.In the following section, we state a simple necessary and sufficient condition under which the connect-the-dots interpolant f D = (f D1 , . . . , f D T ) is the unique optimal interpolant of the datasets D 1 , . . . , D T . We also demonstrate that the set of multi-task datasets which satisfy the necessary condition for non-uniqueness, viewed as a subset of R N × R T ×N , has Lebesgue measure zero. This result raises an interesting new connection between data fitting with ReLU neural networks and traditional kernel-based learning methods, because connect-the-dots interpolation is also the minimum-norm solution to a data-interpolation problem in the first-order Sobolev space H 1 ([x 1 , x N ]), itself an RKHS whose norm penalizes the L 2 norm of the derivative of the function. In particular, Boor and Lynch (1966) . Therefore, our result shows that the individual outputs of solutions to (3) for T > 1 tasks almost always coincide on [x 1 , x N ] with this kernel solution; for example, this occurs with probability one if the task labels are sampled from an absolutely continuous distribution. In contrast, optimal solutions to the (3) in the case T = 1 are generally non-unique and may not coincide with the connect-the-dots kernel solution Hanin (2022) . We note that for T = 1, our result is consistent with the characterization of univariate solutions to (3) in Hanin (2022) .f Dt agrees on [x 1 , x N ] with the function f (x) = N j=1 α j k(x, x j ) whose coefficients α j solve the kernel optimization problem min α1,...,α N ∈R N i=1 N j=1 α i α j k(x i , x j ) s.t. N j=1 α j k(x i , x j ) = y it , i = 1, . . . , N, with the kernel k(x, x ′ ) = 1 -(x -x ′ ) + + (x -x 1 ) + + (x 1 -x ′ ) + DePrevious works Shenouda et al. (2024) and Lindsey and Lippl (2023) showed that multi-task training encourages neuron sharing, where all task are encouraged to utilize the same set of neurons or representations. Our result shows that univariate multi-task training is an extreme example of this phenomenon, since f D can be represented using only N -1 neurons, all of which contribute to all of the network outputs. Therefore, in the scenario we study here, neuron sharing almost always occurs even if the tasks are unrelated.Our main result is stated in the following theorem: Theorem 3.1. The connect-the-dots function f D is always a solution to (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 two vectorsEQUATIONands i+1 -s i = y i+2 -y i+1 x i+2 -x i+1 - y i+1 -y i x i+1 -x i (7)are both nonzero and aligned3 If this condition not satisfied, then f D is the unique solution to (3). Furthermore, as long as T > 1 and N > 1, the set of all possible data points x 1 , . . . , x N ∈ R and y 1 , . . . , y N ∈ R T which admit non-unique solutions has Lebesgue measure zero (as a subset ofR N × R T ×N ).Remark 1. The proof of Theorem 3.1, which relies mainly on Lemma 3.2 as we describe below, also characterizes solutions of the regularized loss problemEQUATIONfor input dimension d = 1, any λ > 0, and any loss function L which is lower semicontinuous in its second argument. Specifically, any solution f of (8) is linear between consecutive data points [x i , x i+1 ] unless the vectors ŝiŝi-1 and ŝi+1ŝi are both nonzero and aligned, where ŝi := ŷi+1-ŷi xi+1-xi and ŷi := f θ (x i ).The full proof of Theorem 3.1 appears in Appendix 6.1. We outline the main ideas here. Our proof relies on the fact that ReLU neural networks are continuous piecewise linear (CPWL) functions, where the change in slope of the function at the k th knot is equivalent to the magnitude of the k th output weight vector. This fact allows us to prove the theorem using reasoning about the knots and slope changes of CPWL functions. The main ingredient of the proof is the following lemma: Lemma 3.2. Let f : R → R T be a function whose t th output f t is a CPWL function which interpolates D t . Suppose that at some x ∈ R between consecutive data points, one or more of the outputs f t has a knot. Let x1 and x2 be the x-coordinates of the closest knots before and after x, respectively.Denote the slopes of f t around this interval in terms of a t , b t , c t , and δ t as in Figure 3 , and let a, b, c, δ ∈ R T be the vectors containing the respective values for each task.Then removing the knot at x and instead connecting x1 and x2 by a straight line does not increase R(f ). Furthermore, if ab and bc are not aligned, then doing so will strictly decrease R(f ). . Each line segment in the figure is labeled with its slope. For any particular output t, it may be the case that f t does not have a knot at x (in which case δ t = 0); does not have a knot at x1 (in which case a t = b t + δ t ); and/or does not have a knot at x2 (in which case b t -τ 1-τ δ t = c t ).Proof of Lemma 3.2. The representation cost (4) is separable across neurons. The contribution of these neurons to R(f ) is:∥δ + b -a∥ 2 + 1 1 -τ ∥δ∥ 2 + ∥c -b + τ δ/(1 -τ )∥ 2 ≥ ∥b -a∥ 2 -∥δ∥ 2 + 1 1 -τ ∥δ∥ 2 + ∥c -b∥ 2 - τ 1 -τ ∥δ∥ 2 (9) = ∥b -a∥ 2 + ∥c -b∥ 2where the inequality follows from the triangle inequality. This shows that taking δ t = 0 for all outputs, which corresponds to connecting x1 and x2 with a straight line in all outputs, will never increase the representational cost of f . The triangle inequality used in (9) holds with equality for some δ ̸ = 0 if and only if ab, bc, and δ are aligned with ∥δ∥ 2 ≤ min{∥a -b∥ 2 , 1-τ τ ∥b -c∥ 2 }.Lemma 3.2 states that removing neurons which are located away from the data points and replacing them with a straight line will never increase the representational cost of the network, and it will strictly decrease the representational cost unless ab and bc are aligned. This result implies that the connect-the-dots interpolant f D is always a solution to (3), since we may take any solution f of (3) and remove all knots from it (resulting in the function f D ) without increasing its representational cost. If s is i-1 and s i+1s i are aligned for some i = 2, . . . , N -2, we can view any interpolant on the interval [x i , x i+1 ] as an instance of Figure 3 with a = s i-1 , b = s i , and c = s i+1 . By Lemma 3.2, any neural network with a knot at some point x ∈ (x i , x i+1 ) can have the same representational cost as the connect-the-dots solution on this interval, only if ab and bc are aligned.We can also prove by contradiction that optimal solutions are unique on [x i , x i+1 ] as long as s is i-1 and s i+1s i are not aligned. Suppose that there is some other optimal interpolant f which is not the connect-the-dots solution f D on an interval [x i , x i+1 ] for which s is i-1 and s i+1s i are not aligned. Then apply the lemma repeatedly to remove all knots from f which are not located at the data points, except for a single remaining knot at some x between consecutive data points. If this knot occurs after x 2 (the second data point) or before x N -1 (second to last data point), the lemma implies automatically (again taking a = s i-1 , b = s i , and s i+1 ) that removing this knot would strictly decrease the representational cost of the function, contradicting optimality of f . To conclude the proof, it remains only to show that any optimal interpolant of the dataset must agree with the connect-the-dots interpolant f D before x 2 and after x N -1 ; the details of this argument appear in Appendix 6.1. To summarize, the connect-the-dots interpolation is the unique solution to (3) except in the special case where s is i-1 and s i+1s i are aligned for one or more i = 2, . . . , N -2. 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). We provide numerical experiments in Appendix 7.1 to illustrate the variety of solutions obtained from single-task versus multi-task learning when training with gradient descent. The single-task problem can produce a variety of solutions, in contrast the multi-task learning problem almost always produces a unique solution.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] Justification: Our experiments use only synthetically-generated data, and the procedure by which the data is generated is described in each case, so there is no real-world 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 7, they should be easy to manually reproduce. Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: Our investigation here is primarily theoretical and, while we hope our work will contribute toward developing a 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 a substantial societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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., deployment 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 not 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 as 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 or 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). 
multivariate multi-task neural network training: 
 In Section 3, we proved that the univariate functions learned by neural networks trained on multiple tasks can be profoundly different from the functions learned by networks trained for each task separately. In this section, we demonstrate similar behavior in multivariate settings. Just like in the univariate case, it is known that multivariate single-task training problems are equivalent to optimization over a non-Hilbertian Banach spaces and that the solutions may be non-unique Parhi and Nowak (2021) . Indeed, in Figure 4 we show that multivariate training problems can be non-unique in terms of their spatial orientation. The following mathematical analysis and empirical evidence shows that, similar to our results in the univariate setting, multivariate multi-task learning can produce solutions that are strikingly different compared to the corresponding single-task training solutions. Moreover, as with univariate multi-task solutions, multivariate multi-task solutions can be related to functions belonging to an RKHS.Here we analyze neural networks of the formEQUATIONwherew k ∈ S d-1 , b k ∈ R, v k ∈ R T , and θ := {v k , w k , b k } K k=1 .Since the analysis in this section is not dependent on the residual connection, we omit it for ease of exposition. We consider the multivariate-input, T -task neural network training problemmin θ N i=1 L (y i , f θ (x i )) + λ K k=1 ∥v k ∥ 2 (11)for some dataset (x 1 , y 1 ), . . . , (x N , y N ) ∈ R d × R T , where L is any convex loss function which is lower semicontinuous in its second argument and separable across the T tasks.To characterize the nature of the functions learned through multi-task training, consider the optimization from the perspective of a single task. The optimal output weights for task s are the solution toEQUATIONwhere v * k\s denotes the vector v * k with its s th element v * ks excluded andΦ ∈ R N ×K is a matrix whose i, k th entry is Φ ik = x ⊤ i w * k + b * k + .J is the objective function of ( 11) with all parameters except for v 1s , . . . , v Ks held fixed at their optimal values. Note that the optimal values v * 1s , . . . , v * Ks for (11) also minimize J; otherwise they would not be optimal for (11).We are interested in analyzing the behavior of solutions to (12) as the number of tasks T grows.Intuitively, if T is large, then the magnitude of the output weight v * ks for an individual neuron k and task s would be relatively small compared to ∥v * k\s ∥ 2 := t̸ =s (v * ks ) 2 . Then by a Taylor series approximation, the k th term of the regularizer in ( 11) would be approximately equal toEQUATION)Notice that the approximation is a quadratic function of v * ks , which suggests that the regularization term of (11) resembles a weighted ℓ 2 regularizer when v ks is close to its optimal value v * ks . The reasoning above can be made precise by assuming that that the vectors y :1 , . . . , y :T , where y :t = [y 1t , . . . , y N t ] is the vector of labels corresponding to task t, are statistically independent conditioned on the data points x 1 , . . . , x N . Intuitively, independence of the task labels means that among many has little effect on the output weights associated with other tasks. This is observed experimentally, as shown in Figure 4 . As an example of a random process generating conditionally independent task labels, consider the following: let µ be a probability measure over a family of conditional probability distributions P. Suppose that p 1 , . . . , p T are independently and identically distributed according to µ and y :t |x 1 , . . . , x N ∼ p t , where y :t := [y 1t , . . . , y N t ] is the vector of labels corresponding to tasks t = 1, . . . , T . Then y :1 , . . . , y :T are independent, conditioned on the data points x 1 , . . . , x N .When y :1 , . . . , y :T are conditionally independent given x 1 , . . . , x N , the optimal output weights for each task in (11) are identically distributed (however, due to the neuron sharing enforced by the K k=1 ∥v 2 ∥ 2 regularization term, they are not independent). Two key facts follow from this observation. As the number of tasks T grows:1. The magnitude of v * ks is dominated by ∥v * k\s ∥ 2 , which implies that the remainder in the quadratic Taylor series approximation tends to zero. 
conclusion and discussion: 
 We have shown that univariate, multi-task shallow ReLU neural networks which are trained to interpolate a dataset with minimal sum of squared weights almost always represent a unique function. This function performs straight-line interpolation between consecutive data points for each task. This solution is also the solution to a min-norm data-fitting problem in an RKHS. We provide mathematical analysis and numerical evidence suggesting that a similar conclusion may hold in the mulvariate-input case, as long as the tasks are sufficiently large in number and "diverse." 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.Here we study shallow ReLU networks due to their relative simplicity and amenability to mathematical analysis. Future work could aim to extend these results to other activation functions and deep network architectures. We also focus here on characterizing global solutions to the optimizations in ( 2 4b 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 0 at the vertices. The inner square has side-length one and values of 1 at the vertices. All three functions interpolate the data and are global minimizers of (2) and (3) when solving for just this task (i.e., T = 1). Due to the simplicity of this dataset the optimality of the solutions in the first row were confirmed by solving the equivalent convex optimization to (2) developed in Ergen and Pilanci (2021) . Bottom Row -Solutions to multi-task training: Figure 4d shows the solution to the first output of a multi-task neural network with T = 101 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 we show one representative example; more examples are depicted in Appendix 7 showing that this phenomenon holds across many runs. Figure 4e shows the solution to fitting the training data by solving (23) over a fixed set of features learned by the multi-task neural network with T = 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, as one would have for kernel methods. Moreover, the solution obtained by solving (23) is also similar to the solution of the full multi-task training problem with all T = 101 tasks.6 Appendix 6.1 Proof of Theorem 3.1Proof. We break the proof into the following sections.Unregularized residual connection. First, we will briefly discuss the utility of the unregularized residual connection in our mathematical analysis. Consider a single input/output function f that is realizable by a ReLU neural network f θ : R → R of the form (1) with unit norm input weights. Suppose that f θ contains two neuronsη 1 (x) = v 1 (w 1 x + b 1 ) + , η 2 (x) = v 2 (w 2 x + b 2 ) +which "activate" at the same location, that is, b 1 /w 1 = b 2 /w 2 . If sgn(w 1 ) = sgn(w 2 ), the neurons η 1 and η 2 activate in the same direction (i.e. both "turn on" or "turn off" at the point b 1 /w 1 = b 2 /w 2 ) and thus they can be combined into a single neuron η. The resulting network will represent the same function as f θ with a representational cost that is no greater than that of f θ . Now suppose instead that the neurons activate at the same location, i.e. b 1 /w 1 = b 2 /w 2 , but that (without loss of generality) w 1 = 1 and w 2 = -1. In this case, the sum of these two neurons η 1 and η 2 can we rewritten asEQUATIONwhich follows from the fact that for any x we havex = (x) + -(-x) + . Since the (v 1 + v 2 )(x + b 1 )term can be incorporated into the unregularized residual connection, the resulting network again represents the same function with representational cost less than or equal to that of the original network.The above reasoning shows that, when discussing optimal neural networks which solve (3), we may limit ourselves to considering neural networks for which no two neurons activate at the same location.Any such network f θ with K neurons represents T univariate continuous piecewise linear (CPWL) functions f 1 , . . . , f T with a combined total of K knots, where each knot k is located at x-coordinate b k /w k , and the change in slope of the function f t at that point is given by w k v kt (recall that w k = ±1).Conversely, any set of T CPWL R → R functions with a combined total of K knots at locations x 1 , . . . , x K ∈ R, where the slope changes of the t th function are denoted µ 1t , . . . , µ Kt (some of which may be zero), is represented by a R → R T network of width K whose parameters satisfy b k /w k = x k and µ kt = w k v kt (hence |µ kt | = |v kt |) for each k = 1, . . . , K and each t = 1, . . . , T . This identification allows us to prove the theorem statement entirely using reasoning about CPWL functions: in the remainder of the proof, we use the terms "knot" and "neuron" interchangeably, and we use |v kt | to denote both the absolute slope change of output f t at knot k and, equivalently, the t th entry of the output weight vector v k .Connect-the-dots interpolation is always a solution to (3). Using Lemma 3.2, we proceed to prove Theorem 3.1. Let S * θ denote the set of parameters of optimal neural networks which solve (3) for the given data points, and letS * := {f : R → R T | f (x) = f θ (x) ∀x ∈ R, θ ∈ S * θ } (25)be the set of functions represented by neural network with optimal parameters in S * θ . First, note that the connect-the-dots interpolant f D is in the solution set S * . To see this, fix any f ∈ S * , and apply Lemma 3.2 repeatedly to remove all "extraneous" knots (i.e., knots located away from the data points x 1 , . . . , x N ) from f . By Lemma 3.2, the resulting function-which is simply f D -has representational cost no greater than the original f , and since f had optimal representational cost, so does f D .Conditions for non-unique solutions. We first prove the conditions for which (3) admits an infinite number of solutions. For some i = 2, . . . , N -2, consider the two vectorsEQUATIONand EQUATIONτ = x -x i x i+1 -x i .Let δ be any vector which is aligned with ab and 1-τ τ (bc) and has smaller norm than both, and let f : R → R T be the function whose output slopes on (x i , x) are given by δ and whose slopes on (x, x i+1 ) are given by b -τ 1-τ δ. Then by Lemma 3.2, R(f ) = R(f D ) and thus f ∈ S * . Since there are infinitely many δ's which satisfy the condition above to choose the solution to (3) is non-unique in this case with infinitely many optimal solutions. Necessary and sufficient condition under which f D is the unique solution. For the other direction of the proof, suppose that for any i = 1, . . . , N -1, the vectors s is i-1 and s i+1s i are not aligned, and assume by contradiction that there is some f ∈ S * which is not of the form f D . This f must not have any knots on (-∞, x 1 ] or [x N , ∞), since removing such a knot would strictly decrease R(f ) without affecting the ability of f to interpolate the data, contradicting optimality of f . So it must be the case that f has an extraneous knot at some x which lies between consecutive data points x i and x i+1 . Let g denote the function obtained by removing all extraneous knots from f except the one located at x. By Lemma 3.2, R(g) ≤ R(f ). Now, suppose the extraneous knot is between [x i , x i+1 ] for i = 2, . . . , N -2. Since g has no extraneous knots away from x, it must be the case that g agrees with f D on [x i-1 , x i ] and [x i+1 , x i+2 ]. We may view the behavior of g around the interval [x i , x i+1 ] as an instance of Lemma 3.2 with a = s i-1 , b = s i , and c = s i+1 . By assumption, ab and bc are not aligned, so by Lemma 3.2, removing the knot at x would strictly reduce R(g). This contradicts optimality of g, hence of f . Finally, consider the case where the extraneous knot is on the interval [x i , x i+1 ] where i = 1 (the case i = N -1 follows by an analogous argument). Let a denote the vector of incoming slopes of g atx 1 . Define b = y 2 -y 1 x 2 -x 1 c = y 3 -y 2 x 3 -x 2 .Since g has no extraneous knots except for x, the slopes of g coming out of x 2 are c. By optimality of g, it must be the case that ab and bc are aligned (otherwise we could invoke Lemma 3.2 and strictly reduce the representational cost of f by removing the knot at x, a contradiction), which implies that sgn(a tb t ) = sgn(b tc t ) for each t = 1, . . . , T . For any outputs t which have a knot at x, this quantity is nonzero, in which case |c tb t | < |c ta t | (see Figure 5a ). Let 1, . . . , t 0 be the indices of the outputs which have a knot at x, and let t 0 + 1, . . . , T be the indices of the outputs which do not have a knot at x. We may again invoke Lemma 3.2 to remove the knots from g, resulting in a new function g (satisfying R(g) ≥ R(g)) which has slopes a coming into x 1 , b between x 1 and x 2 , and c coming out of x 2 . The contribution of these knots to R(g) is then given by:   b 1 -a 1 . . . b t0 -a t0    2 +    c 1 -b 1 . . . c t0 -b t0    2 ≥    b 1 -a 1 + c 1 -b 1 . . . b t0 -a t0 + c t0 -b t0    2 =    c 1 -a 1 . . . c t0 -a t0    2 >    c 1 -b 1 . . . c t0 -b t0    2but the last quantity is exactly the contribution of these knots to R(f D ) (see Figure 5b ). This contradicts optimality of g, hence of g 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 a continuous distribution.Datasets which admit non-unique solutions have Lebesgue measure zero. If N = 2 or N = 3, then f D is the only solution to (3), so we focus on the case where N ≥ 4. Suppose that for some i ∈ {2, . . . , N -2}, the data points x i-1 , x i , x i+1 , x i+2 ∈ R and labels y i-1 , y i , y i+1 , y i+2 ∈ R T satisfy the requirement thatEQUATIONfor some w > 0, where both vectors are nonzero. After some computation, this is equivalent to the requirement that(x i+1 -x i )y i-1 -w(x i+2 -x i+1 )y i + (1 -w)x i -x i+1 + wx i+2 y i+1 -w(x i+1 -x i )y i+2 = 0 (29)or equivalently[y i-1 , y i , y i+1 , y i+2 ] Yi∈R T ×4    x i+1 -x i 0 x i -x i+1 0    a1∈R 4 -w    0 x i+2 -x i+1 -x i+2 x i+1 -x i    a2∈R 4 = 0 (30)for some w > 0. In order for this requirement to be satisfied, it must be the case that Y a 1 = wY a 2 for some w > 0, or equivalently, that the matrix U = Y [a 1 , a 2 ] ∈ R T ×2 has rank one. Since the rank of any matrix and its Gram matrix are equivalent, this is equivalent to requiring that U U ⊤ ∈ R T ×T has rank one, or equivalently (because T > 1), that det(U U ⊤ ) = 0. Now observe that, based on the definition of the determinant and of the matrix U , the function det(U U ⊤ ) is a real-valued polynomial function of the variablesY i = [y i-1 , y i , y i+1 , y i+2 ] ∈ R T ×4 and x i-1 , x i , x i+1 , x i+2 ∈ R 4 .Therefore, as the zero set of a polynomial function (i.e. an algebraic variety), the set of all Y i = [y i-1 , y i , y i+1 , y i+2 ] ∈ R T ×4 and x i-1 , x i , x i+1 , x i+2 ∈ R 4 for which det(U U ⊤ ) = 0 has Lebesgue measure zero. This is true for any i = 1, . . . , N , so taking the union over i = 1, . . . , N , we have that the set of all possible data points x 1 , . . . , x N ∈ R and label vectors y 1 , . . . , y N ∈ R T which admit non-unique solutions has Lebesgue measure zero (as a subset of R N × R T ×N ). 
additional experimental results and details: 
 7.1 Numerical Illustration of Theorem 3.1We 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 Figure 6 shows three randomly initialized univariate neural networks trained to interpolate the five red points with minimum representational cost. While all three of the learned functions have the same representational cost (i.e., all minimize the second-order total variation subject to the interpolation constraint), they each learn different interpolants. This demonstrates that gradient descent does not induce a bias towards a particular solution. The second row shows the function learned for the first output of a multi-task neural network. This network was trained on two tasks. The first task consists of interpolating the five red points while the second consists of interpolating five randomly generated labels sampled from a standard Gaussian distribution. When trained to minimum representation cost we see that the connect-the-dots solution is the only solution learned regardless of initialization, verifying Theorem 3.1. This solution simultaneously minimizes the second-order total variation and the norm in the RKHS associated with the kernel k Boor and Lynch (1966) , subject to the interpolation constraints. Three randomly initialized neural networks trained to interpolate the five red points with minimum path-norm. Bottom Row: Three randomly initialized two-output neural networks trained to interpolate a multi-task dataset with minimum path-norm. The labels for the first task are the five red points shown while the labels for the second were randomly randomly sampled from a standard Gaussian distribution.(x, x ′ ) = 1 -(x -x ′ ) + + (x -x 1 ) + + (x 1 -x ′ ) + DeAll of our experiments were carried out in PyTorch and used the Adam optimizer. We trained the models with mean squared error loss and included the representational cost K k=1 ∥v k ∥ 2 as a regularizer with λ = 1e -5 for the univariate experiments and λ = 1e -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 (23) we utilized CVXPy Diamond and Boyd (2016) .Figure 7 below provides additional experimental results to accompany the discussion in Section 4. The results demonstrate that our observations from Section 4 are true setting across multiple random initializations of the network.In this section we provide additional experiments in a higher dimensional setting to demonstrate how multi-task solutions can differ drastically from single-task. For these experiments we consider a student-teacher model. In particular, we generated 25 random ReLU neurons with unit norm 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 (23). These results suggest that with many diverse tasks the contributions of any one task on the optimal neurons are not significant.input weights w t ∈ R 5 for t = 1, . . . , 25. These served as "teacher" neurons. We then generated a multi-task dataset {x i , y i } 20 i=1 where each x i ∈ R 5 and sampled i.i.d from a standard multi-variate Gaussian distribution. The labels y i ∈ R 25 were then generated according to the teacher ReLU neurons, that is,y it = (w T t x i ) + .Therefore, each task is generated by a 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 a weight decay parameter of λ = 1e -4. All networks nearly interpolated the data with MSE value less than 1e -4. Figure 10 plots the learned single task networks evaluated along a a unit norm vector w ∈ R 5 . From the plots it is clear that the single task networks recover the ground truth function (i.e. a single ReLU neuron) as it looks like a ReLU ridge function in every direction. Moreover, we observed a an average sparsity of five active neurons across all the trained single-output networks.In the Figure 9 we also plot the output of the t th function from the leanred multi-task network evaluated at the same w. In this case, the functions look very different from a single-index model and do not recover the ground truth data-generating function for the respective task. Figure 8 shows the sparsity pattern of the weights for each neuron with roughly 150 neurons contributing to all the outputs. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a 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 no such risks.• Released models that have a 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: The computational packages used (PyTorch and CVXPy Diamond and Boyd (2016) ) are both open-source, and are explicitly mentioned and credited.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 a 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 are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 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 was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Output Weight Sparsity Pattern for Multi-Task Network Here as we expect the single-task nets are ReLU ridge functions. We note that these observations hold across different choices of the one-dimensional subspace w.NeurIPS Paper ChecklistBy an argument similar to the proof of Theorem 5 ofShenouda et al. (2024), the optimal objective value of (3) (hence of (2)) for a given dataset is the same for any K ≥ N.Technically, BV 2 contains all functions with second distributional derivatives in M, the space of Radon measures with finite total variation. M can be viewed as a "generalization" of L 1 (seeCh. 7.3, p.223 in Folland (1999)).Two vectors u1 and u2 are aligned if u ⊤ 1 u2 = ∥u1∥∥u2∥. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * There is a typo in Eq. (3). There is f_{\theta}(x_i)=x_i, the latter x_i should be y_i.
* 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.
questions: questions: None
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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. 

3. 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".

4. For the multivariate case, the exact nature of the kernel corresponding to the neural network solutions is not fully characterized. 

If the authors can solve the above problems, I will consider raising the score.

[1] Generalization Ability of Wide Neural Networks on \mathbb{R}
questions: questions: 1. In Equation (3), do you mean $f_{\theta}(x_i)=y_i$ instead of $f_{\theta}(x_i)=x_i$?

2. What happens when $x$ is different in different tasks? Do your conclusions still hold?
limitations: limitations: The study is limited to shallow ReLU networks. Extending these results to other activation functions and deeper network architectures remains an open question.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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:

- Question 1 below raises a potential gap in the proof.
- 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.
- 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.

**Typos:** in lines 26, 146, 222, before 235: be be, eq (3): f_theta(x_i)=y_i

**References:**
Canatar, 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).
questions: 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.
- 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?
- 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?
- 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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.
- 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.

Minor
- 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.
- 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].
- 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.
- Citations should be changed to parenthetical.
questions: questions: N/A
limitations: limitations: The authors have adequately addressed limitations.

Comments: title: Request for follow-up from reviewer Snxf
references (Follow-up to reviewer XF9Q)
Follow-up to reviewer XF9Q
Follow-up to reviewer Snxf
Thank you for your responds
comment: As the discussion period is coming to a close, we ask that the reviewer please let us know if we have clarified their concerns, and to update their score accordingly.
I thank the authors for these clarifications. After also reading the discussions with other reviewers, several of my concerns have been alleviated, in particular with the proof. I have slightly adjusted my score accordingly. I encourage the authors to further investigate how truly high dimension and task interaction affect the multi-task solution.
[1] Ongie, Greg, et al. "A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case" ICLR 2020

[2] Zeno, Chen, et al. "How do minimum-norm shallow denoisers look in function space?." NeurIPS 2024.

[3] Pilanci, Mert, and Tolga Ergen. "Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks." ICML 2020.

[4] Hanin, Boris. "On The Implicit Bias of Weight Decay in Shallow Univariate ReLU Networks."
We thank the reviewer for engaging in the rebuttal. We want to further clarify that we are only considering interpolating solutions for the univariate setting. Therefore, we only consider solutions which pass through the data points exactly: it is never necessary to introduce additional knots in order to have the function interpolate the data points. However, if we consider an interpolating solution which has some "extraneous knots" (knots which are not located at the data points) and we remove these, additional knots may appear at the data points. Lemma 3.2 says that doing this will never increase the representational cost, and almost always decrease it, even if doing so results in new knots appearing at the data points. While we believe that this is clear in the current statement of the lemma, we are happy to update our language to make this more explicit.

Regarding the new experiments, we would like to clear up some possible misunderstandings about our setup and claims.
 
> In the added experiments, it is not surprising that the single-task and multi-task solutions differ; 
 
We disagree with this claim. In our experiment each task is entirely independent of the rest so there is no reason to assume that the network would exploit some shared representation. The network could have learned the ground truth input weight for each task (a single neuron) and then learned a diagonal output weight matrix for the output weight of each of those teacher tasks. Due to the unrelatedness of the different tasks this would seem like a reasonable solution however it is not the solution ultimately learned.
 
> the question is how. 
 
For the univariate case **we precisely describe how the solutions are different**. Training a single task network can lead to many solutions that interpolate with minimum representation cost. However, doing multitask training almost always leads to the unique “connect-the-dots” interpolant for each task. Moreover, this interpolant is also the solution to minimum norm data interpolation in a particular RKHS for each task individually and we explicitly provide the kernel associated with this RKHS.
 
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. [1],[2], [3]) compared to the complete characterization which is known for univariate solutions ([4]). However, **our analysis and experiments do provide insights into the difference between single-task and multi-task solutions**. Multi-task neural networks learn solutions that behave like an $\ell_2$ 
 minimization over linear combinations of the learned neurons, whereas single-task neural networks learn solutions that  behave as an $\ell_1$ 
minimization over linear combinations the learned neurons. This is, in our opinion, novel and interesting and as pointed out by reiviewer `aewJ` is **arguably unprecedented in the literature.**
 
>  but I would like to see the correspondence to Figure 1 in the attached pdf of single task NNs to have a comparison

As mentioned in the experimental details in the general response, for the single task networks there are only 5-10 active neurons at the end of training.
 
> Also, in Figure 2, it now seems that the single-task solutions are the piecewise linear interpolants and without variation across random seeds, which questions the generalization of the original interpretation in the paper.
 
In this case the ground truth tasks are single ReLU neurons and thus we do not expect non-uniqueness in the solutions here (the function which represents a single ReLU neuron with minimum representation cost is simply a ReLU neuron). The purpose of this experiment was to emphasize the difference between single-task solutions and multi-task solutions in a more extreme setting and in higher dimensions.
 
> In this example, the multi-task solution does not seem to be desirable but instead further away from the piecewise linear interpolant of the data than the single task solution.
 
Our paper does not claim that multi-task solutions are **always** desirable. The main message is that they are different. We have clarified our use of the phrase “generalizes better” in the general response. 
 
> It also remains unclear how task alignment or high dimensionality impacts the conclusions drawn in the paper.
 
The new experiments are in higher dimensions ($\mathbb{R}^5$). We agree that exploring how task alignment affects these solutions would be interesting, but our main message is that multi-task training in ReLU neural networks can be vastly different than single-task training **even with very little assumptions on the tasks**.
I appreciate the authors to respond to my comments. After reading through review comments from other reviewers and authors' response, I would like to keep my initial assessment of this paper.
Thank you for clarifying my confusion with the proof. I am still unable to find a statement anywhere in the proof that discusses introducing knots and why this does not increase the representational cost. I encourage the authors to clarify that in the proof.

In the added experiments, it is not surprising that the single-task and multi-task solutions differ; the question is how. The fact that more neurons are active and they are shared across tasks is an interesting mechanistic understanding in this regard, but I would like to see the correspondence to Figure 1 in the attached pdf of single task NNs to have a comparison. Also, in Figure 2, it now seems that the single-task solutions are the piecewise linear interpolants and without variation across random seeds, which questions the generalization of the original interpretation in the paper. In this example, the multi-task solution does not seem to be desirable but instead further away from the piecewise linear interpolant of the data than the single task solution. It also remains unclear how task alignment or high dimensionality impacts the conclusions drawn in the paper.

Overall, I will keep my score.
We appreciate your response and thank you for increasing the score! 
Indeed, the works mentioned are very relevant and we will be sure to reference them in the camera-ready version of the paper.
I thank the authors for their thorough response, which has helped to alleviate my concerns, and I have increased my score as a result. I apologize for forgetting to include the citations, which are as follows:

[1] Tripuraneni et al., On the theory of transfer learning: The importance of task diversity, NeurIPS 2020. 

[2] Du et al., Few-shot learning via learning the representation, provably, ICLR 2020. 

[3] Sun et al., Towards sample-efficient overparameterized meta-learning, NeurIPS 2021.

[4] Collins et al., Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks, ICML 2024
We thank the reviewer for following up on this! Apologies, we meant to refer to Theorem 3.1 (there is no Theorem 3.2). The statement of **Theorem 3.1** precisely describes the conditions on the data and labels under which the unique solution for each task is connect-the-dots for any number of tasks $T > 1$, including $T=2$. For any dataset with two tasks, the solution is non-unique if and only if the conditions of Theorem 3.1 are satisfied, **otherwise the solution is unique and it is the connect-the-dots solution for both tasks (i.e. the solution is of the form of the right plot on Fig. 1 or the bottom row of Fig. 4)**. This is the difference in the nature of the solution between single task and multi-task learning.

As a simple example, consider the data points {0, 1, 2, 3} and first task labels {0, 1, 1, 0}. A neural network trained on this task alone can interpolate the data either by a "peak" or a "plateau" (connect-the-dots) function with the same representational cost (similar to the example in Fig. 1). However, if we do multi-task learning with a second task with labels {0, 1, 0, 1}, then by Theorem 3.1 the neural network learns a unique solution which will be the connect-the-dots interpolant for both tasks, eliminating the possible "peak" solution for task 1 when learned by itself.

It is possible to construct example sets of data and labels which admit multiple solutions by Theorem 3.1, but if we assume the task labels are real valued (as we do throughout the paper), i.e. a standard regression setting, the set of all such label sets has Lebesgue measure zero (see proof of Corollary 1 in Appendix 6.2). In other words, for real-valued labels, labels which admit non-unique solutions are exceedingly rare. A direct corollary of this fact is that, as long as the labels are sampled i.i.d. from a distribution which is absolutely continuous with respect to the Lebesgue measure on $\mathbb{R}^T$, the multi-task solution is connect-the-dots with probability 1. If the labels are binary-valued, then non-uniquess of solutions may not be as rare as in the real-valued case. For example, consider the two task setting above with task labels {0,1,1,0} and {1,0,0,1}. In this case, there can be multiple solutions to the multi-task training problem. However, our focus in this paper is on the regression setting, and in either case, Theorem 3.1 precisely describes the conditions under which solutions are and are not unique. **Please let us know if this explanation of the difference between one-task and two-tasks solution is still unclear.**

Regarding the question about generalization: [7] shows that, for uniformly-spaced data points the generalization error of ("almost") connect-the-dots interpolation is *lower-bounded* by a constant with probability 1 as the number of samples $N$ grows large. In contrast, [1] (the paper we reference when referring to "desirable generalization properties" of connect-the-dots interpolation) shows that, for data points sampled from an absolutely continuous distribution, the generalization error of (exact) connect-the-dots interpolation is *upper-bounded* by a constant with probability 1 as $N$ grows large. Setting aside the different assumptions employed in both works, these two statements are not incompatible with each other. By the taxonomy in [9], the result in [1] shows that the connect-the-dots solution exhibits "tempered overfitting" which is worse than "benign overfitting" but not as terrible as "catastrophic overfitting".  We note however that **the main focus of the paper is to demonstrate the significant difference between single-task and multi-task solutions** and we will adjust our language about generalization benefits in the camera-ready version as described in the General Response.

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

[9] Mallinar, Neil, et al. "Benign, tempered, or catastrophic: Toward a refined taxonomy of overfitting." NeurIPS 2022.
1. Are you referring to 'Lemma 3.2'? While you've illustrated the difference, the explanation lacks a clear description of the nature of this difference. For instance, what distinguishes a single-task classification problem where \( y_i \in \{0,1\} \) from a 'two-task' classification problem where $ y_i = (y_{i,1}, y_{i,2}) $ and $ y_{i,1} = 1$ if $y_{i,2} = 0 $? Alternatively, consider a scenario where a second task is created with random labels. What would be the implications for the original task?

2 & 3. I referenced [7] because it demonstrates that linear interpolation does not generalize well when the data contains noise. Are you suggesting that linear interpolation can indeed generalize under such conditions?