Pith. sign in

REVIEW 1 major objections 4 minor 141 references

Approximate Message Passing with Random Initialization for Phase Retrieval

T0 review · 1 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read Randomly initialized AMP reaches the sharp recovery thresholds of noiseless phase retrieval.

desk verdict Substantial, original AMP analysis whose central phase diagram rests on an unproven one-line numerical lemma—worth a referee, not yet worth citing. read the letter →

arxiv 2608.01654 v1 pith:S7RP23JC submitted 2026-08-03 math.ST stat.MLstat.TH

Yuchen Chen , Yandi Shen , Xingyu Xu This is my paper
classification math.STstat.MLstat.TH
keywords approximatemessagepassingphaseretrievalrandominitializationstateevolutionweakrecoverythresholdstrongsingle-indexmodelsnon-asymptoticanalysis
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

The paper claims that approximate message passing (AMP) can solve noiseless phase retrieval even when started from a completely random Gaussian vector, with no spectral or model-specific initialization. It proves that this randomly initialized AMP reaches the information-theoretic weak-recovery threshold δ = n/d = 1/2, and that above a second threshold δ_str ≈ 1.13 it converges to arbitrarily accurate recovery in O(log n) iterations. The argument couples the AMP trajectory to independent Gaussian innovations plus a scalar signal coefficient that evolves under state evolution, and controls the residual over growing time horizons—something classical fixed-time AMP theory cannot do when the initial overlap is only d^{-1/2}. If correct, random initialization is not a handicap for this model: the algorithm matches the best known sharp thresholds without any initialization step, and most of the machinery applies to general single-index models.

What carries the argument

The key object is the finite-sample Gaussian coupling (Lemma 3.1): a random design matrix with i.i.d. N(0,1/d) entries is constructed from the same Gaussian directions that appear as the noise terms in the AMP iterates, so the trajectory is exactly a signal vector plus Gaussian innovations plus a residual. The residual is controlled by a recursive inequality whose multiplier is the non-asymptotic Bolthausen constant—the expected squared derivative of the AMP nonlinearities in their Gaussian channels, evaluated away from any fixed point. In the intermediate regime this multiplier is strictly below one and the error stays small for n^{1/3}/polylog(n) iterations; in the strong regime the proof

What would settle it

Compute the scalar function G(μ) = μ / [(1+μ)((1+μ)m(μ)−μ)] to high accuracy, numerically integrating m(μ) = E[G² tanh²(μG|G|+√μ W|G|)] over independent standard Gaussians, on a fine grid over μ ∈ [0, 10]. Check that it has exactly one maximum, near 5.52, with value near 1.13, and that the second derivative at that maximum is negative. The paper's Lemma 7.1 is asserted from numerical computation rather than proved, and the phase diagram in Theorem 2.1 collapses if this unimodality fails, so a direct high-precision check would settle the point.

Watch

Extended reading notes

Core claim

The central claim is that the entire AMP trajectory, starting from v_0 ~ N(0, I_d), can be written, over every growing horizon considered, as a signal part ρ_t θ* plus a unit-mass linear combination of independent Gaussian vectors plus a small residual: v_t = ρ_t θ* + Σ λ s_ℓ + Δ_t. The scalar sequence ρ_t evolves nearly deterministically through the state-evolution map F_δ(μ) = δ(1+μ)((1+μ)m(μ)−μ), where m(μ) = E[G² tanh²(μG|G|+√μ W|G|)]. The phase diagram of this single map is the theorem: for δ ≤ 1/2 zero is the only stable fixed point; for 1/2 < δ < δ_str ≈ 1.13 there is a stable positive fixed point to which the correlation converges; for δ > δ_str the positive fixed points vanish and ρ

Load-bearing premise

The proof hinges on an unproved numerical claim about a one-dimensional function: G(μ) has a single peak, at μ ≈ 5.52, with height δ_str ≈ 1.13. If that function had another peak or a different maximum, the fixed-point classification, both thresholds, and the strong-recovery growth bound would collapse.

Editorial extensions

If this is right

  • Weak recovery becomes a polylog-time event: for every δ > 1/2, after τ_wk = O_δ(log n) iterations the AMP signal coefficient is bounded away from zero, so random initialization costs only a logarithmic warm-up rather than a separate spectral step.
  • In the intermediate regime 1/2 < δ < δ_str, the correlation converges to the deterministic value ρ_∞(δ)/√(1+ρ_∞²(δ)), which tends to about 0.92 as δ ↑ δ_str; the paper bounds this convergence uniformly up to n^{1/3}/polylog(n) iterations.
  • Above δ_str ≈ 1.13, for any fixed ε > 0 the iterate reaches correlation at least 1−ε−o(1) within O_{δ,ε}(log n) iterations, because the state-evolution map has no finite fixed point and ρ_t grows exponentially.
  • The finite-sample coupling and error-recursion analysis are developed for generalized AMP on single-index models y = φ(Xθ*), so the same random-initialization theory is not confined to quadratic sensing.
  • Below δ = 1/2 weak recovery remains information-theoretically impossible under a Gaussian prior, so the random-start threshold is sharp rather than an algorithmic artifact.

Reading between the lines

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

  • The unproved numerical Lemma 7.1—that the scalar function G(μ) has a single maximum near μ ≈ 5.52 with value δ_str ≈ 1.13—is isolated from the rest of the argument; a rigorous unimodality proof would replace the numerical assertion without changing the phase diagram.
  • Phase I's anti-concentration dynamics essentially implements the optimal spectral estimator's leading eigenvector; this suggests the sharp δ = 1/2 threshold may extend to any first-order method whose early dynamics linearize to that spectral method, while the strong-recovery threshold above 1.13 may be special to AMP's Onsager-corrected updates.
  • The figure's Rademacher simulations hint that the two thresholds are not Gaussian-specific, but the proof's rotational invariance does not cover non-Gaussian designs; a universality extension would make random-start AMP a drop-in replacement for spectral initialization in broader single-index models.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 4 minor

