Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912537789857792 |
|---|---|
| author | Reeves, Galen |
| author_facet | Reeves, Galen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_10782 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling Reeves, Galen Machine Learning Probability Statistics Theory 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. |
| title | Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling |
| topic | Machine Learning Probability Statistics Theory |
| url | https://arxiv.org/abs/2508.10782 |