Sampling weights of deep neural networks
Authors: Erik Lien Bolager
Iryna Burak
Chinmay Datar
Qing Sun
Felix Dietrich
Venue: NeurIPS 2023 poster (2023)
Keywords: random sampling
neural network parameters
iterative optimization
TL;DR: We introduce a sampling algorithm for weights and biases of fully-connected neural networks that can replace iterative optimization.

Abstract: We introduce a probability distribution, combined with an efficient sampling algorithm, for weights and biases of fully-connected neural networks. In a supervised learning context, no iterative optimization or gradient computations of internal network parameters are needed to obtain a trained network. The sampling is based on the idea of random feature models. However, instead of a data-agnostic distribution, e.g., a normal distribution, we use both the input and the output training data to sample shallow and deep networks. We prove that sampled networks are universal approximators. For Barron functions, we show that the $L^2$-approximation error of sampled shallow networks decreases with the square root of the number of neurons. Our sampling scheme is invariant to rigid body transformations and scaling of the input data, which implies many popular pre-processing techniques are not required. In numerical experiments, we demonstrate that sampled networks achieve accuracy comparable to iteratively trained ones, but can be constructed orders of magnitude faster. Our test cases involve a classification benchmark from OpenML, sampling of neural operators to represent maps in function spaces, and transfer learning using well-known architectures.

Sampling weights of deep neural networks
Erik Lien Bolager*
Iryna Burak
Chinmay Datar*1
Qing Sun
Felix Dietrich** **
Technical University of Munich
+ School of Computation, Information and Technology: IIstittte for Advanced Study
Abstract
We introduce probability distribution, combined with an efficient sampling algo- rithm, for weights and biases of fully-connected neural networks. In supervised learning context, no iterative optimization or gradient computations of internal network parameters are needed to obtain a trained network. The sampling is based on the idea random feature models. However, instead of a data-agnostic distri- bution, e.g., normal distribution, data to sample shallow and deep networks. We prove that sampled networks are universal approximators. For Barron functions, we show that the Lpppppoxinnttion error of sampled shallow networks decreases with the square root of the number of neurons. Our sampling scheme is invariant to rigid body transformations and scaling of the input data, which implies many popular pre-processing techniques demonstrate that sampled networks
both the input and the output training
not required. In numerical experiments, achieve accuracy comparable to iteratively trained ones, but can be constructed orders of magnitude faster. Our test cases involve classification benchmark from OpenML, sampling of neural operators to represent maps in function spaces, and transfer learning using
architectures.
Introduction
Training deep neural networks involves finding all weights and biases. Typically, iterative, gradient- based methods are employed to solve this high- nigh-dimensional optimization problem. Randomly sampling all weights and biases before the last, linear layer circumvents this optimization and results in much shorter training time. However, the drawback of this approach is that the probability distribution of the parameters must be chosen. Random projection networks [54] or extreme learning machines 30 involve weight distributions that are completely problem- and data-agnostic, e.g., normal distribution. In this work, we introduce a data-driven sampling scheme to construct weights and biases close gradients of the target function (cf. Figure D.. This idea provides solution to three main challenges that have prevented randomly sampled networks to compete successfully against iterative training in the setting of supervised learning: deep networks, accuracy, and interpretability.
Random features
Sampling
data-and -agnosigisiic
data-driven
function
function
data
data
random choice of weights
sampling at large gradients
Figure I: Random feature models choose weights in a data-agnostic way, compared to sampling them where it matters: at large gradients. The arrows illustrate where the network weights are placed.
*Corresponding author, felix. dietrich@tum.ccm de.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Deep neural networks. Random feature models and extreme learning machines are typically defined for networks with single hidden layer. Our sampling scheme accounts for the nigh-dimensional ambient space that is introduced after this layer, and thus deep networks can be constructed efficiently,
Approximation accuracy. Gradient-based, iterative approximation find accurate solutions with relatively small number of neurons. Randomly sampling weights using a data-agnostic distribution often requires thousands of neurons compete. Our sampling scheme takes into account the given training data points and function values, leading to accurate and width-efficient approximations. The distribution also leads to invariance to orthogonal transformations and scaling of the input data, which makes many common pre-processing techniques redundant.
Interpretability. Sampling weights and biases completely randomly, i..., without taking into account the given data, leads to networks that do not incorporate any information about the given problem. We analyze and extend recently introduced weight construction technique [27] that uses the direction between pairs of data points to construct individual weights and biases. In addition, we propose a sampling distribution over these data pairs that leads to efficient use of weights; cf. Figure I
2 Related work
Regarding random Fourier features, Li et al. [41] and Liu et al. 43 review and unify theory and algorithms of this approach. Random features have been used to approximate input-output maps in Banach spaces [50) and solve partial differential equations [16 48 10] Gallicchio and Scardapane
(28) provide a review of deep random feature models, and discuss autoencoders and reservoir computing (resp. echo-state networks (34). The latter are randomly sampled, recurrent networks to model dynamical systems [6]. Regarding construction of features, Monte Carlo approximation of data-dependent parameter distributions used towards faster kernel approximation M 55 47. Our
work differs in that we do not start with kernel and decompose it into random features, but we start with a practical and interpretable construction of random features and then discuss their approximation properties. This may also help to construct activation functions similar to collocation [62]. Fiedler et al. (23 and Fornasier et al. [24] prove that for given, comparatively small networks with one hidden layer, all weights and biases can be recovered exactly by evaluating the network at specific points in the input space. The work of Spek et al. 60) showed a certain duality between weight spaces and data spaces, albeit in purely theoretical setting. Recent work from Bollt 77] analyzes individual weights in networks by visualizing the placement of ReLU activation functions in space. Regarding approximation errors and convergence rates of networks, Barron spaces are very useful 2 20]. also to study regularization techniques, esp. Tikohnov and Total Variation [40]. A lot of work (54 19 17 57 65) surrounds the approximation rate of Om -1/2) for neural networks with one hidden layer of width m, originally proved by Barron [2]. The rate, but not the constant, independent of the input space dimension. This implies that neural networks can mitigate the curse of dimensionality, as opposed to many approximation methods with fixed, non non-trained basis functions [4], including random feature models with data-agnostic probability distributions. The convergence rates of pece-paramterrieed networks with one hidden layer is considered in [19] with comparison to the Monte Carlo approximation. In our work, we prove the same convergence rate for networks. Regarding deep networks, E and Wojtowytsch [17] discuss simple examples that are not Barron functions, i.e., cannot be represented by shallow networks. Shallow [[5] and deep random feature networks 22 have also been analyzed regarding classification accuracy. Regarding different sampling techniques, Bayesian neural networks are prominent examples 44 26 61
The goal is learn a good posterior distribution and ultimately express uncertainty around both weights and the output of the network. These methods are computationally often on par with or worse than iterative optimization. In this work, we directly relate data points and weights, while Bayesian neural networks mostly employ distributions only over the weights. Generative modeling has been proposed as a way to sample weights from existing, trained networks [56 5T). It may be interesting to consider our sampled weights as training set in this context. In the lottery ticket hypothesis 25 g "winning" subnetworks are often not trained, but selected from a randomly initialized starting network. which is similar to our approach. Still, the score computation during selection requires gradient updates. Most relevant to our work is the weight construction method by Galaris et al. (27) who proposed to use pairs of data points to construct weights. Their primary goal was to randomly sample weights that capture low-dimensional structures. No further analysis was provided, and only uniform distribution over the data pairs was used. We expand and analyze their setting here.

---

3 Mathematical framework
We introduce sampled networks, which are neural networks where each pair of weight and bias of all hidden layers is completely determined by two points from the input space. This duality between weights and data has been shown theoretically [60]. here, we provide an explicit relation. The weights are constructed using the difference between the two points, and the bias is the inner product between the weight and one of the two points, After all hidden layers are constructed, we must only solve an optimization problem for the coefficients of linear layer, mapping the output from the last hidden layer to the final output. We start to formalize this construction by introducing some notation.
Let X' S TRP be the input space with ||-I| being the Fuclidean norm with inner product (:-)). Further, let & be a neural network with L hidden layers, parameters {W, L+1 b(221 and activation function by) as the output of the Ith layer, with (0) (x) I. The two activation functions we focus on are the rectified linear unit (ReLU), <(x) = max (x. 0}. and the hyperbolic tangent (tanh). We set N, to be the number of neurons in the lth layer, with No- D and Nr+11 the output dimension. We write wi, for the ith row of W and br, for the ith entry of by Building upon work of Galaris et al. [27], we now introduce sampled networks. The probability distribution to sample pairs of data points is arbitrary here, but we will refine in Definition 2 We use L to denote the loss our network we would like to minimize.
<b R + IR. For E X, we write (xx) = (W,
Definition 1. Let & be nearal network with L hidden layers. Forl= 1,..., , L, let (T0, F )= be pairs of points sampled over X' x X. We say T is sampled network if the weights and biases of every layer 1 = 1,2,- 1,2,.... I, and neurons i = 1,2,.... ......., N₁, are of the form
(1)
1-1,
W1, = | 1-1 111
br, = 100,::2/-10 + 82,
where 81, E IR are constants, (1)
11-1,1 ((1-1)(1)) (1) for 1,2, and (1)
11-1, + I1- The last
(2)
set of weights and biases are WL-1, 14+1 = arg min L(W ((W++10(4))) b1+1).
The constants $1, $2 used to fix what values the activation function takes when it is applied
to the points x! .z(2) ef. Figure ]
For ReLU, we set = 1 and 82 = 0, so that Φ (1) 0
and Φ (2))
1. For tanh, we set 31 2s2 and $2 ln(3)/2, which implies & (2 1/2 and @ (x = -1/2, respectively, and ø (1/2 (z(1) + x()))) = 0. This means that in a regression problem with ReLU, we linearly interpolate values between the two points. For classification, the tanh construction introduces boundary if (+) belongs to a different class than (2)) We will use this idea later to define a useful distribution over pairs points (cf. Definition D
1:0
1.0
0.5
0:5
(2)
.0
(1)
[2]
(2)
(1)
X
-2
-1
2
-2
-1
1
-0.5
-0.5
-1.0
-1.0
Figure 2: Placement of the point pairs ,,()),, (2) for activation functions ReLU (left) and tanh (right). Two data pairs are chosen in each subfigure, resulting in two activation functions on each data domain.
The space of functions that sampled networks can approximate is not immediately clear. First, we are only using points in the input space to construct both the weights and the biases, instead of letting them take on any value. Second, there dependence between the bias and the direction of the weight. Third, for deep networks, the sampling space changes after each layer. These apparent restrictions require investigation into which functions we can approximate. We assume that the input space in Theorem I and Theorem extends into its ambient space RD as follows. Let X" be any compact subset of T with finite reach т > O. Informally, such set has a boundary that does not change too quickly [12.. We then set the input space X' to be the space of points including X'
3

---

