# Sparse Optimization on Measures with Over-parameterized Gradient Descent

arXiv: https://arxiv.org/abs/1907.10300 · HTML: https://mlsanity.com/paper/1907.10300/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2019.

## Built on by (most cited first, 30 of 50)

- [Convex Analysis of the Mean Field Langevin Dynamics](https://mlsanity.com/paper/2201.10469/) (2022)
- [A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network](https://mlsanity.com/paper/2102.02410/) (2021)
- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Learning sparse features can lead to overfitting in neural networks](https://mlsanity.com/paper/2206.12314/) (2022)
- [Understanding Deflation Process in Over-parametrized Tensor Decomposition](https://mlsanity.com/paper/2106.06573/) (2021)
- [Sampling with Mollified Interaction Energy Descent](https://mlsanity.com/paper/2210.13400/) (2022)
- [Global Convergence of Three-layer Neural Networks in the Mean Field Regime](https://mlsanity.com/paper/2105.05228/) (2021)
- [On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Setting](https://mlsanity.com/paper/2106.06251/) (2021)
- [Gradient Descent on Infinitely Wide Neural Networks: Global Convergence and Generalization](https://mlsanity.com/paper/2110.08084/) (2021)
- [An Explicit Expansion of the Kullback-Leibler Divergence along its Fisher-Rao Gradient Flow](https://mlsanity.com/paper/2302.12229/) (2023)
- [Analysis of feature learning in weight-tied autoencoders via the mean field lens](https://mlsanity.com/paper/2102.08373/) (2021)
- [An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games](https://mlsanity.com/paper/2211.01280/) (2022)
- [On Feature Learning in Neural Networks with Global Convergence Guarantees](https://mlsanity.com/paper/2204.10782/) (2022)
- [Features are fate: a theory of transfer learning in high-dimensional regression](https://mlsanity.com/paper/2410.08194/) (2024)
- [Weighted quantization using MMD: From mean field to mean shift via gradient flows](https://mlsanity.com/paper/2502.10600/) (2025)
- [Convergence analysis for gradient flows in the training of artificial neural networks with ReLU activation](https://mlsanity.com/paper/2107.04479/) (2021)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)
- [Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methods](https://mlsanity.com/paper/2205.14818/) (2022)
- [Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activation](https://mlsanity.com/paper/2108.08106/) (2021)
- [Parallel Deep Neural Networks Have Zero Duality Gap](https://mlsanity.com/paper/2110.06482/) (2021)
- [Non-convergence to global minimizers for Adam and stochastic gradient descent optimization and constructions of local minimizers in the training of artificial neural networks](https://mlsanity.com/paper/2402.05155/) (2024)
- [Interaction-Force Transport Gradient Flows](https://mlsanity.com/paper/2405.17075/) (2024)
- [On the symmetries in the dynamics of wide two-layer neural networks](https://mlsanity.com/paper/2211.08771/) (2022)
- [Privacy-preserving data release leveraging optimal transport and particle gradient descent](https://mlsanity.com/paper/2401.17823/) (2024)
- [Hellinger-Kantorovich Gradient Flows: Global Exponential Decay of Entropy Functionals](https://mlsanity.com/paper/2501.17049/) (2025)
- [Understanding the Mechanisms of Fast Hyperparameter Transfer](https://mlsanity.com/paper/2512.22768/) (2025)
- [Rethinking Gauss-Newton for learning over-parameterized models](https://mlsanity.com/paper/2302.02904/) (2023)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [Limiting fluctuation and trajectorial stability of multilayer neural networks with mean field training](https://mlsanity.com/paper/2110.15954/) (2021)
- [Convergence beyond the over-parameterized regime using Rayleigh quotients](https://mlsanity.com/paper/2301.08117/) (2023)

## Abstract (arXiv)

Minimizing a convex function of a measure with a sparsity-inducing penalty is a typical problem arising, e.g., in sparse spikes deconvolution or two-layer neural networks training. We show that this problem can be solved by discretizing the measure and running non-convex gradient descent on the positions and weights of the particles. For measures on a d-dimensional manifold and under some non-degeneracy assumptions, this leads to a global optimization algorithm with a complexity scaling as log(1/ε) in the desired accuracy ε, instead of ε-d for convex methods. The key theoretical tools are a local convergence analysis in Wasserstein space and an analysis of a perturbed mirror descent in the space of measures. Our bounds involve quantities that are exponential in d which is unavoidable under our assumptions.