acceptodds
Under review as a conference paper at ICLR 2027

Symmetrized Phase Retrieval: Infinite versus Finite-Size Dynamics in Learning

Abstract

Even in its simplest setting, phase retrieval is a difficult optimization problem with a rough, high-dimensional loss landscape. In the standard problem, glassy dynamics and finite-size effects obscure the thermodynamic learning transition. Here, we introduce a symmetrized variant, analyze its finite-size behavior numerically, and solve its infinite-dimensional gradient-flow dynamics using dynamical mean-field theory (DMFT). We show that sample complexity is linear in the input dimension and identify two thresholds: a dynamical threshold, above which gradient flow optimization typically generalizes under random initialization; and a landscape-trivialization threshold, at which nongeneralizing minima lose stability. At finite dimensions, the former is significantly lower and learning requires much less data than is necessary for landscape trivialization. In the infinite dimensional limit the thresholds coincide at a limiting value of samples per dimension. We understand this gap in terms of the loss landscape geometry: reflection symmetry confines nongeneralizing minima to the zero-overlap manifold, and retrieval occurs when the initial teacher overlap exceeds a critical value , which depends on the sample-to-dimension ratio . The competition between the initial overlap – which scales with the input dimension as – and – which decreases much more strongly – allows retrieval well before trivialization at finite . In addition, we show that, remarkably, determines not only the learning success but also the dynamical timescale. An approximate exponential-growth description captures the observed dynamics and yields a learning time logarithmic in . Thus, one scalar links basin geometry, retrieval probability, and learning timescale. Extensive finite-size simulations verify the predicted thresholds, retrieval and failure trajectories, and learning-time statistics.

Primary area:
learning theory
Keywords:
Phase retrieval, learning dynamics, dynamical mean-field theory, loss landscape, finite-size effects, nonconvex optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_Ag24OpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The authors analyse the gradient descent / flow dynamics of a symmetrised variant of phase retrieval. In particular, they focus on the ratio α\alpha of sample size to dimension and the values of α\alpha above which (i) success is more likely than failure (dynamical threshold) and (ii) the optimisation succeeds almost surely (trivialisation threshold). They claim that the success and dynamics of the optimisation process are determined by how well the initialisation is aligned with the target and from this, derive a sample complexity linear in dimension. They support their claim with empirical observations as well as theoretical considerations. They find that in finite dimensions, the two thresholds are distinct, while they coincide in the infinite-dimensional mean-field limit.

Critical strengths
  1. The clear writing style and structure make it easy to follow and understand the authors' argumentation.
  2. The paper provides a plausible and comprehensive explanation of the two-threshold phenomenon in the considered example.
  3. The problem is well motivated and the numerical findings provide a good exposition of the qualitative features of the optimisation properties.
Critical weaknesses
  1. The analysis is limited to a simple model using synthetic data and it is unclear if the techniques and findings are applicable outside of this controlled setting. It would be good to have some clarification regarding this (or some other justification for restricting to this setting) as otherwise the paper's impact seems fairly limited.
  2. The argument for the existence of a critical initial overlap in Section 3.2 (which I understand to be the central claim of the paper) is not entirely convincing (see Questions below).
  3. The derivation of the retrieval time distribution is based on an unfounded approximation and comparison to the empirical distribution is done using only histograms, which is not a reliable method (see also Questions below). The text (l. 417) claims a logarithmic dependence of TT on R0R_0, but the curves in Figure 4(a) are not linear within the 75% interval marking the relevant range of R0R_0.
