Topological complexity of spiked random polynomials and finite-rank spherical integrals

• URL: http://arxiv.org/abs/2312.12323v1
• Date: Tue, 19 Dec 2023 16:52:01 GMT
• Title: Topological complexity of spiked random polynomials and finite-rank spherical integrals
• Authors: Vanessa Piccolo
• Abstract summary: In particular, we establish variational formulas for the exponentials of the average number of total critical points and the determinants of local parameters of a finite-rank spiked Gaussian Wigner matrix. The analysis is based on recent advances on finite-rank spherical integrals by [Guionnet, Husson] to study the large deviations of multi-rank spiked Gaussian Wigner matrices. There is an exact threshold for the external parameters such that, once exceeded, the complexity function vanishes into new regions in which the critical points are close to the given vectors.
• Score: 2.1756081703276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the annealed complexity of a random Gaussian homogeneous polynomial on the $N$-dimensional unit sphere in the presence of deterministic polynomials that depend on fixed unit vectors and external parameters. In particular, we establish variational formulas for the exponential asymptotics of the average number of total critical points and of local maxima. This is obtained through the Kac-Rice formula and the determinant asymptotics of a finite-rank perturbation of a Gaussian Wigner matrix. More precisely, the determinant analysis is based on recent advances on finite-rank spherical integrals by [Guionnet, Husson 2022] to study the large deviations of multi-rank spiked Gaussian Wigner matrices. The analysis of the variational problem identifies a topological phase transition. There is an exact threshold for the external parameters such that, once exceeded, the complexity function vanishes into new regions in which the critical points are close to the given vectors. Interestingly, these regions also include those where critical points are close to multiple vectors.

Related papers

• Emergence of meta-stable clustering in mean-field transformer models [1.6385815610837167]
  We model the evolution of tokens within a deep stack of Transformer layers as a continuous-time flow on the unit sphere. We focus on the emergence and persistence of meta-stable phases and clustering phenomena, key elements in applications like next-token prediction.
  arXiv  Detail & Related papers  (2024-10-30T17:16:38Z)
• The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank [0.6963971634605796]
  We construct a convergent family of outer approximations for the problem of optimizing functions over convex subject bodies to constraints. A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.
  arXiv  Detail & Related papers  (2024-06-13T18:00:09Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Symmetry & Critical Points for Symmetric Tensor Decomposition Problems [6.650108973968032]
  We consider the non optimization problem associated with the decomposition of a real symmetric tensor into a sum of rank one terms. Use is made of a rich symmetry structure to construct infinite families of critical points represented by Puiseux series in the problem dimension. Adesirable phenomenon, occurring for all critical points considered, concerns the number of negative Hessian eigenvalues increasing with the value of the objective function.
  arXiv  Detail & Related papers  (2023-06-13T16:25:30Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Complexity-like properties and parameter asymptotics of $\mathfrak{L}_{q}$-norms of Laguerre and Gegenbauer polynomials [0.0]
  Main monotonic statistical complexity-like measures of the Rakhmanov's probability density associated to the hypergeometrics (HOP) in a real continuous variable. The degree and parameters of these two-fold spreading measures are shown for the parameter-dependent families of HOPs of Laguerre and Gegenbauer types.
  arXiv  Detail & Related papers  (2021-08-16T16:49:49Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Hilbert-space geometry of random-matrix eigenstates [55.41644538483948]
  We discuss the Hilbert-space geometry of eigenstates of parameter-dependent random-matrix ensembles. Our results give the exact joint distribution function of the Fubini-Study metric and the Berry curvature. We compare our results to numerical simulations of random-matrix ensembles as well as electrons in a random magnetic field.
  arXiv  Detail & Related papers  (2020-11-06T19:00:07Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.