Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization
Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization
复制标题
广义秩一矩阵感知的交替最小化：随机初始化的敏锐预测
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
A. Pananjady
中科院分区：
文献类型：
--
作者：
Kabir Chandrasekher;Mengqi Lou;A. Pananjady
我们考虑了一个秩-$1$矩阵的因子估计问题，这个秩-$1$的测量值是非线性变换的，并且被噪声破坏。考虑非线性的两种典型选择，研究了从随机初始化出发的非凸优化问题的自然交替更新规则的收敛性。我们通过推导出即使在高维问题中也是准确的确定性递归，证明了该算法的样本分割版本的尖锐收敛保证。值得注意的是，虽然无限样本总体更新是无信息的，并且建议在单个步骤中精确恢复，但算法-以及我们的确定性预测-从随机初始化中以几何速度收敛。我们尖锐的非渐近分析还揭示了该问题的几个其他细粒度特性，包括非线性和噪声水平如何影响收敛行为。在技术层面上，我们的结果表明，当每次迭代使用$n$观测值运行时，经验误差递归可以通过我们的确定性序列在$n^{-1/2}$阶波动内进行预测。我们的技术利用了源自高维M估计文献的“留一”工具，并为在其他具有随机数据的高维优化问题中从随机初始化中尖锐地分析高阶迭代算法提供了途径。
We consider the problem of estimating the factors of a rank-$1$ matrix with i.i.d. Gaussian, rank-$1$ measurements that are nonlinearly transformed and corrupted by noise. Considering two prototypical choices for the nonlinearity, we study the convergence properties of a natural alternating update rule for this nonconvex optimization problem starting from a random initialization. We show sharp convergence guarantees for a sample-split version of the algorithm by deriving a deterministic recursion that is accurate even in high-dimensional problems. Notably, while the infinite-sample population update is uninformative and suggests exact recovery in a single step, the algorithm -- and our deterministic prediction -- converges geometrically fast from a random initialization. Our sharp, non-asymptotic analysis also exposes several other fine-grained properties of this problem, including how the nonlinearity and noise level affect convergence behavior. On a technical level, our results are enabled by showing that the empirical error recursion can be predicted by our deterministic sequence within fluctuations of the order $n^{-1/2}$ when each iteration is run with $n$ observations. Our technique leverages leave-one-out tools originating in the literature on high-dimensional $M$-estimation and provides an avenue for sharply analyzing higher-order iterative algorithms from a random initialization in other high-dimensional optimization problems with random data.