Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies the convergence of the dual averaging method for the 1-hidden layer neural network in the mean-filed regime. Mean-field perspective allows one to recast original non-convex optimization problem over parameters of neural networks into (non necessarily strictly) convex problem in the space of probability measures.   Similarly to Mei et al. 2018 and Hu et al. 2019, authors consider entropy regularised cases under which the optimal solution to the infinite-dimensional problem over measures admits convenient Boltzman/Gibbs distribution.  Unlike Mei et al. 2018 and Hu et al. 2019,  who studied corresponding Langevin dynamics, while here authors study dual averaging methods in which one approximates the optimal sampling distribution by a sequence of simpler distributions that converge to it (with a rate one over a number of iterations), and use Langevin dynamics to sample from each distribution in the sequence.  If one would be able to quantify the rate of convergence of to each distribution in the sequence, this will imply the overall rate and complexity of the algorithm. 
main_review: Originality:  The idea of using a dual averaging algorithm (mainly used in online learning literature) is interesting. The convergence of the approximating sequence (outer loop) is established in Theorem 1, and this seems like the main contribution of this work.  Authors admit the proof idea is the same as in Nesterov 2009 and Xiao 2009, but I'm not familiar with these works.  What's puzzling is Assumption A3 that does not seem to be compatible with Theorem 2 in terms of rate. Furthermore, the authors never verify (at least not in Example 2 and Lemma B as they refer to) that each measure in the sequence satisfies log-Sobolev inequality (with what constant) and do not study the impact of the regularisation \lambda_1 on the rate of convergence.  Hu et al. already established an exponential rate of convergence in the case when \lambda_1 is sufficiently big.  

In line 38 authors claim that continuous-time results cannot be easily translated to a discrete setting, but this is not true. See for example:
Jabir, J. F., Siska, D., & Szpruch, L. (2019). Mean-field neural odes via relaxed optimal control. arXiv preprint arXiv:1912.05475
for an example for such analysis in a fairly general setting. There is large body of research on uniform in time propagation of chaos and discretisation error for mean-field Langevin dynamics e.g:
- Majka, Mateusz B., Aleksandar Mijatović, and Lukasz Szpruch. "Nonasymptotic bounds for sampling algorithms without log-concavity." The Annals of Applied Probability 30.4 (2020): 1534-1581
- Delarue, François, and Alvin Tse. "Uniform in time weak propagation of chaos on the torus." arXiv preprint arXiv:2104.14973 (2021).

Clarity:  The presentation of the paper could improve in places. Some suggestions:
in section 2.1 the authors should stick to 1-hidden layer example. The ensemble of networks is confusing and not so interesting.
I struggled to gain intuition about what the dual averaging method is from section 3.1 and needed to go back to the literature to see what is going on.  Maybe authors could expand section 2.3 and explain dual averaging there. 
Assumption A3 is in fact, a result that needs to be established. The authors should explain how this is done in Theorem 2

Significance:  Overall, this is an interesting research direction, but the presentation would need to improve, and a more thorough comparison with the literature needs to be presented i.e can authors can get away with less regularisation than Hu et al. and still obtain the rate of convergence? 
limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper is motivated by optimizing two-layer neural networks, with entropy and quadratic regularization. The proposed method is an extension of the dual averaging method to the space of probability densities, together with a finite particle approximation based on Langevin dynamics. An error bound is provided, such that to reach an error $\epsilon$, the number of steps and the number of particles required are both polynomial in $1/\epsilon$.

main_review: The paper makes a serious contribution to the growing literature on the global convergence of two layer neural networks, and is one of the first to provide a quantitative error bound, albeit under a somewhat more restrictive setting (requires entropy regularization with a large constant for the bound to be meaningful).
The paper is well-written and an effort is made to make it accessible to a broader audience, and this effort is commendable.

Perhaps because of this, most of the technical contribution is unfortunately pushed to the appendix, and there is no explicit error bound for PDA (the closest is Remark line 782 in the appendix). In other words, the main results (Theorem 1 and Corollary 2) concern an idealized mean field version (Algorithm 2) that is not implementable. I think it would be much better to write an explicit bound for PDA in the main paper.

On the exponential dependence on 1/\lambda_2: thank you for acknowledging this limitation and pointing to precisely why it arises. In the comment line 243, it is claimed that this dependence "is unfortunately unavoidable", is this alluding to a lower bound? If so, please include a reference, otherwise, please rephrase to make it less factual (for example "we believe that...") and provide a reasoning why this might be.

An additional point to clarify: line 665, it is mentioned that when considering the warm-start scheme, $h_x$ is set to $h_q$ ... without tolerance ($\epsilon = 0$). Why is it fine to assume $\epsilon = 0$ in this case? Even in this case one only gets a particle approximation of  q. Please clarify.

