提出可预测非凸优化算法的精确分析工具，适用于更广算法类别。
State evolution beyond first-order methods I: Rigorous predictions and finite-sample guarantees
- 基于状态演化框架，扩展至包含一阶与鞍点更新的通用算法
- 首次实现非坐标可分更新下的严格状态演化预测
- 提供有限样本保证，适合研究高维优化理论者
我们构建了一套用于分析高维非凸优化问题中迭代算法的精确工具箱，该问题具有随机数据特性。尽管已有研究证明一般一阶方法的低维统计量可通过称为状态演化的确定性递推关系进行预测，但本文关注的是将此预测推广到更广泛的算法类别。我们为任意由（可能交错的）一阶和鞍点更新构成的方法提供了状态演化模型，并取得两项核心成果：第一，在更新不满足坐标可分条件下仍建立严格的状态演化预测；第二，建立了有限样本保证，界定了经验更新与状态演化之间的偏差。过程中发展出一套技术工具包，其中一项是通用希尔伯特空间提升法，用于证明状态演化参数化形式的存在与唯一性；另一项结合了Bolthausen条件化方法与序列型Gordon高斯比较不等式，为通用有限样本分析提供了关键支持。
原文摘要 · Abstract (English)
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-order and saddle point updates, showing two main results. First, we establish a rigorous state evolution prediction that holds even when the updates are not coordinate-wise separable. Second, we establish finite-sample guarantees bounding the deviation of the empirical updates from the established state evolution. In the process, we develop a technical toolkit that may prove useful in related problems. One component of this toolkit is a general Hilbert space lifting technique to prove existence and uniqueness of a convenient parameterization of the state evolution. Another component of the toolkit combines a generic application of Bolthausen's conditioning method with a sequential variant of Gordon's Gaussian comparison inequality, and provides additional ingredients that enable a general finite-sample analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。