State evolution beyond first-order methods I: Rigorous predictions and finite-sample guarantees
Michael Celentano, Chen Cheng, Ashwin Pananjady, Kabir Aladin Verchand
我们开发了一套工具箱，用于精确分析随机数据高维非凸优化问题上的迭代算法。虽然先前工作表明(广义)一阶方法的低维统计量可通过称为state evolution的确定性递推来预测，但我们的重点是为更广泛的算法类建立此类预测。我们为任何由(可能交错的)一阶和鞍点更新构成的迭代方法提供了state evolution，并展示两个主要结果：首先，我们建立了严格的state evolution预测，即使更新不是坐标可分时也成立；其次，我们建立了有限样本保证，界定了经验更新与既定state evolution之间的偏差。在此过程中，我们开发的技术工具包可能对相关问题有所助益。该工具包的一个组成部分是通用的希尔伯特空间提升技术，用于证明state evolution便捷参数化存在且唯一。工具包的另一个组成部分将Bolthausen条件方法的通用应用与Gordon高斯比较不等式的序列变体相结合，提供了支持通用有限样本分析的额外要素。
We develop a toolbox for exact analysis of iterative algorithms on a class of high-dimensional nonconvex optimization problems with random data. While prior work has shown that low-dimensional statistics of (generalized) first-order methods can be predicted by a deterministic recursion known as state evolution, our focus is on developing such a prediction for a more general class of algorithms. We provide a state evolution for any method whose iterations are given by (possibly interleaved) first...