Questions for authors
  1. Figure 3(a) contains a region reached by successful and unsuccessful trajectories (which could be a higher-dimensional phenomenon hidden by the projection onto the (R,s)(R,s)-plane). Does this contradict the claim that success is determined by R0R_0? What happens if a trajectory is started somewhere in this region, e.g. with R0≈0.1,s0≈0.5R_0\approx0.1,s_0\approx0.5?
  2. Have you tried initialisations which do not lie on the curve s0=1−R02s_0=\sqrt{1-R_0^2}? Figure 3(a) suggests there may be some higher-dimensional manifold separating successful and unsuccessful initialisations whose intersection with the sphere of radius N\sqrt{N}, on which the initialisations lie, is described by ∣R0∣=Rc|R_0|=R_c. In low dimensions, it may be possible to do a kind of grid search to get a comprehensive picture of which initialisations fail and which succeed. Have you done such an experiment?
  3. Do you claim validity of Eq. (12) for all tt? The approximations R∼N−1/2R\sim N^{-1/2} and s∼1s\sim1 seem valid only close to initialisation and validity for t≫0t\gg0 seems necessary in order to derive the retrieval time.
  4. For comparing the empirical distribution of TT to Eq. (14), can you provide any other statistical evidence beyond the three histograms in the paper, like the empirical CDF, q-q-plots or statistical tests?
  5. For computing VmV_m in Eq. (11), how is u^\hat{u} chosen? Does it vary over the samples?
  6. In Figure 4(a), why are only successful trajectories considered? How do you deal with the possibility that the optimisation fails in your analysis of TT?
  7. At the end of Section 3.4, you state that the shape of the retrieval time distribution may provide evidence for some underlying multiplicative growth. Which distribution shapes would indicate something like this and how would you infer a multiplicative growth mechanism?
  8. Figure 2(a) shows the loss landscape in terms of RR and ss for some fixed u^\hat{u}. What does this picture look like for other u^\hat{u}, is this representative for the general shape of the loss landscape?
6 comments
AuthorsOpenReview ↗

Response to reviewer Ag24 (1/2)

We thank the reviewer for the detailed questions, which pointed to passages that were not clear enough; we have revised them as detailed below.

W1 (simple synthetic model). Phase retrieval is a notoriously hard problem [Fienup 1982; Shechtman et al. 2015; Fannjiang & Strohmer 2020; Candès et al. 2015; Sun et al. 2018; Chen et al. 2019; Barbier et al. 2019; Maillard et al. 2020b; Mignacco et al. 2021]. There is an extensive and currently active research effort devoted to understanding it even, and sometimes especially, in toy models with Gaussian data and a single quadratic neuron [Chen et al. 2019; Sarao Mannelli et al. 2020a; Maillard et al. 2020a; Mignacco et al. 2021; Bonnaire et al. 2025; Tsironis & Moustakas 2025; Maillard et al. 2026]. This is an open and important problem. As Reviewer w46F writes, recovery with gradient-based algorithms in phase retrieval "is still unknown", and a mechanism that carries over to it would be "an important step towards its comprehension". We make a substantial contribution to this problem by studying the simplest variant in which the question of generalization can be answered completely. This is in the spirit of Bonnaire et al. (2025), who analyzed a variant of the original problem. Symmetrization is such a variant: it only restores at finite sample size a symmetry of the population loss, yet makes the problem tractable. The history of this and related fields has many examples in which the study of simple solvable models produced insights that later proved general, both in learning theory [Seung et al. 1992; Saad & Solla 1995; Saxe et al. 2014; Advani et al. 2020; Goldt et al. 2020] and in high-dimensional non-convex optimization [Sarao Mannelli et al. 2019; Antenucci et al. 2019; Aubin et al. 2020; Maillard et al. 2020a].

W2, Q1-Q2 (existence of a critical overlap; Fig. 3(a); other initializations). We thank the reviewer for this question, which showed us that Fig. 3(a) was not presented clearly enough. We have revised the text and the figure accordingly. In short, Fig. 3(a) directly demonstrates that, for the parameters used there (N=1000N=1000, α=10\alpha=10), trajectories starting with R0>RcR_0>R_c retrieve the teacher, and those starting with R0<RcR_0<R_c converge to a nongeneralizing state. The two ensembles differ only in R0R_0 (0.030.03 and 0.070.07, on either side of Rc≈0.052R_c\approx0.052), so the outcome is set by R0R_0. Fig. 3 makes this quantitative: as R0R_0 is scanned, the retrieval probability rises from 0 to 1 around RcR_c, the rise sharpens as N−1/2N^{-1/2} (Fig. 3(c)), and its location agrees with the DMFT prediction for all α\alpha studied (Fig. 3(d)). Together these imply a step at Rc(α)R_c(\alpha) as N→∞N\to\infty, Eq. (8).

