Polynomial-time Sparse Measure Recovery: From Mean Field Theory to Algorithm Design
This work addresses sparse measure recovery for applications in neural network optimization, but it appears incremental as it builds on existing mean-field theory and focuses on specific regimes.
The authors tackled the problem of sparse measure recovery by proposing a polynomial-time algorithm inspired by mean-field theory, which improves upon convex relaxation methods in a specific parameter regime and is applied to optimize two-dimensional, single-layer neural networks in realizable settings.
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 $\mathbb{R}$, 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.