Summary. This paper analyzes Bayes-optimal approximate message passing (AMP) with an independent Gaussian initialization for noiseless phase retrieval in the proportional regime n/d -> delta. The main result (Theorem 2.1) asserts a Gaussian decomposition of the AMP trajectory and a phase diagram: weak recovery above delta_weak = 1/2, state-evolution tracking for delta in (1/2, delta_str) over an n^{1/3}/polylog(n) horizon, and arbitrarily accurate strong recovery for delta > delta_str ≈ 1.13 within O(log n) iterations. The proof combines an exact finite-sample Gaussian coupling (Lemma 3.1), a second-order non-asymptotic error recursion (Proposition 3.4), and phase-specific analyses in Sections 5–8.

Significance. If correct, the result is a substantial advance: it shows that randomly initialized Bayes-optimal AMP reaches the information-theoretic weak-recovery threshold and provides a growing-horizon state-evolution analysis from a vanishing initial overlap. The constructive coupling, the recursive control of the Onsager correction terms, and the separation into three phases are valuable technical contributions. The main caveat is that the entire phase diagram depends on a one-dimensional fixed-point lemma whose proof is omitted; this lemma must be supplied before the theorem can be regarded as established.

major comments (1)
  1. [§7.1 (Lemma 7.1, Proposition 4.11)] Lemma 7.1 is the load-bearing structural fact of the paper. It asserts that G(µ)=µ/[(1+µ)((1+µ)m(µ)-µ)] is unimodal with a unique critical point µ⋆≈5.52, that S(µ)=D(µ)-µD'(µ) has the stated sign pattern, and that D''(µ⋆)>0. The entire proof is the sentence 'This can be checked routinely by numerical computation, which we omit here.' This is not a proof. Proposition 4.11 then derives from this lemma the classification of stable/unstable fixed points, the values δ_weak=1/2 and δ_str≈1.13, and the strong-recovery growth bound F_δ(µ) ≥ (δ/δ_str)µ. The same lemma supplies the positivity of χ_δ in (173)-(174), which is used in Proposition 4.12's contraction argument, and the intermediate-recovery bound (178). If the sign pattern of S(µ) or the non-degeneracy D''(µ⋆)>0 failed, both thresholds and the main theorem would collapse. A numerical computation without error bounds, code, or a reproduc
minor comments (4)
  1. [General] The text refers to Figure 1 and Figure 2, but the figures are not present in the reviewed version. Please ensure they are included; the claimed agreement with Rademacher simulations in Section 2.3 is otherwise unverifiable.
  2. [§2.2] The citation list contains a duplicated reference '[BHX25, BHX25]' and several typos in displayed equations, e.g. 'eut', 'bµt', 'bvt' in Section 7/8. These should be cleaned up.
  3. [Sections 4–8] The numerous interlocking finite-size conditions (202), (273), (165), (347), (184) are hard to track. A table or a short appendix listing each condition and where it is used would improve readability substantially.
  4. [§2.1, Eq. (20)] The constants C_δ in Theorem 2.1 are not tracked near δ=δ_str, and the text explicitly disclaims polynomial dependence on (δ-δ_str)^{-1}. This is fine, but the reader should be told whether the stated O(log n) times have a uniform constant on compact subsets of each regime; the compact-uniform statement at the end of the proof addresses this, but it would help to state it in the theorem itself.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reduction found: thresholds are derived from the population state-evolution map and the trajectory bounds are non-asymptotic; the main weakness is an unproved numerical lemma, which is a rigor gap rather than a circular step.

full rationale

I walked the derivation chain for the main assertions: the Gaussian coupling (Lemma 3.1), the signal-coefficient recursions (Propositions 4.6, 4.10, 4.12, 4.14), and the fixed-point classification (Proposition 4.11). I found no step in which a quantity called a prediction is equal by construction to an input, and no load-bearing argument that reduces to a self-citation. The weak-recovery threshold δ_weak = 1/2 enters as the stability boundary of the linearized signal recursion √(2δ) ρ_t, and δ_str is defined from the population map via δ_str = sup_μ G(μ) with G(μ) = μ/[(1+μ)((1+μ)m(μ)−μ)]; neither threshold is fitted from the AMP trajectory. The vector decomposition (21) is exact by the constructive coupling (Lemma 3.1), and the subsequent work consists of bounding the residual Δ_{V,t}; the signal coefficients ρ_t are defined from the trajectory itself, not posited to match the conclusion. The state-evolution estimate |ρ_t² − μ_∞(δ)| is proved via an error recursion, not by imposing the fixed point. I do flag one passage under the review rule: Lemma 7.1, the entire proof of which is 'This can be checked routinely by numerical computation, which we omit here.' That lemma supplies the unimodality of G, the value μ⋆ ≈ 5.52, and the critical value δ_str ≈ 1.13. Proposition 4.11, and with it the phase diagram and the strong-recovery growth bound F_δ(μ) ≥ (δ/δ_str)μ, depends on this unverified numerical claim. This is a genuine, localized rigor gap and a correctness risk: if the sign pattern of S(μ) = D(μ) − μD′(μ) failed, the fixed-point classification and both thresholds would lose their justification. However, this is not circularity: the numerical claim is an independent property of a scalar map, structurally distinct from the AMP trajectory theorem, and it is not assumed in the statement of Theorem 2.1. No code, table, or interval bound is supplied to support it, but the absence of a proof is not a reduction of the conclusion to its inputs. Accordingly, the circularity score is 0, with the caveat that the paper's phase diagram is less rigorously grounded than its main theorem because of the omitted numerical verification.

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