The region visited by both ensembles does not contradict this. The full dynamics also involves the transverse direction u^\hat{\mathbf u} and its relation to the data, and Fig. 3(a) shows only its projection on the (R,s)(R,s) plane. Two trajectories can therefore pass through the same point of the plane with different futures (in the reviewer's words, "a higher-dimensional phenomenon hidden by the projection"). The region is shared only in the projection, not in the full state space. Failing trajectories reach it only later, once u^\hat{\mathbf u} has relaxed toward the data. We realize that the figure did not make the direction of time visible, so we have added arrows along the trajectories in Fig. 3(a) and refer to them in Sec. 3.2.

Following the reviewer's helpful suggestion (Q2), we have also added a grid search over the initial overlap and the initial transverse norm, (R0,s0)(R_0,s_0), with 0.1≤s0≤20.1\le s_0\le2 and the transverse direction drawn at random, at N=1000N=1000 and α=10,15,20\alpha=10,15,20 (new App. E, Fig. 8). This does not change the picture: for every s0s_0 there is still a sharp critical overlap, only at a different value Rc(s0)R_c(s_0). For the reviewer's example, R0≈0.1R_0\approx0.1, s0≈0.5s_0\approx0.5 (at α=10\alpha=10, as in Fig. 3(a)), we find Rc(s0=0.5)≈0.02R_c(s_0=0.5)\approx0.02, so a trajectory started there retrieves the teacher, while one started at the same s0s_0 with R0=0.01R_0=0.01 fails. Rc(s0)R_c(s_0) is almost proportional to s0s_0, with slight deviations. Random initialization concentrates on s0≃1s_0\simeq1, which is the case studied in the main text.

AuthorsOpenReview ↗

Response to reviewer Ag24

W3, Q3 (validity of Eq. (12)). The reviewer caught an important weakness in our argument. Thank you. We do not claim that Eq. (12) holds for all tt, and we have rewritten Sec. 3.4 to state its regime of validity. The argument now has three steps.

(i) Fig. 4(a) shows that, at fixed α\alpha, the retrieval time is a function of R0R_0, up to fluctuations; for N→∞N\to\infty this function is given by DMFT.

(ii) Eq. (12) describes only the early escape from the symmetry plane, and only for initial overlaps well above the critical one, Rc(α)≪∣R0∣≪1R_c(\alpha)\ll|R_0|\ll1. It cannot hold near RcR_c: a constant growth rate would imply that all trajectories retrieve, whereas there trajectories linger at the basin boundary. This is the origin of the non-linearity in Fig. 4(a) that the reviewer points out: TT is logarithmic in ∣R0∣|R_0| away from RcR_c and steeper as RcR_c is approached. Eq. (14) follows when most random initializations are in this regime, Rc≪N−1/2R_c\ll N^{-1/2}, as for α=20\alpha=20 at N=1000N=1000. Nor do we claim that the growth is exponential up to Rret=0.99R_{\rm ret}=0.99: stages whose duration does not depend on R0R_0 only add a constant to TT. The final approach to the teacher is such a stage: from ∣R∣=0.5|R|=0.5 to RretR_{\rm ret} it takes a time of about 300300 at N=1000N=1000, with a standard deviation below 1010 between trajectories, so the choice of threshold only shifts TT. cαc_\alpha is therefore an effective rate; this is now clearly stated in Sec. 3.4, which was substantially edited. For comparison, Fig. 4(b) now also shows the exact full-population prediction (App. D), which has no fitted parameter.

(iii) When a significant fraction of the retrieving trajectories start near RcR_c (α=10\alpha=10 at N=1000N=1000), these assumptions do not hold. Empirically, Eq. (14) with a fitted rate still describes the distribution, but we do not have a derivation for this regime.

Q4 (statistics of TT). We have added App. F (Fig. 9), comparing the empirical CDF of TT with Eq. (14) at N=1000N=1000, α=10,15,20\alpha=10,15,20. cαc_\alpha is the single fitted parameter (maximum likelihood). The Kolmogorov-Smirnov distances are DKS=0.044,0.064,0.053D_{\rm KS}=0.044, 0.064, 0.053, showing that Eq. (14) is a good description of the distribution (fitting in addition a time shift does not consistently improve the agreement).

Q5 (u^\hat{\mathbf u} in VmV_m). u^(t)\hat{\mathbf u}(t) is the student's transverse direction at time tt, an (N−1)(N-1)-dimensional unit vector orthogonal to the teacher, shared by all samples and evolving in time. VmV_m and V⊥V_\perp contract this high-dimensional tensor to a scalar, so Eq. (11) is exact (App. B), but its coefficients change in time. In Fig. 2(a,b), u^\hat{\mathbf u} is frozen at its value after training, for visualization purposes.

Q6 (successful runs only). TT is defined only for runs that reach ∣R∣=Rret|R|=R_{\rm ret}, so its statistics are conditional on success; the failure probability is shown in Figs. 3(b) and 1(b). Eq. (14) neglects this conditioning, which is justified when Rc≪N−1/2R_c\ll N^{-1/2} so that almost all runs retrieve (α=20\alpha=20 at N=1000N=1000), and not for α=10\alpha=10; see point (iii) above.

Q7 (multiplicative growth). Eq. (12) gives Eq. (13), T=c−1log⁡(Rret/∣R0∣)T=c^{-1}\log(R_{\rm ret}/|R_0|), so p(T)p(T) in Eq. (14) has an exponential right tail ∝e−cT\propto e^{-cT}, from small ∣R0∣|R_0|, and a sharp left cutoff. Conversely, observing this shape points to multiplicative growth, and the tail's decay rate estimates cc, even when the growing coordinate is unknown. Since this remark was speculative and not supported by an analysis in the paper, we have removed it from the revision.

Q8 (other u^\hat{\mathbf u} in Fig. 2(a)). Fig. 2(a) uses the u^\hat{\mathbf u} reached by gradient descent on the original problem at α=3\alpha=3. Other seeds give the same qualitative picture: the two teacher minima and one spurious minimum, whose position varies (with positive or negative RR). For a random u^\hat{\mathbf u}, xμ⋅u^\mathbf x_\mu\cdot\hat{\mathbf u} is Gaussian and (Vt,Vm,V⊥)→(3,1,3)(V_t,V_m,V_\perp)\to(3,1,3): no spurious minimum, only a saddle at R=0R=0, s2=1/3s^2=1/3.

We believe that the revision addresses the concerns about soundness raised in the review. If the reviewer agrees, we would appreciate it if they would reconsider their score.

Thank you for the detailed response and revised manuscript. Could you maybe highlight the changes in a different colour to make them easier to identify?

W1

The clarification and helpful additional explanations have made the relevance much clearer. I share the sentiment that a comprehensive understanding of a simplified setting is a valuable contribution. However (as Reviewer w64F also mentions), the unclear applicability to the relevant general setting still remains a weakness and it would significantly strengthen the manuscript (for ICLR or future submissions) if more insight could be provided.

W2, Q1-Q2

I like the new Section E, thank you for providing this additional evidence and the explanation for why the N\sqrt{N}-sphere is a natural choice for initialisation. I am still not convinced by the claim that "trajectories starting with R0>RcR_0>R_c retrieve the teacher, and those starting with R0<RcR_0<R_c converge to a nongeneralizing state", even when including the new dependence of RcR_c on s0s_0. Fig. 3(a) shows that there is some region AA (passed by the failing trajectories) and a region BB (passed by the successful ones) whose projection onto the (R,s)(R,s)-plane is the same (however far apart they may be in the full, NN-dimensional space). If a trajectory was started in region AA, say with R0=0.1R_0=0.1 and s0=0.5s_0=0.5, it would continue along one of the orange lines of Fig. 3(a) and subsequently fail (a point visited in the intermediate stages of one of the orange trajectories could also be used as a starting point). But the (0.1,0.5)(0.1,0.5) rectangle in Fig. 8 would imply success almost surely. This suggests that whether a trajectory fails or succeeds has an additional dependence on the type of initialisation. In other words, if the probability of success was only determined by (R0,s0)(R_0,s_0) for all initialisations, projecting trajectories onto the (R,s)(R,s) plane should retain the boundary of Fig. 8. What your findings do seem to show is that for typical choices of initialisation (e.g. standard Gaussian with concentration on the N\sqrt{N}-sphere), there is indeed such a threshold RcR_c. I would be interested to get your thoughts on this and if this issue was resolved (e.g. by discussing this dependence on initialisation and adapting the claim in the paper) I would definitely raise my score.

W3, Q3

While the revised Section 3.4 is more sound, I find the new exposition a bit confusing. As I understand it, you claim validity of Eqns. (13) (up to a constant) and (14) in the setting where Rc≪N−1/2R_c \ll N^{-1/2}. If this is correct, it would be good to make this clearer and adjust the claims about the findings of this section in the introduction and conclusion (in line with the explanation "We note that ..." starting in l. 487). Regarding the exposition, I still have some open questions:

  • If you do not claim that the growth is exponential up to RretR_\mathrm{ret}, why should Eqn. (13) be valid (even up to a constant)?
  • What is the motivation for replacing λ(t)\lambda(t) by cαc_\alpha? What do you mean by your claim that this approximation "quantitatively captures the retrieval time distribution"? If you use your empirical findings to motivate this theory and then subsequently claim that the theory is supported by these findings, the argumentation seems circular.
  • Can you provide more details about your experiment on the final approach to the teacher? Over which trajectories and ranges of R0R_0 did you compute these statistics? It would be good to include more details in the paper to support your claim that the final approach only adds a constant.

Q5

I unfortunately still do not understand how u^\hat{u} is chosen. By "the student's transverse direction at time tt", do you mean the (normalised) projection of w(t)w(t) onto the orthogonal complement of span(w∗)\mathrm{span}(w^*)? If this is the case, how is u^\hat{u} shared by all samples, are these projections then averaged over all samples to obtain u^\hat{u}?

Q4 & Q6-8

Thank you for the responses, which have resolved these questions.

Reviewer_w46FOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces and studies a variant of the Phase Retrieval problem, where the dataset is symmetrised by considering inputs in pairs whose directions perpendicular to the teacher are opposites. This leads to a symmetry in the loss function that is also displayed by the population loss, and for this reason the model can be seen as an interpolation between the actual phase retrieval problem with a finite dataset and its population counterpart. This symmetrisation leads to a great simplification of the landscape, namely that all local minima are in the manifold with zero alignment with the teacher, and this allows the authors to consistently solve the model, by using a DMFT approach together with many simulations. They find that the success of a simulation depends exclusively on the initial overlap with the signal, and are able to predict the N→∞N\to\infty limit of this critical overlap using DMFT. Furthermore they are able to resolve finite N recovery probabilities, and escape time distributions using some more observation-based insights.

Critical strengths

The presentation is tidy, self contained and in many ways satisfactory. The authors find a simple mechanism for recovery in a simplified model of Phase Retrieval, whose recovery with gradient based algorithms is still unknown. If a similar mechanism is proven to hold also in Phase Retrieval then this is an important step towards its comprehension.

Critical weaknesses

My main criticism is about the relevance of the proposed model: it is unclear whether the mechanism identified here has any relevance to asymmetrical phase retrieval, or if the symmetrisation has just simplified the model too much.

Questions for authors

-) The use of the world “trivialisation transition” is slightly misleading. In most works I am familiar with, trivialisation is used to indicate that no local minima exist, and only the global ones survive. Here it seems to indicates something different, namely the destabilisation of the local minimum that is found by this dynamics. If I am not mistaken there could be other rarer minima, that could be found with different dynamics or initialisations, and these would not be described by this transition. If this is correct, I suggest either changing the name to destabilisation transition, or at least to clarify what trivialisation stands for. For example the wording in line 293 “the loss has no spurious minima” seems to be too strong.

