High-dimensional random landscapes: from typical to large deviations

I would like to thank the Referee for their very careful reading of these lecture notes and for all the comments and suggestions. Below, I provide an account of the modifications made to the notes, following the Referee’s comments. The changes are listed in the same order as the corresponding comments in the report, and the numbering refers to that order. The numbering of the equations and of the references refer to the updated version of the notes.

1) I thank the referee for this relevant suggestion. I have now included several comments to emphasize that the concepts and methods presented in the notes (with the aim of introducing tools for high-dimensional landscapes) represent a specific and not exhaustive approach to the inference problem. These clarifications, with the relative references, have been included at the following points throughout the notes:

Sec. 1.2, on the scope of the lecture notes: In these notes, we consider the denoising problems as illustrative examples to motivate our discussion of the landscape program. To this end, we focus on a specific inference framework, maximum likelihood, since it naturally maps the denoising problem onto a landscape optimization problem. We caution, however, that this is not the only possible approach to address inference tasks, and in some cases, it may not be the optimal one, as we briefly mention in Secs. 2.3.1 and 3.3.1. For a broader overview of how these denoising problems are addressed within the framework of statistical inference, we refer the interested reader to the review articles [4,9].

Section 2.3.1, on the recovery transition — matrix case: The threshold $(r/\sigma)_c=1$ is associated to one specific procedure to estimate the signal, that is maximum likelihood. One may wonder whether this threshold is optimal, or whether different estimators allow to recover information on the signal for values of $(r/\sigma)<1$. This is a question to address within the Bayesian formalism, and the answer depends on the assumptions made on the statistical distribution of the signal (i.e., in the language of Box [B1], on the prior). For the low-rank matrix approximation problem that we are studying, one can show that the threshold given by maximum likelihood is optimal, for instance, when the signal vector v is taken with a spherical prior, meaning that v is extracted randomly with uniform measure in $\mathcal{S}_N(\sqrt N)$; in this case, $(r/\sigma)=1$ coincides with the detection threshold, below which no estimator is able to distinguish between the spiked matrix and a GOE matrix. On the other hand, maximum likelihood is generally not optimal when the signal prior encodes additional structure, for example sparsity [43].

Sec. 2.3.3, on gradient descent —matrix case: We remark that this corresponds to a specific choice of the optimization algorithm, just as maximum likelihood is a specific choice of the estimator of the signal. Different algorithms may be considered, which can perform better than Langevin at signal estimation. The readers interested in algorithms commonly used in the context of statistical inference and in their application to the low-rank matrix estimation problem are referred to [62, 63]. (The two added references are on AMP)

Section 3.3.1, on the recovery transition — tensor case: Also in the tensor case, the recovery threshold achieved by maximum likelihood is optimal—that is, it coincides with the detection threshold—if a spherical prior is assumed on the signal v [90,91]. As for the matrix case, this is not expected to be generic under more structured assumptions on the statistics of the signal.

Sec. 3.3.3, on gradient descent —tensor case: As in the matrix case, we have focused here on a specific optimization algorithm, Langevin dynamics (or gradient descent). Other algorithms can be considered, which may outperform Langevin. In fact, for the spiked tensor problem, it is known that there exist algorithms that recover the signal at values of the signal-to-noise ratio that scale with N with a smaller power than the $\alpha_c = (p−2)/2$ required by Langevin [9, 64].

2) Indeed, the notes focus on continuous variables. On p. 3, I now write: For ease of discussion, we henceforth assume that the si are continuous variables, and we refer to $\mathcal{E}(s)$ as an “energy landscape" that the system aims at minimizing through its dynamics. Subsequently, on the same page, I have rephrased the sentence as: their number grows exponentially fast with N; that is, it exhibits the same scaling with N as the volume of the configuration space accessible to the system.

