Paper ID: 2204.07879 • Published Apr 16, 2022

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

Hadi Daneshmand, Francis Bach
TL;DR
Get AI-generated summaries with premium
Get AI-generated summaries with premium
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.