-) Details of the numerical simulations should be given. For example: when is a run considered failed? Is a maximum number of epochs set? Does this maximum number of epochs depend on N? This could be a short paragraph in the appendix.

-)I don’t like how the approximation in equation 12 is presented. In what sense is it an approximation? When is this approximation valid? Clearly it cannot be valid at large times, since the teacher student overlap would diverge exponentially in time. Making the argument more precise would improve the presentation of the result, and give a theoretical justification for the logarithmically diverging escaping times.

-)I would like the RS closure to be discussed in greater detail. Is this an approximation? Or is RS expected for some reason? Perhaps naively I would’ve said that the presence of local minima in the R=0 manifold could have made the landscape glassy, is there some reason why this shouldn’t hold?

1 comment
AuthorsOpenReview ↗

Response to reviewer w46F

We thank the reviewer for the careful reading and the constructive questions. We have revised the manuscript as detailed below.

Weakness (relevance to standard phase retrieval). We agree that this is the central open question. Symmetrization only restores at finite sample size a symmetry of the population loss, which confines the spurious minima to R=0R=0. The mechanism itself, an initial overlap of order N−1/2N^{-1/2} competing with a finite failure basin, does not rely on this confinement. Testing it in standard phase retrieval is the natural next step, and we now say so in the Discussion.