Additional suggestions:
- Consider adding a remark that the Gibbs distributions (such as $q_*^{(t)}$) are well defined thanks to L2 regularization and assumption (A1). This will clarify some of the importance of regularization.
- Appendix A: clarify what definition of gradient you are using, since $P_2$ is not a vector space.
- Overloaded notation: p denotes a density and the dimension of the parameter space (e.g. Definition A)
- Line 647: typo.
- Line 680: optimal coupling is not defined.
- The second and third experiments in the main paper don't seem to relate to the main narrative. They may be moved to the appendix to make additional space for an explicit bound on PDA.
- Experiment G.1: when comparing to SGD, it seems appropriate to also use entropy regularization (i.e. compare to Langevin gradient descent).
limitations_and_societal_impact: The authors adequately addressed the limitations of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper the authors  propose the particle dual averaging (PDA) method, which generalizes the dual averaging method in convex optimization to the optimization over probability distributions with quantitative runtime guarantee. The method in thi paper can thus be interpreted as an extension of the Langevin algorithm to naturally handle nonlinear functional on the probability space. An important application of the proposed method is the optimization of neural network in the mean field regime. By adapting finite-dimensional convex optimization theory into the space of distributions, the athors  establish global convergence of PDA for two-layer mean field neural networks under more general settings and simpler analysis. Numerics support the   theoretical findings. 
main_review: This paper  develops optimization algorithms called PDA for neural networks in the mean field regime with 
accurate quantitative guarantees as  the kernel regime enjoys,  which is an important issue in understanding the 
optimization error in deep learnling.  Althrouth the ideas and techniques used in this paper are not new, the authors 
establish quantitative global convergence rate of PDA in minimizing an KL-regularized objective  for the two layer neural network opitmization.   Overall,  this paper gives a nice contribution in understanding optimization in deep learning. 

One question: Does the constant hidden in $\tilde{O}(\epsilon^3)$ depend on the ambient dimension? If so, what is the quantitive 
relation between them? 
limitations_and_societal_impact: No.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a Particle Dual Averaging (PDA) algorithm to minimize non-linear functional of probability distributions. One of the main application of this algorithm is the training of two-layer neural networks. The authors obtain quantitative convergence results for PDA under mild assumption on the neural network for the minimization of an entropy-regularized loss function. In particular they show that a solution can be reached with precision $O(\varepsilon)$ after $O(\varepsilon^{-3})$ iterations. The theoretical study is completed with the investigation of the finite particle algorithm and generalization bounds. The authors then present a short experimental study on regression and classification tasks, illustrating the properties of the algorithm.
main_review: STRENGTHS:
First of all the paper is very well-written. The motivation and the algorithm are clearly presented and the theoretical results are given with precise assumptions. 

The idea of using dual averaging for probabilistic optimization is original and really promising. One of the key remark that minimizers of linearized functionals on probability measures with Kullback-Leibler regularization are given by Gibbs measures might find applications outside of the context of overparameterized neural networks.

The authors use recent tools in optimization/sampling (convergence in Kullback-Leibler divergence of the Langevin algorithm under log-Sobolev condition with quantitative rates, convergence of the dual averaging algorithm) in order to derive quantitative results. These quantitative results are really promising. 

WEAKNESSES:
One of the main weakness of the paper is its experiments which I found to be a bit too limited even for a theoretical paper. The authors could have dealt with real datasets for classification such as MNIST or CIFAR-10 in order to assess the scalability of their method with respect to the dimension and hence its applicability.

Similarly, even if some comparison with a classical training of neural networks (with SGD) are reported in the appendix, I think further comparisons should be conducted to assess the efficiency of the proposed methodology (for instance in Figure 4 in the appendix, PDA seems to perform only marginally better than SGD which is simpler to train). Also instead of SGD the author might consider sampling with a Langevin algorithm (i.e. changing the noise scaling). Doing so incorporates an entropic term and will allow for a fairer comparison with PDA in my opinion.

From a theoretical point of view I think that the authors should discuss in greater details the relationship between their algorithm and other works. In particular, how does the proposed approach relates to the ones of [1,2] which prove theoretical results for either SGD or the Langevin dynamics and not the PDA algorithm.

[1] Hu, Ren, Siska, Szpruch - Mean-field Langevin dynamics and energy landscape of neural networks
[2] Javanmard, Mondelli, Montanari - Analysis of a two-layer neural network via displacement convexity

COMMENTS:
-The original dual averaging algorithm allows flexibility in the primal and dual discretization steps, see (2.14) in [3]. In this work the authors have chosen $\beta_k = O(k^2)$ and $\lambda_k = O(k)$ if I am not mistaken. This choice of parameters is not discussed in the paper.
-Related to this remark, one of the limitation of the algorithm is that each inner-loop gets more and more expensive. Is this due to the way the parameters of the dual averaging are set? Is there any way to mitigate this issue?

MINOR COMMENTS:
-I am not sure to understand the role of $n$ in Proposition D. I assume that $x_i$ are the generated the test data points?

[3] Nesterov - Primal-dual subgradient methods for convex problems
limitations_and_societal_impact: Societal impact is irrelevant for this very theoretical work. The limitations of the algorithm could have been better highlighted and addressed (increasing cost of the inner loop, marginal performance over SGD), see my previous comments.
review_title: null

Meta-review: The authors introduce a novel Particle Dual Averaging technique to minimize to minimize a non-linear functional of probability distributions. In terms of applications, they focus on the training of two-layer neural networks. In this context, they present quantitative convergence results for an entropy-regularized loss function. They also discuss the finite particle algorithm and present generalization bounds. 

There was a short but informative discussion between reviewers. All the reviewers agree that the paper presents some original, interesting and solid theoretical contributions. However, it was felt by some reviewers that the experimental section was fairly weak and I encourage the authors to improve it before publication.

I recommend acceptance of the paper.


Decision: Accept (Poster)