# Polynomial-time Sparse Measure Recovery: From Mean Field Theory to Algorithm Design

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 46 references that are in the map.
- First posted on arXiv 16 Apr 2022.

## Builds on (most cited first, 12 of 12)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Gaussian Process Behaviour in Wide Deep Neural Networks](https://mlsanity.com/paper/1804.11271/) (2018)
- [The large learning rate phase of deep learning: the catapult mechanism](https://mlsanity.com/paper/2003.02218/) (2020)
- [Dynamical Isometry and a Mean Field Theory of CNNs: How to Train 10,000-Layer Vanilla Convolutional Neural Networks](https://mlsanity.com/paper/1806.05393/) (2018)
- [Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice](https://mlsanity.com/paper/1711.04735/) (2017)
- [The Emergence of Spectral Universality in Deep Networks](https://mlsanity.com/paper/1802.09979/) (2018)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Sparse Optimization on Measures with Over-parameterized Gradient Descent](https://mlsanity.com/paper/1907.10300/) (2019)
- [Exact Support Recovery for Sparse Spikes Deconvolution](https://mlsanity.com/paper/1306.6909/) (2013)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Convergence Rates of Gradient Methods for Convex Optimization in the Space of Measures](https://mlsanity.com/paper/2105.08368/) (2021)

## Built on by (most cited first, 1 of 1)

- [On the symmetries in the dynamics of wide two-layer neural networks](https://mlsanity.com/paper/2211.08771/) (2022)

## Abstract (arXiv)

Mean field theory has provided theoretical insights into various algorithms by letting the problem size tend to infinity. We argue that the applications of mean-field theory go beyond theoretical insights as it can inspire the design of practical algorithms. Leveraging mean-field analyses in physics, we propose a novel algorithm for sparse measure recovery. For sparse measures over ℝ, we propose a polynomial-time recovery method from Fourier moments that improves upon convex relaxation methods in a specific parameter regime; then, we demonstrate the application of our results for the optimization of particular two-dimensional, single-layer neural networks in realizable settings.