Q1 (trivialization). We thank the reviewer for this point, which is correct and helped us sharpen the terminology. As the reviewer suspected, our threshold marks the destabilization of the minima found by the dynamics, not the disappearance of all spurious minima, and the submitted text did not make this clear. We now define αtriv(N)\alpha_{\rm triv}(N) by the absence of dynamically accessible spurious minima (Secs. 3 and 3.1), and have removed the claim that the loss has no spurious minima.

Q2 (numerical details). We apologize that the submitted version lacked these details, and have added them in App. A. In short, we use full-batch gradient descent, so one step is one epoch. A run succeeds when ∣R∣|R| first exceeds Rret=0.99R_{\rm ret}=0.99. It fails if this does not happen within 5000 steps (tmax⁡=12,500t_{\max}=12{,}500), and this limit is the same for all NN. It is ample: at N=1000N=1000, no retrieval takes longer than t≈2000t\approx2000. In the runs with a controlled initial overlap, a run is also stopped as failed once ∣R∣|R| falls below half the smallest spacing of the R0R_0 grid. We checked on long runs that this trapping is absorbing.

Q3 (Eq. (12)). We agree, and have rewritten Sec. 3.4. Eq. (12) combines two steps. Expanding Eq. (11) to leading order in RR gives dR/dt=λ(t)RdR/dt=\lambda(t)R, which is controlled while R2≪1R^2\ll1. Replacing λ(t)\lambda(t) by a constant cαc_\alpha is the uncontrolled step. It describes the early escape from the symmetry plane for ∣R0∣≫Rc(α)|R_0|\gg R_c(\alpha), and fails near RcR_c, where trajectories linger at the basin boundary.