3) In the revised version, I have added the general references ([1]–[4]) shortly after the first sentence, when mentioning different examples of landscapes (energy, fitness, loss, and cost functions). In addition, I have modified the last sentence of the introduction to cite volume [8], which collects review papers discussing the emergence of glassy-related phenomena in various contexts. The concluding sentence of the introduction now reads: Recently, the characterization of high-dimensional random landscapes has regained prominence, also driven by the emergence of ruggedness and glassy phenomenology in a wide range of fields, including machine learning, quantum control, theoretical biology, and inference (see [8] for a collection of review papers).

4-6) Following the suggestions, in Figure 2 I have removed one of the two images of the noisy picture and added in the caption a citation to the source of the image. I have replaced 'matrix denoising' with 'low-rank matrix estimation' throughout the notes, and have made the same replacement for the tensor case. Moreover, I have specified the ordering of the indices in the expression for the variance in both places, as suggested.

7) I thank the referee for this remark. I have now introduced the Jacobian of the transformation (just below Eq. (4)) and added a comment to clarify that it is this Jacobian whose determinant has absolute value equal to unity, which in turn follows from the orthogonality of the matrix O. This comment is provided in footnote 1.

8) In the main text, I have now clarified that I refer to a single eigenstate. Moreover, I have added footnote 2 with the following comment: Notice that the joint distribution of the complete set of eigenvectors must include the constraint that they are orthogonal to one another, and this orthogonality condition couples the eigenvectors. The orthogonal matrix made by the eigenvectors can however be viewed as being drawn at random from the set of all orthogonal matrices: every orthonormal basis is equally likely, with no preferred direction. This is phrased mathematically by saying that the eigenvectors are distributed according to the Haar measure on the orthogonal group O(N) of $N \times N$ orthogonal matrices.

9-12) To avoid this confusing formulation, I have removed the word “several” and, just below, added the following comment: Tools of statistical physics allow us to answer this question for typical instances of the noisy matrix, i.e., to characterize what happens with high probability with respect to the noise. I have implemented the other suggested changes.

13) The relevant references are [18] and [20–25], which discuss some of the results in this subsection in more general contexts than spiked GOEs. Since these references pertain to different aspects (e.g., the Wigner law or the typical value of the outliers), I have decide to cite each of them in the corresponding points in the text where the different results are discussed for the spiked GOE case, and I have added at the beginning of the subsection the sentence: readers interested in such generalizations are referred to the specific references cited when each result is presented.

14-16) Thank you for the suggestions, that I have implemented. In particular, I have added the very relevant reference that was erroneously missing, and included the following comment: For rank-1 GOE perturbed matrices, the transition of the typical value was first determined in the seminal work [19]. The transition in the scaling of the fluctuations was instead characterized in [27] for Wishart matrices, and it is now referred to generically as the BBP transition. Ref [19] is now also cited on p. 17, when discussing the typical value of the isolated eigenvalue.

17) Following the suggestion, in Fig. 4 I have added the definition of $g_N$ in the caption. Moreover, I have modified the symbol denoting the Stieltjes transform to avoid any confusion. Thank you for pointing this out.

18) The definition of $\theta(x)$ is now given in Eq. (58). Moreover, I have expanded that section of the notes to include a discussion on how Eq. (57) is derived. The procedure for $r>0$ is very similar to that for $r=0$, as it is now commented at the end of page 21. I hope these comments gives some useful insight on how Eq. (57) arises.

19) Following this suggestion, I have modified the text around Eq. (60) and rephrased the comment as follows: The components of the vector w in the basis $u^\alpha$ are distributed like the components of a vector extracted randomly from the hypersphere. This mirrors the statement that the eigenvectors of GOE matrices have the statistics of an orthonormal basis sampled uniformly, as discussed around Eq. (4) and in Box [B2].

20) Indeed, as the referee suggests this part of the notes lacked some precision regarding the nature of the low-temperature phase. I have added a discussion that hopefully clarifies that this phase is not a "usual"spin glass phase, but rather a “ferromagnet in disguise.” The new paragraph appears at the end of page 23 (not reproduced here because it is a bit lengthy).

