Optimal sample complexity of subgradient descent for amplitude flow via non-Lipschitz matrix concentration

DOI10.4310/CMS.2021.V19.N7.A11MaRDI QIDQ2057056zbMATH OpenOpenAlexFDO

Authors Oscar Leong, Vladislav Voroninski, Paul E. Hand

Publication date 8 December 2021

Published in Communications in Mathematical Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.00288

zbMATH Keywords

concentration inequalitynon-convex optimizationphase retrievalsubgradient descent

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Information theory (general) (94A15)

Abstract: We consider the problem of recovering a real-valued $n$-dimensional signal from $m$ phaseless, linear measurements and analyze the amplitude-based non-smooth least squares objective. We establish local convergence of subgradient descent with optimal sample complexity based on the uniform concentration of a random, discontinuous matrix-valued operator arising from the objective's gradient dynamics. While common techniques to establish uniform concentration of random functions exploit Lipschitz continuity, we prove that the discontinuous matrix-valued operator satisfies a uniform matrix concentration inequality when the measurement vectors are Gaussian as soon as $m=Omega(n)$ with high probability. We then show that satisfaction of this inequality is sufficient for subgradient descent with proper initialization to converge linearly to the true solution up to the global sign ambiguity. As a consequence, this guarantees local convergence for Gaussian measurements at optimal sample complexity. The concentration methods in the present work have previously been used to establish recovery guarantees for a variety of inverse problems under generative neural network priors. This paper demonstrates the applicability of these techniques to more traditional inverse problems and serves as a pedagogical introduction to those results.

Recommendations

• Subgradient Sampling for Nonsmooth Nonconvex Minimization
• Convergence of the Gradient Sampling Algorithm for Nonsmooth Nonconvex Optimization
• A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization
• A subgradient method based on gradient sampling for solving convex optimization problems
• Subdeterminant maximization via nonconvex relaxations and anti-concentration
• Non-asymptotic guarantees for sampling by stochastic gradient descent
• A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
• Sample complexity of sample average approximation for conditional stochastic optimization
• Subsampled nonmonotone spectral gradient methods
• Sublinear convergence of a tamed stochastic gradient descent method in Hilbert space

This page was built for publication: Optimal sample complexity of subgradient descent for amplitude flow via non-Lipschitz matrix concentration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2057056)