As the reviewer notes, Eq. (12) cannot hold at long times, and we do not claim exponential growth up to RretR_{\rm ret}. Stages whose duration does not depend on R0R_0 only add a constant, T≃t0+cα−1log⁡(1/∣R0∣)T\simeq t_0+c_\alpha^{-1}\log(1/|R_0|). The final approach to the teacher is such a stage: at N=1000N=1000, going from ∣R∣=0.5|R|=0.5 to RretR_{\rm ret} takes about 300300, with a standard deviation below 1010. cαc_\alpha is therefore an effective rate. As a theoretical check of the logarithmic escape time, the exactly solvable full-population dynamics (App. D) gives the same dependence on ∣R0∣|R_0| without assuming a constant rate. Its retrieval-time density, which has no fitted parameter, is now shown in Fig. 4(b).

Q4 (RS closure). The RS closure is an additional assumption, not a controlled approximation. We use it only in a complementary calculation, which carries the threshold measured in Fig. 2(c) over to infinite NN; the time-dependent DMFT does not rely on it. We now say so explicitly in App. C.4, where we also spell out what the closure assumes. The finite-NN thresholds αtriv(N)\alpha_{\rm triv}(N) are measured directly from the zero crossing of λR\lambda_R and involve no RS assumption; only the N→∞N\to\infty value, α∞≈26.86\alpha_\infty\approx26.86, depends on the closure. The concern about glassiness is natural, given the many minima at R=0R=0, and we cannot exclude replica-symmetry breaking. Still, we have good reasons to trust it here. Proposition 2 (App. C.5) shows that the closure has at most one regular solution, and our stationary solves find it from every initial guess we tried. Moreover, the finite-NN trajectories, both retrieving and failing, follow the full DMFT more closely as NN grows (Figs. 5–6).

Reviewer_1NPXOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes and analyzes a version of phase retrieval problem in which the training set of vectors is symmetrized with respect to the teacher vector. The paper shows that in this problem the loss has two global opposite minima and, generally, multiple local minima on the hyperplane between them. The main object of study is the competition between these two sorts of minima. The paper develops a DMFT theory describing this problem in infinitely high dimensions. In finite dimensions, stability of the local minima and convergence of the optimization trajectories to global vs. local minima are studied numerically. The main findings include the observation that in finite dimensions there is a range of training set sizes for which the optimization typically converges to a global minimum despite the presence of multiple local minima. In the infinite-dimensional limit this distinction between loss surface triviality and guaranteed generalization seems to disappear. A specific limiting critical ratio of data size to dimension as well as the phase retrieval distributions are found.

Critical strengths

Strong exposition

The paper is very readable and contains a clear narrative arc. The introduction gives a detailed and informative account of prior works, indicates the key challenge to be addressed (does successful retrieval precede desappearance of local minima?), thus motivating the proposed symmetrized model. The model is clearly described. Then, based on DMFT and numerical simulations, a detailed analysis of the model is performed, in particular revealing an answer to the addressed question.

Interesting, rich results in a complex non-convex setting

The setting of the paper is complex, high-dimensional and non-convex. Its analysis is genuinely challenging. The specific addressed question of predominant global convergence despite the presence of many local minima is deep and natural. The simplified symmetrized model proposed is somewhat artificial, but is justified by the the nice geometric picture revealed by the study. The obtained results characterizing the loss surface and typical behavior of optimization trajectories are rich, detailed and interesting.

