Parameters as interacting particles: long time convergence and asymptotic error scaling of neural networks
The performance of neural networks on high-dimensional data distributions suggests that it may be possible to parameterize a representation of a given highdimensional function with controllably small errors, potentially outperforming standard interpolation methods. We demonstrate, both theoretically and numerically, that this is indeed the case. We map the parameters of a neural network to a system of particles relaxing with an interaction potential determined by the loss function. We show that in the limit that the number of parameters n is large, the landscape of the mean-squared error becomes convex and the representation error in the function scales as O(n −1 ). In this limit, we prove a dynamical variant of the universal approximation theorem showing that the optimal representation can be attained by stochastic gradient descent, the algorithm ubiquitously used for parameter optimization in machine learning. In the asymptotic regime, we study the fluctuations around the optimal representation and show that they arise at a scale O(n −1 ). These fluctuations in the landscape identify the natural scale for the noise in stochastic gradient descent. Our results apply to both single and multi-layer neural networks, as well as standard kernel methods like radial basis functions.
proved for radial basis functions [16]. However, the proofs of the universal approximation theorems do not ensure that any particular optimization technique can locate the ideal set of parameters.
Parameters as particles-In order to study the properties of stochastic gradient descent for neural network optimization, we recast the standard training procedure in terms of a system of interacting particles [17]. In doing so, we give an exact rewriting of stochastic gradient descent as a stochastic differential equation with multiplicative noise, which has been studied previously [18,19]. We interpret the limiting behavior of the parameter optimization via a nonlinear Liouville equation for the time evolution of a parameter distribution [20]. This framework provides analytical tools to determine a Law of Large Numbers for the convergence of the optimization and to derive scaling results for the error term as time and the number of parameters grow large. A similar perspective has been adopted concurrently by Mei et al. [21], Chizat and Bach [22], and Sirignano and Spiliopoulos [23], which study the "mean field limit", similar to our Law of Large Numbers, but not asymptotic fluctuations or error scaling.
Convergence and asymptotic dynamics of stochastic gradient descent-We demonstrate that the optimization problem becomes convex in the limit n → ∞ and we show that both gradient descent and SGD convergence to the global minimum [24,21]. This argument shows that the universal approximation theorem can be obtained as the limit of a stochastic gradient based optimization procedure under an appropriate choice of hyper-parameters. In the scaling limit, our analysis gives bounds on the error of a representation and characterizes the asymptotic fluctuations in that error. Convergence to the optimum to first order occurs rapidly, i.e. on O(1) timescales. Diminishing the error at next order requires quenching the noise in the dynamics on O(log n) time scales.
Implications of noise in descent dynamics-Our results give an explicit theoretical explanation for the observation that additional noise in can lead to better generalization for neural networks [25,26]; local minima of depth O(n −1 ) are washed out by the noise of SGD.
Numerical experiments-We verify the scaling predicted by our asymptotic arguments for single layer neural networks. Because it is impossible to determine the exact interaction potential in general, we carry out numerical experiments using stochastic gradient descent for ReLU neural networks. We use the p-spin energy function [27,28] as the target function due to its complexity as the dimension grows large.
Key assumptions-In order to derive the stochastic partial differential equation for SGD, we effectively assume the large data limit. Because we are focusing on function approximation we can always generate new training data by sampling random points in the domain of the function and evaluating the target function at those points. The partial differential equation for gradient descent represents the evolution of the parameters on the true loss landscape, i.e., the large data limit. In this limit, the dynamics is similar to online algorithms for stochastic gradient descent [5].
In this manuscript the authors show that neural networks can be used to get approximations to given high-dimensional function with controllable errors. In particular, they consider the case where the function parameters satisfy either Gradient Descent or Stochastic Gradient Descent dynamics and prove law of large numbers and central limit theorems for the function the neural network outputs. They then use simulations, where the input function is a spherical 3-sping model, to show the performance of neural networks in estimating these functions.  I find the paper to be very clear and well-written. The authors do a good job in setting up the problem, discussing the two different settings and explaining the results. Those results are in my opinion very relevant since they shed new light, and provide important insights, in the strength of neural networks for representing complex high-dimensional functions, which can have several important applications in both theory and practice.  The authors have chosen to put all technical derivations and details in the supplementary material. Given the depth of the paper I understand this choice. However, the links between the parts of the main text and the supplementary material are not very clear. For instance, the authors use S1 in the main text to refer to Section 1 in the supplementary material, although sections there are simply numbered by 1, 2 and so on. Moreover, I found it hard to move between the main and supplementary parts in a continuous way. I ended up first reading the main text and then the supplementary material, which made it very hard to directly related the results in the latter to the main text. Here the problem arises that not everything used in the supplementary material is defined there, forcing the reader to go back to the main text and finding the missing definitions. Finally, I want to mention that the supplementary material does not follow the standard setup of first given a statement and then a detailed proof of it. Instead the results are preceded by lengthy computations which should represent the proof of this statement. This works in some case, but in most I was unable to parse the derivations I just read to get the proof of the result. I therefore stopped reviewing the computations after page 6 because of the difficulties in parsing them into needed proofs. To summarize, the paper investigates the very interesting and important usage of neural networks for representing complex high-dimensional functions using input parameters coming from given dynamics. The results seem solid and establishing the relation between function representation by neural networks and particle dynamics can potentially lead to better understanding and new advances of these systems. However, the way in which the results and technical derivations are split between the main text and supplementary material make it very difficult to properly check and verify the results. Still, I would recommend this paper for acceptance in NIPS, given that the authors take some time to better structure their results.  ADDED AFTER FEEDBACK: I remain convinced that the approach in the paper and results are interesting enough to validate acceptance in NIPS 2018. Although I strongly encourage the authors to restructure their supplementary material and discuss the contributions of the paper more clearly.  Below is a detail list of comments. Main text: Line 14, [batch size]: It is not clear to the reader at this point what this means. Line 31, [Progress analyzing…]: I would write: Progress on analyzing. Line 56: Another instance where batch size is used without having explained what is means. Line 59: I was confused by: justification explanation. It feels that it should be just one of these words. In addition, I would remove [in] in: noise in can lead… Line 70, [an exacting test]: Don’t you just mean: a test? Line 74-75: I would remove: is the following criterion, since it repeats the part of the sentence that precedes it.  Equations (4) and (5): Here the use of h is confusing since it was just use to denote an arbitrary test function. Line 86, [In this case, we…]: I would write: In this case, since we… Also, I would remove [and] in: and we can view… Line 92, [converges]: What type of convergence? I guess you mean pointwise.  Line 104, [synergies will…]: I would write: synergies which will… Line 114: As mentioned before, there is no Section S1. Moreover, it really is Section 1.1 in the supplementary material. I would recommend to be more specific here to avoid confusion and unnecessary text scanning by the reader. This holds for all subsequent occurrences of S references.  Equation (15): It is unclear with respect to what variables the integrals are taken. Please be explicit here. Equation (16): What is \rho_0? It is never defined and clearly cannot be a case of eq (13). Could you please give some more details here. Line 121: I would remove [and] in: point is and… Line 125: What is the difference between f_n(t) and f_n(x)? This is not clear from the text. Line 127: The \mathbb{P}_{in} comes out of nowhere which creates confusion. I would advise to spend some words on this before the statement of Proposition 3.1. Equation (19): Is this convergence uniform in t? I was not able to extract this from the proof and it feels that this is somewhat necessary to make the result applicable. This also applies to eq (29). Line 160: Here you refer to equation (27) which comes only later. I would recommend to follow the practice of not referring ahead and first give (27). In addition, I would write: (27) is statistically… Line 162, [spation-temporal]: I am not completely familiar with the terminology in Langevin dynamics but I would think that spatial-temporal is the right term. Line 172: What are \bm{\eta} and \eta? I understand that they refer to noise terms but it would be better to at least refer to the equation in the supplementary material that defines them. Line 192, [of noise term…]: I would write: of the noise term… Line 205: It would help the reader if you explain what S^{d-1}(\sqrt{d}) is. Figure 1: This figure is unclear. For instance, what do the different color stars mean? I would strongly recommend to add more explanation in the caption. Also, the figure is never explicitly referenced in the main text. Line 241, [that the]: I would replace this with: where the Supplementary material: Line 12: Are there really no restrictions on the input distribution \mathbb{P}_{in}? Line 14: What is \Omega? This is never defined. Line 37: What does the half arrow mean? I guess it means convergence in distribution. Please be more specific. Line 42-Equation (16): It is not clear why any of this is needed, since it does not seem to be used in the derivations that follow. Moreover, what is the derivative in eq (11)/(13)? Is this the Fréchet derivative? If so then why does \frac{\partial \mathcal{E}_0}{\partial \rho_0} seem to be a function, while \mathcal{E}_0 is a functional? It would really help if you give more details and a motivation for this part. Equation (18): I did not immediately see who (10) can be rewritten as (18). Could you please add some additional derivations? Line 58, [By the assumptions…]: Which assumptions are you referring to? The only assumption I could find here is 1.2 which says the kernel is continuously differentiable but I do not see why that is enough. Proposition 1.3: I was unable to transform the computations preceding this proposition into a proof of it. Please try and make the proof more apparent from the computations so that the reader does not need to solve this puzzle themselves. Line 72: I did not understand why the minimizers of \mathcal{E}_0 are relevant. Could you please elaborate a bit on this? Line 93: There seems to be a typo here. Along is written twice. Equation (32): I found the notation here quite confusing. First it is only revealed later that \xi(t) also depends on n which is indeed needed for else (32) would not be true in general. Second, what is the difference between \tilde{\rho}_\xi(t) and \tilde{\rho}_{\xi(t)}? Equation (38): What asymptotic are you considering here? Is it n \to \infty, t \to \infty or both n, t \to \infty?