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.
Paper
Similar papers
Peer review
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.
Strengths
- I think the method is original, interesting and easy to understand. - 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). - 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,...)? - The use in modern tasks and architectures seems very limited. - In the experiments, it seems that we need quite wide networks to reach Adam networks.
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? - 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? - 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.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Limitations were addressed in the broader impact. I am willing to modify my score accordingly to how the weaknesses and questions sections are addressed.
Summary
The paper proposes a novel approach and analysis to sample weights of neural networks that can potentially address backprop limitations. The 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.
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. 2. The method is supported by rigor mathematical formulation. 3. The experiments are extensive and diverse, including experiments with large networks, showing some benefits of the method.
Weaknesses
1. 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. 2. 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. 3. 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. 4. 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. 5. 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. 6. The paper claims improved "Interpretability" in the Introduction, however, this claim was not supported empirically. I will be willing to raise my score if the weaknesses are addressed.
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? 2. 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?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
Limitations are discussed, but not all (e.g. see Weakness 3 about scalability above). **I updated the rating from 4 to 6 based on the author response and other reviews**
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.
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. Additionally, 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. Furthermore, 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. Several closely related works are omitted, for example, such as - attempts to use (Quasi) Monte Carlo computation of integral transforms (that describe data-dependent parameter distributions): - https://arxiv.org/abs/1902.00648 - https://jmlr.csail.mit.edu/papers/volume22/20-1300/20-1300.pdf - https://jmlr.org/papers/volume18/15-178/15-178.pdf - strong lottery ticket hypothesis (particularly the edge-pop algorithm and its universality): - https://arxiv.org/pdf/2111.11146.pdf - and representer theorem for deep ReLU nets: - https://jmlr.org/papers/v20/18-418.html
Questions
Please refer to the weakness section
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
n/a
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.
Strengths
1. This is a well-written paper with clear descriptions and detailed formula derivations. 2. 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. 2. There is a notable lack of analysis regarding the convergence rate within the paper. 3. 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.
Questions
1. In Algorithm 1, the L2 Loss function is consistently used. Can this method be adapted to accommodate other types of loss functions? 2. Could you elucidate on the process used to select the data pairs? 3. 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?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
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.
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.
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. - The invariance properties of the sampling scheme remove the need for several data preprocessing techniques, which often require significant domain knowledge to determine. - The theoretical analysis and experimental verification are sound. Proof sketches provided in the main paper are useful to gain insight into the method. - 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. - 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.
Questions
- As above, how would the theory and/or experiments change for different loss functions and different optimizers used as comparisons? - 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? - Similarly, what are the challenges to constructing sampled networks for unsupervised or self-supervised tasks? - 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"?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Authors clearly and satisfactorily state the limitations and impact of their work.
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. This 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.
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. I 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. That 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.
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.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
1 poor
Contribution
2 fair
Limitations
I think the limitations were adequately addressed, as this work applies to small neural networks there shouldn't be any concerns.
Thank you for addressing the concerns in detail. In particular, I found the random features experiments [W2] and the new visualizations for 2d and MNIST [W5] very useful and convincing. I'm generally satisfied with the response and will raise my score accordingly (once this option becomes available to reviewers). One minor note is that there are several recent works studying the idea of learning a representation of neural network weights to sample new weights from the latent distribution, e.g. [A, B]. It would be useful to see some discussion in the Related Work w.r.t. this kind of papers. [A] Hyper-Representations as Generative Models: Sampling Unseen Neural Network Weights, NeurIPS 2022 [B] Learning to Learn with Generative Models of Neural Network Checkpoints, 2022
Thank you! We will cite [A,B] (and potentially others), and discuss learning weights from existing models in the related work section. It may be interesting to consider our sampled weights as training set in this context.
Answer to rebuttal
I would like to thank the authors for their answer. I think this paper is an interesting proof of concept, and that the experiments shown here are interesting. I am however left with the question on whether this method would scale to real tasks. I think this line of work is promising and worth exploring, and I am therefore increasing my rating from 5 to 6.
Thank you! Regarding the question on scaling to real tasks: We interpret this as a question on how our algorithm scales to large data sets, as they are enountered in real, big-data settings. Section F in the supplemental material contains a complexity analysis of the algorithm. It is mostly based on complexity analysis for solving linear systems. For a fixed network, the convergence to a solution is linear in the number of training data points, which is not worse than classical neural network training and should be sufficient for big-data settings.
I appreciate the additional summary and feedback by the authors. I also found the additional experiments (particularly figure 1) to be illuminating with regard to the advantages of the sampling distribution over other approaches. I am happy with the authors responses, as it cleared up multiple pain points for me, such as the reasons behind the limitations with sampling convolutional networks. I will adjust my score accordingly from a 5 to a 6.
Thank you for providing the rebuttal and the additional experiments. I agree with the authors' answers to my questions, but the discussion regarding the comparison of non-iterative methods and convergence rates in the weakness section is still insufficient. Despite this, the paper still presents a promising method, and I will keep my rating of 6.
Thank you! Technically, experiment 4.1 in the paper already is an empirical comparison to a non-iterative method (random features). Still, we agree that there is more research and discussion possible, both toward convergence rates and non-iterative methods.
Thank you to the authors for their clarifications and explanations regarding my questions. I will keep my score of 6.
Decision
Accept (poster)