Critical weaknesses

Unclear DMFT derivations and overstated mathematical claims

The paper repeatedly claims rigorous DMFT results: "The resulting symmetrized model allows us to analyze rigorously both the retrieval dynamics and the landscape trivialization in a controlled setting" (line 99), "the thermodynamic limit N→∞N\to\infty can be rigorously solved with DMFT" (line 249), However, the presented solutions are nowhere near rigorous. My impression is that they are even below theoretical physics standards of nonrigorous, but complete derivations. Appendix B looks very sketchy; I found it hard to understand the underlying theory from it. In particular, transition from the path integral (38) to the representative process (39) is completely omitted. The exposition is hardly accessible to general ML audience not familiar with theoretical physics techniques.

There are some further related issues.

  1. The summary of the DMFT analysis presented in section 2.1 is not a closed-form solution (in particular, the kernels CC and GG are not specified). As a result, neither the analysis nor its outcome is clearly and completely exposed to the reader. In essense, the readers just have to trust the authors that there is some theory somehow explaining the described phenomena.

  2. An especially questionable theoretical claim is that both αGD\alpha_{GD} and αtriv\alpha_{triv} converge to the common N→∞N\to\infty limit α∞≈26.86\alpha_{\infty}\approx 26.86 (lines 370-377). In contrast to some other assertions more or less confirmed by numerics, the respective curves in Figure 1(c) do not look like converging to the same limit. The derivations in the appensix rely on several unverified assumptions (such as uniqueness of the nontrivial regular-RS solution).

Questions for authors

Can the DMFT representation in section 2.1 be formulated as a proper theorem and provided with a proper proof?

I suggest to at least revise the paper to accurately qualify the actual status of its various theoretical results (such as "rigorously proved", "nonrigorous, but conjectured to be exact in the thermodynamic limit", merely "approximate", etc.)

3 comments
AuthorsOpenReview ↗

Response to reviewer 1NPx (1/2)

We thank the reviewer for the careful reading and for the constructive criticism. We have taken all the points into account and revised the manuscript, as detailed below. We believe the revised version is substantially improved, in part due to the reviewer's criticism.

In short, we agree with the main points: the original version overstated the mathematical status of the DMFT results, and the description of the derivation was hard to follow.

Overstated claims. We removed the word "rigorously" from the two sentences the reviewer quotes (Introduction and Sec. 3), and "exactly" from the statement of the limiting threshold in the list of contributions. The status of each result is now stated where it appears:

  • Proved: the confinement of all spurious minima to the symmetry plane R=0R=0 (Proposition 1, proved in App. B); the exact solution of the full-population dynamics (App. D); the uniqueness of the regular stationary solution within the RS closure (Proposition 2, App. C.5).
  • Non-rigorous, expected to be exact as N→∞N\to\infty: the time-dependent DMFT (Sec. 2.1, App. C.1-C.3). Such non-rigorous derivations are standard for DMFT in the statistical physics of learning [Agoritsas et al. 2018; Mignacco et al. 2020; Bordelon & Pehlevan 2022]; rigorous proofs exist so far only for a subclass of problems [Gerbelot et al. 2024]. The finite-dimensional identities and the Gaussian average are exact. The evaluation at a self-averaging large-NN saddle point is formal and we do not prove convergence. This is now stated in Sec. 2.1 and at the beginning of App. C. It is supported by the concentration of finite-NN trajectories around the DMFT prediction as NN grows (Fig. 6).
  • Additional assumption: the stationary replica-symmetric closure (App. C.4), whose assumptions are now listed explicitly there. It enters only in the stationary calculation that gives the N→∞N\to\infty value, α∞≈26.86\alpha_\infty\approx26.86. The finite-NN thresholds αtriv(N)\alpha_{\rm triv}(N) are measured directly from the zero crossing of λR\lambda_R and involve no RS assumption, and none of the results on the retrieval probability, Rc(α)R_c(\alpha) or the retrieval times depend on it.
  • Approximate: the constant-rate growth law, Eq. (12), and the retrieval-time density that follows from it, Eq. (14). Sec. 3.4 now separates the controlled step (expansion to leading order in RR) from the uncontrolled one (a constant rate) and states the regime of validity.

