# Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling

arXiv: https://arxiv.org/abs/2508.10782 · HTML: https://mlsanity.com/paper/2508.10782/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 55 references that are in the map.
- First posted on arXiv 14 Aug 2025.

## Builds on (most cited first, 20 of 20)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [The Lasso with general Gaussian designs with applications to hypothesis testing](https://mlsanity.com/paper/2007.13716/) (2020)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [Approximate Message Passing algorithms for rotationally invariant matrices](https://mlsanity.com/paper/2008.11892/) (2020)
- [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization](https://mlsanity.com/paper/2110.02318/) (2021)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Information-Theoretic Limits for the Matrix Tensor Product](https://mlsanity.com/paper/2005.11273/) (2020)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021)
- [Approximate Message Passing for the Matrix Tensor Product Model](https://mlsanity.com/paper/2306.15580/) (2023)
- [Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding](https://mlsanity.com/paper/1501.05892/) (2015)
- [Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles](https://mlsanity.com/paper/2101.07464/) (2021)
- [Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing](https://mlsanity.com/paper/2309.15507/) (2023)

## Built on by (most cited first, 2 of 2)

- [Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime](https://mlsanity.com/paper/2509.24882/) (2025)
- [Decoupled Descent: Exact Test Error Tracking Via Approximate Message Passing](https://mlsanity.com/paper/2604.27883/) (2026)

## Abstract (arXiv)

We establish non-asymptotic bounds on the finite-sample behavior of generalized first-order iterative algorithms -- including gradient-based optimization methods and approximate message passing (AMP) -- with Gaussian data matrices and full-memory, non-separable nonlinearities. The central result constructs an explicit coupling between the iterates of a generalized first-order method and a conditionally Gaussian process whose covariance evolves deterministically via a finite-dimensional state evolution recursion. This coupling yields tight, dimension-free bounds under mild Lipschitz and moment-matching conditions. Our analysis departs from classical inductive AMP proofs by employing a direct comparison between the generalized first-order method and the conditionally Gaussian comparison process. This approach provides a unified derivation of AMP theory for Gaussian matrices without relying on separability or asymptotics. A complementary lower bound on the Wasserstein distance demonstrates the sharpness of our upper bounds.