论文标题
在随机设计下，凸出和非凸优化都是最小的噪声盲卷积的最小值
Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
论文作者
论文摘要
我们研究了在两个不同的设计下（即$〜$〜$〜$一种随机的傅立叶设计和高斯设计）下，凸出松弛和非凸优化在求解双线性系统中的有效性。尽管有广泛的适用性，但在存在随机噪声的情况下，对这两个范式的理论理解在很大程度上仍然不足。当前的论文通过证明：（1）两阶段的非convex算法在对数迭代次数中达到最小的精度。 （2）凸松弛还达到了最小的统计精度，相对于随机噪声。两种结果都在最新的理论保证方面有了显着改善。
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-à-vis random noise. Both results significantly improve upon the state-of-the-art theoretical guarantees.