Completeness of the derivation. The section of the main text describing the DMFT calculation was rewritten and a heuristic explanation of the equation is given. A full derivation is given in App. C, which was rewritten. It now specifies the microscopic dynamics, initialization and response conventions (C.1), explicitly performs the Gaussian disorder average and derives the saddle-point equations (C.2), and gives the complete self-consistent closure (C.3). In particular, C.2 fills the gap identified by the reviewer: we introduce the correlation and response kernels, write the factorized dynamical functional, and derive its saddle-point action. We then represent the quadratic response-field terms using auxiliary Gaussian processes and integrate out the response fields to obtain the representative processes, including their noise covariances and causal memory terms. C.3 derives the response and covariance equations that determine all kernels.

AuthorsOpenReview ↗

Response to reviewer 1NPx (2/2)

Convergence of αGD(N)\alpha_{\rm GD}(N) and αtriv(N)\alpha_{\rm triv}(N) to a common limit. The reviewer is right that the curves in Fig. 1(c) do not look as if they converge, and the submitted text did not explain why. We added this explanation to Sec. 3.3.

The argument for a common limit is straightforward: Retrieval from an initial overlap R0R_0 occurs when ∣R0∣>Rc(α)|R_0|>R_c(\alpha), and Rc(α)>0R_c(\alpha)>0 as long as the zero-overlap minima are stable. For random initialization ∣R0∣∼N−1/2→0|R_0|\sim N^{-1/2}\to0, so for N→∞N\to\infty retrieval fails if and only if Rc(α)>0R_c(\alpha)>0, i.e. the two thresholds coincide.

The same argument gives the rate of convergence of αGD(N)\alpha_{\rm GD}(N), and shows that it is extremely slow. Setting P=1/2P=1/2 in Eq. (9) gives Rc(αGD(N))≃0.67 N−1/2R_c(\alpha_{\rm GD}(N))\simeq0.67\,N^{-1/2}. With the DMFT Rc(α)R_c(\alpha), which decreases roughly exponentially with α\alpha (Fig. 3(d)), this is a prediction for αGD(N)\alpha_{\rm GD}(N) with no fitting parameter, which can be compared directly with the numerics. Thanks to the reviewer's comment, this comparison is now shown in Fig. 1(c): the prediction closely matches the measured values. It also explains the slow convergence: the slow growth of αGD(N)\alpha_{\rm GD}(N) over the accessible sizes is what the theory predicts, and sizes at which the two curves visibly approach each other are far beyond simulations.

For αtriv(N)\alpha_{\rm triv}(N) we do not have a theory of the finite-size corrections. The measured values increase monotonically with NN (22.922.9 at N=100N=100 to 25.225.2 at N=2000N=2000) and remain below α∞≈26.86\alpha_\infty\approx26.86. We agree that these data alone do not establish convergence to that value, and we now say so in the text. The value of the common limit is the prediction of the stationary RS closure (see above), and the statement that the two thresholds share a limit rests on the argument of the previous paragraph, not on an extrapolation of Fig. 1(c).

Regarding the assumptions of the stationary analysis: the uniqueness of the regular RS solution is no longer assumed. It is proved in Proposition 2 (App. C.5), whenever such a solution exists. The remaining assumptions (relaxation to a fixed point, time-translation-invariant integrable responses) are listed at the beginning of App. C.4.

Question (theorem and proof). We are not able to formulate the DMFT representation of Sec. 2.1 as a theorem with a proof. Rigorous proofs of DMFT equations exist for related gradient-flow problems, but we have not verified that their assumptions cover our loss and the symmetrized data, and we do not claim it. Following the reviewer's suggestion, we instead qualify the status of each result, as listed above. We also show increasing concentration of finite-NN trajectories around the DMFT prediction as NN grows (Fig. 6), providing numerical support for the representation.

We believe that the revision addresses the concerns raised in the review. If the reviewer agrees, we would appreciate it if they would reconsider their score.

I thank the authors for addressing my concerns. I think the revised paper still needs some polishing. For example, I had difficulty finding an explicit definition of the finite-dimensional growth rate λR\lambda_R used in Figure 2(c). Also, the statement “When α→αtriv(N)\alpha\to\alpha_{\mathrm{triv}}(N), every trajectory generalizes by definition” in line 411 is puzzling: αtriv(N)\alpha_{\mathrm{triv}}(N) is defined through the average growth rate, whose vanishing does not imply that all spurious minima have become unstable or that every trajectory generalizes.

Nevertheless, I acknowledge the substantial improvements in the exposition, particularly regarding the DMFT derivation and the careful qualification of mathematical claims. Accordingly, I am raising my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.