# Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs

arXiv: https://arxiv.org/abs/2008.01724 · HTML: https://mlsanity.com/paper/2008.01724/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2020.

## Built on by (most cited first, 4 of 4)

- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [How robust is randomized blind deconvolution via nuclear norm minimization against adversarial noise?](https://mlsanity.com/paper/2303.10030/) (2023)

## Abstract (arXiv)

We investigate the effectiveness of convex relaxation and nonconvex optimization in solving bilinear systems of equations under two different designs (i.e.~a sort of random Fourier design and Gaussian design). Despite the wide applicability, the theoretical understanding about these two paradigms remains largely inadequate in the presence of random noise. The current paper makes two contributions by demonstrating that: (1) a two-stage nonconvex algorithm attains minimax-optimal accuracy within a logarithmic number of iterations. (2) convex relaxation also achieves minimax-optimal statistical accuracy vis-`a-vis random noise. Both results significantly improve upon the state-of-the-art theoretical guarantees.