No numbers are fitted to data. The thresholds δ_weak = 1/2 and δ_str ≈ 1.13, and the fixed point μ∞(δ), are outputs of the derived state-evolution recursion: δ_weak is the stability boundary of the linearized signal recursion, and δ_str is the supremum of a model-defined function. The technical constants (C_δ, c_δ, etc.) are allowed to depend on δ but are universal, not tuned. Inputs the paper assumes without proof include the Gaussian-design model, the Bayes-optimal normalization (which fixes the Gaussian level at 1), regularity conditions (41)-(43) whose verification is delegated to Lemma 4.3, and, critically, Lemma 7.1's numerically asserted unimodality of G, for which no proof or code is given. No new postulated entities are introduced: the Gaussian vectors g_ℓ, s_ℓ, W in the coupling (25)-(26) are an exact probabilistic representation of the existing algorithm, not new objects.

assumptions (6)
  • domain assumption Sensing vectors x_i i.i.d. N(0, I_d/d) and signal norm ∥θ⋆∥ = √d (Eq. (1)).
    The entire analysis is for the Gaussian design phase retrieval model; universality beyond Gaussian is explicitly left open in Section 2.3.
  • domain assumption Proportional asymptotics n/d → δ ∈ (0, ∞).
    The thresholds and state evolution are stated in this regime (Section 2.1).
  • domain assumption Normalized Bayes-optimal AMP nonlinearities (11)-(13) define the algorithm; the quotient at µ=0 is taken by continuity.
    The theorem is about this specific algorithm; Appendices A.1-A.2 derive the Bayes-optimal form.
  • domain assumption Regularity and predictability conditions (41)-(43) and (47) on nonlinearities for general single-index models.
    Verified for phase retrieval in Lemma 4.3; assumed for the general framework of Section 3.
  • ad hoc to paper Lemma 7.1: G(µ) is unimodal with unique critical point µ⋆ ≈ 5.52 and G(µ⋆) = δ_str ≈ 1.13 (proof omitted, 'checked by numerical computation').
    Proposition 4.11 relies on this to classify fixed points of F_δ, define both thresholds, and give the exponential lower bound F_δ(µ) ≥ (δ/δ_str)µ; no derivation or reproducible code is provided.
  • standard math Fixed-time state evolution of AMP as background (Appendix A, invoking MTV22 Assumption B.1).
    Used as the reference point for what the paper extends; not used to prove Theorem 2.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximate Message Passing with Random Initialization for Phase Retrieval." pith.science (2026). https://pith.science/paper/S7RP23JC

@misc{pith2026260801654,
  author       = {Pith},
  title        = {Pith review of: Approximate Message Passing with Random Initialization for Phase Retrieval},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S7RP23JC}},
  note         = {Machine review of arXiv:2608.01654}
}
abstract

We analyze approximate message passing (AMP) with an independent Gaussian initialization for noiseless phase retrieval in the proportional asymptotic regime. A random initialization has overlap of order $d^{-1/2}$ with the signal, and AMP requires a growing number of iterations to attain non-vanishing overlap. Thus, its precise behavior cannot be characterized by classical fixed-time state evolution. We prove a Gaussian decomposition of the AMP trajectory and control its error over the horizons required for recovery. The resulting analysis shows that random initialization attains the weak-recovery threshold $\delta_{\rm weak}=1/2$. For $\delta\in(\delta_{\rm weak},\delta_{\rm str})$, where $\delta_{\rm str}\approx1.13$, the signal strength follows state evolution and approaches its stable finite fixed point uniformly for \(n^{1/3}/\operatorname{polylog}(n)\) iterations. For $\delta>\delta_{\rm str}$, AMP reaches any prescribed fixed recovery accuracy within $O_{\delta,\varepsilon}(\log n)$ iterations. The majority of our analysis applies more generally to generalized AMP for single-index models.

Figures

Figures reproduced from arXiv: 2608.01654 by the authors.