21) Following the suggestions, I have modified the formulation of the sentence as follows: For the model we are looking at, not surprisingly one finds that in the mean-field limit the dynamics does not depend on r: exactly as for the eigenvalue distribution, the rank-one perturbation gives sub-leading contributions that are negligible when $N \to \infty$. The solution to the DMFT equations for $r = 0$ has been studied in detail in [45]. We briefly summarize some of the results obtained studying the equations in the noiseless limit $\beta \to \infty$. The footnote 3 specifies: Due to the fact that r does not affect the equations in the mean-field limit, the phenomenology of [45] holds true also for r >0, if one focuses on the short timescale regime. (The current reference [45] was the previous reference [32]).

22-23) Regarding Eq. (78), I have added a citation to Ref. [61], where the corresponding calculation is performed, and included a comment that the prefactor scaling as $t^{−3/2}$ actually arises from the contribution of the eigenvalues in the continuous part of the eigenvalue distribution. Concerning the scaling function in the critical regime, the numerical analysis in Ref. [61] indeed shows that the function depends only on the scaling variable $\omega$ and appears to follow a power law with an exponent linear in $\omega$. I have added these comments around Eq. (79).

24) Indeed, as the referee points out the equations written in the previous version of the notes were correct only up to subleading terms in N, but this was not made explicit. Following the referee’s comment, I have modified the variance in Eq. (82) writing the multiplicity factors that arise due to repetitions in the indices, thereby uniformizing the choice of variance with the matrix case. Moreover, I have added footnote 4 to clarify how these factors arise when constructing a symmetric tensor by taking linear combinations of the entries of an asymmetric tensor. I have also slightly modified the discussion in Box [B6] accordingly, since the covariances were used there.

25-26) I have modified Eq. (94) and added the following comment: Notice that a small difference between the quenched and annealed complexities may correspond to a large difference between the typical and average value of N_N when N is large, due to the exponential amplification. Also, the slashed notation is now explained.

27) Here, I am using the fact that the surface of a sphere of dimension $n-1$ and radius $r$ is given by $\frac{2 r^{n-1} \pi^{n/2}}{\Gamma(n/2)}$. Eq. (109) corresponds to this formula, for $n-1\to N-2$ and $r \to \sqrt{1-q^2}$.

28) Indeed, the argument around Eq. (110) could be made more precise. I have hopefully made it more precise by adding the following sentence: For GOE matrices, the latter takes the Large Deviation form (56). The explicit form of the Large Deviation function $\mathcal{S}[\rho]$ is not needed to proceed with the calculation: the only relevant ingredient is that the probability decays with speed $N^2$, i.e., much faster than the determinant term in (112), which behaves only exponentially in N. When computing (112) via the Laplace method for large N, the term proportional to $N^2$ dominates and must be optimized. This obviously selects the typical density $\rho_\infty(\lambda)$ as the optimizer. Correspondingly, in Sec. 2.2.2, when accounting for Large Deviation results for the GOE, I have added a comment on the Large Deviation probability of the GOE eigenvalue density around the newly added Eq. (56).

29) Indeed, the referee is correct, I(y) is an even function depending on |y|. I have specified that in the text we are giving the explicit expression for I(y) only for y<0.

30) Following the referee’s suggestion, I have added the sentence: This comes from the fact that an analytic solution of the DMFT equations in the large time limit has been found in [95]. The form found in [95] solves the equations up to a reparametrization of time [99]. The newly-added Ref. [99] discuss the issue of time reparametrization.

31) Thank you very much for spotting these typos, which I have corrected in the revised version of the notes.

I would like to thank the Referee for carefully reading these lecture notes and for pointing out the typos and/or imprecisions. In the revised version of the notes, I have implemented the suggested changes. In particular, regarding point 5: thank you for noting that the previous formulation was confusing. To clarify, I have removed the statement that the distribution has a “well-defined limit when N→∞” and have instead written that “the scaled variable N(ε)/N remains of order O(1) when N→∞.” I have implemented this correction in all other instances where the same phrasing appeared, including in Box [B5].