{"ID":2890629,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.19611","arxiv_id":"2507.19611","title":"State evolution beyond first-order methods I: Rigorous predictions and finite-sample guarantees","abstract":"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.","short_abstract":"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 foc...","url_abs":"https://arxiv.org/abs/2507.19611","url_pdf":"https://arxiv.org/pdf/2507.19611v1","authors":"[\"Michael Celentano\",\"Chen Cheng\",\"Ashwin Pananjady\",\"Kabir Aladin Verchand\"]","published":"2025-07-25T18:28:09Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"cs.LG\",\"math.OC\",\"stat.ML\"]","methods":"[]","has_code":false}