Figure 1
Figure 1. The final correlation of random initialized Bayes optimal AMP for sensing matrices with iid [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. The maps ρ 7→ p Fδ(ρ 2) and ρ 7→ B(ρ), with B defined in (171). Left: δ = 1.1, for which there are two positive fixed points. Right: δ = δstr ≈ 1.13, where the two positive fixed points merge at ρ = p µ∞(δstr) ≈ 2.35. The main goal of the remainder of this section is to show that, in the current phase, the empirical signal strength {ρt} of random initialized AMP exhibits the same behavior as the state evolution pred… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

141 extracted references · 50 canonical work pages

  1. [1]

    arXiv preprint arXiv:2602.02431 , year=

    Full-batch gradient descent outperforms one-pass sgd: Sample complexity separation in single-index learning , author=. arXiv preprint arXiv:2602.02431 , year=

    arXiv

  2. [2]

    Robust Learning of Multi-index Models via Iterative Subspace Approximation

    Robust learning of multi-index models via iterative subspace approximation , author=. arXiv preprint arXiv:2502.09525 , year=

    work page Pith review arXiv

  3. [3]

    arXiv preprint arXiv:2602.09959 , year=

    Statistical-Computational Trade-offs in Learning Multi-Index Models via Harmonic Analysis , author=. arXiv preprint arXiv:2602.09959 , year=

    work page arXiv

  4. [4]

    Advances in Neural Information Processing Systems , volume=

    Algorithms and SQ lower bounds for robustly learning real-valued multi-index models , author=. Advances in Neural Information Processing Systems , volume=

  5. [5]

    SIAM Journal on Mathematics of Data Science , volume=

    Precise asymptotics for spectral methods in mixed generalized linear models , author=. SIAM Journal on Mathematics of Data Science , volume=. 2026 , publisher=

    2026

  6. [6]

    Journal of Machine Learning Research , volume=

    How two-layer neural networks learn, one (giant) step at a time , author=. Journal of Machine Learning Research , volume=

  7. [7]

    Advances in Neural Information Processing Systems , volume=

    Learning single index models via harmonic decomposition , author=. Advances in Neural Information Processing Systems , volume=

  8. [8]

    Advances in Neural Information Processing Systems , volume=

    Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models , author=. Advances in Neural Information Processing Systems , volume=

Show all 141 references
  1. [9]

    Conference On Learning Theory , pages=

    Learning single-index models in gaussian space , author=. Conference On Learning Theory , pages=. 2018 , organization=

    2018

  2. [10]

    The Thirty Sixth Annual Conference on Learning Theory , pages=

    Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=

    2023

  3. [11]

    Conference on Learning Theory , pages=

    The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  4. [12]

    arXiv preprint arXiv:2403.05529 , year=

    Computational-statistical gaps in gaussian single-index models , author=. arXiv preprint arXiv:2403.05529 , year=

    arXiv

  5. [13]

    Conference on Learning Theory , pages=

    Neural networks can learn representations with gradient descent , author=. Conference on Learning Theory , pages=. 2022 , organization=

    2022

  6. [14]

    Foundations of Computational Mathematics , volume=

    Learning time-scales in two-layers neural networks , author=. Foundations of Computational Mathematics , volume=. 2025 , publisher=

    2025

  7. [15]

    Mathematical and Scientific Machine Learning , pages=

    Exact asymptotics for phase retrieval and compressed sensing with random generative priors , author=. Mathematical and Scientific Machine Learning , pages=. 2020 , organization=

    2020

  8. [16]

    The Thirty Sixth Annual Conference on Learning Theory , pages=

    From high-dimensional & mean-field dynamics to dimensionless odes: A unifying approach to sgd in two-layers networks , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=

    2023

  9. [17]

    arXiv preprint arXiv:2602.01434 , year=

    Phase transitions for feature learning in neural networks , author=. arXiv preprint arXiv:2602.01434 , year=

  10. [18]

    Advances in Neural Information Processing Systems , volume=

    Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit , author=. Advances in Neural Information Processing Systems , volume=

  11. [19]

    arXiv preprint arXiv:2405.15459 , year=

    Repetita iuvant: Data repetition allows sgd to learn high-dimensional multi-index functions , author=. arXiv preprint arXiv:2405.15459 , year=

    arXiv

  12. [20]

    arXiv preprint arXiv:2402.03220 , year=

    The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents , author=. arXiv preprint arXiv:2402.03220 , year=

    arXiv

  13. [21]

    arXiv preprint arXiv:2509.23527 , year=

    Learning single index model with gradient descent: spectral initialization and precise asymptotics , author=. arXiv preprint arXiv:2509.23527 , year=

  14. [22]

    Advances in Neural Information Processing Systems , volume=

    Optimal spectral transitions in high-dimensional multi-index models , author=. Advances in Neural Information Processing Systems , volume=

  15. [23]

    arXiv preprint arXiv:2511.15120 , year=

    Neural Networks Learn Generic Multi-Index Models Near Information-Theoretic Limit , author=. arXiv preprint arXiv:2511.15120 , year=

  16. [24]

    arXiv preprint arXiv:2506.05500 , year=

    The generative leap: Sharp sample complexity for efficiently learning gaussian multi-index models , author=. arXiv preprint arXiv:2506.05500 , year=

    arXiv

  17. [25]

    arXiv preprint arXiv:2405.15480 , year=

    Fundamental computational limits of weak learnability in high-dimensional multi-index models , author=. arXiv preprint arXiv:2405.15480 , year=

  18. [26]

    Bolthausen, Erwin , TITLE =. Comm. Math. Phys. , FJOURNAL =. 2014 , NUMBER =. doi:10.1007/s00220-013-1862-3 , URL =

    2014 doi

  19. [27]

    Bao, Zhigang and Han, Qiyang and Xu, Xiaocong , TITLE =. Ann. Appl. Probab. , FJOURNAL =. 2025 , NUMBER =. doi:10.1214/25-AAP2186 , URL =

    2025 doi

  20. [28]

    IEEE Trans

    Rush, Cynthia and Venkataramanan, Ramji , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2018 , NUMBER =. doi:10.1109/TIT.2018.2816681 , URL =

    2018

  21. [29]

    Advances in Neural Information Processing Systems , volume=

    Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction , author=. Advances in Neural Information Processing Systems , volume=

  22. [30]

    , TITLE =

    Lu, Yue M. , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2021 , NUMBER =. doi:10.1109/TIT.2021.3114351 , URL =

    2021

  23. [31]

    Information and Inference: A Journal of the IMA , volume=

    Statistically optimal firstorder algorithms: a proof via orthogonalization , author=. Information and Inference: A Journal of the IMA , volume=. 2024 , publisher=

    2024

  24. [32]

    Journal of Statistical Mechanics: Theory and Experiment , volume=

    The effective noise of stochastic gradient descent , author=. Journal of Statistical Mechanics: Theory and Experiment , volume=. 2022 , publisher=

    2022

  25. [33]

    Conference on Learning Theory , pages=

    The estimation error of general first order methods , author=. Conference on Learning Theory , pages=. 2020 , organization=

    2020

  26. [34]

    Information and Inference: A Journal of the IMA , volume=

    State evolution for general approximate message passing algorithms, with applications to spatial coupling , author=. Information and Inference: A Journal of the IMA , volume=. 2013 , publisher=

    2013

  27. [35]

    IEEE Transactions on Information Theory , volume=

    The dynamics of message passing on dense graphs, with applications to compressed sensing , author=. IEEE Transactions on Information Theory , volume=. 2011 , publisher=

    2011

  28. [36]

    Physical Review Letters , volume=

    Analytical solution of the off-equilibrium dynamics of a long-range spin-glass model , author=. Physical Review Letters , volume=. 1993 , publisher=

    1993

  29. [37]

    Journal of Statistical Physics , volume=

    Limiting dynamics for spherical models of spin glasses at high temperature , author=. Journal of Statistical Physics , volume=. 2007 , publisher=

    2007

  30. [38]

    arXiv preprint arXiv:2502.01953 , year=

    Local minima of the empirical risk in high dimension: General theorems and convex examples , author=. arXiv preprint arXiv:2502.01953 , year=

  31. [39]

    arXiv preprint arXiv:2502.02545 , year=

    Optimal spectral transitions in high-dimensional multi-index models , author=. arXiv preprint arXiv:2502.02545 , year=

    arXiv

  32. [40]

    arXiv preprint arXiv:2502.01583 , year=

    Spectral estimators for multi-index models: Precise asymptotics and optimal weak recovery , author=. arXiv preprint arXiv:2502.01583 , year=

    arXiv

  33. [41]

    arXiv preprint arXiv:2504.05426 , year=

    Survey on algorithms for multi-index models , author=. arXiv preprint arXiv:2504.05426 , year=

    arXiv

  34. [42]

    Information and Inference: A Journal of the IMA , volume=

    Hitting the high-dimensional notes: An ode for sgd learning dynamics on glms and multi-index models , author=. Information and Inference: A Journal of the IMA , volume=. 2024 , publisher=

    2024

  35. [43]

    Communications on Pure and Applied Mathematics , year=

    On learning Gaussian multi-index models with gradient flow part I: General properties and two-timescale learning , author=. Communications on Pure and Applied Mathematics , year=

  36. [44]

    Mathematical and Scientific Machine Learning , pages=

    Construction of optimal spectral methods in phase retrieval , author=. Mathematical and Scientific Machine Learning , pages=. 2022 , organization=

    2022

  37. [45]

    Dembo, Amir and Subag, Eliran , TITLE =. J. Stat. Phys. , FJOURNAL =. 2020 , NUMBER =. doi:10.1007/s10955-020-02587-z , URL =

    2020 doi

  38. [46]

    arXiv preprint arXiv:2011.00288 , year=

    Optimal sample complexity of subgradient descent for amplitude flow via non-Lipschitz matrix concentration , author=. arXiv preprint arXiv:2011.00288 , year=

    2011 arXiv

  39. [47]

    arXiv preprint arXiv:1905.09320 , year=

    Solving Random Systems of Quadratic Equations with Tanh Wirtinger Flow , author=. arXiv preprint arXiv:1905.09320 , year=

    1905 arXiv

  40. [48]

    2018 IEEE International Symposium on Information Theory (ISIT) , pages=

    A precise analysis of phasemax in phase retrieval , author=. 2018 IEEE International Symposium on Information Theory (ISIT) , pages=. 2018 , organization=

    2018

  41. [49]

    2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages=

    Phase retrieval via linear programming: Fundamental limits and algorithmic improvements , author=. 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages=. 2017 , organization=

    2017

  42. [50]

    2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages=

    Phase retrieval using iterative projections: Dynamics in the large systems limit , author=. 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages=. 2015 , organization=

    2015

  43. [51]

    Davis, Damek and Drusvyatskiy, Dmitriy and Paquette, Courtney , TITLE =. IMA J. Numer. Anal. , FJOURNAL =. 2020 , NUMBER =. doi:10.1093/imanum/drz031 , URL =

    2020 doi

  44. [52]

    and Ruan, Feng , TITLE =

    Duchi, John C. and Ruan, Feng , TITLE =. Inf. Inference , FJOURNAL =. 2019 , NUMBER =. doi:10.1093/imaiai/iay015 , URL =

    2019 doi

  45. [53]

    arXiv preprint arXiv:1706.03474 , year=

    Coordinate descent algorithms for phase retrieval , author=. arXiv preprint arXiv:1706.03474 , year=

    arXiv

  46. [54]

    IEEE Signal Processing Letters , volume=

    Kaczmarz method for solving quadratic equations , author=. IEEE Signal Processing Letters , volume=. 2016 , publisher=

    2016

  47. [55]

    Inverse Problems , FJOURNAL =

    Wei, Ke , TITLE =. Inverse Problems , FJOURNAL =. 2015 , NUMBER =. doi:10.1088/0266-5611/31/12/125008 , URL =

    2015 doi

  48. [56]

    arXiv preprint arXiv:1706.10291 , year=

    Convergence of the randomized Kaczmarz method for phase retrieval , author=. arXiv preprint arXiv:1706.10291 , year=

    arXiv

  49. [57]

    Advances in Neural Information Processing Systems , volume=

    Solving most systems of random quadratic equations , author=. Advances in Neural Information Processing Systems , volume=

  50. [58]

    IEEE Trans

    Soltanolkotabi, Mahdi , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2019 , NUMBER =. doi:10.1109/TIT.2019.2891653 , URL =

    2019

  51. [59]

    Tony and Li, Xiaodong and Ma, Zongming , TITLE =

    Cai, T. Tony and Li, Xiaodong and Ma, Zongming , TITLE =. Ann. Statist. , FJOURNAL =. 2016 , NUMBER =. doi:10.1214/16-AOS1443 , URL =

    2016 doi

  52. [60]

    Advances in Neural Information Processing Systems , volume=

    Phase retrieval using alternating minimization , author=. Advances in Neural Information Processing Systems , volume=

  53. [61]

    Waldspurger, Ir\`ene and d'Aspremont, Alexandre and Mallat, St\'ephane , TITLE =. Math. Program. , FJOURNAL =. 2015 , NUMBER =. doi:10.1007/s10107-013-0738-9 , URL =

    2015 doi

  54. [62]

    Tan, Yan Shuo and Vershynin, Roman , TITLE =. Inf. Inference , FJOURNAL =. 2019 , NUMBER =. doi:10.1093/imaiai/iay005 , URL =

    2019 doi

  55. [63]

    Strohmer, Thomas and Vershynin, Roman , TITLE =. J. Fourier Anal. Appl. , FJOURNAL =. 2009 , NUMBER =. doi:10.1007/s00041-008-9030-4 , URL =

    2009 doi

  56. [64]

    Tan, Yan Shuo and Vershynin, Roman , TITLE =. J. Mach. Learn. Res. , FJOURNAL =. 2023 , PAGES =

    2023

  57. [65]

    Advances in Neural Information Processing Systems , volume=

    Optimization and generalization of shallow neural networks with quadratic activation functions , author=. Advances in Neural Information Processing Systems , volume=

  58. [66]

    Cai, Jian-Feng and Huang, Meng and Li, Dong and Wang, Yang , TITLE =. Appl. Comput. Harmon. Anal. , FJOURNAL =. 2022 , PAGES =. doi:10.1016/j.acha.2022.01.002 , URL =

    2022 doi

  59. [67]

    Physical Review X , volume=

    Glassy nature of the hard phase in inference problems , author=. Physical Review X , volume=. 2019 , publisher=

    2019

  60. [68]

    Physical Review X , volume=

    Marvels and pitfalls of the langevin algorithm in noisy high-dimensional inference , author=. Physical Review X , volume=. 2020 , publisher=

    2020

  61. [69]

    Barbier, Jean and Krzakala, Florent and Macris, Nicolas and Miolane, L\'eo and Zdeborov\'a, Lenka , TITLE =. Proc. Natl. Acad. Sci. USA , FJOURNAL =. 2019 , NUMBER =. doi:10.1073/pnas.1802705116 , URL =

    2019 doi

  62. [70]

    , TITLE =

    Luo, Wangyu and Alghamdi, Wael and Lu, Yue M. , TITLE =. IEEE Trans. Signal Process. , FJOURNAL =. 2019 , NUMBER =. doi:10.1109/TSP.2019.2904918 , URL =

    2019

  63. [71]

    Conca, Aldo and Edidin, Dan and Hering, Milena and Vinzant, Cynthia , TITLE =. Appl. Comput. Harmon. Anal. , FJOURNAL =. 2015 , NUMBER =. doi:10.1016/j.acha.2014.06.005 , URL =

    2015 doi

  64. [72]

    and Cahill, Jameson and Mixon, Dustin G

    Bandeira, Afonso S. and Cahill, Jameson and Mixon, Dustin G. and Nelson, Aaron A. , TITLE =. Appl. Comput. Harmon. Anal. , FJOURNAL =. 2014 , NUMBER =. doi:10.1016/j.acha.2013.10.002 , URL =

    2014 doi

  65. [73]

    international conference on machine learning , pages=

    Passed & spurious: Descent algorithms and local minima in spiked matrix-tensor models , author=. international conference on machine learning , pages=. 2019 , organization=

    2019

  66. [74]

    Advances in neural information processing systems , volume=

    Who is afraid of big bad minima? analysis of gradient-flow in spiked matrix-tensor models , author=. Advances in neural information processing systems , volume=

  67. [75]

    2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) , pages=

    Fundamental limits of phasemax for phase retrieval: A replica analysis , author=. 2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) , pages=. 2017 , organization=

    2017

  68. [76]

    Artificial Intelligence and Statistics , pages=

    Phase retrieval meets statistical learning theory: A flexible convex relaxation , author=. Artificial Intelligence and Statistics , pages=. 2017 , organization=

    2017

  69. [77]

    IEEE Trans

    Goldstein, Tom and Studer, Christoph , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2018 , NUMBER =. doi:10.1109/TIT.2018.2800768 , URL =

    2018

  70. [78]

    IEEE Trans

    Schniter, Philip and Rangan, Sundeep , TITLE =. IEEE Trans. Signal Process. , FJOURNAL =. 2015 , NUMBER =. doi:10.1109/TSP.2014.2386294 , URL =

    2015

  71. [79]

    2012 IEEE international symposium on information theory proceedings , pages=

    Iterative estimation of constrained rank-one matrices in noise , author=. 2012 IEEE international symposium on information theory proceedings , pages=. 2012 , organization=

    2012

  72. [80]

    IEEE Trans

    Li, Zhenzhen and Cai, Jian-Feng and Wei, Ke , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2020 , NUMBER =. doi:10.1109/TIT.2019.2956922 , URL =

    2020

  73. [81]

    Sun, Ju and Qu, Qing and Wright, John , TITLE =. Found. Comput. Math. , FJOURNAL =. 2018 , NUMBER =. doi:10.1007/s10208-017-9365-9 , URL =

    2018 doi

  74. [82]

    2017 International Conference on Sampling Theory and Applications (SampTA) , pages=

    Performance of real phase retrieval , author=. 2017 International Conference on Sampling Theory and Applications (SampTA) , pages=. 2017 , organization=

    2017

  75. [83]

    and Li, Xiaodong and Soltanolkotabi, Mahdi , TITLE =

    Cand\`es, Emmanuel J. and Li, Xiaodong and Soltanolkotabi, Mahdi , TITLE =. Appl. Comput. Harmon. Anal. , FJOURNAL =. 2015 , NUMBER =. doi:10.1016/j.acha.2014.09.004 , URL =

    2015 doi

  76. [84]

    and Strohmer, Thomas and Voroninski, Vladislav , TITLE =

    Cand\`es, Emmanuel J. and Strohmer, Thomas and Voroninski, Vladislav , TITLE =. Comm. Pure Appl. Math. , FJOURNAL =. 2013 , NUMBER =. doi:10.1002/cpa.21432 , URL =

    2013 doi

  77. [85]

    and Eldar, Yonina C

    Cand\`es, Emmanuel J. and Eldar, Yonina C. and Strohmer, Thomas and Voroninski, Vladislav , TITLE =. SIAM Rev. , FJOURNAL =. 2015 , NUMBER =. doi:10.1137/151005099 , URL =

    2015 doi

  78. [86]

    and Li, Xiaodong , TITLE =

    Cand\`es, Emmanuel J. and Li, Xiaodong , TITLE =. Found. Comput. Math. , FJOURNAL =. 2014 , NUMBER =. doi:10.1007/s10208-013-9162-z , URL =

    2014 doi

  79. [87]

    Zhang, Huishuai and Zhou, Yi and Liang, Yingbin and Chi, Yuejie , TITLE =. J. Mach. Learn. Res. , FJOURNAL =. 2017 , PAGES =

    2017

  80. [88]

    , TITLE =

    Chen, Yuxin and Cand\`es, Emmanuel J. , TITLE =. Comm. Pure Appl. Math. , FJOURNAL =. 2017 , NUMBER =. doi:10.1002/cpa.21638 , URL =

    2017 doi

  81. [89]

    Balan, Radu and Casazza, Pete and Edidin, Dan , TITLE =. Appl. Comput. Harmon. Anal. , FJOURNAL =. 2006 , NUMBER =. doi:10.1016/j.acha.2005.07.001 , URL =

    2006 doi

  82. [90]

    and Chen, Yuxin , TITLE =

    Chi, Yuejie and Lu, Yue M. and Chen, Yuxin , TITLE =. IEEE Trans. Signal Process. , FJOURNAL =. 2019 , NUMBER =. doi:10.1109/TSP.2019.2937282 , URL =

    2019

  83. [91]

    Ma, Cong and Wang, Kaizheng and Chi, Yuejie and Chen, Yuxin , TITLE =. Found. Comput. Math. , FJOURNAL =. 2020 , NUMBER =. doi:10.1007/s10208-019-09429-9 , URL =

    2020 doi

  84. [92]

    Mondelli, Marco and Montanari, Andrea , TITLE =. Found. Comput. Math. , FJOURNAL =. 2019 , NUMBER =. doi:10.1007/s10208-018-9395-y , URL =

    2019 doi

  85. [93]

    Mondelli, Marco and Thrampoulidis, Christos and Venkataramanan, Ramji , TITLE =. Found. Comput. Math. , FJOURNAL =. 2022 , NUMBER =. doi:10.1007/s10208-021-09531-x , URL =

    2022 doi

  86. [94]

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

    Celentano, Michael and Cheng, Chen and Montanari, Andrea , month = dec, year =. The high-dimensional asymptotics of first order methods with random data , url =. doi:10.48550/arXiv.2112.07572 , urldate =

    doi arXiv

  87. [95]

    Machine Learning: Science and Technology , volume=

    Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem , author=. Machine Learning: Science and Technology , volume=. 2021 , publisher=

    2021

  88. [96]

    Advances in Neural Information Processing Systems , volume=

    Complex dynamics in simple neural networks: Understanding gradient flow in phase retrieval , author=. Advances in Neural Information Processing Systems , volume=

  89. [97]

    IEEE Trans

    Dudeja, Rishabh and Ma, Junjie and Maleki, Arian , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2020 , NUMBER =. doi:10.1109/TIT.2020.3015173 , URL =

    2020

  90. [98]

    Chen, Yuxin and Chi, Yuejie and Fan, Jianqing and Ma, Cong , TITLE =. Math. Program. , FJOURNAL =. 2019 , NUMBER =. doi:10.1007/s10107-019-01363-6 , URL =

    2019 doi

  91. [99]

    2025 , eprint=

    Dynamical mean-field analysis of adaptive Langevin diffusions: Replica-symmetric fixed point and empirical Bayes , author=. 2025 , eprint=

    2025

  92. [100]

    2025 , eprint=

    Dynamical mean-field analysis of adaptive Langevin diffusions: Propagation-of-chaos and convergence of the linear response , author=. 2025 , eprint=

    2025

  93. [101]

    The Annals of Statistics , volume=

    Approximate message passing algorithms for rotationally invariant matrices , author=. The Annals of Statistics , volume=. 2022 , publisher=

    2022

  94. [102]

    Journal of Machine Learning Research , year =

    Huishuai Zhang and Yingbin Liang and Yuejie Chi , title =. Journal of Machine Learning Research , year =

  95. [103]

    IEEE Transactions on Signal Processing , volume=

    Perturbed amplitude flow for phase retrieval , author=. IEEE Transactions on Signal Processing , volume=. 2020 , publisher=

    2020

  96. [104]

    arXiv preprint arXiv:2404.17856 , year=

    Uncertainty quantification for iterative algorithms in linear models with application to early stopping , author=. arXiv preprint arXiv:2404.17856 , year=

    arXiv

  97. [105]

    Advances in Neural Information Processing Systems , volume=

    Estimating generalization performance along the trajectory of proximal SGD in robust regression , author=. Advances in Neural Information Processing Systems , volume=

  98. [106]

    arXiv preprint arXiv:2502.21269 , year=

    Dynamical decoupling of generalization and overfitting in large two-layer networks , author=. arXiv preprint arXiv:2502.21269 , year=

  99. [107]

    arXiv preprint arXiv:2505.04898 , year=

    Precise gradient descent training dynamics for finite-width multi-layer neural networks , author=. arXiv preprint arXiv:2505.04898 , year=

    arXiv

  100. [108]

    Annals of Statistics , year=

    Entrywise dynamics and universality of general first order methods , author=. Annals of Statistics , year=

  101. [109]

    arXiv preprint arXiv:2204.04476 , year=

    High-dimensional asymptotics of Langevin dynamics in spiked matrix models , author=. arXiv preprint arXiv:2204.04476 , year=

    arXiv

  102. [110]

    SIAM Journal on Mathematics of Data Science , volume=

    Rigorous dynamical mean-field theory for stochastic gradient descent methods , author=. SIAM Journal on Mathematics of Data Science , volume=. 2024 , publisher=

    2024

  103. [111]

    Foundations and Trends

    Convex optimization: Algorithms and complexity , author=. Foundations and Trends. 2015 , publisher=

    2015

  104. [112]

    International conference on machine learning , pages=

    No spurious local minima in nonconvex low rank problems: A unified geometric analysis , author=. International conference on machine learning , pages=. 2017 , organization=

    2017

  105. [113]

    2017 , journal=

    Statistical guarantees for the EM algorithm: From population to sample-based analysis , author=. 2017 , journal=

    2017

  106. [114]

    Journal of the Optical Society of America A , volume=

    Phase retrieval in crystallography and optics , author=. Journal of the Optical Society of America A , volume=. 1990 , publisher=

    1990

  107. [115]

    Image recovery: theory and application , volume=

    Phase retrieval and image reconstruction for astronomy , author=. Image recovery: theory and application , volume=

  108. [116]

    Physical Review Letters , volume=

    Dynamic theory of the spin-glass phase , author=. Physical Review Letters , volume=. 1981 , publisher=

    1981

  109. [117]

    Physical Review B , volume=

    Relaxational dynamics of the Edwards-Anderson model and the mean-field theory of spin-glasses , author=. Physical Review B , volume=. 1982 , publisher=

    1982

  110. [118]

    Probability Theory and Related Fields , volume=

    Large deviations for Langevin spin glass dynamics , author=. Probability Theory and Related Fields , volume=. 1995 , publisher=

    1995

  111. [119]

    The Annals of Probability , volume=

    Symmetric Langevin spin glass dynamics , author=. The Annals of Probability , volume=. 1997 , publisher=

    1997

  112. [120]

    Probability Theory and Related Fields , volume=

    Averaged and quenched propagation of chaos for spin glass dynamics , author=. Probability Theory and Related Fields , volume=. 1997 , publisher=

    1997

  113. [121]

    Conference on Learning Theory , pages=

    Rank-one matrix estimation: analytic time evolution of gradient descent dynamics , author=. Conference on Learning Theory , pages=. 2021 , organization=

    2021

  114. [122]

    arXiv preprint arXiv:1408.4837 , year=

    The gaussian min-max theorem in the presence of convexity , author=. arXiv preprint arXiv:1408.4837 , year=

    arXiv

  115. [123]

    The Annals of Statistics , volume=

    Observable adjustments in single-index models for regularized M-estimators with bounded p/n , author=. The Annals of Statistics , volume=. 2025 , publisher=

    2025

  116. [124]

    IEEE Trans

    Guo, Dongning and Wu, Yihong and Shamai, Shlomo and Verd\'u, Sergio , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2011 , NUMBER =. doi:10.1109/TIT.2011.2111010 , URL =

    2011

  117. [125]

    arXiv preprint arXiv:2401.03923 , year=

    A non-asymptotic distributional theory of approximate message passing for sparse and robust regression , author=. arXiv preprint arXiv:2401.03923 , year=

    arXiv

  118. [126]

    Proceedings of the National Academy of Sciences , volume=

    Approximate message passing from random initialization with applications to Z 2 synchronization , author=. Proceedings of the National Academy of Sciences , volume=. 2023 , publisher=

    2023

  119. [127]

    Mondelli, Marco and Venkataramanan, Ramji , TITLE =. J. Stat. Mech. Theory Exp. , FJOURNAL =. 2022 , NUMBER =. doi:10.1088/1742-5468/ac9828 , URL =

    2022 doi

  120. [128]

    The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing , volume=

    Bayati, Mohsen and Montanari, Andrea , year=. The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing , volume=. IEEE Transactions on Information Theory , publisher=. doi:10.1109/tit.2010.2094817 , number=

    2010

  121. [129]

    and Li, Gen , TITLE =

    Lu, Yue M. and Li, Gen , TITLE =. Inf. Inference , FJOURNAL =. 2020 , NUMBER =. doi:10.1093/imaiai/iaz020 , URL =

    2020 doi

  122. [130]

    Advances in Neural Information Processing Systems , volume=

    Phase retrieval in high dimensions: Statistical and computational phase transitions , author=. Advances in Neural Information Processing Systems , volume=

  123. [131]

    IEEE Trans

    Ma, Junjie and Xu, Ji and Maleki, Arian , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2019 , NUMBER =. doi:10.1109/TIT.2019.2893254 , URL =

    2019

  124. [132]

    Mathematical and Scientific Machine Learning , pages=

    Landscape complexity for the empirical risk of generalized linear models , author=. Mathematical and Scientific Machine Learning , pages=. 2020 , organization=

    2020

  125. [133]

    2021 , eprint=

    The high-dimensional asymptotics of first order methods with random data , author=. 2021 , eprint=

    2021

  126. [134]

    Journal of Machine Learning Research , volume=

    Online stochastic gradient descent on non-convex losses from high-dimensional inference , author=. Journal of Machine Learning Research , volume=

  127. [135]

    2011 IEEE international symposium on information theory proceedings , pages=

    Generalized approximate message passing for estimation with random linear mixing , author=. 2011 IEEE international symposium on information theory proceedings , pages=. 2011 , organization=

    2011

  128. [136]

    arXiv preprint arXiv:2208.03313 , year=

    A non-asymptotic framework for approximate message passing in spiked models , author=. arXiv preprint arXiv:2208.03313 , year=

    arXiv

  129. [137]

    arXiv preprint arXiv:2509.11426 , year=

    Long-time dynamics and universality of nonconvex gradient descent , author=. arXiv preprint arXiv:2509.11426 , year=

  130. [138]

    2015 , journal=

    Universality in polytope phase transitions and message passing algorithms , author=. 2015 , journal=

    2015

  131. [139]

    2021 , journal=

    Universality of approximate message passing algorithms , author=. 2021 , journal=

    2021

  132. [140]

    The Annals of Applied Probability , volume=

    Universality of approximate message passing algorithms and tensor networks , author=. The Annals of Applied Probability , volume=. 2024 , publisher=

    2024

  133. [141]

    The Annals of Probability , volume=

    Universality of approximate message passing with semirandom matrices , author=. The Annals of Probability , volume=. 2023 , publisher=

    2023

Pith tools

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