Geometric step decay yields local linear convergence for stochastic algorithms on sharp nonconvex problems and gives matching or new guarantees for phase retrieval and blind deconvolution under Gaussian and heavy-tailed measurements.
Composite optimization for robust blind deconvolution
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The blind deconvolution problem seeks to recover a pair of vectors from a set of rank one bilinear measurements. We consider a natural nonsmooth formulation of the problem and show that under standard statistical assumptions, its moduli of weak convexity, sharpness, and Lipschitz continuity are all dimension independent. This phenomenon persists even when up to half of the measurements are corrupted by noise. Consequently, standard algorithms, such as the subgradient and prox-linear methods, converge at a rapid dimension-independent rate when initialized within constant relative error of the solution. We then complete the paper with a new initialization strategy, complementing the local search algorithms. The initialization procedure is both provably efficient and robust to outlying measurements. Numerical experiments, on both simulated and real data, illustrate the developed theory and methods.
fields
math.OC 1years
2019 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Stochastic algorithms with geometric step decay converge linearly on sharp functions
Geometric step decay yields local linear convergence for stochastic algorithms on sharp nonconvex problems and gives matching or new guarantees for phase retrieval and blind deconvolution under Gaussian and heavy-tailed measurements.