Sparse optimization on measures with over-parameterized gradient descent

• 成果类型: Article
• 署名作者: Chizat, Lenaic
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Universite Paris Saclay
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01636-z
• 发表日期: 2022
• 页码: 487-532
• 关键词: empirical measures; transport; inequalities; CONVERGENCE; distance

摘要

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/epsilon) in the desired accuracy epsilon, instead of epsilon(-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.