On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport
Many tasks in machine learning and signal processing can be solved by minimizing a convex function of a measure. This includes sparse spikes deconvolution or training a neural network with a single hidden layer. For these problems, we study a simple minimization method: the unknown measure is discretized into a mixture of particles and a continuous-time gradient descent is performed on their weights and positions. This is an idealization of the usual way to train neural networks with a large hidden layer. We show that, when initialized correctly and in the many-particle limit, this gradient flow, although non-convex, converges to global minimizers. The proof involves Wasserstein gradient flows, a by-product of optimal transport theory. Numerical experiments show that this asymptotic behavior is already at play for a reasonable number of particles, even in high dimension.
This paper considers the problem of optimizing over measures instead of parameters directly ( as is standard in ML), for differentiable predictors with convex loss. This is an infinite dimensional convex optimization problem. The paper considers instead optimizing with m particles (dirac deltas). As m tends to infinity this corresponds to optimizing over the measure space. Proposition 2.3 shows existence and uniqueness of the particle gradient flow for a given initialization. The main results show convergence of the particle gradient flow to the minimizer under infinite particle limit and under the assumptions of  separability of the support of initialization.   The paper has experiments on toy synthetic problems for sparse deconvolution and training one hidden layer neural nets, evaluating the performance of the finite particle method. The experiments show that for these toy problems, gradient flow with smaller number of particles (~100) converges to a global minimizer. Even though the theoretical results do not apply for ReLU networks, experiments show favorable performance for this class as well.     Comments:   The paper is a theoretical paper studying the optimization over measures using particle gradient flow,  and provides conditions for convergence to global optima. It also has  encouraging experiments on toy examples. The paper currently lacks discussion of limitations of this approach and what is required to scale it to solving reasonable ML tasks.   The results also hold under some fairly strong assumptions on initialization and technical conditions on the functions. It will also be useful to discuss these assumptions a bit more on when do we expect them to hold in practice.   In the introduction, it might be useful to introduce the optimization problem slowly with more details, as it is optimization on \mu and not \theta (as normally done). May be even highlight this difference to make it more clear.  In line 25, the rectified linear unit doesn't fit the framework that requires \phi be differentiable.   Subdifferential as defined in line 135 need not exist for a non-convex function right?. What happens to the subgradient flow then?  Why is the condition on initialization required for proposition 2.5 but not for proposition 2.3?   The description about gap between stationarity and optimality in lines 189-190 is not very clear.    Other comments:    R() is a poor choice of notation for the loss function, as it is confusing with the Real line and is also commonly used for the regularizer part.  There is div() notation used in line 157 and  referred to in appendix without defining it in the main paper, which reduces the readability of the paper.   There has been some empirical work in neural nets that separately optimizes magnitude and direction of units of neural nets (https://arxiv.org/abs/1602.07868). It seems there is some high level similarity between these methods that might be interesting to explore more.   Typos in lines 181, 220