and those that are at most Ej away from X', given the canonical distance function in R2, where E, T. Theorem we also consider L layers to show that the construction of weights in deep networks does not destroy the space of functions that networks with one hidden layer can approximate, even though we alter the space of weights we can construct when I, >
Theorem For any number of layers I. E Nyo, the space of sampled networks with hidden layers. $: X' - NE=1, with activation function ReLU, is dense in C(X, B.N++)).
Sketch of proof: We show that the possible biases that sampled networks can produce are all we need inside neuron, and the rest can be added in the last linear part and with additional neurons. We then show that we can approximate any neural network with one hidden layer with at most NN neurons -which is not much, considering the cost of sampling versus backpropagation. We then show that we can construct weights so that we preserve the information of X' through the first L - 1 layers, and then we the arbitrary width result applied the last hidden layer. The full proof can be found in Appendix A.I We also prove similar theorem for networks with tanh activation function and one hidden layer. The proof differs fundamentally, because tanh is not positive homogeneous.
We now show existence of sampled networks for which the L approximation error of Barron functions is bounded (cf. Theorem D
We later demonstrate that can actually construct such networks (cf. Section 4.1) The Barron space 2 20 is defined as
/ w2r( x) b)du(b, w1, w2) and |l < oc}
B= (f:
with o being the ReLU function, Q R x RD R. and μ being probability measure over S2 The Barron norm is defined as || = inf, (b.wn ara) Esupp(())) (1w2 [[ + [b])]-
Theorem 2. Let I E B and X [0, 1| For any Ni Noo. e O, and an arbitrary probability measure n, there exist sampled networks & with one hidden layer, N1 neurons, and ReLU activation function, such that
f -
())) -
(3 + f1l.1111
Iff 1 -
<
N1
Sketch of proof: It quickly follows from the results of al. 20), which showed it for regular neural networks, and Theorem The full proof can be found in Appendix A.2
Up until now, have been concerned with the space of sampling networks, but not with the distribution of the parameters. We found that putting emphasis on points that are close and differ a lot with respect to the output of the true function works well. As want sample layers sequentially, and neurons in each layer independently from each other, we define a layer-wise conditional definition underneath. The norms ||-|| xx and I1-1|y, that defines the following densities, are arbitrary over their respective space, denoted by the subscript.
Definition 2. Let f: D + N be Lipschitt-contimuous and set y = f(X). For any I E (1,2,... L}, setting 0 when I and otherwise we define
(1) -((
+ x
(2)
of , (2) (W
maxx[12zf" (2) - x [xxx_,))
(2)
otherwise,
(1) (2) where 20 ,2, E X, x|-1 (1(-1) (z and 2 (x1-1) with the network Q(t-1) parameterized by sampled [W,, by b, 1- Then, using X as the Lebesgue measure, we define the integration constant Ct Jxxx of dd. The density pi to sample pairs of points for weights and biases in layer is equal to of C1 if C O, and uniform over X x X otherwise.
Note that here, a distribution over pair of points is equivalent to a distribution over weights and biases, and the additional is regularization term. Now we can sample for each layer sequentially, starting with / = 1, using the conditional density yf. This induces a probability distribution P over the full parameter space, which, with the given regularity conditions on X' and f, is valid probability distribution. For a complete definition of P and proof of validity, see Appendix A.3

---

Using this distribution also comes with the benefit that sampling and training are not affected by rigid body transformations (affine transformation with orthogonal matrix) and scaling, as long as the true function ʃ is equivariant w.r.t. to the transformation. That is, if H is such a transformation, we say s' equivariant with respect to H. if there exists a scalar and rigid body transformation H' such that (f))) = (()())) for all x E X. and invariant if H' is the identity function. We also assume that norms I1-Iyy and I1-11x, in Equation (2 are chosen such that orthogonal matrix multiplication is an isometry.
Theorem 3. Let f be the target function and equivariant w.r.t. to a scalar and rigid body trans- formation H. If we have two sampled networks, $, &, with the same number of hidden layers L and neurons N1...., NL. where Φ: X + RNN and &: H(2) - RNN+1, then the following statements hold for all x E X:
(1) = ( and 0 = (zb))) for all i= ..,, then $ (x)))) 5( (x))=((((H())) (1) of
(2) I is invariant w.E.. H, then for any parameters of 4, there exist parameters of & such that ((x)= = ((H())), and vice versa.
(3) The probability measure P over the parameters is invariant under H.
Sketch of proof: Any neuron in the sampled network can be written as ((($1 [|
w x(()) $2).
As we divide by the square of the norm of w, the scalar in H cancels. There is difference between two points in both inputs of () which means the translation cancels. Orthogonal matrices cancel due to isometry. When f is invariant with respect to H, the loss function is also unchanged and lead to the same output. Similar argument is made for P. and the theorem follows (cf. Appendix (A.3).
If the input embedded in a higher-dimensional ambient space I with D D', we sample from subspace with dimension D dim(span S D'. All the results presented in this section still hold due to orthogonal decomposition. However, the standard approach of backpropagation and initialization allows the weights to take on any value in IR"", which implies lot of redundancy when 1) < D' The biases are also more relevant to the input space than when initialized to zero potentially avoiding the issues highlighted by Holzmüller and Steinwart [32. For these reasons, we have named the proposed method Sampling Where It Matters (SWIM), which is summarized in Algorithm|] [ For computational reasons, we consider a random subset of all possible pairs of training points when sampling weights and biases
We end this section with a time and memory complexity analysis of Algorithm T In Table D we list runtime and memory usage for three increasingly strict assumptions. The main assumption is that the dimension of the output is less than or equal to the largest dimension of the hidden layers. This is true for the problems we consider, and the difference in runtime without this assumption is only reflected in the linear optimization part. The term [N/M] i.e., integer ceiling of N/M, is required because only subset of points are considered when sampling. For the full analysis, see Appendix F
4 Numerical experiments
We now demonstrate the performance of Algorithm|| I on numerical examples. Our implementation is based on the numpy and scipy Python libraries, and we run all experiments on machine with 32GB system RAM (256GB in Section 43 and Section 4.4) and a GeForce RTX 3080 Turbo GPU with 10GB RAM. The Appendix contains detailed information on all experiments. In Section 4.1 we compare sampling to random Fourier feature models regarding the approximation of a Barron function. In Section 4.2 we compare classification accuracy of sampled networks to iterative, gradient- based optimization in a classification benchmark with real datasets. In Section 4.3 we demonstrate that more specialized architectures can be sampled, by constructing deep neural architectures as PDE solution operators. In Section 4.4 we show how to use sampling of fully-connected layers for transfer learning. For the probability distribution over the pairs in Algorithm I we always choose the _ norm for Il-lly and for = 1, 2, ...... L, we choose the L2 norm for [|- The code to reproduce the experiments from the paper, and an up-to-date code base, can be found at
5

---

Algorithm 1:
The SWIM algorithm, for activation function ø, and norms on input, output the hidden layers, and output space, -ll.llllllx,, and I-lly respectively. Also, L is loss function, which in our case is always L loss, and arg min ((:,)) becomes a linear optimization problem.
1L+1 and E IR Constant: :c E R>0. E N5o, L E No., {Nt E Nsolizi'
Data: X { E -R = 1.2..... M)
Y {yl: f(x;)= 3: RN ..,....,AM M}
( (x) r;
for = 1.2.... L do
M + 5. [M 1M;
p()) E RM; p(l) f- 0 Vi;
X ((x (1) 2 ) (11-1) (x(1)) + Tt ),.")(
Uniform (X X);
for i = 1,2, ........
M do
8 (1) (2) 1(1-1) (z! (1)) (xx )²);
(2)
-(xx (1) Mar (2)
Vi Di
p!l) m 5. x
11 2. byy
end
Wi NN. ,b, E : for k =
N₁ do Sample (1(2), 22) from X, with replacement and with probability proportional to p();
a(1), ,2(2) 1b(111) (2) ( (zl22)
wi(hi)) t $1 200 (/m) + (o((k))=(()) s2;
end
(.)).) + < W/ (1)-))() - b:);
end
WL+1, + arg min (() (x), Y); return (Wi L+1 L+1
Table 1: Runtime and memory requirements for training sampled neural networks with the SWIM algorithm, where N = max{No No. N1, N2,..., Nr.) Assumption (I) is that the output dimension is less than equal to N. Assumption (II) adds that N < M2, i.e., number of neurons and input dimension is less than the size dataset squared. Assumption (III) requires a fixed architecture.
Runtime
Memory
Assumption (I)
OLL OLL.M( ((mii[[[/// M) + +N2)) O[L. M + N
O(M min[[N/M] M) + LN2)
Assumption (II)
O(M [N/M] + LN*)
Assumption (III)
(M)
((M)

---

4.1 Illustrative example: approximating a Barron function
We compare random Fourier features and sampling procedure networks (64): f(z) f all || all), with E RR and the vector E RR defined by D. The Barron norm of ff is equal to one for all input dimensions, and it can be represented exactly with network with infinitely wide hidden layer, ReLU activation, and weights uniformly distributed of up to three hidden layers. The error is defined by e (f() -fxx)² Exex fax)². We compare this error over the domain X' = [-1, with 10, 000 points sampled uniformly, separately for training and test sets. For random features, we use w (0, 1), b U(- x², as proposed in [54], and Φ = sin. For sampling, we also use Φ = sin to obtain fair comparison. We also observed similar accuracy results when repeating the experiment with the tanh function. The number of neurons m is the same each hidden layer and ranges from m 64 up to m = 4096. Figure 3 10 (results similar for D 2, 3, 4, and sampled networks be
test function for neural
a,
sphere of radius 1 We approximate f using networks
shows results for D constructed as fast as the random feature method, ef. Appendix B Random features here have
10F
10
Ber. &P amoe arey
sampling, tandomtestures,
samplingg randomtestures, sampling, Lo? randomfeatures, L-3 xampling, 1-3
10-1
sampling, randomfeatures,, L-3
10-1
sampling, L-3
10-4
reference
10-1
reference
10
19'
10
10
Figure 3: Relative L approximation error of Barron function (test set), using random features and sampling, both with sine activation. Left: input dimension = Right: input dimension D = 10.
comparable accuracy for networks with one hidden layer, but very poor performance for deeper networks. This may be explained by the much larger ambient space dimension of the data after is processed through the first hidden layer. With our sampling method, we obtain accurate results even with more layers. The convergence rate for D 10 seems be faster than the theoretical rate.
4.2 Classification benchmark from OpenML
We the "OpenMLL-CC18 Curated Classification benchmark" 4 with all its 72 tasks to compare our sampling method to the Adam optimizer [36]. With both methods, we separately perform neural architecture search, changing the number of hidden layers from 1 to 5. All layers always have 500 neurons. Details of the training are in Appendix C Figure(sshowe shows the benchmark results. On all tasks, sampling networks is faster than training them iteratively (on average, 30 times faster). The classification accuracy is comparable (cf. Figure 4, second and third plot). The best number of layers for each problem is slightly higher for the Adam optimizer (cf. Figure fourth plot).
Adam
Connt
Sampinng
Average
Couse
6.6
Sanoling
Figure 4: Fitting time, accuracy, and number of layers using weight sampling, compared training with the Adam optimizer. The best architecture is chosen separately for each method and each problem, by evaluating 10-fold validaaaoo error over 1-5 layers with 500 neurons each.

---

4.3 Deep neural operators
We sample deep neural operators and compare their speed and accuracy to iterative gradient-based training of the same architectures. As a test problem, we consider Burgers' equation. 0n u
Lu at
8x
" "2 (0, 2 E (0, 1]. with periodic boundary conditions and viscosity V/ 0.1. The goal is to predict the solution at t = 1 from the initial condition at t = 0. Thus, we construct neural operators that represent the map G u(zz 0) + u(x, 1). We generate initial conditions by sampling five Fourier coefficients of lowest frequency and restoring the function values from these coefficients. Using a classical numerical solver, generate 15000 pairs of (u(x,0) 0), u(x:, 1)), and split them into the train (60%), validation (20%), and test sets (20%). Figure shows samples from the generated dataset.
_8
4.3.1 Fully-connected network in signal space
The first baseline for the task is a fully-connected network (FCN) trained with tanh activation to predict the discretized solution from the discretized initial condition. We trained the classical version using the Adam optimizer and the mean squared error as a loss function. We also performed early stopping based on the mean relative L'-error on the validation set. For sampling, we use Algorithm | to construct a fully-connected network with tanh as the activation function.
4.3.2 Fully-connected network in Fourier space
Similarly to Poli et al. 53 we train a fully-connected network in Fourier space. For training, we perform Fourier transform on the initial condition and the solution, keeping only the lowest frequencies. We always split complex coefficients into real and imaginary parts, and train a standard FCN on the transformed data. The reported metrics are in signal space, i.e., after inverse Fourier transform. For sampling, we perform exactly the same pre- pre-processing steps.
4.3.3 POD-DeepONet
The third architecture considered here is variation of deep operator network (DeepONet) archi- tecture 44]. The original DeepONet consists of two trainable components: the trunk net, which transforms the coordinates of an evaluation point, and the branch net, which transforms the function values on some grid. The outputs of these nets are then combined into the predictions of the whole network (v)
Ek= by (t) - bo. where is discretized input function; y is an evaluation point; [4,, tp_ T E RP are the p outputs of the trunk net; [61, ( by]" E IRP are the p outputs of the branch net; and by is a bias. DeepONet sets no restrictions on the architecture of the two nets, but often fully-connected networks are used for one-dimennt me-dimensional input. POD- ROD-DeepONet proposed by Lu et al. [46] first assumes that evaluation points lie on the input grid. It performs proper orthogonal decompo- sition (POD) of discretized solutions in the train data and uses its components instead of the trunk net to compute the outputs (E)) = Ex= (u)))e(())) + vo(E)) Here [w/
(E,(E)
p precomputed POD components for point Ej. and (E(E)) is the mean of discretized solutions evaluated at E,. Hence, only the branch net is trained in POD-DeepONG and applied scaling of 1/p the network output. For sampling, we employ orthogonality of the components and turn POD-DeepONet into a fully-connected network. Let E = [EI..... En]] be the grid used to discretize the input function u and evaluate the output function (uu). Then the POD components of the training data are V (E) = [2/2 (f), (p(()] E Raxp If b(u) E IR" is the output vector of the trunk net, the POD-DeepONet transformation can be written G(u)(E) = Vb(u) + vo( As y T = Ip. we can express the output of the trunk net as b(u)= (E( - (o())). Using this equation, we can transform the training data to sample a fully-connected network for b(u). We again use tanh as the activation function for sampling.
We followed Lu et al. [46]
4.3.4 Fourier Neural Operator
The concept of Fourier Neural Operator (FNO) was introduced by Li et al. 44] to represent maps in function spaces. An FNO consists of Fourier blocks, combining a linear operator in the Fourier space and a skip connection in signal space. As first step, FNO lifts an input signal to a higher dimensional channel space. Let i E gaxd. be an input to a Fourier block having d, channels and discretized with n points. Then, the output 0141 of the Fourier block is computed as Ut+1 6(F (R.FF(e))) W out) E gaxd, Here, F3 is discrete Fourier transform keeping only
8

---

Up
Model
width
layers
rel. L
Time
FCN; signal space
1024
2
4.48 10-3
644s
0.5
Admm
PCN: Fourier space
1024
3.29 x 10
1725s
POD-DeepONet
2048
4
1.62 x 10
42176
0.0
FNO
n/a
4
0.38 x 10
3119%
Sampling
FCN; signal space
4096
1
0.92 x 3
20s
-0.5
FCN: Fourier space
4096
1.08 10-3
16s
POD. DeepONet
4096
0.85 10
21s
FNO
4096
0.94 x 10
387s
Figure 5: Left: Samples of initial conditions un and corresponding solutions un for Burgers' equation. Right: Parameters of the best model for each architecture, the mean relative 1,2 error on the test set, and the training time. We average the metrics across three runs with different random seeds.
the k lowest frequencies and Fr is the corresponding inverse transform; & is an activation function; is a spectral convolution; is a 1 x 1 convolution with bias; and R E Ckxd, xdv, W E Rd. x du are learnable parameters. FNO stacks several Fourier blocks and then projects the output signal to the target dimension. The projection and the lifting operators are parameterized with neural networks. For sampling, the construction of convolution kernels is not possible yet, so cannot sample FNO directly. Instead, we use the idea of FNO to construct a neural operator with comparable accuracy. Similar to the original FNO, normalize the input data and append grid coordinates to it before lifting. Then, we draw the weights from a uniform distribution on [-1, 1] to compute the 1 x 1 lifting convolution. We first apply the Fourier transform both input and target data, and then train a fully-connected network for each channel in Fourier space. We use skip connections, as in the original FNO, by removing the input data from the lifted target function during training, and then add it before moving to the output of the block. After sampling and transforming the input data with the sampled networks, we apply the inverse Fourier transform. After the Fourier block(s), we sample a fully-connected network that maps the signal to the solution.
The results of the experiments in Figure 5h that sampled models are comparable to the Adam- trained ones. The sampled FNO model does not directly follow the original FNO architecture, as we able only sample cully-connected layers. This shows the advantage of gradient-basse methods: as of now, they are applicable to much broader use cases. These experiments showcase one of the main advantages of sampled networks: speed of training. We run sampling on the CPU; nevertheless, we see a significant speed-up compared to Adam training performed on GPU.
4.4 Transfer learning
Training deep neural networks from scratch involves finding a suitable neural network architecture (1 and hyper-parameten [3] 66). Transfer learning aims to improve performance on the target task by leveraging learned feature representations from the source task. This has been successful in image classification [35), multi-languuge text classification, and sentiment analysis [63] 9. Here, we compare the performance of sampling with iterative training on an image classification transfer learning task. We choose the CIFAR-10 dataset (39], with 50000 training and 10000 test images. Each image has dimension 32 x 32 x 3 and must be classified into one of the ten classes. We consider ResNet50 (1I, VGG19 [58] and Xception [ all pre-trained on the ImageNet dataset (55]. We freeze the weights of all convolutional layers and append one fully connected hidden layer and one output layer. We refer to these two layers as the classification head, which we sample with Algorithm [ and compare the classification accuracy against iterative training with the Adam optimizer.
Figure o (left) shows that for a pre-trained ResNet50, the test accuracy using the sampling approach is higher than the Adam training approach for a width greater than 1024. We observe similar qualitative behavior for VGG19 and Xception (figures in Appendix E Figure (middle) shows that the sampling approach results in higher test accuracy with all three pre-trained models. Furthermore, the deviation in test accuracy obtained with the sampling algorithm is very low, demonstrating that sampling is more robust to changing random seeds than iterative training. After fine-tuning the whole neural network with the Adam optimizer with a learning rate 10-5, the test accuracies of sampled networks are close to the iterative approach. Thus, sampling provide good starting point for fine-tuning the entire model. comparison for the three models before and after fine-tuning is contained Appendix F Figure 6 (right) shows that sampling is up to two orders of magnitude faster than iterative training for
9

---

Adam: Teat data
Mam
Adam: Resher50
Samplig: Redletto
Acam: Train sata
Adam + Ano tuntuning
Asam: VGG19
-- Sampling: VSG19
100
Sempling: Train
Sampling: Text sata
100
Sampling fire-tuning
Sampling
10
Adam: Xccptton
Sampling: Xception
85
95
sccuracy
10
90
10
10"
10
10
Reseer50
voo19
Kapptrns
10'
10
10
Withh
Witth
Figure 6: Left: Train and test accuracies with different widths for ResNet50 (averaged over 5 random seeds). Middle: Test accuracy with different models with and without fine-tuning (width 2048). Right: Adam training and sampling times of the classification head (averaged over 5 experiments).
smaller widths, and around ten times faster for a width of 2048. summary. Algorithm[] much faster than iterative training, yields a higher test accuracy for certain widths before fine-tuning, and is more robust with respect to changing random seeds. The sampled weights also provide a good starting point for fine-tuning of the entire model.
Broader Impact
Sampling weights through data pairs large gradients of the target function offers improvements over random feature models. In terms of accuracy, networks with relatively large widths can even be competitive to iterative, gradient- based optimization. Constructing the weights through pairs of points also allows to sample deep architectures efficiently. Sampling networks offers straightforward interpretation of the internal weights and biases, namely, which data pairs are important. Given the recent critical discussions around fast advancement in artificial intelligence, and calls to slow it down, publishing work that potentially speeds up the development (concretely, training speed) in this area by orders of magnitude may seem irresponsible. The solid mathematical underpinning of random feature models and, now, sampled networks, combined with much greater interpretability the individual steps during network construction, should mitigate some of these concerns.
6 Conclusion
We present data-driven sampling method for fully-connected neural networks that outperforms random feature models in terms of accuracy, and many cases is competitive to gradient- based optimization. The time to obtain trained network is orders of magnitude faster compared to gradient- based optimization. In addition, much fewer typerparameters need to be optimized, as opposed to learning rate, number of training epochs, and type of optimizer.
Several open issues remain, we list the most pressing here. Many architectures like convolutional or transformer networks cannot be sampled with our method yet, and thus must still be trained with iterative methods. Implicit problems, such as the solution to PDE without any training data, are a challenge, as our distribution over the data pairs relies on known function values from a supervised learning setting. Iteratively refining a random initial guess may prove useful here. On the theory side, convergence rates for Algorithm beyond the default Monte-Carlo estimate are not available yet, but are important for robust applications in engineering.
In the future, hyperparameter optimization, including neural architecture search, could benefit from the fast training time of sampled networks. We already demonstrate benefits for transfer learning here, which may be exploited for other pre-trained models and tasks. Analyzing which data pairs are sampled during training may help to understand the datasets better. We did not show that our sampling distribution results in optimal weights, so there is possibility of even more efficient heuristies. Applications in scientific computing may benefit most from sampling networks, as accuracy and speed requirements much higher than for many tasks in machine learning.
10

---

Acknowledgments and Disclosure of Funding
We are grateful for discussions with Erik Bollt, Constantinos Siettos, Edmilson Roque Dos Santos, Anna Veselovska, and Massimo Fornasier. We also thank the anonymous reviewers at NeurIPS for their constructive feedback. E.B., LB.., and F.D. are funded by the Deutsche forschungssemmeinshaatt (DFG, German Research Foundation)- project no. 468830823, and also acknowledge association to DFG-SPP-229, C.D. is partially funded by the Institute for Advanced Study (IAS) at the Technical University of Munich. F.D. and Q.S. are supported by the TUM Georg Nemetschek Institute Artificial Intelligence for the Built World.
References
[1] Francis Bach. On the equivalence hetween kernel quadrature rules and random feature expansions. Journal of Machine Learning Research, 18(21):1-3,, 2017. URI. hhttp://jml:1 httpa//rrrr/ppppe///////11--/1-.
html
[2] A.R. Barron. Universal approximation bounds for superpositions a sigmoidal function. IEEE Transac- tions on Information Theory, 3933)930-994, 1993. ISSN 0018-9448, 1557-9654. doi: 10.1 10.1109/18.2566
[3] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-parameter optimization. Advances in neural information processing systems, 24, 2011.
[4] Bernd Bischl, Giuseppe Casalicchio, Matthias Feurer, Picter Gijsbers, Frank Hutter, Michel Lang, Rafacl Gomes Mantovani, Jan N. van Rijn, and Joaquin Vanschoren. OpenML benchmarking suites. In Thirty-fitth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. httpstts::///////m pesttp:///oennrviee... http:///peeeeeeeeeeeeeeeooorro/a wett://oooommmm.d0d0003eey
[5] Charles Blundell, Julien Comebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In Proceedings the 32nd Internatiiona Conference on Machine Learning, ICML, 2015. URL
http://proceeding/ mlr wwwpppresss/. v37 bwwddlll html
[6] Erik Bollt. On explaining the surprising success of reservoir computing forecaster of chaos? The universal machine learning dynamical system with contrast VAR and DMD. Chaos: Interdisciplinary Journal of Nonlinear Science, 31(1):013100 2021. doi: 10. 10.1006/5.000
1663//.00244890. 00248900
[7] Erik M. Bollt. How Neural Networks Work: Unraveling the Mystery of Randomized Neural Networks For Functions and Chaotic Dynamical Systems. unpublished, submitted, 2023.
[8] Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the Existence of Universal Lottery Tickets. In International Conference on Learning Representations, 2022. URL httpt //opereviee net hett///orurrd--SSBiir.lll...
[9] Jireh Yi-Le Chan, Khean Thye Bca, Steven Mun Hong Leow, Scuk Wai Phoong, and Wai Khuen Cheng. State of the art: a review of sentiment analysis based on sequential transfer learning. Artificial Intelligence Review, 56(1):749-780, 2023.
[10] Jingrun Chen, Xurong Chi, Weinan E, and Zhouwang Yang. Bridging traditional and machine learning- based algorithms for solving PDEs: The random feature method, (arXiv:2207. 13380), 2022.
[11] François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEFE conference on computer vision and pattern recognition, pages 1251-1258, 2017.
[12] A. Cuevas, R. Fraiman, and B. Pateiro-López. On Statistical Properties Sets Fulfilling Rolling-Tyr Conditions. Advances in Applied Probability, +4(2)311-322) 2012. ISSN 0001-8678, 1475-6064. doi: 10. 12119/2ap/133339778
[13] G. Cybenko. Approximation by superpositions a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4))303-311 1989. ISSN 1435-568X. doi: 10.10/////025512744
[14] Ronald DeVore, Boris Hanin, and Guergana Petrova. Neural network approximation. Acta Numerica, 30: 327-444, 2021. ISSN 0962-4929, 1474-0508. doi: (0.101779962249222000002..
[15] Sjoerd Dirksen, Martin Genzel, Laurent Jacques, and Alexander Stollenwerk. The separation capacity of random neural networks. Journal of Machine Learning Research, 23(309):1-47, 2022.
[16] Suchuan Dong and Zongwei Li. Local extreme learning machines and domain decomposition for solv- ing linear and nonlinear partial differential equations. Computer Methods in Applied Mechanics and Engineering, 387:1 14129, 2021. ISSN 00457825. doi: 100.6f..cma.222..11..4
11

---

[17] Weinan E. Towards Matherattial Understanding of Neural Network- Machine Learning: What We Know and What We Don't. CSIAM Trunsactions Applied Mathematics, 1(4):561-615, 2020. ISSN 2708-0560, 2708-0579,
doi: 10.4208/csiam--am.. aww.ammm000000000222222
[18] Weinan E and Stephan Wojtowytsch. Representation formulas and pointwise properties for Barron functions. Calcudus of Variations and Partial Differential Equations. 61(2):46, 2022. ISSN 0944-2669,
1432-0835, doi: 10. 10.1007/s00526-02 021-02156-6
[19] Weinan E, Chao Ma, and Lei Wu. A Priori estimates of the population risk for two-layer neural networks. Communications in Mathematical Sciences, 1705):1407-1425, 2019. ISSN 15396746, 19450796. doi:
10.4310/CMS.2019, v 17..n...ll...
[20] Weinan E, Chao Ma, and Lei Wu. The Barron Space and Flow-Induced Function Spaces for Neural Network Models. Constructive Approximation, 55(1):369 406, 2022. ISSN 0176-4276, 1432-0940, doi: 10. 10.10007/50035-000 0200:000000000000-5999009
[21] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 20 2011191977-0017 2019.
[22] Matthias Feurer, Jan N. Rijn, Arlind Kadra, Pieter Gijshers, Neeratyoy Mallik, Sahithya Ravi, Andreas Müller, Joaquin Vanschoren, and Frank Hutter. OpenMI--Python: An extensible Python API for OpenMI. aucivv:191..0244 1.02490), 2021.
[23] Christian Fiedler, Massimo Fornasier, Timo Klock, and Michael Rauchensteiner. Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples. (arXiv:2101.00 000000007150.. 2021.
[24] Massimo Fornasier, Timo Klock, Marco Mondelli, and Michael Rauchensteiner. Finite Sample Identifica- tion Wide Shallow Neural Networks with Biases. (arXiv:2211 1tfi::22111005899 1.04589), 2022.
[25] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
[26] Yarin Gal and Zoubin Ghahramani. Dropout as Bayesian Approximation: tainty in Deep Learning. In Proceedings of The 33rd International Conference on Machine Learning. pages 1050-1059. PMLR, 2016.
Representing Model Uncer-
[27] Evangelos Galaris, Gianluca Fabiani, Ioannis Gallos, Joannis Kevrekidis, and Constantinos Siettos. Numer- ical Bifurcation Analysis PDEs From Lattice Boltzmann Model Simulations: A Parsimonious Machine Learning Approach. Journal of Scientific Computing, 92(2):34, 2022. ISSN 0885-7474, 1573-7691, doi: 10. 1000077/0011-022-0118000
[28] Claudio Gallicchio and Simone Scardapane. Deep Randomized Neural Networks. In Recent Trends in Learning From Data, volume 896, pages 43-68. Springer International Publishing, Cham, 2020. ISBN 978-3-030-43882-11 978-3-033-43883-8,
doi: 000077978833030-48888
[29] Raja Giryes, Guillermo Sapiro, and Alex M. Bronstein. Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy? IEEE Transactions on Signal Processing, 64(13):34443345) 2016. ISSN 1941-0476. doi: 10. N0.10999PP2201225422222
[30] Guang-Bin Bin Huang, Qin- Yu Zhu, and Chee-Kheong Siew. Extreme learning machine: A new learning scheme of feedforward neural networks. In IEFE International Joint Conference on Neural Networks (IEEF Cat. No.04CH37541), volume 2, pages 985-990. TEFE, 2004. ISBN 978-0-7803-83599-3 doi: N0.1109/JCCNN.0004 1380068..
[31] Kaiming He,, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual lcarning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
[32] David Holzmüller and Ingo Steinwart. Training two-layer ReLU networks with gradient descent is inconsistent. Journal of Machine Learning Research, 23(181):1-82. 2022.
[33] Kurt Horik,, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2 1989, doi: 10.1016/0893. 1000100893-000000999000000000 6080(89)90020-8.
[34] Herbert Jaeger and Harald Haas Hamessing Nonlinearity: Predicting Chaotic Systems and Saving Energy in Wireless Communication. Science, 304(5667):78 80, 2004. ISSN 0036-8077 8075, 10.1 111.//scienne110112777
doi:
12

---

[35] Hee E Kim, Alejandro Cosa-Linan, Nandhini Santhanam, Mahboubeh Jannesari, Mate E Maros, and Thomas Ganslandt. Transfer learning for medical image classification: A literature review. BMC medical imaging, 22(1):69, 2022.
[36] D. P. Kingma and L.. J. Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations ICLR, 2015.
[37] Klaus Greff, Aaron Klein, Martin Chovanec, Frank Hutter, and Jürgen Schmidhuber. The Sacred Infras- tructure for Computational Research, In Proceedings of the 16th Python in Science Conference, pages 49- 56, 2017. doi: 10. 10.25000/shinma-77 2attsssiiimaa77464--0000000 7446677-088
[38] Nikola Kovachki, Zongyi Li, Burigede Liu, Kamyar Azizzadenesheli, Kaushik Bhattacharya, An- drew Stuart, and Anima Anandkumar. Neural Operator: Learning Maps Between Function Spaces. (arXiv:2108.0848) 2022.
[39] Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. PhD thesis, University of Toronto, 2009.
[40] Lingfeng Li, Xue-Cheng Tai Null, and Jiang Yang. Generalization Error Analysis of Neural Networks with Gradient Based Regularization. Communications in Computational Physics, 3204):0007-1038, 2022. doi: 22.4208/cicp.0A-2021---1
ISSN 1815-2406, 1991-7120.
[41] Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards unified analysis random fourier features. Journal of Machine Learning Research, 22( 2021.
[42] Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Fourier Neural Operator for Parametric Partial Differential Equations. In International Conference on Learning Representations, 2021. doi: (0.48550/rxxi..2100.8888
[43] Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan A. K. Suykens. Random Features for Kernel Approximation: Survey on Algorithms, Theory, and Beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44( (4(10)711287777 12447148, 2022. ISSN 1939-3539. doi: 10. 1109/TPAM..2001.300000
[44] Lu Lu, Pengzhan Jin, Guofei Pang, Zhongqiang Zhang, and George Em Kariaadaii.. Learning nonlinear operators via DeepONet based on the universal approximation theorem of operators. Nature Machine Intelligence, 3(3):218-22) 2-2229, March 2021. doi: 10. 101008044255-0001000000---
[45] Lu Lu, Xuhui Meng, Zhiping Mao, and George Em Kariadakis. DeepXDE: Deep Learning Library for Solving Differential Equations. SIAM Review, 63(1):208-22) 2021. ISSN 0036- 1665, 1095-7200, doi: 10. 00.137/19M1274001
[46] Lu Lu, Xuhui Meng, Shengze Cai, Zhiping Mao, Somdatta Goswami, Zhonggiang Zhang, and George Em Karniadakis. A comprehensive and fair comparison of two neural operators (with practical extensions) based FATR data. Computer Methods in Applied Mechanics and Engineering, 194:11,778, 2022. TSSN 00457825. doi: 10. 10166...cma.2 2022.1 14778.
[47] Takuo Matsubara, Chris J. Oates, and François-Xave Xavier Briol. The ridgelet prior: A covariance function approach to prior specification for bayesian neural networks. Journal of Machine Learning Research, 22 (157):1-57, 2021. hRL j/mmrr jmlr org/ papers/ -22/20012202 html
[48] A.J. Meade and A.A. Femandez. Solution of nonlinear ordinary differential equations by feedforward neural networks. Mathematical and Computer Modelling, 2999)119-44, 1994. ISSN 08957177. doi: 10.10166000 0/106605-7777000 71770000-7777740000660--
[49] Radford M. Neal. Bayesian Learning for Neural Nenworks, volume 118 of Lecture Notes in Statis- tics. Springer New York, 1996. ISBN 978-0-387-94724-2 978-1-4612-0745.4 978- 178---460-00745-00
doi: 10.1007/
[50] Nicholas H. Nelsen and Andrew M. Stuart. The Random Feature Model for Input-Output Maps between Banach Spaces. SIAM Journal Scientific Computing, 4315)-33222-33243, 2021. ISSN 1064-8275, 1095-7197. doi: 10.1 0..1137/2MM13395777
[51] William Peebles, Ilija Radosavovic, Tim Brooks, Alexei A. Efros, and Jitendra Malik. Learning to Learn with Generative Models of Neural Network Checkpoints. (arXiv:2209, 12892), 2022.
[52] Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8:143-195
1999. ISSN 4929, 1474-0508, doi: (0.110177700022222000299999
13

---

[53] Michael Poli, Stefano Massaroli, Federico Berto, Jinkyoo Park, Tri Dao, Christopher Ré, and Stefano Ermon. Transform once: Efficientt operator learning in frequency domain. In Advances in Neural Information Procexsing Systems, volume 35, pages 7947-7959, 2022.
[54] Ali Rahimi and Benjamin Recht. Uniform approximation of functions with random bases. In 46th Annual Allerton Conference on Communication, Control, and Computing, pages 555-561, IEEE, 2008 ISBN 978- 978-1-4244-2925-7. doi: 10.1109/ALEERTON. 2008 74777777.
[55] Olga Russakovsky, Jia Deng, Hao Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115:211 1122,, 2015.
[56] Konstantia Schürholt, Boris Knyazev, Xavier Giró-i Nieto, and Damian Borth. Hlpper-epressentatios as generative models: Sampling unseen neural network weights. In Advances in Neural Information Process- ing Systems, volume 35, pages 27906 27920, 2022. URL https: httthttttp//ceeeeeeeee http://pcccceeee..ee/e/ neurris....... cc/paper Paper Conference. pdf
[57] Jonathan W. Siegel and Jinchao Xu. Approximation rates for neural networks with general activation functions. Neural Networks, 128:313-321, 2020. ISSN 08936080. doi: 1.10166..mumeet2222000000011
[58] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogni- tion. (arXiv:1409.1555 1556), 2014.
[59] Sho Sonoda. Fast Approximation and Estimation Bounds of Kernel Quadrature for Infinitely Wide Models. (90X0v:1902.00648). 2020.
[60] Len Spek. Tjeerd Jan Heeringa, and Christoph Brune. Duality for neural networks through Reproducing Kernel Banach Spaces. carXiv:2211.0500 1.0520)) 2022.
[61] Shengyang Sun, Guodong Zhang, Jiaxin Shi, and Roger Grosse. Functional variational Bayesian neural networks. International Conference on Learning Representations, 2019.
[62] Michael Unser. A representer theorem for deep neural networks. Journal Machine Learning Research, 20(110):1330 2019. URL http::/jmmlr pttet:://jmmll.oo//pppeereeee
wwggppappss//v0/111 418.418.... hhtml
[63] Karl Weiss, Taghi M. Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal Big Data, 3())9, 2016. ISSN 2196-1115, doi: 10.11866/40537-006-0004
[64] Stephan Wojtowytsch and Weinan E. Can Shallow Neural Networks Beat the Curse of Dimensionality? Mean Field Training Perspective. JEEE Transactions on Artificial Intelligence, 1(2):211-12, 2020. ISSN 2691-4581. doi: 10. 101109/AA22221135555557
[65] Lei Wu and Jihao Long. Spectral-Based Analysis Separation between Two-Layer Neural Networks and Linear Methods. Journal of Machine Learning Research, 23(1), 2022. ISSN 1532-4435. doi: 0te.5/3586689.35866000
[66] Li Yang and Abdallah Shami. On hyperparameter optimization of machine learning algorithms: Theory and practice. Neurocomputing, 415:295 316, 2020.
14

---

Appendix
Here we include full proofs of all theorems in the paper, and then details on all numerical experiments. In the last section, we briefly explain the code repository (URL in section Appendix F)) the analysis of the algorithm runtime and memory complexity.
and provide
Contents
A Sampled networks theory
A.I
Universality of sampled networks
A.1.1
Input space
A.1.2
Networks with single hidden layer
A.1.3
Deep networks
A.1.4
Networks with single hidden layer, tanh activation
A.2
Barron spaces
14
3
Distribution of sampled networks
15
Illustratvve example: approximating Barron function
18
Classification benchmark from OpenML
18
Deep neural operators
18
I Dataset
18
D.2 Experiment setup
21
D.3 Results
22
E
Transfer learning
23
Sampling Vs Adam training
24
E.2 Sampling with tanh ReLU activation functions
24
E.3 Fine-tuning
24
E,4 One two hidden layers in the classification head
25
Code repository and algorithm complexity
26
Sampled networks theory
In this section, provide complete proofs of the results stated in the main paper. In Appendix A. we consider sampled networks and the universal approximation property, followed by the result bounding L2 approximation error between sampled networks and Barron functions in Appendix A.2 We end with the proof regarding equivariance and invariance in Appendix A.3]
We start by defining neural networks and sampled neural networks, and show more in depth the choices of the scalars sampled networks for ReLU and tanh. Let the input space of D We now define a fully connected, feed forward neural network; mostly to introduce some notation.
subset
Definition 3. Let o: R + R be nol-polynomial,, L 1, No D, and N1....,NLo E Noo- A (fully connected) neural network with L. hidden layers, activation function é, and weight space L+1 a function 4: RRD + RR,++ of the form = (Wr E RN.NN.-1 N J++1
Tb (xx = I b
(3)

---

As study the space of these networks, find it useful introduce the following notation. The space of all neural networks with L hidden layers, with N = [N1,.... NN] neurons in the separate layers, is denoted FL,N, assuming the input dimension and the output dimension are implicitly where is defined recursively as zu = E 2' and
I = ===(WWr-- bi), 1= 1.2,..,,
The image after | layers is denoted as X; 4(1) (X)).
given. each hidden layer has N neurons, and we let the input dimension and the output dimension be fixed, write the space of all such neural networks as FI,N- We then let
Fxr, U FL,N,
L=1
meaning the set of neural networks with N width, and arbitrary depth. Similarly,
20
FL.0
U FL,N.
N=1
for arbitrary width at fixed depth. Finally,
F F
U FL,N-
L=1N=1
We will now introduce sampled networks again, and go into depth the choice constants. The imput space X' is a subset of Euclidean space, and we will work with canonical inner products (, and their induced norms |-|| if we do not explicitly specify the norm.
Definition& 4. Let tb be an neural network with L hidden layers. For ael=11.... L. let (# Jo.s be pairs of points sampled over X' x X. We say t is sampled network if the weights and biases of every layer | 1, 1,2,.... and neurons i 1, 2.2...., N2, are of the form
(2)
.,....,,,
(2)
(1)
Wi,i = 81
| 1-1
I1-
21-14
11)
br,5 = (Wi,5 2111,)) + 82
(5)
1,
where 81, E R. are constants related to the activation function, and ()) Li $ (x)-)
for j 1,2, assuming (1)
zi-1, # 21-1,- The last set of weights and biases are WL+1, arg min L(W,+ (()+++((()()))) ()) bT.1), where C is suitable loss.
Remark 1. The constants 81, 82 can be fixed such that for a given activation function, we can specify values at specific points, e.g., we can specify what value to map the two points z(1) and 222) to; cf. Figure 7 Also note that the points we sampled from X' X' are sampled such that we have unique points after mapping the two sampled points through the first 1 layers. This is enforced by constructing the density of the distribution we use to sample the points so that zero density is assigned to points that map to the same output of ((-1) (see Definition 2
1:0
1.0
0.5
0.5
(1)
[2]
X
-2
-1
2
-2
-1
1
-0.5
-0.5
-1.0
-1.0
Figure 7: Illustration of the placement point pairs (1), (2) for activation functions ReLU (left) and tanh (right).

---

Example A.1. We consider the construction of the constants $1, 82 for ReLU and tanh, as they are the two activation functions used for both the proofs and the experiments. We start by considering the activation function tanh, i.e., (xx)
exp 2 -1
exp2 2 +1
Consider an arbitrary weight w, where we drop the subseripts for simplicity. Setting $1 2- s2, the input of the corresponding activation function, at the mid-point x = x1) +
,0) ,(3) +2
is
2
2
(2) (()
(w, r) - 6 =
w 2
(w, (11)
(2)) (()
w,
82
282
xx - x01))=(2)) -0(0)
x(1)) -82
(2( x011
2
2
82 82 = 0.
The output of the neuron corresponding to the input above is then zero, regardless of what the constant 82 is. Another aspect of the constants are that we can decide activation values for the two sampled points. This can be seen with similar calculation as above.
(w, ( b = 82-
Letting 82
3 we see that the output of the corresponding neuron at point (11) is 2
expln(3) -1
((-82) exp [n)) +1 2'
and for (2) we get 1.4 We can also consider the ReLU activation function where we choose to set 81 and s2 = 0. The center of the real line is then placed at 2011, and x²(2) is mapped to one.
A.1 Universality sampled networks
In this section we show that universal approximation results also holds for our sampled networks. We start by considering the ReLU function. To separate it from tanh, which the second activation function we consider, we denote á to be ReLU and v to be tanh. Networks with ReLU as activation function are then denoted by Φ and V are networks with tanh activation function. When we use ReLU, set $1 and $2 0, as already discussed. We provide the notation that is used throughout Appendix A in Table 2
The rest of this section is structured as follows:
1. We introduce the type of input spaces we are working with.
2. We then aim rewrite an arbitrary fully connected neural network with one hidden layer into sampled network.
3. This is done by first constructing neurons that add constant to parts of the input space while leaving the rest untouched.
4. We then show that we can translate between an arbitrary neural network and a sampled network, if the weights of the former are given. This gives us the first universal approximator result, by combining this step with the former.
5. We go on to construct deep sampled networks with arbitrary width, showing that we can contain the information needed through the first I. layers, and then apply the result for sampled networks with one hidden layer, to the last hidden layer.
6. We conclude the section by showing that sampled networks with tanh activation functions are also universal approximators. Concretely, we show that it is dense in the space of sampled networks with ReLU activation function. The reason we need a different proof for the tanh case is that it is not positive homogeneous, a property of ReLU that we heavily depend upon for the proof of sampled networks with ReLU as activation function.
Before we can start with the proof that F1,oc xc. is dense in the space of continuous functions, we start. by specifying the domain/input space for the functions.
3

---

Table 2: Notation used through the theory section of this appendix.
X' Pre-noise input space. Subset of IR and compact for Appendix A.1 and
Appendix A.2
x
Input space. Subset of I2,, X² C X, and compact for Appendix A.1 and Appendix [A.2
Noise level for X', Definition 5
Activation function ReLU, ((x) max (æx, 0}.
+
Neural network with activation function ReLU. Activation function tanh.
V
Neural network with activation function tanh.
Constant block. 5 neurons that combined add constant value parts the input space X, while leaving the rest untouched. Definition Number of neurons in layer of neural network. No- D and N is the output dimension network.
Ni
W1,
The weight at the ith neuron, of the /th layer.
b1,
The bias at the ith neuron, of the ith layer.
(())
Function that maps x X to the output the Ith hidden layer. The ith neuron for the Ith layer.
(1.4)
X
The image of X after / layers, i.e., X ((X). We set X6 X.
(x) Space of neural networks with L. hidden layers and neurons in layer 1. Space of all neural networks with one hidden layer, i.e., networks with arbitrary width.
FLAN Na.
Nu]
F1.00
Ff.e
Space of all sampled networks with one hidden layer and arbitrary width. Function that maps points from X' to X", mapping to the closest point in X', which is unique.
Maps E X x [0. 1] to X. by 7( 8) (((((())))))))))))))())))()))) x).
||-||
Canonical norm of R with inner product (-).
B. B.(z) (x)
The ball B. (x) = {a' E R": | xx-x't I'll < c).
B, (x)
The closed ball (xx) (a' E RRD: || (
Reach of the set X" Lebesgue measure.
A.1.1
Input space
We again assume that the input space X' is subset of RD. We also assume that &' contains some additional additive noise. Before we can define this noisy input space, we recall two concepts.
Let (Z, d) be a metric space, and the distance between a subset A C Z and point z E Z be defined
dz A) inf(d(z, a): A}-
If 2 is also normed space, the medial axis is then defined as
Med(A) = {a E Z: 3p + A, z|| 1 2|| dz(z,A))
The reach of is defined as
TA = inf dz (a, Med(A))
aEA
Informally, the reach is the smallest distance from point in the subset to non-unique projection of it the complement A This means that the reach of convex subsets is infinite (all projections are unique), while other sets can have zero reach, which means 0 S TA I oc.
Let 2 R and d be the canonical Euclidean distance.
Definition 5. Let X' be a nonempty compact subset of RR. with reach Tx > O. The input space X' is defined as
X x= far E RR: dz(x, Sc) where 0 < Er < min(Tx' 1}. We refer to X' as the pre-noise input space.

---

Remark 2.
As (z, X") = 0 for all Z E X", we have that X' C X. Due to (x) ci we preserve that X closed, and as E do means have enlarged the input space with new points at most 6 distance away from X". This preserves many properties of the pre-noise input space X', while also being helpful in the proofs to come. We also argue that in practice, we are often faced with "noisy" datasets &' anyway, rather than non-perturbed data X²
bounded, and hence compact. Informally, we
We also define function that maps elements in X') \ X" down X', using the uniqueness property given by the medial axis. That is, Ç: X' - X' is the mapping defined as {(z) = x', for x' E X and x' E X², such that d(x x²) = dz (z, X²). As we also want work along the line between these two points, we set 77 X' x [0, 1] + X, where 17(2, 6) = x + 8(((2) - z). We conclude this part with an elementary result.
Lemma 1. Let z E X, ó E [0, 11, and x' = n 8) E X. then || - x S 6, with strict inequality when 6 > O. Furthermore, when 8 O, we have x' & 0x.
Proof. We start by noticing
d(C()),z'))= = [I<(x) - 2' = (1- (1)5))((2)) x11 S (1 8)El S Ex,
which means x' E X. When 5 > 0, we have strict inequality, which implies x' E int = X' \ OX. Furthermore,
d(z, | - ='1l 01(((2) x|| < 5..66. S 6,
where the last inequality holds due to < 1, and is equal only when ô = 0.
A.1.2 Networks with a single hidden layer
We can now proceed to the proof that sampled networks with one hidden layer are indeed universal approximators. The main idea is to start off with arbitrary network with single hidden layer, and show that we can approximate this network arbitrarily well. Then we can rely on previous universal approximation theorems
to finalize the proof. We start by showing some results for different type of neural networks, but very similar in form. We consider networks where the bias is of the same form sampled network. However, the weight is normalized to be unit weight, that is, divided by the norm, and not the square of the norm. We show in Lemma 4 that the results also hold for any positive scalar multiple of the unit weight, and therefore our sampled network, where divide by the norm of the weight squared. To be more precise, the weights are of the form
B3 33 52
(2)
(1)
3 1,5 1/
W1,1
2 1,
(2)
2 2111
and biases by, = (wi, 1 2,,)) Networks with weights/biases in the hidden layers of this form referred to as unit sampled network. In addition, when the output dimension is Ni+1 = 1, we split the bias of the last layer, b into N& parts, make the proof easier to follow. This is of no consequence for the final result, as we can always sum up the parts to form the original bias. We write the different parts of the split bL+1,; for 1.2....,NZ
We start by defining a constant block. This crucial for handling the bias, as we can add constants to the output of certain parts of the input space, while leaving the rest untouched. This is important when proving Lemma 2
Definition 6. Let C2 < C3. and c E R+. A constant block o. is defined as five neurons summed together as follows. For x E RR,
3
(x(2)= = Σ f((x),
im
where
fi(x) = ai Φ(0 02), fa(x) = ai 60- c3)), fa(z) = -1 6(x cz), fa(z) = a2 6(- c1))
ft(x)) = 0g 6(r C1),
and 01 03-05" a2 a1
and a3 a2 aq
5

---

Remark 3. The function &e are constructed using neurons, but can also be written as the continuous function,
I S c1
(.(5)
03 d 61 x 02
I C2
where d = 01 C3 + 02 c2- Obviously, if needs to be negative, one can simply swap the sign on each of the three parameters, 0z--
We by the construction of &e that we might need the negative of some original weight. That is, the input to &e is of the form (Wi, x), and for fz and fa. we require (-W1,, . In Lemmal 3 shall see that this is not issue and that we can construct neurons such that they approximate constant blocks arbitrarily well, as long as C1, C2; C3 can be produced by the inner product between a weight and points in X, that is, if we can produce the biases equal the constants C1 C22 C3-
Let & Fi.K, with parameters f bt. 2. 1=1,1=1 be arbitrary neural network. Unless otherwise stated, the weights in this arbitrary network & are always nonzero. Sampled networks cannot have zero weights, as the point pairs used to construct weights, both for unit and regular sampled networks, are distinct. However, one can always construct the same output as neurons with zero weights by setting certain weights Wt+ 1++1 to zero.
We start by showing that, given all weights of a network, we can construct all biases in a unit sampled network that the function values agree. More precisely, weights i, and show that we can find points in N' to construct the biases of the form in unit sampled networks, such that the resulting neural network output on X' equals exactly the values of the arbitrary network 4
want to construct network with
Lemma 2. Let & E FI,K: X
RN. There exists of at most 6 Nı points I; X and biases b2, E R, such that a network & with weights W1,5 = W1,5 W2,5 = 22 and biases b2, E R.
1 (W1,1. 24),
for =
satisfies ((x) ((x) = 0 for all E X.
Proof. W.L.o.g.. assume N2 1. For any weight/bias pair th d1.1, let w1,s $1.1. W2,; = 22 B, = ((1,,,,)) r): x E X²) b(th = inf B,, and bV = sup B,. As (w), is continuous, means B, is compact and 6%2 669 Bi.
We have four different cases, depending on 61...
(1) If b E B;, then simply choose corresponding x; X' such that bi, (wi,,, 2x)) b
Letting b2, = b2, we have
w2 ((1,,, - by.i) - b2, t2. (0 by.i) - 82.1-
(2) If bi; > (1) we choose x; such that b1,; = (wi, xz) = (59) and b2,; = 62.1. As o((w1,s,
b1.s) (( by,)) = 0, for all X, we are done.
(3) If bi < h we choose corresponding æ; such that b1.; (wI,1, (1) and set b2,
6 + W2, (b1,1- -ka) We then have
(2.10((W1,5:00 x) - b1.s) - be. = (2 x) - W2, b1.5 bz,
-22i(W1,,s x) - b 12,1 by, + b2
1, x) - .2. ú2, b1.
v22, (101,,, by.1) b2
where first and last equality holds due to (w1,s, x) $1d b1, for all E X.

---

(4) If b < b2, < 6/ and ,1,5 & B3, things are bit more involved. First notice that B,!). n [b% d and B = B, n bh,,. 6 are both non-empty compact sets. We therefore have that supremum and infimum of both sets are members of their respective set, and thus also part of B, We therefore choose 24 such that 61, = (W1,s, xi) = inf B(a). To make up for the difference between b1,4 < b1,t, we add a constant to all x E X where (w1,s, > b1. To do this we add some additional neurons, using our constant block Φ ((wr,e))) ))- Letting -b.5). (b..--b,,,.c c sup B C2 b1,s, and C3 b4" We have now added five more neurons, and the weights and bias in second layer corresponding to the neurons is set to be ta and O, respectively, where both a and the sign of a depends on Definition case we require negative sign in front of (11,6)) :), we simply set it as we are only concerned with finding biases given weights. We then have that for all x E X,
c= -= (b1..
{ 0,
(wI,i. > b1Gi
( ((w1,,, 2))
otherwise.
Finally, by letting b2,4 = b2,t, we have
(2,10((001,,01)) b1,)) b2, + $1 ((w1,
=w2,(w1,..3) -12, b - 82. + 12, bis5 - W2 ,1,i
(w1,11)) u2 bi,5 b
when (w1,i, b and
12 b):s) - b2 + (b(.) ((01,.;;. = b2 = b22
( x)b1,)) 62.6.
otherwise. And thus, (xx) = ((x) for all æ E X. As we add five additional neurons for each constant block, and may need one for each neuron, means we need construct our network with at most 6 N₁ neurons.
Now that we know we can construct suitable biases in our unit sampled networks for all types of biases by, in the arbitrary network é we show how to construct the weights.
Lemma 3. Let & Fi,k: X - RNN, with biases of the form bı.e (, where vi E X for i == 1,2,..... N₁. N1, For any e > 0, there exist unit sampled network h such that || - $1 < E.
Proof. W.L.ogg, we assume N₂ 1. For all i 1.2,... N1. we construct the weights and biases as follows: If x, & 0X, then we set è' such that B (2x) C X. Let =b,3 = 2g and
Fo. 2b. 2 fwn, E (x( c X. Setting W2,5 || (22. b2, 82,5. and w1.a
(2)
(2)
| + | implics
#.. 00. #1.1
02.00((11.5
((1))) b2. = || 1
((rrri
23) b2
u (00(((1),,)) xz)) 12.
where last equality follows by & being positive homogeneous.
If v; E 0X, by continuity we find 5 > 0 such that for all i = 1,2.... .... N1 and x',x x E X, where
|| 21 6, we have
10((1),,1, x')) (1 N₁ W2
7

---

where w2 max (102, 1 We set z0, - (2 min 13), with 20, E int X' and || - = < ((2) We may proceed by constructing "0,i above, and similarly
(2)
(2)
5, due and Lemma
setting W2,4 || ||,20 b2 b2,s. we have
N1
N1 22 ( xz)) 62.
Σ
02 00 (wi,i -x0 ((!)) 62,6
N
(0((28,,1, -x0 x0,i)) - (((00),11 x- zii))
x001)) - -
(00()))~(((11111)))) -xx))
(((111,,,
W2
U02
=,
Ni
U2
and thus ||
① 100000000000
<
however, the weights in sampled network divided by the norm squared, not just the norm. We now show that for all the results so far, and also for any other results later on, differing by a positive scalar (such as this norm) irrelevant when ReLU is the activation function.
Until now, we have worked with weights of the form w
[|x O1
Lemma 4. Let & be network with one hidden layer, with weights and biases of the form
(2)
(1)
U.
1U
61.5 (w..1:00111 (1))
W1,
22
(1)
for = 1,,,...,, For any weights and biases in the last layer, {w22 b2,)) and set strictly positive scalars {wi) N. there exist sampled networks P., where weights and biases the hidden layer (w/,s: U 1 are of the form
w1, WiWl.i
b/ = (w/
such that (w) (xx) for all x X.
Proof. We set w/,s w2.1 for all x E X,
and b2, b2,3. As ReLU is positive homogeneous function, have
We
M2 x)) b/,i) - 11,5 w;W2, o((W1,i, -1.5)
02,00(wu1,.0) b1.s).
The result itself is not too exciting, but it allows us to use the results proven earlier, applying them to sampled networks by setting the scalar be w,
We are now ready to show the universal approximation property for sampled networks with one hidden layer. We let FSS be defined similarly to FL,c, with every ob FiS being sampled neural network.
Theorem 4. Let g C(X,R. Then, for any O, there exist F.. with ReLU activation function, such that
llg
loo < E.
That is, FS.00 is dense in C(X, NN-11.

---

Proof. W.l.ogg.. let NL+1 = 1. and in addition, let > 0 and g E C(X, Using the universal approximation theorem of Pinkus [52), we have that for >> 0, there exist network &b Fi, such that ||g - L1 < 2. Let K be the number of neurons in 4. We then create new network 4, by first keeping the weights fixed to the original ones, {ui 2 and setting the biases of Φ according to Lemma 2 using {ō1,:: b adding constant blocks if necessary. We then change the weights of our & with the respect to the new biases, according Lemma (with the epsilon set to c/2). It follows from the two lemmas that | 11100 <
2' That means
llg +
9 - ② + i- / 1 I l1g $1100 + |1
+11x0 <c.
(2) (2)
As the weights of the first layer of 4 can be written as w1,1 = 1 UP and bias b1,t = (Wi,1 =0,))
"o.
both guaranteed by Lemma means & E Ff,00 Thus, Ff.00 is dense in C(X,
Remark 4. By the same two lemmas, Lemma 2 and Lemma B] one show that other results regarding networks with one hidden layer with at most K neurons, also hold for sampled networks, but with 6 K neurons, due to the possibility of one constant block for each neuron. When X' is connected set, we only need K neurons, as no additional constant blocks must be added; see proof of Lemma for details.
A.1.3 Deep networks
The extension of sampled networks into several layers not obvious, as the choice of weights in the first layer affects the sampling space for the weights in the next layer. This additional complexity raises the question, letting NL = NN,,
1. is the space UNZ=1 FE,N, dense in C(K,RNN1N when L > 1? We aim to answer this question in this section. With dimensions in each layer being Nr = [D, D....,
: D, Nr.. we start by showing holds for UN FE,N2 i.e., the space of sampled networks with hidden layers, and D neurons in the first L layers and arbitrary width in the last layer.
Lemma 5. Let NL = DD.....,,,AA and L > 1. Then FE.IFF.N. is dense in C(11.
Proof. Let E > 0, and g E C(X, ((X,RNNN+) NN Basic linear algebra implies there exists a set of D linearly independent unit vectors v = (v, ) such that X' S span (v, )- with vy E X for all uy E v. For I 1 and i {1, 2, .,.,, N). the bias is set to b inf (u;, 2): x E X). Due to continuity and compactness, we can set 1; correspond an x E X' such that (1,, Fi, (1)
b We must have fi-1, 0x - otherwise the inner product between some points in X' and v; is smaller than the bias, (1) which contradicts the construction of bt,i- We need to show that ((x[1), 2/-1. cuu + + for c R to proceed constructing (2) similar fashion as in Lemma
Let U = Be, (C(=(())))))) with 2 U. Also, U is the only closed ball with center ((1-11)) and (3/11)) U n 0x otherwise Ç would not give unique element, which is guaranteed by Definition We define the hyperplane Ker fa E R:: (Wr, x²) (U,,, = 0}, and the projection matrix P from R. onto Ker. Let x' P((x If r' # 11-1, then x' E intU, as (1)
(1)
(1)
o L aU and P is a unique projection minimizing the distance. As x' E int means there an open ball around x', where there are points in B,, (c(=(( separated by Ker, which implies (v;, ( is not the minimum. This is a contradiction, and hence s' = 2 This means Ker is tangent hyperplane, and as any vectors along the hyperplane is orthogonal to ((x zi, implies (1) is 0 or As (v,, ( is the minimum, means there (1)
the angle between U; and ((x 21
exist a E R such that ((x (11,11 #1-1, c + #1-14
(1)
(1)
We may now construct (2) = x/-1,1 1,i + cu2, assured that x 2 E X' due to the last paragraph.
1,
We then have Wt,i dy and by. = (1 for all neurons in the first hidden layer. The image
(1)

---

after this first hidden layer (2)) is injective, and therefore bijective. To show this, let u1 U2 E X such that in # u2. As the vectors in v spans X, means there exists two unique set of coefficients,
C1, C2 E such that Σ ci U, and Σ C2 Uz We then have
T (un) Vc + Vo² = $ (u2),
where V is the Gram matrix of As vectors in v linearly independent, V is positive definite, and combined with # C2. this implies the inequality. That means p(()) is bijective mapping of X. As the mapping bijective and continuous, we have that for any x E X", there an e (1) B,; (f()())) C X.
0, such that
For < 1 < I., we repeat the procedure, but swap X' with 4 As ((l-1) is a bijective mapping, we may find similar linear independent vectors and construct similar points 22(1) 2/-1,1 2 but now with noise level (1) For L, as we have a subset of X' that is a closed ball around each point in (x), for every x X", means we can proceed by constructing the last hidden layer and the last layer in the same way explained when proving Theorem The only caveat is that are approximating network with one hidden layer with the domain X and the function we approximate is ÿ = g o ( Given this, denoting ((L:L+1) as the function of last hidden layer and the last layer, there exists number of nodes, weights, and biases in the last hidden layer and the last layer, such that
ej
l|g 1
+ (1::++1) |150 <e.
due to construction above and Theorem As 4 is unit sampled network, it follows by Lemma that U Fi,Nz dense in C(X, A
We can now prove that sampled networks with L layers, and different dimensions in all neurons, with arbitrary width in the last hidden layer, are universal approximators, with the obvious caveat that each needs at least D neurons, otherwise we will lose some information regardless of how we construct the network.
hidden layer = 1, 1.2....,44
Theorem 5. Let N N21, NN-1, N1), where min(N]: == 1,2, ..... - 1} 2 D, and L 1. Then UN FL,NZ is dense in C(X,RNL1
Proof. Let e > and g E C(X,RN For L = Theorem is enough, and we therefore assume <> We start by constructing network & E UN- JS N, where Ñ₂, = DD, D, N FE,N,
according to Lemma such that | glloo <. To construct & E I - let = 1, and start by constructing weights/biases for the first D nodes according &. For the additional nodes, in the first hidden layer, select an arbitrary direction w. Let X, = (* i = 1,
D and j = 1, be the of all points needed to construct the D neurons in the next layer of o. Then for each additional node i = D + 1, NN. we set
(1) 3 oo = arg max ( (w, a): x E X' and (()) E X1).
and choose (2) proof for Lemma Using these points to define the weights and biases of the last N, - D nodes, the following space X, contains points [, 0, 0), for j 1, and i 1, 1,2,.... ... D. For
(1) = aw, where a E Rso, similar to what is done in the oo, E X' such that (2) =u,
1 < l < repeat the process above, setting =7, [ 0,0, 0.....0) 0] for the first D nodes, and construct the weights of the additional nodes described above, but with sampling space being X/-1. When / L, set number of nodes to the same in Φ and choose the points to construct the weights and biases as = 1,i = [ 1. 0, .........
. OJ, for 1,2 and i = 1, 2...,, Nr.. The weights and biases in the last layer are the same in क. This implies.
1 glloo = - glloo <
and thus UN FL.N, N, is dense in C(X, ((XRRNAA N2+1).
10

---

Remark 5. Important to note that the proof is only showing existence, and that we expect networks to have a more interesting representation after the first L- layers. With this theorem, we can conclude that stacking layers is not necessarily detrimental for the expressiveness of the networks, even though may alter the sampling space in non-trivial ways. Empirically, we also confirm this, with several cases performing better under deep networks very similar to iteratively trained neural networks.
Corollary 1. Fo is dense in C(X,R
A.1.4 Networks with single hidden layer, tanh activation
We now turn to using tanh as activation function, which we find useful for both prediction tasks, and we need the activation function to be smooth. We will use the results for sampled networks with ReLU as activation function, and show we can arbitrarily well approximate these. The reason for this, instead using arbitrary network with ReLU as activation function, is that we are using weights and biases of the correct form in the former, such that the tanh networks construct will more easily have the correct form. We set 52 In(3) 81 $2 - as already discussed and let & be the tanh function, with Y being neural networks with v as activation function simply to separate from the ReLU Φ, as we are using both this section. Note that still network with ReLU as activation function and $1 1, $2 O.
We start by showing how
of tanh functions can approximate set of particular functions.
Lemma Let f [co, cM++] + R defined as f(x) = - 0g 1 le..eM (2). with 1 being the indicator function, co C1 .... < CM < CM+1, and for all 0, 1...., M 1, C E R and a, E Rx0- Then there exists strictly positive scalars w = {wi ) such that
M Σ 1=1
M
((x)
(1(z) =
Σ
ai
[plli(s - a) - 82) +1,
2
fulfills f(c--1) < g(x) < f((+1) whenever x E [c-11 C+11. for all 1,2...., M.
Proof. We start by observing that both functions, f and g. are increasing, with the latter strictly increasing. We also have that fco) = < g(x) < Σ Li= as fCMM), for all E [co, regardless choice of w. We then fix constants
0< 8,
< M
< 6i-1
for i = 1,2,..., 1. We have, due to 82, that (c() = 2s for all i ., M. V. In addition, we can always increase w; to make sure gi (C(+1) ) is large enough, and gi (c:-1) small enough for our purposes, v is bijective and strictly increasing, We set w1 large enough such that gi (c,) > 01 Ej. for all j = 2,3,
M - 1. For = 2, ...,..... where j = 1,2, ... i 1, and (c,c)) > Ej, where j i 1, 2, ..... M 1. Finally, let WM be large enough such that gMz (cy < oU, for = 1,2 2. property of every It. see that
11 we set wi large enough such that g: < 8,.
With the strictly increasing
1-1
M
g(c)
Σ
91
(c))
Σ j=
(ci)
J=1
1-1
M
Σ
0: + Σ
8
1=
i-1
Σ
aj
0:
3a,
f(a),
4
4
j=l
11

---

and
i-1
M
(()
9j (c)
0: +
Σ g)(c))
1=1
ji++
a
(aj 4)
4
i-1
Σ ==
aj
01
ai
= f(e-1)..
4
4
. M, and the Combing the observations at the start with f(c-1) g(c;) f(c), for ..........
property sought after follows quickly.
We can now show that we can approximate neuron with ReLU @ activation function and with unit sampled weights arbitrarily well.
Lemma 7. Let 10), ((2) E X and Wn E R. For any > 0, there exist a M E No and M pairs of
distinct points {(I; I E X'
(2))
2) Ji=l such that
(020((101
(1))))
Σ Wi (t
82 + <e,
-(1) where wi [ 1 Wi IR, and wi 51
2 -2(1 (1)
11r -x: 111
Proof. Lete Onnd, w.l.o.g., úh Let x) x X), as well as f(x) ( x- a(1)). We start by partitioning f into /attoe/4-cheeee /4-cchunks. More specifically, let e = max B, and M' 2, .... M", M' + We will now define points cj, with the goal of constructing function f as in Lemma 6 Still, because we require e, E B to define biases in our tanh functions later, we must define the e,s iteratively, by setting ci 0, k = j = 2, and define every other Gj follows:
4s0g lel
Set d (k-1)c for k
MP
1. If d. c, we are done, otherwise proceed
2. Set
d= sup B dc) dy = inf B [dg, c].
3. If d' d= set Cj = dæ. and increase j and k, and go to 1.
4. If d; > Cj-1, set Cj dy. and increase j. otherwise discard the point d'.-
5. Set C = d' and increase j. Set & = arg min ( (d, Cj: da Cj > 0} and go to I.
We have M M' points, and can now construct the ays of f. For j 1,2, ... M, with
CM-1 = G, let
o c f(e++))((c)) - f(G)), 6j41 - M7' 0 f(p(c;)) - f(e,), otherwise,
where p(cy) = arg min(d:------ cc: de -c 2 and 1: = .... M'+ Note that 0 < C-CM S Mr by Definition 5 and continuity of the inner product (ı01, (1)). namely,
.....
We then construct f as in Lemma
M
f(x)
Σ
a (e (z).
12

---

Letting C = fle,, c/al: j= = -,,,,....... o....... M and cj+1 -cj S c. M }. it is easy to see
((x)-f(x)) 4'
for all x E Ue c. For any a outside said set, we are not concerned with, as it is not part of B, and hence nothing from X' is mapped to said points.
Construct w = [ according to Lemma 6 We will now construct a sum of tanh functions, using only weights/biases allowed in sampled networks. For all i 1, 1,2,.... M, define úi; 2 and set
(1) n)(2,, 6,), with d; 0 and E X, such that (01, I
where ó; 0 iff & OX. We
specify & and & > 0 such that +/ 2 W/, B2r; (2) ) S X. and
(0 x - 2(11) .2) - + (w x) - -2) <
W
M
with 51 - 2 = x (1) E and for all x E X. It is clear that x; 2 E X. We
( -1))
(2)
(1) (2)
may rewrite the of tanh functions
M
g(x)=
Σ
xx,)) + W/
x
Σ
M
81
/
6:00
2 x1(1)
+ is
||e/bbll
||e//0111"
1m1
Wayh
(111 - -82-22 -82) + 0z
c
aj p (1, - - -8)) +
where ē
(w,,2 I
)
As wi S Wi for all i = 1,2, 1,2,..., M, it follows from Lemma and the
construction above that
(9(x) - f(x) s [g(z)
Σ 2
b (w)((11 c. -82) 1]1
M
+ Σ
( (wo(
c -2-25))) 22) 11-11111 f(x)
1=1
+ 1f(x) - f(x))
< E c
_ =c.
4 2 4
We are now ready to prove that sampled networks with one hidden layer with tanh as activation function are universal approximators.
Theorem 6. Let F.S. be the set of all sampled networks with one hidden layer of arbitrary width and activation function Fs. is dense in C(X, N. with respect the uniform norm.
0, and w.l.o.g., N₂ 1. By Theorem we know there exists network T. with Nr neurons and parameters { d02, b2 b2 / function, such that | glo < 2- We can then construct a new network W, with z! as activation function, where for each neuron ((1.n), we construct M, neurons in V, according to Lemma 7 with
Proof. Let g C(X,RN))
Nr i= and ReLU activation
2N1 Setting the biases in last layer of v based on &. i.e., for every i = 1, 2..., .Ñ. b2 M,
$2.1
13

---

where j = 2,2,.... M, We then have, letting N1 be the number of neurons in L
N
((r)
(())]
2 1 (x) bz,s
Σ
22 1 (x)) 62.6
N1
W2 15 ((WW - b(o))
22 22 02,0((00,,10)) - -((,))
N1
M,
W2 ( -b())
022 - -b(.)
1=1
N;
2N
2'
for all x E X. The last inequality follows from Lemma 7 This implies that
e
V o|1bo
V/
110 gllx
<
+
2
2
and Pi,3o is dense in C(X' N2..
A.2 Barron spaces
Working with neural networks and sampling makes it very natural to connect our theory to Barron spaces 2 20) This space of functions be considered continuum analog of neural networks with one hidden layer of arbitrary width. We start by considering all functions f: X - R that can be written
f(x) / u22(((11 x) b)du(bb, w1, W2),
where is probability measure over (2, En), with Ω R X R x RR. A Barron space B, is equipped with a norm of the form,
|f s, inf [22 1B))
1 0o,
taken over the space of probability measure a over (Ω, En). When p cc, we have
||
inf max (b,a0, wa (e) (supp(())
{/w2 [102|(11001]) (6)))
#
The Barron space can then be defined as
Bp = (f: f(x) / w2d((w1, b)dp(b, w1, w2) and || 20).
As for any 1 S p S co, we have Bp Boc, and so we may drop the subscript p 20]. Given our previous results, we can easily show approximation bounds between our sampled networks and Barron functions.
Theorem 7. Let f E B and X = [0, 1)_ For any N1 E Noo, e > 0, and an arbitrary probability measure n, there exist sampled networks t with one hidden layer, N₂ neurons, and ReLU activation function, such that
- / [5(x)) ((1)) <
(3 1)1ff
N1
Proof. Let N1 E Nyo and O. By E al. 20). we know there exists network è E Fi,
where 2(-) Ni 22 02 b1.), such that ||f 211
3|/l
By Theorem letting
Ni
14

---

= -=,,,,1--] we know there exists network & E F I.N, such that 1 < We do not need constant blocks, because X' is connected. We then have
/
/clffl
N1
/ ((x) - f(x)
| f112 - x [+(x) (x))
+
<|lsll
N1 / dπ(x)) +
311S1:
(3 + +0)1111
N1
N1
A.3 Distribution of sampled networks
In this section we prove certain invariance properties for sampled networks and our proposed distribution. First, we define the distribution to sample the pair of points, or equivalently, the parameters. Note that X' is now any compact subset of IR as long as AD(X)= > 0, where AD the D-dimensional Lebesgue measure.
As we are in a supervised setting, we assume access to values of the true function f. and define y f(X).. We also choose a norm II-Iby over N2, and norms I|-1|x; over IR A for each 1 - 1, ...., L. For the experimental part of the paper, we choose the - norm for II-Ily and for 1 1, L, we choose the L norm for I|- We also denote N Σ Nr as the total number of neurons in given network, and N; = Ek= Ng. Due to the nature of sampled networks and because we sample each layer sequentially, we start by giving more precise definition of the conditional density given in Definition 2 As a pair of points from X' identifies a weight and bias, we need distribution over X22N, and for each layer condition on sets of 2. points, which then parameterize the network ((I-1) by constructing weights and biases according to Definition { Definition 7.
Let be compact, An(xt) > O, and f: IRD - RRNZIA be Lipschitz-coninnuni w.r.f. the metric spaces induced by I1-Ily and |-1|x. For any 1 E 2 L}. setting e = 0 when I = and otherwise e > O, we define
1lf(z))) - f(ab')) )(b }|b>
(1) (2) qi F0 50
((-1)=
1 # x
max (1101 11-1lxx 1,
O,
otherwise,
where x0 ,00 (0) (2) E X. ( = (x()))xx)))) and (2, Φh (x)-)) with the network (11-1)
parameterized by pairs of points in 8 Then, define the integration constant Ct- -xxx oi dx. The Ilaayered density pf is defined as
ifC
pf
otherwise.
A2D(Xxx))
Remark 6. The added e is there ensure the density bounded, but not needed when considering the first layer, due to the Lipschitz assumption. Adding > for = 1 is both unnecessary and affects cquivariant/invarint results in Theorem g included.
We drop the superscript wherever it is unambiguously
We can now use this definition to define the probability of the whole parameter space X22 i.c., given an architecture provide a distribution over all weights and biases the network require. Let X' = 2N i.e., the sampling space of P with the product topology, and D 2.N D as the dimension of the space. Since all the parameters is defined through points of X x X, we may choose an arbitrary ordering of the points, which means one set of weights and biases for the whole network can be written as 1
{a/ x1()) Fi=1
Definition 8. The probability distribution P3 over X have density p.
1.
(1) (2)
(1)
(1) N2
x (2) Ny itt X
p
1 2
Pt
a
145
with
X
N4 U
No
Nots
15

---

It is not immediately clear from above that P is valid distribution, and in particular, that the density is integrable. This what we show next.
Proposition 1. Let X C IRD be compact, (D(X) O, and be Lipschitz continuous w.r.l. the metric spaces induced by I-lly and I|-1|x.. For fixed architecture {Ni]i=v the proposed function is integrable and
{ pddD= =1.
therefore follows that P is valid probability distribution.
Proof. We will show for each I 1, 1, L that is bounded a.e. and is nonzero for at least one subset with nonzero measure. There exist C X such that pi (A) + 0 and 222 > 0, as either C₁ > 0 or pt is the uniform density by Definition and (2 X) 0 by assumption and the product topology.
For let Kı zz(), ,x(2) X. When I 1, for all X1-1 X2N; 1, we have that there exist constant K; > 0 due to continuity and compactness, such that
be the Lipschitz constant. Then (x(11) ((())))(2)) by assumption of f for all
K2
(1(x x (2)
Xi) S max
(2 x))
As is a multiplication finite set of elements, we end up with
0 0< pdd < f II
Kı (
+ Ki + A20 x 2)) dAn
1=1
L max Ni (
Kr + + A2d x x))
) 1 AD(d) 00.
1=1
using the fact that 0 < (p()) < co and Xn being the product measure, implies 0 < >x( < co. Due to the normalization constants added to q. we see pt integrates to one. This means / is valid distribution of X. with implied independence between the neurons in the same layer.
One special property of sampled networks, and in particular of the distribution P, is their invariance under both linear isometries and translation (together forming the Euclidean group, i.c., rigid body transformations), as well as scaling. We denote the set of possible transformations as H(D)
R {((0) x O(D) x R. with O(D) being the orthogonal group of dimension D. We then denote A,c = H E H(D) as (xx) = aAæ + where x E X. The space H2(D) S H are all transformations such that f: X' + R is equivariant with respect to the transformations, with the underlying metric space given by I-lly. That is, for any H (D),), there exists H' E H((N++1). such that (*)( w.r.t. I1- Note that often the H' will be the identity transformation, for example by having the same labels for the transformed data. When H' is the identity function, we say f is invariant with respect H. In the next result, we assume we choose norms || xa and Il-lly, such that the orthogonal matrix part of H is isometric w.r.t. those norms and the canonical norm ||-I|, as well as continue the assumption of Lipschitz-contiuuuus/ f.
(f(())) where x E X', and the orthogonal matrix part of H' is isometric
Theorem Let H E (D) Φ, be two sampled networks with the same number of layers L and neurons N1...., NL, where क. X' - N2N1 and ē H + Ne+1, and f: X - R. N441 is the true function. Then the following statements hold:
(1) If f = -H(
(1) and a H H(xo))
(2)) ) for all i = 1, 2.....N.. then
(11) = =+()(H())) for for all x X.
(2) I is invariant w.r.t. H: + FS
Ni, (X) if and only if FS Fi. (H(()) such
(H()),
that ((x) (xx) for all X.
(3) The probability measure P over the parameters is invariant under H.
16

---

Proof. Let H = (a, A,C). Assume we have sampled a0. i == 1,2,.... .I. The points sampled determines the weights and biases in the usual way, giving
H( and -0. -v for all
((111,112-5)) -03)) =
To.
(2)
(1)
(1)
)
||
(2)
uu, 112
(1)
10,3
(2)
A(x A(x-=100 ((-=) ))
00,
|LA4 (2) -0
(1)
a
0,
A(x - =6.1)
a2
|LA(20. (2)
(1)
2 0,
(2) (1)
aA(x - - 1)
0o 0,
0.1
||aA(10,)
(2) J
(2)
10. + c 10
.aAxx + c 2o.i (2)
-0))
aA
||aA(=0.1 +
(2)
To -c)112
(1)
H H ((
(()) - H((EO))
(- (2) - H (a )112
(11)
NN. for all x E X, & E HX), and i 1,2, N1, Which implies that (1) holds.
Assuming/ is invariant w.r.t H. then for any & E Fi..N (X), let X = f21, #1, N we can then choose (X) as points to construct weights and biases in the first layer of á and by (1), we have X1 = 2 (1) (x') = ( (H()) = &. As the sampling space is the same for the next layer, we see that we can choose the points for the weights and biases of ④ such that 2 = &. where 1= 1, 2, ... L. As the input after the final hidden layer is also the same, by the same argument, means the weights in the last layer must be the same, due to the loss function L. in Definition i the same due to the invariance assumption. Thus, (zx) (+((())) for all E X. As H is bijective, means the same must hold true starting with & and constructing 4 and we conclude that (2) holds.
E X, letting (a') be the set such that g(aAr + c) = a' A' (xx) + c', and č₁ Cj be the normalization constants over the conditional density Pt, for HX)) and X' resp. We have for the conditional density when = is,
For any distinct points
1 ( + c) (1 (1) + c)lly Ō [( +c (1) cllx
Pi
1 (x) + - a' ((((x( e'lb
G
||Ax((2) cAr(1) llx
|a'l (1f(z(2) f(x()))lx |a'l
Pi (2(1))
aaCi ||x(2) - xx1) (a/ci
With similar calculations, we have
|a| |a'|
|a| |a') xxx
/ Pı (H) H(:))dodz=
|a| |a'l la'l |a| xxxx pı p1 2)dadz C1-
Hence, the conditional probability distribution for the first layer is invariant under H, and then by (1) and (2), the possible sampling spaces are equal for the following layers, and therefore the conditional distributions for each layer is the same, and therefore P is invariant under H.
Remark 7. Point (2) in the theorem requires f to be invariant w.r.t. H. This is due to the fact that the parameters the last layer minimizes the implicitly given loss function L, seen Definition We have rarely discussed the loss function, it depends on what function we are approximating.
17

---

Technically, (2) also holds as long as the loss function is not altered by H in way that the final layer alters, but we simplified it be invariant, as this is also the most likely case to stumble upon in practice. The loss function also appears in the proofs given in Appendix A. and Appendix A.2 Here both uses, implicitly, the loss function based on the uniform norm.
B Illustrative example: approximating Barron function
All computations for this experiment were performed on the Intel Core i7-7700 CPU @ 3.60GHz x 8 with 32GB RAM.
We compare random Fourier features and our sampling procedure on a test function for neural networks [4]] f(x) = /3/2 alle= - || + allea), ), with the constant vector a E I2 defined by aj 2 1. For all dimensions d, sample 10,000 points uniformly at random in the cube [-1, 1] for training (i.e., sampling and solving the last, linear layer problem), and another 10,000 points for evaluating the error. We re-run the same experiment with five different random seeds, but with the same train/test datasets. This means the random seed only influences the weight distributions in sampled networks and random feature models, not the data. Figure 8/shows the relative 1,2 error in the full hyperparameter study, i.e. in dimensions E 2,,2,3, 4,5, 5, TO} (rows) and for tanh (left column) and sine activation functions (right column). For the random feature method, we always use sine activation, because we did not find any data-agnostic probability distributions for tanh. Figure shows the fit times for the same experiments, demonstrating that sampling networks are not slower than random feature models. This is obvious from the complexity analysis in Appendix F and confirmed experimentally here. Interesting observations regarding the full hyperparameter study are that for one dimension, d = 1, random feature models outperform sampled networks and can even use up to two hidden layers. In higher dimensions, and with larger widths more layers, sampled networks consistently outperform random features. In d 10, sampled network with even single hidden layer is about one order of magnitude more accurate than the same network with normally distributed weights. The convergence rate of the error of sampled networks with respect to increasing layer widths is consistent over all dimensions and layers, even sometimes outperforming the theoretical bound of 0/2-)
C Classification benchmark from OpenML
The Adam training was done on the GeForee 4x RTX 3080 Turbo GPU with 10 GB RAM, while sampling was performed on the Intel Core i7-7700 CPU @ 3.60GHZ x 8 with 32GB RAM.
We use all 72 datasets in the "OpenMLL-CC1 Curated Classification benchmark" from the "OpenML Benchmarking Suites" (CC-BY) 44 which is available on openml betps://openns .orgp/mloor/// wtw.rrttttttsssssccceeeeeeeeeeee
gearchhttype-benchmarr wtacchhnnnkkkoorere k& taskkorttttaasseoomm wwcecks_innicuuee htwpo/uddddssuuddyyyeeettasessee
download the benchmark datasets. The 3 From all datasets, we use at most 5000 points. This was done for all datasets before applying any sampled or gradient- basedd approach, because we wanted to reduce the training time when using the Adam optimizer. We pre-process the input features using one-hot encoding for categorical variables, and robust whitening (removal of mean, division by standard deviation using the Robust.Scaler class from scikit-learn). Missing features are imputed with the median of the feature. All layers of all networks always have 500 neurons. For Adam, we employ early stopping with patience=3, monitoring the loss value. The least squares regularization constant for sampling is 10-10, We split the data sets for 10-fold cross-validation using stratified k-fold "StratifiedKee accuracy scores and times over the ten folds (Figure 4 in the main paper).
We use the OpenML Python API (BSD-3 Clause)
22
hyperparameters used in the study are listed in Table
class from scikit-learn), and report the average of the
D Deep neural operators
D.1 Dataset
To generate an initial condition ugg we first sample five Fourier coefficients for the lowest frequencies. We sample both real and imaginary parts from normal distribution with zero mean and standard
18

---

12a
undarffoffutes Le1 samiling Lee)
undonfcitee.. Le Samping Lel
Bel Fener dm
andontiatures L-2 amppnn
20-4
samoiing Lin2
uandorfeat.res. bnd sampling. Lod
andermaatiess L-3 samping
10-4
inforence
reference-m m
10-9
reteretee
10 1
10
12
with
Network with
sampiigg
and. Perro drew
andenfeaturss
20
anderfestuess, samping Lo3
refererce mil
20-1
10
10t
Network with
Network wath
10a
andarffuatttss Le1
10"
andornlatuus 1:1
samcling Loe
d smpping L-1
andarfeattrrss Lm2
not frncr sirw
anjonfeaturss Le2
10-3
samsiing Lan
Sa Samping Le2
randorfeat-res, Led
andombestuess Lo
sampling Lod
ampiing
reforence
20-1
referrce
reference my-
10
10 witth
12
15
Network
andarfaatatts,
Rat of crcrr sloed
smpping
anderneettues
L-d
reference m-10
10
10
10-
10-1
10
10t Network witth
19
Network with
125
addanfaatuuss Le]
10"
andomffaturss, Le]
mollnng Led
da samplngg L-1
iddmfeaaturss Lm2
caner dinss
tandommittusss. Le2
10-1
samiiing Lun
Sa sampling Le
tandomiiatturea Le
samplingg Lec
Sa sampling Led
referenceim mn
10--
reference my
refersnce
Network wilth
Ketwork
andurffatiiss
andemnlatturs,
caror dire19
Sampingg
campling
10
10.
20m
10-
107
30a
12
12'
Network widt)
Network with
Figure 8: Relative 2 approximation error for random features (using sine activation) and sampling (left: using tanh activation, right: using sine activation), with input dimensions d' = 1,2, 3, 4, 5 and 10. Results averaged over five with different random seeds.
deviation equal to five. We then scale the k-th coefficient by 1/(k: + 1)2 to create a smoother initial condition. For the first coefficient corresponding to the zero frequency, we also set the imaginary part to zero as our initial condition should be real-valued. Then, we use real inverse Fourier transform with orthonormal normalization (np fff.ffiiirm generate initial condition with the
19

---

rnndorfeattness bed
undomiiatee.. Le 20 Samplng Lel
Sansingg Lee
301
andarfeatinss. Lm2
tammmtii din-1
andonnicttees. L-2 samping
sameing L-2
Rk ReSmetss
anndermaattuns L-3 samplngg
samsing Led
30"
10-1
20
12 Network witth
Network w dts
100
Le]
10t
andendeatuess
Le2
100
inddrrfeatuess
sampling Lxd
Pt tei
andernisttees, samplng Le3
20
1.a Network wisth
andombhat..ee L:]
andommlatuus 1:1
sampiigg Lid
10t
do samping L-1
andirfostinss Lm2
andonfeaturss L=2
samsling Lm2
Sa samping Le2
10a
andorffatiiss,
owmping
muure at
10"
samplnng
andommesttrss Lo
1.7
20
125
Network
Network wisth
1.00
10t
smmpingg
oympling Lid
1: bu
1.0
Fr
20-2
10-1
16
10
Network w
Network it whith
indorffatttt Led
andomnfatuuess Le] da camping Lod
swmtiing Lind
101
randorteat.res. Lod
Fttims dm-3
sandommaaturss. Lo2 Sa sampling Lo
samping Lod
2.0
andrrfaaturss Lod
1.a
candoniicaturea. L-3
sampiing Lec
Sa sampling Len
Fermm
100
10
andomnlatturss
sampiigg
PR dmm12
Retimete)
1.7
sampling
10-1
107
10'
20"
Network o de
Notwork wisth
Figure 9: Fit times in seconds for random features (using sine activation) and sampling (left: using tanh activation, right: using sine activation), with input dimensions 1,2,3, 3, 4, and 10. Results averaged five with different random seeds.
discretization over 256 grid points. To solve the Burgers' equation, we use classical numerical solver (scipy. inntegatteee.... solve_ive and obtain solution μı at / = This way, generate 15000 pairs of (ug, w1) and split them between train (9000 pairs), validation (3000 pairs), and test sets (3000 pairs).
20

---

Table 3: Network hyperparameters used in the OpenML benchmark study.
Parameter
Value
Shared
Number of layers
1, 1,2,3, 4,5]
Layer width Activation
500
tanh
Sampling
1 //-regularization
10-5
Adam
Learning rate
10
Max. epochs
100
Early stopping patience
3
Batch size
64
Loss
mean-squared error
Table 4: Network hyperparameters used to train deep neural operators.
Parameter
Values
Note
Shared
Number layers
1, 1,2,
Layer width
256, 512, 1024, 2048, 4096] 8, 16,62
Number of modes
Number of channels
16,32
Activation
tanh
Sampling Adam
I -regularization Learning rate
10-10,10-8,100
10-6
10-5,5-10 1000 10-10-4... 5 10-4
FCNs and POD-DeepONet FNO
10 10-4,5 4,10
10-3
Weight decay
0
Max. epochs
2000
FNO, FCN in signal space
5000
FCN in Fourier space
90000
POD-DeepONet
Patience
100
FNO, FCN in signal space
200
FCN in Fourier space
4500
POD-DeepONet
Batch size
64
FCNs and FNO
full data
POD-DeepONet
Loss
mean-squared етгог
FCNs and POD-DeepONet
mean relative -ossoss
FNO
D.2 Experiment setup
The Adam training was done on the GeForce 4x RTX 3080 Turbo GPU with 10 GB RAM, while sampling performed on the 1x AMD EPYC 7402 @ 2.80GHz 8 with 256GB RAM. We the sacred package https:/ggihub.cco///S///asa search.
MIT license
337 to conduct the hyperparameter
We perform a grid search over several hyperparameters (where applicable): the number of lay- ers/Fourier blocks, the width of layers, the number of hidden channels, the regularization scale, the learning rate, and the number of frequencies/modes to keep. The full search grid is listed Table
Adam With the exception of FNO, with Adam. For FNO, we train with the default option, that is, with the mean relative -loss. This loss is based on the Hormorm for one-dimensional function f defined as
the squared error the loss function when training
|
|f + ||
For all the experiments, we use the mean relative I error as the validation metric. We perform an early stopping on the validation set and restore the model with the best metric.
DeepONet We use the deepxde package
LGPL-2.1 License
(55) to define and train POD-DeepONet for our dataset. After defining the model, we apply an output transform by centering and scaling the output with 1/p, where p is the number of modes
21

---

comv
fon
lnrwer
Figure 10: The architecture of the sampled FNO.
keep in the POD. To compute the POD, we first center the data and then use np. www.nln..llee... eigh to obtain the modes. We add two callbacks to the standard training: the early stopping and the model checkpoint. We use the default parameters for the optimization and only set the learning rate. The default training loop uses the number of iterations instead of the number of epochs, and train for 90000 iterations with patience set to 4500. By default, POD-DeepONee uses all the data available as batch. We ran several experiments with the batch size set to 64, but the results were significantly worse compared to the default setting. Hence, we stick to using the full data as one batch.
We use the neuralop package with slight modifications. We changed the trainer. py to add the early stopping and to store the results of experiments. Apart from these changes, we use the functionality provided by the library to define and run experiments. We use batch size 64 and train for 2000 epochs with patience 100. addition to the hyperparameters considered for other architecture, we also did a search over the number of hidden channels (32 or 64). We use the same number of channels for lifting and projection operators.
FNO
MIT license
42
38)
FCN For both fully-connected networks in our experiments, use PyTTorch framework define the models. For training a network in Fourier space, we prepend a forward Fourier transform before starting the training. During the inference, we applied the inverse Fourier transform compute the validation metric. We considered using the full data as a batch, but several experiments indicated that this change worsens the final metric. Hence, use batch size 64 for both architectures.
Sampling FNO Here, we want to give more details about sampled FNO. First, we start with input un and append the coordinate information it as an additional channel. Then, we lift this input to a higher dimensional channel space by drawing 1 x convolution filters from normal distribution. Then, we apply Fourier block which consists of fully-connected networks in Fourier space for each channel. After applying the inverse Fourier transform, we add the input of the block to the restored signal as a skip connection. After applying several Fourier blocks, we learn another FCN signal space to obtain the final prediction. We can see the schematic depiction of the model in Figure I0 We note that to train fully-connected networks in the Fourier space, we apply Fourier transform to labels and use it during sampling target functions. Similarly to the Adam-trained FNO, we search over the number of hidden channels we use for lifting.
D.3 Results
We can see the results of the hyperparameter search in Figure IT We see that sampled FNO and FCN in Fourier space perform well even with a smaller number of frequencies available, while DeepONet requires more modes to achieve comparable accuracy. We also see that adding more layers is not beneficial for sampled networks. A more important factor the width of the layers: all of the sampled networks achieved the best results with the largest number of neurons.
For the Adam-traines models, we note that we could not significantly improve the results by increasing the widths of the layers. Possibly, this due to a limited range of learning rates considered in the experiments.
22

---

FCN,
layencs
FCN, Fourforr
POD DespONet.
layerts)
1001-
10
10
liver witth
layer with
lnser AMM
lever witt layerts)
toporate aner
1011
signal space. leyeris)
space. layeris)
PO0-DeepONet: layeris)
20mm modes
adom. modes
10
10-1
Swim: modes
lyyer width
layar with
lnger AMd
lagvr witth
SWBTI rooees
ICN, signal space, layer(s)
LNN, hourier space, layer(s)
POU-JeepCCeet layer(s)
enue
FNG, layer(s)
1000
2000 byyer witth
3000
4020
1000
2000
2003
4000
1000
2200 5000
4002
1003
2000
3000 4030
bayer with
lnyer AMP
byyr w6th
Figure 11: Comparison of different deep neural operators trained with Adam and with SWIM algorithm. FNO with Adam has no dependency on a layer width. Thus, we show results for FNO trained with Adam chose the values that produce the lowest error on the validation set. We repeat each experiment three times and average the resulting metries for the plotting. The error is computed the validation set.
straight line in all rows. For the hyperparameters not present in the plot,
E
Transfer learning
This section contains details about the results shown in the main paper and the supporting hyper- parameter search concerning the transfer learning task. The source and target tasks of transfer learning, train-test split, and pre- ereitri models are the same in the main paper. We describe the software, hardware, data pre-processing, and details of the sampling and the Adam training approach. Note that the results shown here are not averaged over five runs, was done for the plots in the main paper.
Software and hardware We performed all the experiments concerning the transfer learning task in Python, using the TensorFlow framework. We used GeForce 4x RTX 3080 Turbo GPU with 10 GB RAM for the Adam training and a 1x AMD EPYC 7402 socket with 24 cores @ 2.80GHz for sampling. We use the pre- pre-trained models from Keras Applications which are licensed under the Apache 2.0 License which can found at https: /ttp://gtttttbuuu wwwoo//eerasse. 12.0/LICENSE
Pre-processing of data The size of images the ImageNet data set is larger than the ones in CIFAR- 10, so we use a bicubic interpolation to upscale the CIFAR-10 images to dimensions 224 x 224 x 3. We pre-process the input data for each model the same way it was pre-processed during the pre- training ImageNet. Moreover, we apply some standard data augmentation techniques before training, such as vertical and horizontal shifts, rotation, and horizontal flips. After pre-pre pre-processing. the images are first passed through the pre-trained classification layers and global average pooling layer. The output of the global average pooling layer and classification labels serve as the input and output data for the classification head respectively.
Details of the Adam training and sampling approaches We find the weights and biases of the hidden layer of the classification head using the proposed sampling algorithm and the usual gradient-based training algorithm.
First, in the Adam-training approach, we find the parameters of the classification head by iterative training with the Adam optimizer. We use a learning rate of 10-3, batch size of 32, and train for 20 epochs with early-stopping patience of 10 epochs. We store the parameters that yield the lowest loss on test data. We use the tanh activation function for the hidden layer, the softmax activation function for the output layer, and the categorical cross-entropy loss function with regularization.
Second, in the sampling approach, we use the proposed sampling algorithm to sample parameters of the hidden layer of the classification head. We use the tanh activation function for the hidden layer.
23

---

Once the parameters of the hidden layers are sampled, an optimization problem for the coefficients of linear output layer solved. For this, the mean squared error loss function without regularization is used.
Unless mentioned otherwise, the above-mentioned setup is used for all the experiments in this section.
E.1
Sampling Vs Adam training
Figure 12 compares the train and accuracy for different widths (number of neurons in the hidden layer of the classification head) using three pre-trained neural network architectures for the Adam training and sampling approaches. sampling approach results in higher test accuracy than the Adam training approach for sufficiently higher widths.
the main paper, we observe that for the models, the
The sampling algorithm tends to over-fit for very high widths. The loss on the train data for the iterative training approach decreases with width, particularly for the Xception network. This suggests that an extensive hyper-parameter search for the iterative training approach could yield higher classification accuracy on the train data. However, as shown in the main paper, the iterative training approach can be orders of magnitude slower than the sampling approach.
Adam: Test data
Adam: Train data
Sampling: Test data
Sampling: Train data
100.0
97.5
95.0
92.5
90.0
85.0
82.5
80.0
10a
10'
101
10
10
10'
10²
10'
10*
Width
Width
Width
Figure 12: Left: ResNet50. Middle: VGG19. Right: Xception.
E.2 Sampling with tanh Vs ReLU activation functions
This sub-section compares the performance of the sampling algorithm used to sample the weights of the hidden layer of the classification head for tanh and ReLu activation functions.
Figure 13 shows that for ResNet50, the accuracy with tanh is similar to that obtained with ReLU for a width smaller than 2048. As the width increases beyond 4096, test accuracy with ReLU is slightly better than with tanh. However, for VGG19 and Xception, test accuracy with tanh is higher than equal to that with ReLU for all widths. Thus, we find the sampling algorithm with the tanh activation function yields better results for classification tasks than with ReLU.
On the training dataset, tanh and ReLU yield similar accuracies for all widths for ResNet50 and Xception. For VGG19, using the ReLU activation function yields much lower accuracies the train and test data sets, especially as the width of the fully connected layer is increased. Thus, we observe that the tanh activation function is more suitable for classification tasks.
E.3 Fine-tuning
There are two typical approaches transfer learning: feature extraction and fine-tuning. In feature extraction, there is need to retrain the pre- treitrained model. The pre-trained models capture the

---

tanh: Train data
tant: Test data
ReLU: Train data
ReLU: Test data
100.0
95.0
92.5
Accuracy
90.0
87.5
80.0
10a
10a
10a
10a
10a
10
Width
Width
Width
Figure 13: Left: ResNet50, Middle: VGG19, Right:Xception
essential representation/feature from similar task. One only needs to add new classifier (one or more fully connected layers) and find the parameters of the new classifier.
In fine-tuning, after the feature extraction, some all the parameters of the pre-trained model (a few of the last layers or the entire model) are re-trained with much smaller learning rate using typical gradient-basee optimization algorithms. Fine-tuning is not the focus of this work. Nevertheless, is essential to verify that the weights of the last layer sampled by the proposed sampling algorithm can also be trained effectively in the fine-tuning phase. The results shown in Figure
we observe that for certain widths (512, 1024, and 4096), sampling the last layer followed by fine-tuning the entire model yields slightly higher test accuracies than training the last layer followed by fine-tuning. For widths 2048, 6144, and 8192, for some models, sampling the last layer, followed by fine-tuning, is better, for others, training the last layer, followed by fine-tuning, is better.
In Figure 14
Nevertheless, these experiments validate that the parameters of the last layer sampled with the proposed algorithm serve good starting point for fine-tuning Moreover, the test accuracy after fine-tuning is comparable irrespective of whether the last layer was sampled or trained. However, as we show the main paper, sampling the weights the feature extraction phase takes much less time and gives better accuracy than training with the Adam optimizer for appropriate widths.
E.4
One vs two hidden layers in the classification head
The goal of this sub-section is to explore whether adding additional hidden layer in the classification head leads to an improvement in classification accuracy. We keep the same width for the extra layer in this experiment.
Figure 15 compares the train and test accuracies obtained with one and hidden layers in the classification head for different widths.
Figure 15 (left) shows that unless chooses very high width with the sampling approach >= 6148, adding an extra hidden layer yields lower test accuracy. On the train data, the sampling approach with hidden layers results in lower aceuracy for all widths in consideration.
Figure 15 (right) shows that with the Adam training approach, adding an extra hidden layer yields a lower test accuracy for all the widths in consideration. For lower widths, adding more layers results in over-fitting We believe that the accuracy on the train data for higher widths could improved with search. However, adding extra layer increases the training time too.
an extensive
25

---

Adam
Adam + Fine-tuning
Sampling
Sampling Fine tunettnnng
Wicth: 512
1024
2048
100
95
Test accuroc)
90
85
80
4096
100
95
Test accuracy
90
85
60
ResNer50
VGG19
Xception
ResNer50
VG619
Xception
ResNer50
VG619
Xception
Figure 14: Comparison of test accuracies obtained by the sampling approach followed by fine-tuning and Adam training approach followed by fine-tuning for different widths
Code repository and algorithm complexity
The code to reproduce the experiments from the paper can be found
An up-to-date code base is maintained
Python 3.8 is required to run the computational experiments and install the software. Installation works using "pip install -e in the main code repository. The python packages required can be installed using the file requirements. txt file, using pip. The code base contained in the folder swimnetworks the experiments and code for hyperparameter studies in the folder experiments.
We now include a short complexity analysis of the SWIM algorithm (Algorithm in the main paper), which is implemented in the code used in the experiments. The main points of the analysis can be found in 5
There are two separate parts that contribute to the runtime. First. consider sampling the pa- rameters of the hidden layers. Letting N = the number of neurons in any given layer and the input dimension, and M being the size of the training set. The size of the training set also limits the number of possible weights bi- sample, namely M The time complexity to sample the parameters of the
i.c., the maximum of
ases that hidden layers is O(L M (minq [/M], M) + N²)). We can further refine the expression with O M (min([Ni:M]] M M) + N₁ Nr-1)). Several factors contribute to this runtime. (1) The
26

---

1-Layer: Train data
1-Layer: Test data
2-Layers: Train
2-Layers: Test data
100.0
97.5
95.0
Accuracy
90.0
87.5
85.0
80.0
10a
10a
10'
102
10a
10a
Width
Width
Figure 15: Left: Sampling, Right: Adam training
Table 5: Runtime and memory requirements for training a sampled neural networks with the SWIM Assumption assume the output dimension
algorithm, where N max NY, N is less than or equal to N. Assumption (II) assumes in addition that N < M2, i.e., number of neurons and input dimension less than the size of dataset squared. Assumption (III) assumes fixed architecture.
Runtime
Memory
Assumption (I) Assumption (II) Assumption (III)
OLL ((min M1+N2) O(M min([N/M] M) + LN3) O(L M(IN/M N²))
O(M [N/M + LN2)
(MM)
O(M)
number of layers increases the number of samples. (2) Computing the output after / - layers for the entire dataset to compute the space from which we construct the weights, hence the term M). When the
Ni -N-11 M. (3) Computing M Mi probabilities, where Mi minf [Ni/M]] MM, size of the hidden layer is less than the number of training points - which is often the case we compute .M probabilities
depending on scaling constant. On the other hand, when the size of the layer is greater than or equal to M², we compute in worst case all possible probabilities, that is, 2 probabilities. The last contributing factor to sample Nj pair of points, that the expression is dominated by the term Ni N1 M. We are often interested in fixed architecture, or at least to bound the number neurons in each hidden layer to be less than the square the number of training points, i.e., N < M Adding the latter as an assumption, we end up with the runtime OLL M ([N/M]] + N2)).
For the second part, we optimize the weights/biases WL+11 bi+1 to map from the last hid- den layer the output. Assume that use the SVD decomposition inverse and subsequently solve the least squares problem. The time complexity in general is then O(M - .N. min (M, Nz) +N M NN++1). Again, if we make the reasonable assumption that the number of training points is larger than the number of hidden layers, and that the output dimension smaller than the dimension the last hidden layer, we find (MM which can be rewritten to O(MN2). With these assumptions in mind, the run time for the full training procedure, from start to finish, is (l. M(NN/M] + N2)), and when the architecture is fixed, we have ((M) runtime for the full training procedure.
compute the pseudo-
27

---

In terms of memory, at every layer 1, we need to store the probability matrix, the output of the training set when mapped through the previous I - 1 layers, and the number of points we sample. This means the memory required is O(M [N/M]] + NI+1 Nr.. In the last layer, we only need the image of the data passed through all the hidden layers, as well as the weights/biases, which leads to O(M + NL+1 Nr). We end with the required memory for the SWIM algorithm is O(M [N/M] + L.7).
28


Reviews:
[{"review_id": "rQ5ytyxJfz", "reviewer": "Reviewer_LFwn", "summary": "This work presents a method for sampling the parameters of a deep neural network, including the final task-specific layer. In contrast to prior work that leverages Bayesian deep learning or generative models to learn the sampling distribution, this work presents a sampling algorithm that defines a data-dependent sampling distribution, so no gradient descent is used to train any parameters.  \n\nThis sampling algorithm is compared with conventionally trained networks (with Adam) on a number of different tasks, where the sampled networks are shown to perform on par or somewhat better than the trained counterparts. Importantly, the sampling procedure faster than iterative training. Currently, this sampling algorithm is restricted to fully connected neural networks. ", "questions": "I'm curious if there is any connection to NTK or to NNGP models here? Both employ a similar property of converging on a solution as the width of the network tends to infinity -- and are data dependent, though in a different way. ", "limitations": "I think the limitations were adequately addressed, as this work applies to small neural networks there shouldn't be any concerns. ", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Being familiar with the (sometimes fraught) work on Bayesian neural networks, I appreciate that this work designs an algorithm for effective sampling of neural network weights that is not computationally intractable. This is a new perspective to me, and I found the theoretical results, in particular theorems 1 & 2 to be quite useful in establishing that the sampling algorithm is sound.  \n\nI found the empirical results to be interesting, especially the transfer learning / CIFAR-10 experiment that showed comparable test-time performance to an Adam trained network while being far more efficient to \"train\". ", "weaknesses": "I'll start by saying that I have very unfamiliar with this line of work, though work in learning to sample neural network parameters is relevant to me. I am quite certain that the main novelty of this paper was missed by me.\n\nThat being said, I found this paper to be impenetrable even at a high level. Any confusion I have with the sampling distribution for example, is not alleviated by any satisfactory explanation in the text. I think the only people who will be able to digest this paper in its current form are those completely familiar with this line of work. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "This high-level explanation of the paper may help: instead of training all parameters of hidden layers with gradient-based methods, we construct each combination of weight and bias using pairs of data points from the training set, i.e., $(x_1,x_2)$. As there are usually many more pairs of points in a dataset than we need for the number of neurons (each associated with a weight vector and bias value), we assign probabilities to pairs. The probability for a pair to be chosen is proportional to the finite difference $|f(x_2)-f(x_1)|/|x_2-x_1|$, where $f$ is the function we want to approximate. The higher the absolute value of the finite difference, the more likely we pick that data pair for a weight in the network. We use finite differences so that weights are more likely distributed around high gradients of the target function than in flat regions.\nIn the context of classification and using tanh as an activation function, an informal explanation behind the theory is that we pick two points $x_1$ and $x_2$ for each neuron, where the two points belong to different classes. In addition, we try to pick them as close to the decision boundary as possible. Then, by letting the bias be set as described in the paper, we end up assigning positive values to points that are closer to $x_1$ and negative values to points closer to $x_2$. Then, the last set of weights can use this information to perform the final classification, as the decision boundary separates the two points. \n\nRegarding NNGP/NTK:\nThere certainly is a relation, but not an immediate one. Our sampling distribution is one of the differences from the models considered in the NNGP/NTK literature. Classically, the weights of a neural network are initialized with a normal distribution. In our case, we use the distribution from Equation 2. Yet, as we sample parameters i.i.d., we can still consider infinitely wide sampled networks and apply the central limit theorem to get a process similar to NNGP.\nThe NTK describes the training dynamics of a network under gradient descent. Sampled networks do not use gradient optimization for hidden layers, so we cannot define such a kernel evolution. However, one could consider only the last layer of a sampled network and assume gradient descent optimization for its weights. This would make it possible to recover a variation of NTK."}, {"review_id": "MUJVDWCqdl", "reviewer": "Reviewer_jKG3", "summary": "This work provides a method to sample weights of a neural network in a data-driven manner, such that expensive iterative gradient calculations and optimization can be avoided. The proposed sampling technique sets weights and biases of fully connected networks with ReLU and tanh activations based on pairs of training data points. This mechanism is used for all but the last layer of the network, which is then trained in a gradient-based manner at the very end. This method constructs neural network predictors orders of magnitude faster than some iterative training techniques, while matching them in performance. Experiments include a classification becnhmark, deep neural operators and a transfer learning setting.", "questions": "- As above, how would the theory and/or experiments change for different loss functions and different optimizers used as comparisons?\n- The authors provide a sampling method for fully connected layers and state that architectures like convolutions or transformers cannot be sampled with their method yet. Since convolutions ultimately implement linear transformations, is it possible to leverage that view of the convolution operator to extend this sampling scheme? If not, what are the concrete challenges to be solved for extending such a method to convolutional networks or transformers? \n- Similarly, what are the challenges to constructing sampled networks for unsupervised or self-supervised tasks?\n- The method intuitively provides greater interpretability since the mechanism of sampling weights is given. Do the authors have any thoughts on how this may help compute things like influence functions to answer questions like \"what is the influence of a given training point on a given prediction\"?", "limitations": "Authors clearly and satisfactorily state the limitations and impact of their work. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of data-driven sampling of neural networks, as opposed to the random features model, is an interesting and original one. This paper sufficiently demonstrates the ability of their method to compete with iterative training methods while being much more efficient. \n- The invariance properties of the sampling scheme remove the need for several data preprocessing techniques, which often require significant domain knowledge to determine. \n- The theoretical analysis and experimental verification are sound. Proof sketches provided in the main paper are useful to gain insight into the method.\n- Given the computational expense of training neural networks currently, extensions of this work to larger scales would have high impact. I find the demonstration and proof of concept shown in this work to be significant.", "weaknesses": "- All the analysis seems to be done using mean squared error as the loss function. Stating whether this can be generalized to other losses and/or providing intuition on how that can be done would be useful.\n- The main iterative training technique that the proposed sampling technique is compared to is the Adam optimizer. Results using different optimizers/training techniques would strengthen the claims of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Weaknesses:\n\n * [W1] Please see our general answer on the topic of choosing different loss functions (multiple reviewers asked for this).\n * [W2] Different optimizers other than Adam should not drastically change the results in our chosen experiments, as long as they are iterative and gradient based. It may be that for some of the classification problems in Section 4, other optimizers like stochastic gradient descent or particle based methods result in slightly better results compared to Adam, but it is unlikely that they are much faster, given the highly optimized implementations in TensorFlow.\n\n Questions:\n\n * [Q1] See W1.\n * [Q2] Regarding convolutional network sampling: We have tried to extend sampling to convolution kernels, but as of now, it seems that sampling kernels is fundamentally different than sampling weights in a feed-forward network. One of the main challenges is that convolution kernels do not have a one-to-one correspondence to individual data points, so it is not easy to extend the idea of \"one data pair per weight\" into \"one pair of images per convolution kernel\". If we would use all possible sub-images of each image pair to determine good kernels, this would quickly lead to an unmanageable amount of kernel pairs. Remark 3 in (https://jmlr.csail.mit.edu/papers/volume22/20-1300/20-1300.pdf) (a paper cited by reviewer ReAz) contains a brief discussion how to convert convolutional networks to feed-forward networks, maybe this can be used as a path forward.\n\n Regarding transformers: A crude simplification of a transformer block is to apply an embedding to each token in a sequence, in such a way that the covariance matrix of the embedded sequence helps in the prediction of the output sequence. It also seems to be important to stack transformer blocks several times. At this point, the main challenge to extend sampling to transformers is how one would sample good token embedding maps without already knowing the embedding or at least the covariance (unsupervised setting). It certainly is possible to sample a transformer's last layer(s), much like our transfer learning experiment with the convolution backbones (Section 4.4).\n\n * [Q3] Regarding unsupervised, self-supervised tasks: The main challenge for our sampled networks in unsupervised tasks is that we require the target function values to fit the coefficients of the last layer. Still, the main benefit of our sampling of weights and biases, even without fitting the last layer, is to create a \"good\" set of basis functions on the data. This set can then be used in downstream tasks, including unsupervised learning, even if the data pairs are \"just\" chosen uniformly at random (i.e., not taking into account the target function values). A direction we are currently exploring is the solution of partial differential equations, where the solution is unknown (unsupervised setting), but \"good\" ansatz functions can help to solve the equation easily. Self-supervised tasks may similarly benefit from sampling. One could sample a set of weights/biases without knowledge of the target function (by sampling uniformly over pairs), solve the last layer with gradient descent, and then refine the sampled weights once a new approximation of the function is available.\n \n * [Q4] Regarding interpretability: The direct connection of weights and biases to data pairs is indeed what we think helps most to interpret the network \"internals\". This connection answers the question \"What is the influence of certain pairs of training data points on all predictions?\". Given, individual predictions, as asked by the reviewer, are more difficult to interpret because individual predictions often need multiple activation functions to be \"active\" (meaning non-zero, in the case of ReLU activation). A simple answer may be: if the training point is part of the \"active\" ReLUs weights, it is \"important\", otherwise not. How important exactly should be determined by the magnitude of the connected weight, i.e., the gradient of the ReLU function - which, also using our algorithm, means \"how close the training point is to its paired point\". For classification problems, this means \"how close is the training point to the decision boundary\", because only data pairs with differing classes are considered (otherwise the probability of choosing them is zero)."}, {"review_id": "MK3zX51KQI", "reviewer": "Reviewer_5eGE", "summary": "This paper presents an approach to training deep neural networks by introducing a probability distribution for weights and biases, which significantly reduces the necessity for iterative optimization or gradient computations. The proposed sampling scheme is data-driven, factoring in the input and output training data to sample both shallow and deep networks. The paper demonstrates the universality of the constructed networks as well as their invariance to rigid transformations and scaling of the input data. The robustness and speed of the method are shown through various test trials, including a classification benchmark from OpenML, sampling of neural operators to represent maps in function spaces, and transfer learning using well-known architectures. Overall, this approach provides a valuable direction in neural network training, promoting the efficiency of training and the interpretability of the model.", "questions": "1. In Algorithm 1, the L2 Loss function is consistently used. Can this method be adapted to accommodate other types of loss functions?\n2. Could you elucidate on the process used to select the data pairs?\n3. In the paper, you mention that this method can serve as a good starting point for fine-tuning. However, in Figure 5, even though the initial accuracy of the Sampling method surpasses that of ADAM, the test accuracy after fine-tuning falls short compared to ADAM + Fine-tuning. Can you offer an explanation for this outcome?\n", "limitations": "This paper adequately discusses the limitations, primarily focusing on the following aspects: the sampling strategy is not well-suited for convolutional or transformer networks, the method faces challenges in handling implicit problems, and a theoretical analysis of convergence rates is not provided.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.  This is a well-written paper with clear descriptions and detailed formula derivations.\n2.  The data-driven sampling scheme demonstrated in this paper addresses several challenges posed by random feature models compared to iterative optimization methods in supervised learning. Numerical experiments highlight its superiority in training time, accuracy, and interpretability against the ADAM optimizer. Further, its application in transfer learning indicates its potential for broader tasks.", "weaknesses": "1. The experiments in the paper only compare this method with iterative optimization methods, specifically ADAM. However, it lacks comparative experiments with related non-iterative training methods, thus not fully showcasing its potential advantages in non-iterative training tasks.\n2. There is a notable lack of analysis regarding the convergence rate within the paper.\n3. The technique of using data pairs to build model weights is akin to the approach by Galanis et al.[21]. The paper, though, does not provide a sufficient discussion about this similarity, which could potentially undersell the novelty of the methodology.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Regarding weaknesses: \n * [W1] Indeed, comparisons to non-iterative methods are still missing, e.g. particle-based or simulated annealing. We expect that these methods sometimes may lead to more accurate solutions (if they find a global solution that we did not), but are probably still orders of magnitude slower - because the time complexity of our method is the same as solving a single linear problem (see our complexity analysis in Section F of the supplemental material).\n * [W2] Theorem 2 states convergence rates with respect to functions in the Barron space. There still remains questions relating specific sampling distribution to convergence rates. This also reflects the state of research around neural networks and how its often limited to very few results in terms of convergence (except for strong assumptions such as convexity of the loss), and Theorem 2 builds upon the current existing theory on neural networks approximating Barron spaces. However, the theory behind random feature methods are more rich in this instance, and we aim to connect more theory between the networks we propose and random feature methods theory, to provide stronger and probabilistic convergence rates.\n * [W3] Galaris et al. [21] propose to use the data to find the direction and center of the weights for the sigmoid activation function in a shallow neural network, applied to numerical bifurcation analysis of PDEs from a certain type of simulations. We greatly extend their initial work, which we now also emphasize more in the manuscript:\n\n   *  We define a non-uniform probability density over the data pairs, which forces weights to be close to steep gradients of the target function.\n   *  We extend the idea to different activation functions, by adding scaling factors (the square of the norm) and change the bias. We show that these changes are essential in theory and experiments, particularly for tanh activation functions. \n   *  We extend the construction to deep neural networks. \n   *  Our work brings the key insight from Galaris et al. into a broader machine learning framework, with all the added theoretical investigation (including convergence), to ensure we do not lose anything by enforcing the weights and biases to a restrictive space.\n\nRegarding questions:\n * [Q1] Yes - please see our general answer to this (several reviewers asked this question).\n * [Q2] We hope the figures in the general answer to all reviewers also help to illustrate how we choose pairs.\n    \n    In theory, we start by sampling the weights of the first hidden layer by sampling from the joint distribution over the square of the dataset, with density given by Equation 2 of the paper. After we have sampled a pair of points for each neuron in the first hidden layer, we construct the weight according to Definition 1. If we have more than one hidden layer, we pass the whole dataset through the first hidden layer and proceed to sample as before, but from the dataset transformed by the first hidden layer. This continues until we reach the last layer, the coefficients of which we then approximate using least squares (in case of mean squared loss). \n    \n    In practice, due to the complexity of computing the density of every pair of points, we first uniformly draw a number of data pairs. This number is only proportional to the data set size, not the square of it. From this set, we then draw again, randomly, a number of pairs equal to the number of desired weights in the current hidden layer, but now with a probability that is proportional to the finite difference computed for each pair (and the corresponding target function values on this pair). This means pairs associated with steeper gradients of the target functions are chosen more likely than pairs in flat regions.\n    \n * [Q3] In the paper, we state, 'The sampled weights also provide a good starting point for the fine-tuning of the entire model.' Here, we mean that even though fine-tuning the entire network after sampling breaks the direct connection of weights and biases to data pairs, the ADAM optimizer can still improve the test loss. Essentially, we demonstrate that sampling provides a good starting point for fine-tuning in weight space, i.e., the sampled weights are not a \"bad\" local minimum from which it is difficult to escape with ADAM.\n\nIn our experiments, regardless of whether the weights of the classification head are sampled or trained, the difference in the test accuracy after retraining the whole network is rather small. Thus, for comparable test accuracy, the computational efficiency of sampling is higher.\n\nNevertheless, we list possible reasons for the small differences: \n * (a) Note that for the fine-tuning after Sampling, we use the ADAM optimizer. This suffers from comparatively high variance, mostly from iterative optimization and mini-batching, i.e. stochastic approximation of the local gradient. We believe the differences after fine-tuning are mostly due to this variance and not caused by sampling before. \n * (b) The accuracy after fine-tuning also changes with the chosen architecture. For ResNet50, 'Adam training + finetuning' yields a slightly higher test accuracy as compared to 'sampling + finetuning'. However, for Xception architecture, we observe that 'sampling  + finetuning' yields a higher test accuracy (which is also the highest overall test accuracy in our experiments).\n"}, {"review_id": "JoysbEtCRI", "reviewer": "Reviewer_ReAz", "summary": "This study proposes a sampling learning method for deep ReLU networks. The proposed distribution is data dependent and the sampled network is shown to have universality. ", "questions": "Please refer to the weakness section", "limitations": "n/a", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The idea of sampling parameters is well-investigated, for example, such as Bayesian NNs, sampling-based dimension reduction for kernel methods, random Fourier features, mean-field theory and Langevin dynamics to mimic SGD learning dynamics, and ridgelet transform for Barron-type integral representation theory. One of the major shortcomings of these methods is that these theories are often limited to shallow networks. This is because the math behind these algorithms is an integral representation of a neural network, and it is essentially a model of a single hidden layer with infinite units. Despite this difficulty, this study has developed and proposed data-dependent proposal parameter distributions for multiple layers.", "weaknesses": "However, I could not figure out if the proposed distribution, Eq.2, is well-defined. Since $\\Phi^{(l-1)}$ is a piecewise linear map, the graph of Eq.2 may have (1) a constant direction, and (2) line singularities as $|x_1 - x_2| \\to 0$. These characteristics suggest that the proposed function is not generally *integrable*, thus the well-definedness is not trivial. Nevertheless, theorems are proved without regularity conditions, so I consider the theory as incomplete.\n\nAdditionally, the design of experiments are not consistent to the theory, since (1) Figure 2 draws reference lines $m^{-1/2}$ and $m^{-1}$, but there is no guarantee that the proposed algorithm converges at these rate, and (2) Section 4.3 deals with neural operators, but the architecture is not considered with theory.\n\nFurthermore, Section 2 “Related work” is rather a compressed list of related works than literature overview since it lacks reviewing on what problems remain open in the past studies and how the authors addressed them. \nSeveral closely related works are omitted, for example, such as \n- attempts to use (Quasi) Monte Carlo computation of integral transforms (that describe data-dependent parameter distributions):\n  - https://arxiv.org/abs/1902.00648\n  - https://jmlr.csail.mit.edu/papers/volume22/20-1300/20-1300.pdf\n  - https://jmlr.org/papers/volume18/15-178/15-178.pdf\n- strong lottery ticket hypothesis (particularly the edge-pop algorithm and its universality):\n  - https://arxiv.org/pdf/2111.11146.pdf\n- and representer theorem for deep ReLU nets:\n  - https://jmlr.org/papers/v20/18-418.html\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding the sampling distribution:** Equation 2 uses both the map $\\Phi^{(l-1)}$ (ReLU) in the denominator, and the target function values $f(x)$ in the nominator. Based on this review, we refined the definition of our probability density and now assume the following:\n * Compactness of the data domain. This is already stated in the paper, and in the supplemental material, Definition 3.\n * Non-constant, Lipschitz-continuous target function $f$. This was not stated before, and we are thankful to the reviewer for pointing it out. If the function $f$ is constant on $\\Phi^{(l-1)}(\\mathcal{X})$ or the map $\\Phi$ maps all points to a single point, we define $p$ to be uniform.\n * Regularization with a small constant $\\epsilon>0$ of the denominator for every hidden layers except the first one. We already state this (for all layers) in Algorithm 1, but did not do so in the definition of the probability density. In the numerical experiments, we used $\\epsilon=10^{-10}$.\n\nThe new definition of the density is now the following (slightly adapted because not all LaTeX features are available here):\n\n**Definition 2.** Let $\\mathcal{X}$ be the compact input space, and let $f$ be a Lipschitz-continuous, non-constant function on $\\mathcal{X}$. Let $\\mathcal{Y} = f(\\mathcal{X})$ be given function values, and let $P$ be a continuous probability distribution defined through its conditional distribution with density $p$, for $l=1,2,\\dots,L$ and $x^{(1),0}$, $x^{(2),0}$ $\\in\\mathcal{X}$, setting $x^{(1),l-1}$,  $x^{(2),l-1} = \\Phi^{(l-1)}(x^{(1),0}), \\Phi^{(l-1)}(x^{(2),0})$, where $p(x^{(1),0}, x^{(2),0}| \\{W_{j}, b_{j}\\}, j=1,\\dots,l-1)$ is proportional \nto\n$ | f(x^{(2),0}) - f(x^{(1),0})| / \\text{max}\\lbrace|  x^{(2),l-1}- x^{(1),l-1} |, \\epsilon\\rbrace,$ when $x^{(1),l-1}\\neq  x^{(2),l-1}$ and $0$ otherwise.\n\n  Here, $\\Phi^{(l-1)}(\\cdot)$ is the sampled network up to layer $l-1$ with parameters {${W_{j}, b_{j}}$}, $j=1,\\dots,l-1$, $\\mathcal{X}^{l-1}= \\Phi^{(l-1)}(\\mathcal{X})$, and $\\epsilon$ is a regularization constant that we set to zero for $l=1$ and larger than zero for $l>1$.\n  If $f$ is constant or $p$ above would be zero a.e., we define $p$ to be the uniform distribution over $\\mathcal{X}\\times\\mathcal{X}$.\n\nWith these additions, most of them being incorporated in the experimental part already, we can now guarantee the proposed density induces a proper distribution. By leaving the conditional density for the first hidden layer unregularized, also all the theory, including Theorem 3, is now consistent.\n\n**Regarding the convergence rate:** we prove (Theorem 2) that there exist sampled networks that achieve convergence rates $m^{-1/2}$, which is why we added the line in the plots for the experiments. Indeed, it is not clear if the specific sampling probability leads to this convergence rate, we only demonstrate that it does so empirically. The architectures we use in Section 4.3 can be mostly considered pre-processing techniques for the sampled networks we study analytically. For example, mapping the target function to Fourier space before constructing a sampled network does not change the theory surrounding it, just the target values. Of course, there are still a lot of open questions (beyond the scope of this paper), e.g., convergence in Sobolev spaces of the sampled networks. The third paper cited by the reviewer may help here.\n\n**Regarding related work:** We greatly appreciate the pointers to additional literature. We comment on them below, and also incorporated them together with a more detailed review in the related work section of the manuscript.\n * Monte-Carlo / kernels:\n   * Paper1: We construct an inverse mapping from the given target function to the distribution in parameter space of (deep) networks. Even though we currently cannot prove the same exponential convergence rates, our sampling algorithm works for networks with more than one layer. We also introduce a duality between training data and network parameters, which makes the sampled parameters easily interpretable.\n   * Paper2: The ridgelet prior is constructed with normally distributed weights in the first hidden layer, so it \"does not require access to any part of the dataset\" (quote). Thus the prior does not utilize the information to construct weights, as we do here. The analysis in the paper offers a path toward Bayesian framework for our sampling procedure.\n   * Paper3: There is a strong relation between random features and  kernel functions. The cited paper covers many examples and provides a unifying view on weights for kernel quadrature and random feature approximation of functions. Our work differs in that we do not start with a kernel and decompose it into random features, but we start with a practical and interpretable construction of random features and then discuss their approximation properties. Exploring the kernel (and related RKHS / Bayesian framework) that corresponds to \"our\" sampled features is an exciting future work that we already started to pursue.\n * Lottery ticket: The strong lottery ticket hypothesis, where the \"winning\" subnetworks are not trained but selected from a randomly initialized starting network, is similar to our approach of randomly choosing data pairs and then selecting highly probable ones for weights and biases. The two approaches are still not easily comparable: in the edge-pop algorithm, iterative gradient-based updates of the weight scores are required, and the remaining weights after pruning cannot be interpreted as easily as they can with our algorithm (see our general answer).\n *  Deep ReLU nets: The paper states that \"Designing an algorithm that can effectively deal with this issue [of selecting proper spline points] will be a very valuable contribution to the field.\" Our sampling procedure may offer a path toward such an algorithm. Even though we cannot ensure that we only find optimal spline points, at least we offer a solution to constructing useful ones based on given data.\n"}, {"review_id": "5BmcWLUiSR", "reviewer": "Reviewer_KCHD", "summary": "The paper proposes a novel approach and analysis to sample weights of neural networks that can potentially address backprop limitations. \nThe method is based on computing differences between data points and can be scaled to deep networks (by computing the difference of data point activations). The paper introduces a rigor mathematical formulation supported by several experiments showing some benefits of the approach compared to backprop.", "questions": "1. L213: \"Pre-processing failed in 11 of the 72 datasets\" - what kind of pre-processing and what exactly means \"failed\"? Was it applied to both the Adam and proposed approach? Are those 11 datasets ignored in Figure 3? Were the Adam hyperparameters (learning rate, weight decay, etc.) tuned?\n\n2. In Algorithm 1, arg min L is a linear optimization problem. Is it solved using some kind of least-square in a closed form/gradient-based way? Does this step dominate time complexity in large experiments (ResNet, VGG, Xception) in Fig. 5 right?", "limitations": "Limitations are discussed, but not all (e.g. see Weakness 3 about scalability above).\n\n**I updated the rating from 4 to 6 based on the author response and other reviews**\n\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem of sampling weights better than using a data-agnostic random distribution is very interesting and solving it might have a lot of practical implications.\n2. The method is supported by rigor mathematical formulation.\n3. The experiments are extensive and diverse, including experiments with large networks, showing some benefits of the method.", "weaknesses": "\n1. In L24, it says \"we introduce a data-driven sampling scheme to construct weights and biases close to gradients\". However, in Section 3, the connection of the proposed approach to gradients is missing. Is the difference between data points related to gradients? In that sense, is there a connection of this submission with Forward Gradient approaches, e.g. \"Gradients without Backpropagation. Baydin et al., 2022.\" or \"Learning by Directional Gradient Descent. Silver et al., 2022\"? In Forward Gradient, the gradients are often estimated by perturbing the inputs/weights a little bit. Even if it's directly related, I believe since this submission and Forward Gradient papers are both alternative approaches to backprop, it should be discussed at least in Related Work.\n\n2. An important baseline for the Fig. 3 and 5 experiments that is missing would be to keep the first layers initialized randomly, while still apply arg min L for the last layer. This baseline would show more clearly the benefit of sampling weights. It may be that the main benefit is coming from solving argmin L.\n\n3. It's a bit unclear why the proposed approach scales poorly with width (Fig 5, right). It seems that in Algorithm 1 most of the loops, specifically for k=1,2,...N_l, can be run in parallel for all neurons, so it should scale well with width if implemented efficiently. Perhaps, the comparison to Adam is not very fair as the authors are probably using a very efficient Adam implementation.\n \n4. In algorithm 1, ||y_i - y_j|| must be a constant (same for all i,j) for classification problems (assuming y is a one hot vector and i, j are of different classes), so it's not very clear what's the purpose of this term. If labels are not that important, it could be beneficial for the paper to claim that the approach works without the need of labels (which are often expensive to obtain), perhaps except for the last layer.\n\n5. Some visualizations of sampled vs trained weights would be useful. In particular, for tasks such as MNIST, where sampled first layer weights can be easy to interpret. In general, it remains a bit mysterious how the algorithm actually samples weights that are better than random weights. So some visualization like in Fig. 1 but for actual optimization tasks would be useful.\n\n6. The paper claims improved \"Interpretability\" in the Introduction, however, this claim was not supported empirically.\n\nI will be willing to raise my score if the weaknesses are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Regarding weaknesses:**\n * [W1] In both papers, \"Gradients without Backpropagation\" and \"Learning by Directional Gradient Descent\", the authors propose methods to compute the gradient of the network with respect to its parameters (weights and biases). In contrast, we propose to choose data point pairs that are close to regions with steep gradients *of the target function* with respect to the input. We choose this so that the corresponding network activation functions $\\phi(\\langle w,x\\rangle-b)$ are \"placed\" close to these steep slopes. We hope the new illustration in the general answer to all reviewers clarifies this. We still added a brief discussion of the two papers in the related work section of the revised manuscript.\n * [W2] In Section 4.1, for random features, we do indeed initialize randomly all layers except the last one. Then, we use a least squares solver to find the weights and biases of this last layer, exactly in the same way as for our sampled network.\n    We did not also add this comparison in Figures 3 and 5 (corresponding to Section 4.2 \"OpenML\" and Section 4.4 \"Transfer learning\"). In our experience, random feature models only perform comparatively well for layers with much more neurons - but we would be happy to extend the experiments to demonstrate it.\n * [W3] The scaling with width may be clarified with our complexity analysis (Section F in the supplemental material). Essentially, the *minimum* of the (a) width of the last layer and (b) number of training data points determines how much work the linear solver for the last layer must do; it scales cubically with this number. Note that this is the time complexity *until convergence* for our sampled network, which usually is very hard to obtain in general for methods like ADAM. The sampling of the hidden layer weights is negligible for the computation time. It is true that we also compare a CPU-based research code against an efficient implementation running on the GPU. We also want to highlight that in Figure 5, our approach outperforms the Adam optimizer on the test set already at around 1000 neurons, where our approach is still around ten times faster. It is not clear how long the ADAM optimizer would have to run to reach the same test accuracy.\n * [W4] The function value differences are indeed constant (equal one) if the classes are one-hot encoded. However, for data pairs inside the same class, the difference is zero. The purpose of the term thus is that only pairs that are in different classes are selected. Furthermore, points that are closer to the decision boundary are selected with higher probability, because they correspond to different classes, but have smaller distances - and the distances are included in the denominator (Equation 2). Figure 1 in the answer to all reviewers should visualize this.\n * [W5] We added two figures related to the interpretability of the weights in sampled networks to the answer to all reviewers. The examples are constructed on actual tasks (one classification task in two dimensions, one classification using MNIST).\n * [W6] We hope that the visualization in the answer to all reviewers helps to emphasize how the weights and biases of networks can now be interpreted better. In fact, in the proof of Theorem 1, we show that any neural network can be transformed into a sampled network (with identical values on the input space, but potentially not away from it). This means the sampling method may be useful to interpret even other neural networks that were not obtained with our algorithm, as we can take a trained network as input and output a network with weights and biases of the form given by Definition 1. Once this is done, we can use the information to interpret which datapoints in the training set have been essential to create the neural network which was trained by ADAM. \n\n**Regarding questions:**\n * [Q1] The datasets from OpenML must be pre-processed before they can be used by standard feed forward neural networks (they contain nominal variables and missing values). The pre-processing steps are listed in the supplemental material (lines 496-499). This pre-processing was applied before we construct the networks, the same way for sampling and Adam training. The datasets where pre-processing \"failed\" were excluded from all evaluations. We re-ran the code after the submission period ended, and it seems that there may have been an issue with the openml package downloading the data. With a newer version, all 72 datasets work correctly now (no change to our code was needed, just an update to the package). The results of all missing datasets are now included in the new manuscript, they do not change the results shown in Figure 3 significantly.\n    \n    We did not modify the standard hyperparameters of Adam, and except for neural architecture search (number of layers), we did not perform hyperparameter search for the OpenML experiment. This hyperparameter search would have skewed the time for the Adam algorithm even more in favor of sampling - as there is just a single hyperparameter to tune for sampling (regularization of the least-squares solve), as compared to many for Adam. Of course, the accuracy for Adam may have improved.\n    \n * [Q2] Indeed, we solve it using the closed form of a least-squares optimization problem (Tikhonov regularization), which is the key source to the scaling. For the scaling factors of the network, we have also included a time and space complexity analysis in the supplemental material, Table 4 (p. 25). Note that the scaling in Figure 5 is due to the increasing, large widths of the networks, not the number of datapoints.\n"}, {"review_id": "6YvTsbNtJQ", "reviewer": "Reviewer_b7pE", "summary": "This article introduces an alternative to random features for sampling weights of neural networks. Their method relies on data points (both inputs and outputs) and activations to build iteratively the weights and biases of one layer after the other, in opposition with data-agnostic/purely random methods. It proves several results in term of function approximation by their sampled networks. Finally, they compare accuracy, training speed and size of model needed on a classification benchmark, an ODE approximation problem and a vision classification fine-tuning problem.", "questions": "- I am not an expert in deep neural operators, but it is not clear to me how to use the method in the presence of a time-series? How to take into account the time-dependency of the data in the sampling process?\n- It seems to me that this method may have a link with Bayesian neural networks (a field I am not an expert too), i.e. we have a distribution probability over layers. Could the authors comment on this, and maybe add a small paragraph in the text?\n- The authors did not comment the case where we have outliers in the data? How would the method perform in that case? How easily these outliers would impact the target function? The method seems quite sensitive to them. ", "limitations": "Limitations were addressed in the broader impact. \nI am willing to modify my score accordingly to how the weaknesses and questions sections are addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I think the method is original, interesting and easy to understand.\n- The method is more robust to depth than standard Random Features.", "weaknesses": "- The presentation of the paper is not perfect ( the algorithm is not easily readable, there is an indent missing for the for loop over $l$, the theory section is quite dense).\n- The comparison against random features is only on a toy example. It is also not clear which algorithm is used on top on the RFs (linear regression, SGD,...)?\n- The use in modern tasks and architectures seems very limited. \n- In the experiments, it seems that we need quite wide networks to reach Adam networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n**Regarding weaknesses:**\n * [W1] We hope that an additional page after - potentially - accepting the paper can help to make Algorithm 1 more readable, and we can also add more explanations to the theoretical section.\n * [W2] We also commented on a similar question in our answer to reviewer KCHD: In our experience, random feature models only perform comparatively well for layers with much more neurons - but we would be happy to extend the experiments to\ndemonstrate it (there was not enough time in one week, unfortunately). For the last layer of random feature models, we use exactly the same algorithm (least squares, same regularization) as we use for the last layer in sampling. Only the hidden layer is sampled differently.\n * [W3] We argue that many modern tasks involve supervised learning problems (surrogate modeling, learning classifiers and solving regression problems on tabular data, machine learning potentials for molecular dynamics), and we are currently experimenting with using the sampled weights as a \"good basis\" even for unsupervised tasks (modeling dynamical systems, solving partial differential equations). We demonstrate in Section 4.3 that more complicated architectures can be decomposed into smaller sequences of supervised learning problems as well, which can then be solved by the proposed algorithm without any modifications.\n    \n    Furthermore, we argue that with our work we encourage constructing neural networks that use data much more directly to create their parameters. This may spur interesting ideas and extensions to different tasks and architectures, also the ones trained with gradient descent. This type of thinking also very easily leads to many ways to construct interesting densities and emphasizes a more probabilistic approach to neural networks that are also very efficient computationally. Interpretability of our networks is also a benefit that may help the acceptance of machine learning methods in practice.\n * [W4] Indeed. The main reason wider networks are needed is that we randomly sample the hidden layers' weights and biases, so a certain amount of the neurons will not be very useful in the final layer. In followup work, we have started experimenting with $L^1$ optimization of the last layer (instead of $L^2$), which leads to many coefficients in the last layer being exactly zero. This means we can easily prune the sampled networks after solving the last layer, too, something we will explore in the future.\n\n**Regarding questions:**\n\n * [Q1] The experiments presented in the paper do not use time series as input data. Models in Section 4.3 approximate an operator that transforms an initial condition into the solution at a particular time step. More specifically, the task’s input is function values at $t = 0$, while the target is function values at $t = 1$. Thus, we do not employ any time dependency in input data during sampling.\n\nIf we had time-series data, we could attempt to learn the underlying dynamics of it, for example, an ordinary differential equation (ODE). To do this, we would compute finite differences (in time) in the input time series first, and then train a network to predict those in a supervised manner. This way, we could approximate the right-hand side of the underlying ODE and then solve it using classical integration methods.\n * [Q2] The manuscript already contains a brief discussion in \"related work\" (lines 65-68). Note that we effectively connect training data points and weights, while Bayesian neural networks mostly use distributions over the weights without a direct connection to the data. We have expanded our discussion in the manuscript based on the reviewer's question.\n * [Q3] Indeed, analyzing the behavior of the algorithm in a stochastic setting, or with measurement noise, was left for future work. Experiments in Section 4.2 (OpenML) and Section 4.4 (transfer learning) demonstrate empirically that the method is not very sensitive to noise: we use real data for the experiments, which always contains a certain noise level. If we would find a specific sensitivity to noise in a certain setting, it would be possible to study robust methods for linear systems (e.g., robust least-squares) as a replacement for the current standard least-squares method we use in the last layer. Sampling hidden weights and biases may also be affected by noise (mostly by poor function values, like wrong labels, for example). This would cause a less optimal selection of internal weights, which may still be mitigated by more robust methods for the last layer.\n"}]

Author rebuttal:
We very much appreciate all the constructive criticism, feedback, and suggestions. We replied to every review individually. Several questions were raised on (a) the loss function we use for the last layer, and (b) the interpretability of the sampled networks, so we would like to comment on these here. We added two figures in the attached PDF file, which we refer to in the text.

Regarding different loss functions for the final layer:
We only use mean squared error as the loss function because there is a closed-form solution to the linear system in the final layer (using the least squares method, with Tikhonov regularization). This leads to very fast approximation and clear time and space complexity of the algorithm (see Section F in the supplemental material).
If approximation time is not a concern, loss functions used in standard neural network training can also be used - for example, cross-entropy loss for classification tasks. If no closed-form solution is available, the last layer must be trained iteratively. This should still be much faster than training the entire network iteratively.
According to Theorem 1, any loss function based on the $L_p$ norm, for $1\leq p \leq \infty$ is admissible. This covers most of the norms, and therefore losses, that are used to study universal approximations and convergence of neural networks.

Regarding the interpretability of sampled networks:
We argue that sampled networks are inherently more interpretable than iteratively trained ones. This is because we associate a pair of data points in the training set with every weight and bias pair in the network. Note that the pairs are not assigned after training; the network parameters are *constructed* using these data pairs. This allows us to interpret what part of the data domain the network is using most (cf. Figure 1, experiment A), and which data pairs are most important for predictions (cf. Figure 2, experiment B).
In experiment A, we first sample $10^6$ data points in $[0,1]^2$. From those, we sample $10^6$ data pairs with uniform distribution (as suggested in Galaris et al., [21]) and separately with our proposed distribution, using the class as target function values  $(A=1,B=0)$. Finally, we plot the density of all points that were sampled (Figure 1, center and right plots). Obviously, the uniform distribution does not take into account the classification task. In contrast, our distribution mostly concentrates the data pairs around the decision boundaries.
In experiment B, we construct three very small networks with five neurons in one hidden layer each and train them on the MNIST image data set (50,000 training images, ten classes, one-hot encoded). All of the networks are classical feed-forward networks, so the input images (dimension $28\times 28$ pixels) are first flattend to vectors of length 784. The last layer is always constructed using least squares (Tikhonov regularization). In Figure~2, we illustrate the five hidden weights for each neuron by reshaping them from $784$ back to a $28\times 28$ pixel image again. The first network uses random features (weights distributed in a standard normal distribution, biases uniformly in $[0,1]$). The second network uses uniform sampling of pairs, and the third network uses our proposed distribution. Classification accuracy on the test set (10,000 images) is 24% (random features), 43% (uniform), and 47% (ours), respectively. Note that the goal of this experiment is not to achieve high accuracy - the networks have only five neurons each in the hidden layer - but to highlight the differences in interpretability. For random features, the sampled weights are hard to interpret. For the second and third network (second and third row in the figure), the weights are directly computed from the data points. With this knowledge, it is easy to understand why, for example, classes 2 and 4 are poorly classified: none of them are included in the weights. Also, the third weight of the uniformly sampled network does not add a lot of information, because it is constructed from a pair with both points in the same class.
We would also like to point out that the proof of Theorem 1 is constructive, which means we provide a method to convert any given network to a sampled network-effectively by re-constructing data pairs the weights and biases are associated to. This means even networks trained iteratively could now be interpreted using our construction (as long as the training data set contains a large set of points).

Meta-review: The paper proposes a sampling strategy for weights and biases of neural networks using a Bayesian approach. The method is data-driven and does not require further gradient descent steps for optimization. The authors did an excellent work addressing the reviewers' concerns and the reviewers increase their scores post-rebuttal. However, Reviewer ReAz is still concerned with the validity of the theoretical results. It is acceptable if the theory is used only as a guide for developing the technique. However, the authors must update the proofs and fix the bugs before the final version. Also, there are some references that do not follow the `last name (year)` format, which need to be fixed.
Decision: Accept (poster)