Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

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

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that iterates of generalized first-order methods on Gaussian matrices can be coupled to a conditionally Gaussian proxy, with maximum deviation over $T$ steps bounded by a constant independent of the ambient dimension $n$.

desk verdict A genuinely new coupling idea, but the main theorem is unproven because Definition-1 matching does not make the mismatch term ψ1 vanish. read the letter →

arxiv 2508.10782 v1 pith:MUXOJW7Z submitted 2025-08-14 stat.ML math.PRmath.STstat.TH

Galen Reeves This is my paper · ORCID
classification stat.MLmath.PRmath.STstat.TH
keywords generalizedfirst-ordermethodsapproximatemessagepassingstateevolutionGaussiancouplingdimension-freeboundsnon-asymptoticanalysisconcentrationWassersteindistance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to show that the state-evolution picture behind approximate message passing (AMP) — the replacement of a complicated iterative algorithm by a Gaussian process whose covariance is updated by a deterministic recursion — holds at finite dimension, uniformly across all $n$ coordinates at once, not only in an asymptotic or coordinate-by-coordinate sense. The main claim, Theorem 1, couples the iterates $x_t$ of a generalized first-order method (a recursion $x_t = A f_t(x_{

What carries the argument

The load-bearing object is the explicit coupling of Definition 2. At each step the nonlinear response $f_t(y_{<t})$ is turned into a nearly orthonormal vector $q_t$ by Gram–Schmidt against the previous $q_s$ (normalized to length $\sqrt{n}$), and the noise entering the comparison process is $z_t = A q_t - \frac{1}{n}\sum_{s \le t}\langle z_s, q_t\rangle q_s + \sum_{s \le t} A'_{st} q_s$, where $A'$ is an independent copy of $A$; the correction terms are Onsager-like debiasing terms that make the $z_t$ exactly i.i.d. standard Gaussian, so $w_t = \sum_{s \le t}\Omega_{st} z_s$ has covariance $\Sigma = \Omega^\top\Omega$. The proof that the increments are independent is a Gaussian-conditioning argument (Lemma 9, generalizing the lemma in [2]): conditional on the past, a GOE matrix has Gaussian law with computable mean and covariance, and orthogonality of the row spaces forces the conditional means to zero and conditional variances to the identity. Three quantitative tools complete the argument: a discrete-time stability bound (Lemma 14) that inflates the one-step mismatch by $(1 + L_f + L_g)^{T-1}$; Gaussian concentration of measure (Lemma 10) that controls the mismatch terms $\psi_1, \psi_2$ at the $\sqrt{r}$ scale; and a Cholesky perturbation inequality (Lemma 12, from [57]) that turns errors in the empirical second-moment matrix into errors in the Cholesky factors at the cost of a $\log(4T)$ factor.

What would settle it

Simulate the exact coupling of Definition 2 for a non-separable, full-memory Lipschitz recursion with a numerically matched pair $(m,\Sigma)$, across $n = 10^3, 10^4, 10^5$ at fixed $T$: if $\max_{t \in [T]}\|x_t - y_t\|$ grows with $n$ (for instance like $\sqrt{n}$), or if the empirical probability $\mathbb{P}[\max_t \|x_t - y_t\| \ge C\sqrt{r}]$ exceeds $2e^{-r}$, Theorem 1 is refuted. The same setup with $T = c\log n$ chosen so that $T + \ln\kappa(\Sigma)$ exceeds $C\log n$ tests the predicted breakdown of the scaling condition (12), namely that $n^{-1/2}\|X - Y\|$ should then fail to vanish.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for $A \sim \mathrm{GOE}(n)$ and $L$-Lipschitz, possibly non-separable, full-memory nonlinearities $f_t, g_t$, if the mean functions $(m_t)$ and covariance $\Sigma$ of the comparison process are matched to the original recursion by the recursive state-evolution construction in Definition 1 and $\Sigma$ is positive definite, then there is a coupling of the two processes under which $\mathbb{P}\big[\max_{t \in [T]} \|x_t - y_t\| \ge C\sqrt{r}\big] \le 2e^{-r}$ for all $0 \le r \le n$, with $C$ depending only on $T$, $L$, and the extreme eigenvalues of $\Sigma$. In plain terms, the whole $n$-dimensional trajectory of the algorithm stays within a dimension-free distance of a Gaussian process whose law is known, up to an exponentially small failure probability. The proof is one-shot rather than inductive: an independent copy of the Gaussian matrix supplies a stochastic correction so that the comparison process has exactly its target law, and then Gaussian concentration converts the mismatch between $(f,g)$ and $(m,\Sigma)$ into the tail bound. Theorem 6 complements this with an exact formula for the quadratic Wasserstein distance in a constant/linear setting, showing the coupling distance cannot vanish with $n$ and that for autoregressive updates with $|\lambda| > 1$ the optimal error grows exponentially in $T$.

Load-bearing premise

The argument presupposes that the state-evolution recursion of Definition 1 has a solution — matched mean functions $m_t$ and a positive-definite covariance $\Sigma$, with each $m_t$ Lipschitz — and the paper proves no existence or uniqueness theorem for such a matched pair for general Lipschitz $(f,g)$; Theorem 1 as stated does not even list the Lipschitz condition on $m_t$ that the proof of Theorem 5, from which it follows, requires.

Editorial extensions

If this is right

  • State evolution becomes a finite-sample theorem: for fixed $T$, the full trajectory $\{x_1,\dots,x_T\}$ of an AMP or gradient-based method is within $\mathrm{O}(1)$ of a Gaussian process with deterministically evolving covariance, with exponential tails, for non-separable nonlinearities that earlier non-asymptotic results could not handle.
  • The iteration count may grow with dimension: the condition $T + \ln\kappa(\Sigma) = O(\log n)$ suffices for $n^{-1/2}\|X - Y\|$ to vanish, improving on the previous $T = o(\log n/\log\log n)$ regime for finite-sample AMP.
  • Because the GOE result transfers to asymmetric Gaussian matrices with correlated rows and columns via the arguments of [17,18], the dimension-free bound applies beyond the symmetric ensemble in which it is proved.
  • The lower bound shows the $\mathrm{O}(1)$ scale is not an artifact of the coupling: in the exactly solvable linear setting the quadratic Wasserstein distance between $x_t$ and $y_t$ is bounded below by $(\sqrt{2}-1)^2$ times the state-evolution variance $\alpha_t^2$ for every $n$, and with $|\lambda| > 1$ autoregressive updates the optimal error grows exponentially in $T$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The construction doubles as a simulation scheme and a diagnostic: because the coupling needs only two independent GOE draws and the Gram–Schmidt basis built from the algorithm's own responses, one can generate the comparison process exactly; conversely, if the empirical law of the increments $z_t$ departs from i.i.d. Gaussian, the algorithm is outside the regime where state evolution describes it.
  • The bound's dependence on $\kappa(\Sigma)$ suggests the guarantee degrades exactly where AMP analyses usually operate: close to a state-evolution fixed point the conditional variance of the increments collapses, so $\Sigma$ becomes near-singular and the constant $C$ blows up before the asymptotic description takes over. A numerical check of the error versus $\kappa(\Sigma)$ along the iteration pat
  • Because the argument is a one-shot comparison rather than an induction over steps, it is plausible that the same coupling strategy transfers to continuous-time limits and to stochastic-gradient dynamics, where inductive decorrelation proofs are awkward; the paper gestures at dynamical mean-field theory but does not make this transfer.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper develops a coupling-based framework for non-asymptotic analysis of generalized first-order methods (1) with Gaussian data matrices. The main object is a conditionally Gaussian comparison process (2) whose mean and covariance are prescribed by a state-evolution recursion (Definition 1). For any Lipschitz f_t,g_t and positive-definite Σ, the authors construct an explicit coupling (Definition 2) between the true iterates x_t and the Gaussian process y_t, and prove (Theorems 4 and 5) high-probability bounds on the coupling error in terms of deterministic mismatch parameters ψ1,ψ2. They then claim that under the state-evolution matching of Definition 1 these mismatches vanish, so that a dimension-free bound follows (Theorem 1). A separate lower bound (Theorem 6) computes the exact quadratic Wasserstein distance in a linear setting and is used to argue tightness of the upper bounds. The paper also claims improved scaling T=o(log n) for the number of iterations and an extension to pseudo-Lipschitz nonlinearities.

Significance. If the main theorem were established, the paper would be a significant advance: it would give the first dimension-free, non-asymptotic coupling bounds for full-memory, non-separable nonlinearities in AMP-type algorithms, going beyond the row-separable and asymptotic results in the literature. The Gaussian-conditioning construction and the exact Wasserstein lower bound in Theorem 6 are valuable and self-contained contributions in their own right. However, the central upper-bound claim is not established in the current version. The proof of Theorem 5 has a false step in the claim that Definition 1 matching implies ψ1=ψ2=0, and Theorem 3's proof has an unaddressed completeness gap in the Gram-Schmidt construction. These issues undermine the paper's main advertised result, although the general sample-mismatch bound in Theorem 4 may remain of independent interest.

major comments (3)
  1. [§4.2, proof of Theorem 3] The assertion that Definition 1 matching gives ψ1=ψ2=0 is false. Consider T=2, α>0, f1=c with ||c||^2=n, f2(y1)=c+α y1, and g1=g2=0. Definition 1 gives m1=0, Σ=[[1,1],[1,1+α^2]], b_{1,2}=(1+α^2)/α, and m2=(1+α^2)c/α. However, the matrix B defined just before Theorem 5 equals Σ^{-1}E[(Y-M(Y))^T F(Y)]/n = [[0,α],[0,0]], because f2(y1)=c+α y1 and Cov(w1,w2)=I. Hence the second column of M(Y)-G(Y)-F(Y)B is m2-αc = c/α, so ψ1 = (√n/α)/(1+√(1+α^2)), which grows as √n. The root cause is that Definition 1 (Eq. 6b) uses the leading principal inverse Σ_{≤t}^{-1}, whereas B in Theorem 5 uses the full T×T inverse Σ^{-1}; these agree only in special cases. Consequently Theorem 5 does not imply Theorem 1 via ψ1=ψ2=0, and the central dimension-free upper bound is unsupported as written.
  2. [§4.2, proof of Theorem 3] The proof of Theorem 3 relies on the identity Σ_{t=1}^T u_t u_t^T = I. This identity holds only if the vectors q1,...,qT from Definition 2 are extended to an orthonormal basis of R^n; for T<n, Definition 2 as written defines only T vectors. The fallback rule in Definition 2 references 'the span of {q1,...,qn}' before q_n has been defined, so the construction is not well-defined. The authors should specify a completion of the Gram-Schmidt process to n vectors (for example, using the fixed basis v1,...,vn) and verify that the independence of z1,...,zT and identity (10) are independent of the chosen completion. As it stands, Theorem 3 is not fully proved.
  3. [§1, Theorem 1; §3.2, Theorem 5] Theorem 1 assumes only that f_t and g_t are L-Lipschitz, but the proof route through Theorem 5 requires each m_t to be L_m-Lipschitz, and the final bound depends on L_m through L = log2(2T) + √T(Lf+Lg+Lm)(1+Lm)^{T-1}κ(Σ)^{1/2}. No argument is given that the matched m_t defined by (6a)-(6b) are Lipschitz with constants bounded independently of n; the coefficients b_st depend on the conditioning of Σ_{≤t} and may be large. Theorem 1 should either state the Lipschitz condition on m_t explicitly or prove that it follows from the matching construction with a dimension-free constant; otherwise the theorem is not a consequence of Theorem 5.
minor comments (4)
  1. [§4.5] In the display after solving for X and Y, the second equality reads Y = ZΩ(I−Λ)^{-1}, but it should be Y = ZΩ(I−Γ)^{-1} since Y = YΓ + ZΩ.
  2. [§3.2, Theorem 5; §4.4] Theorem 5 defines L := log2(2T) + ... while the proof in Section 4.4 defines L = log2(T) + ...; the two definitions should be made consistent.
  3. [§3.2.1, Eq. (13)] The inequality Lip(g_t) ≤ (Σ_{s<t}|b_st|^2)^{1/2} L_f ≤ √T L_f^2 appears to assume |b_st| ≤ L_f, which is not established in the text; please justify or remove this step.
  4. [§3.2.2] The pseudo-Lipschitz extension argument applies Theorem 5 to Lipschitz extensions and then uses the resulting bound on ∥X−Y∥ to infer that both X and Y lie in the ball B_n(ρ); this is circular unless ρ is chosen first and the Lipschitz-extension constants are shown to be acceptable for the resulting probability bounds. Please spell out the order of quantifiers.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the coupling proof is self-contained; the unsupported claim that Definition 1 matching implies ψ1=ψ2=0 is a proof gap, not a circular reduction.

full rationale

The central result is a constructive coupling (Definition 2) whose proof verifies that the constructed z_t are i.i.d. standard Gaussian via Gram-Schmidt orthogonality and Gaussian conditioning; this does not presuppose the theorem. Theorem 4 bounds the coupling error by explicit mismatch terms Δ1 and Δ2, and Theorem 5 converts these into dimension-free tail bounds using Gaussian concentration and stability lemmas. The parameters (m,Σ) in Definition 1 are defined by moment-matching recursions, not fitted to data to force the final bound; ψ2=0 is literally Σ = E[F^T F]/n, while ψ1=0 would be a nontrivial orthogonality property of the debiasing coefficients. The paper asserts without proof that matched parameters give ψ1=ψ2=0 and that Theorem 1 follows; this step is mathematically unsupported (indeed a two-step linear example can give ψ1~√n), but that is an error in the derivation chain, not circularity, because the asserted identity is not the same as the theorem's conclusion and is not established by definition. Self-citations to [17,18] are used only for an extension from GOE to other Gaussian ensembles and are not load-bearing; no uniqueness theorem from prior work is invoked to forbid alternatives, and no known result is simply renamed. The lower bound is obtained from closed-form Gaussian Wasserstein formulas, independent of the upper-bound construction. Hence no circular step satisfies the evidential standard of this review.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the assumed existence of a state-evolution fixed point, the unproven vanishing of the mismatch term ψ1, and Lipschitz regularity. No numbers are fitted to data; the state-evolution parameters are defined by fixed-point equations, so there are no free parameters in the sense of ad hoc fitted values. No new physical entities or mediators are introduced.

assumptions (4)
  • domain assumption The state-evolution recursion in Definition 1 admits a solution (m, Σ) with Σ positive definite and each m_t Lipschitz for the given (f, g).
    Theorem 1 and the ψ1 = ψ2 = 0 simplification in Theorem 5 require the parameters to be matched to the original system via Definition 1, but no existence or uniqueness result is provided for general Lipschitz functions. This is load-bearing because the simple dimension-free bound depends on the matched parameters.
  • ad hoc to paper Under state-evolution matching, the residual M(Y) - G(Y) - F(Y)B has zero expected norm, i.e., ψ1 = 0.
    This is stated after Theorem 5 without proof. It is not obvious from the recursion because m_t only depends on past f's, while B includes all s,t entries. A full proof would need to show the population least-squares coefficient matrix B equals the strictly lower-triangular state-evolution coefficient matrix.
  • domain assumption The functions ft, gt (and mt for Theorem 5) are Lipschitz with constants independent of n and T.
    Assumed in Theorem 1 and Theorem 5; the dimension-free nature of the bounds depends on these constants not growing with n. Theorem 1 does not explicitly assume mt is Lipschitz, yet the proof via Theorem 5 requires it.
  • standard math Standard Gaussian concentration and matrix concentration inequalities, including Lemma 10 and Lemma 11, hold as stated.
    These are standard results with proofs cited or sketched in the paper, and they are used throughout the upper-bound arguments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling." pith.science (2026). https://pith.science/paper/MUXOJW7Z

@misc{pith2026250810782,
  author       = {Pith},
  title        = {Pith review of: Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MUXOJW7Z}},
  note         = {Machine review of arXiv:2508.10782}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2508.10782 by the authors.

Figure 1
Figure 1. An explicit coupling between the generalized first-order method [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime

    cs.LG 2025-09 conditional novelty 6.0 of 10

    For diagonal and quadratic two-layer networks, training maps to LASSO and matrix compressed sensing, yielding a full phase diagram of excess-risk scaling exponents and a spectral characterization of the trained weights.

Reference graph

Works this paper leans on

57 extracted references · 46 canonical work pages · cited by 1 Pith paper

  1. [1]

    Message-passing algorithms for compressed sensing,

    D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,” Proceedings of the National Academy of Sciences , vol. 106, no. 45, pp. 18 914–18 919, Nov. 2009

    work page 2009

  2. [2]

    The dynamics of message passing on dense graphs, with applications to compressed sensing,

    M. Bayati and A. Montanari, “The dynamics of message passing on dense graphs, with applications to compressed sensing,” IEEE Transactions on Information Theory , vol. 57, no. 2, pp. 764–785, Feb. 2011

    2011

  3. [3]

    Generalized approximate message passing for estimation with random linear mixing,

    S. Rangan, “Generalized approximate message passing for estimation with random linear mixing,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT) , St. Petersburg, Russia, 2011, pp. 2174–2178

    work page 2011

  4. [4]

    The LASSO risk for gaussian matrices,

    M. Bayati and A. Montanari, “The LASSO risk for gaussian matrices,”IEEE Transactions on Information Theory, vol. 58, no. 4, pp. 1997–2017, Apr. 2012

    work page 1997

  5. [5]

    State evolution for general approximate message passing algorithms, with applications to spatial coupling,

    A. Javanmard and A. Montanari, “State evolution for general approximate message passing algorithms, with applications to spatial coupling,” Information and Inference: A Journal of the IMA , vol. 2, no. 2, pp. 115–144, 2013

    work page 2013

  6. [6]

    Vector approximate message passing,

    S. Rangan, P. Schniter, and A. K. Fletcher, “Vector approximate message passing,” IEEE Transactions on Information Theory , vol. 65, no. 10, pp. 6664–6684, 2019

    work page 2019

  7. [7]

    Approximate message passing with rigorous guarantees for pooled data and quantitative group testing,

    N. Tan, P. P. Cobo, J. Scarlett, and R. Venkataramanan, “Approximate message passing with rigorous guarantees for pooled data and quantitative group testing,” SIAM Journal on Mathematics of Data Science, vol. 6, no. 4, pp. 1027–1054, 2024

    work page 2024

  8. [8]

    Capacity-achieving sparse superposition codes via ap- proximate message passing decoding,

    C. Rush, A. Greig, and R. Venkataramanan, “Capacity-achieving sparse superposition codes via ap- proximate message passing decoding,” IEEE Transactions on Information Theory , vol. 63, no. 3, pp. 1476–1500, 2017

    work page 2017

Show all 57 references
  1. [9]

    Iterative reconstruction of rank-one matrices in noise,

    A. K. Fletcher and S. Rangan, “Iterative reconstruction of rank-one matrices in noise,” Information and Inference, vol. 7, no. 3, pp. 531–562, Jan. 2018

    2018

  2. [10]

    Bilinear generalized approximate message passing—part II: Applications,

    J. T. Parker, P. Schniter, and V. Cevher, “Bilinear generalized approximate message passing—part II: Applications,” IEEE Transactions on Signal Processing , vol. 62, no. 22, pp. 5854–5867, Nov. 2014

    2014

  3. [11]

    Information-theoretically optimal sparse PCA,

    Y. Deshpande and A. Montanari, “Information-theoretically optimal sparse PCA,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT) , Honolulu, HI, 2014, pp. 2197–2201

    2014

  4. [12]

    Constrained low-rank matrix estimation: Phase transitions, approximate message passing and applications,

    T. Lesieur, F. Krzakala, and L. Zdeborov´ a, “Constrained low-rank matrix estimation: Phase transitions, approximate message passing and applications,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2017, no. 7, Jul. 2017

    2017

  5. [13]

    Estimation of low-rank matrices via approximate message passing,

    A. Montanari and R. Venkataramanan, “Estimation of low-rank matrices via approximate message passing,” The Annals of Statistics , vol. 49, no. 1, pp. 321–345, Feb. 2021

    2021

  6. [14]

    Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity,

    J. K. Behne and G. Reeves, “Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity,” in Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, 2022

    2022

  7. [15]

    Fundamental limits in structured principal component analysis and how to reach them,

    J. Barbier, F. Camilli, M. Mondelli, and M. S´ aenz, “Fundamental limits in structured principal component analysis and how to reach them,” Proceedings of the National Academy of Sciences , vol. 120, no. 30, Jul. 2023

    2023

  8. [16]

    Approximate message passing for the matrix tensor product model,

    R. Rossetti and G. Reeves, “Approximate message passing for the matrix tensor product model,” [Online]. Available https://arxiv.org/pdf/2306.15580, 2023. 24

    2023 arXiv

  9. [17]

    Linear operator approximate message passing: Power method with partial and stochastic updates,

    R. Rossetti, B. Nazer, and G. Reeves, “Linear operator approximate message passing: Power method with partial and stochastic updates,” in 2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 741–746

    2024

  10. [18]

    Linear operator approximate message passing (OpAMP),

    ——, “Linear operator approximate message passing (OpAMP),” [Online]. Available https://arxiv.org/ pdf/2405.08225, 2024

    2024

  11. [19]

    Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization,

    A. El Alaoui, A. Montanari, and M. Sellke, “Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization,” in IEEE Symposium on Foundations of Computer Science (FOCS), 2022, pp. 323–334

    2022

  12. [20]

    Posterior sampling in high dimension via diffusion processes,

    A. Montanari and Y. Wu, “Posterior sampling in high dimension via diffusion processes,” [Online]. Available: https://arxiv.org/abs/2304.11449, 2024

    2024 arXiv

  13. [21]

    Sampling from spherical spin glasses in total variation via algorithmic stochastic localization,

    B. Huang, A. Montanari, and H. T. Pham, “Sampling from spherical spin glasses in total variation via algorithmic stochastic localization,” [Online]. Available: https://arxiv.org/abs/2404.15651, 2024

    2024 arXiv

  14. [22]

    Sampling from the random linear model via stochastic localization up to the AMP threshold,

    H. Cui, Z. Yu, and J. Liu, “Sampling from the random linear model via stochastic localization up to the AMP threshold,” [Online]. Available: https://arxiv.org/abs/2407.10763, 2024

    2024 arXiv

  15. [23]

    The estimation error of general first order methods,

    M. Celentano, A. Montanari, and Y. Wu, “The estimation error of general first order methods,” in Conference on Learning Theory. PMLR, 2020, pp. 1078–1141

    2020

  16. [24]

    The high-dimensional asymptotics of first order methods with random data,

    M. Celentano, C. Cheng, and A. Montanari, “The high-dimensional asymptotics of first order methods with random data,” [Online]. Available https://arxiv.org/pdf/2112.07572.pdf, 2021

    2021 arXiv

  17. [25]

    Rigorous dynamical mean-field theory for stochastic gradient descent methods,

    C. Gerbelot, E. Troiani, F. Mignacco, F. Krzakala, and L. Zdeborov, “Rigorous dynamical mean-field theory for stochastic gradient descent methods,” SIAM Journal on Mathematics of Data Science , vol. 6, no. 2, pp. 400–427, 2024

    2024

  18. [26]

    Statistically optimal firstorder algorithms: a proof via orthogonalization,

    A. Montanari and Y. Wu, “Statistically optimal firstorder algorithms: a proof via orthogonalization,” Information and Inference: A Journal of the IMA , vol. 13, no. 4, 2024

    2024

  19. [27]

    Dynamical mean-field analysis of adaptive langevin diffusions: Propagation-of-chaos and convergence of the linear response,

    Z. Fan, J. Ko, B. Loureiro, Y. M. Lu, and Y. Shen, “Dynamical mean-field analysis of adaptive langevin diffusions: Propagation-of-chaos and convergence of the linear response,” [Online]. Available https://arxiv.org/abs/2504.15556, 2025

    2025

  20. [28]

    State evolution for approximate message passing with non-separable functions,

    R. Berthier, A. Montanari, and P.-M. Nguyen, “State evolution for approximate message passing with non-separable functions,” Information and Inference: A Journal of the IMA , vol. 9, no. 1, pp. 33–79, 2020

    2020

  21. [29]

    Graph-based approximate message passing iterations,

    C. Gerbelot and R. Berthier, “Graph-based approximate message passing iterations,” Information and Inference: A Journal of the IMA , vol. 12, no. 4, pp. 2562–2628, 2023

    2023

  22. [30]

    Finite sample analysis of approximate message passing algorithms,

    C. Rush and R. Venkataramanan, “Finite sample analysis of approximate message passing algorithms,” IEEE Transactions on Information Theory , vol. 64, no. 111, pp. 7264–7286, 2018

    2018

  23. [31]

    A non-asymptotic analysis of generalized approximate message passing algorithms with right rotationally invariant designs,

    C. Cademartori and C. Rush, “A non-asymptotic analysis of generalized approximate message passing algorithms with right rotationally invariant designs,” [Online]. Available: https://arxiv.org/abs/2302. 00088, 2023

    2023

  24. [32]

    Approximate message passing from random initialization with applications to Z2 synchronization,

    G. Li, W. Fan, and Y. Wei, “Approximate message passing from random initialization with applications to Z2 synchronization,” Proceedings of the National Academy of Sciences , vol. 120, no. 31, 2023

    2023

  25. [33]

    A non-asymptotic framework for approximate message passing in spiked models,

    G. Li and Y. Wei, “A non-asymptotic framework for approximate message passing in spiked models,” [Online]. Available: https://arxiv.org/pdf/2208.03313.pdf, 2023. 25

    2023 arXiv

  26. [34]

    Entrywise dynamics and universality of general first order methods,

    Q. Han, “Entrywise dynamics and universality of general first order methods,” [Online]. Available https://arxiv.org/pdf/2406.19061, 2025

    2025 arXiv

  27. [35]

    A theory of solving TAP equations for Ising models with general invariant random matrices,

    M. Opper, B. C ¸akmak, and O. Winther, “A theory of solving TAP equations for Ising models with general invariant random matrices,” Journal of Physics A: Mathematical and Theoretical , vol. 49, no. 11, p. 114002, Feb. 2016

    2016

  28. [36]

    Orthogonal AMP,

    J. Ma and L. Ping, “Orthogonal AMP,” IEEE Access, vol. 5, pp. 2020–2033, 2017

    2020

  29. [37]

    Approximate message passing algorithms for rotationally invariant matrices,

    Z. Fan, “Approximate message passing algorithms for rotationally invariant matrices,” The Annals of Statistics, vol. 50, no. 1, pp. 197–224, Feb. 2022

    2022

  30. [38]

    Universality of approximate message passing with semirandom matrices,

    R. Dudeja, Y. M. Lu, and S. Sen, “Universality of approximate message passing with semirandom matrices,” The Annals of Probability , vol. 51, no. 5, pp. 1616–1683, Sep. 2023

    2023

  31. [39]

    Approximate message passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization,

    X. Zhong, T. Wang, and Z. Fan, “Approximate message passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization,” arXiv preprint arXiv:2110.02318, Oct. 2021

    2021 arXiv

  32. [40]

    O. Y. Feng, R. Venkataramanan, C. Rush, and R. J. Samworth, A Unifying Tutorial on Approximate Message Passing, ser. 335-536. Foundations and Trends in Machine Learning, 2022, vol. 15

    2022

  33. [41]

    Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing,

    D. L. Donoho, A. Javanmard, and A. Montanari, “Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing,” IEEE Transactions on Information Theory , vol. 59, no. 11, pp. 7434–7464, Jul. 2013

    2013

  34. [42]

    Asymptotic mutual information for the balanced binary stochastic block model,

    Y. Deshpande, E. Abbe, and A. Montanari, “Asymptotic mutual information for the balanced binary stochastic block model,” Information and Inference, vol. 6, no. 2, pp. 125–170, Jun. 2017

    2017

  35. [43]

    The replica-symmetric prediction for random linear estimation with Gaussian matrices is exact,

    G. Reeves and H. D. Pfister, “The replica-symmetric prediction for random linear estimation with Gaussian matrices is exact,” IEEE Transactions on Information Theory , vol. 65, no. 4, pp. 2252–2283, Apr. 2019

    2019

  36. [44]

    Optimal errors and phase transitions in high-dimensional generalized linear models,

    J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zdeborov´ a, “Optimal errors and phase transitions in high-dimensional generalized linear models,” Proceedings of the National Academy of Sciences , vol. 116, no. 12, pp. 5451–5460, Mar. 2019

    2019

  37. [45]

    Information-theoretic limits for the matrix tensor product,

    G. Reeves, “Information-theoretic limits for the matrix tensor product,” IEEE Journal on Selected Areas in Information Theory , vol. 1, no. 3, pp. 777–798, 2020

    2020

  38. [46]

    Householder dice: A matrix-free algorithm for simulating dynamics on Gaussian and random orthogonal ensembles,

    Y. M. Lu, “Householder dice: A matrix-free algorithm for simulating dynamics on Gaussian and random orthogonal ensembles,” IEEE Transactions on Information Theory , vol. 67, no. 12, pp. 8264–8272, 2021

    2021

  39. [47]

    Local convexity of the tap free energy and amp convergence for Z2-synchronization,

    M. Celentano, Z. Fan, and S. Mei, “Local convexity of the tap free energy and amp convergence for Z2-synchronization,” The Annals of Statistics , vol. 51, no. 2, pp. 519–546, 2023

    2023

  40. [48]

    The lasso with general gaussian designs with applications to hypothesis testing,

    M. Celentano, A. Montanari, and Y. Wei, “The lasso with general gaussian designs with applications to hypothesis testing,” The Annals of Statistics , vol. 51, no. 5, pp. 2194–2220, 2023

    2023

  41. [49]

    J. A. Tropp, An introduction to matrix concentration inequalities . Now Publishers, Inc., 2015, vol. 8, no. 1-2

    2015

  42. [50]

    Villani, Optimal transport, old and new

    C. Villani, Optimal transport, old and new . Springer, 2008

    2008

  43. [51]

    R. S. Liptser and A. N. Shiryaev, Statistics of Random Processes: II Applications , 2nd ed. Berlin Heidelberg GmbH: Springer Science & Business Media, 2001, vol. 6

    2001

  44. [52]

    J. R. Magnus and H. Neudecker, Matrix Differential Calculus with Applications in Statistics and Economitrics, 3rd ed. Wiley, 2007. 26

    2007

  45. [53]

    Local operator theory, random matrices and Banach spaces,

    K. R. Davidson and S. J. Szarek, “Local operator theory, random matrices and Banach spaces,” Handbook of the Geometry of Banach Spaces , vol. 1, pp. 317–366, 2001

    2001

  46. [54]

    The Fr´ echet distance between multivariate normal distributions,

    D. Dowson and B. Landau, “The Fr´ echet distance between multivariate normal distributions,”Journal of Multivariate Analysis , vol. 12, no. 3, pp. 450–455, 1982

    1982

  47. [55]

    Boucheron, G

    S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013

    2013

  48. [56]

    Vershynin, High-Dimensional Probability

    R. Vershynin, High-Dimensional Probability. Cambridge University Press, Sep. 2018

    2018

  49. [57]

    On Parlett’s matrix norm inequality for the Cholesky decomposi- tion,

    A. Edelman and W. F. Mascarenhas, “On Parlett’s matrix norm inequality for the Cholesky decomposi- tion,” Numerical linear algebra with applications , vol. 2, no. 3, pp. 243–250, 1995. 27

    1995

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.