Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery

• URL: http://arxiv.org/abs/2502.01583v1
• Date: Mon, 03 Feb 2025 18:08:30 GMT
• Title: Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery
• Authors: Filip Kovačević, Yihan Zhang, Marco Mondelli,
• Abstract summary: We focus on recovering the subspace spanned by the signals via spectral estimators. Our main technical contribution is a precise characterization of the performance of spectral methods. Our analysis unveils a phase transition phenomenon in which, as the sample complexity grows, eigenvalues escape from the bulk of the spectrum.
• Score: 21.414505380263016
• License:
• Abstract: Multi-index models provide a popular framework to investigate the learnability of functions with low-dimensional structure and, also due to their connections with neural networks, they have been object of recent intensive study. In this paper, we focus on recovering the subspace spanned by the signals via spectral estimators -- a family of methods that are routinely used in practice, often as a warm-start for iterative algorithms. Our main technical contribution is a precise asymptotic characterization of the performance of spectral methods, when sample size and input dimension grow proportionally and the dimension $p$ of the space to recover is fixed. Specifically, we locate the top-$p$ eigenvalues of the spectral matrix and establish the overlaps between the corresponding eigenvectors (which give the spectral estimators) and a basis of the signal subspace. Our analysis unveils a phase transition phenomenon in which, as the sample complexity grows, eigenvalues escape from the bulk of the spectrum and, when that happens, eigenvectors recover directions of the desired subspace. The precise characterization we put forward enables the optimization of the data preprocessing, thus allowing to identify the spectral estimator that requires the minimal sample size for weak recovery.

Related papers

• Optimal Spectral Transitions in High-Dimensional Multi-Index Models [21.56591917674864]
  We introduce spectral algorithms based on the linearization of a message passing scheme tailored to this problem. We show that the proposed methods achieve the optimal reconstruction threshold. Supported by numerical experiments and a rigorous theoretical framework, our work bridges critical gaps in the computational limits of weak learnability in multi-index model.
  arXiv  Detail & Related papers  (2025-02-04T18:15:51Z)
• Matrix Completion via Residual Spectral Matching [2.677354612516629]
  Noisy matrix completion has attracted significant attention due to its applications in recommendation systems, signal processing and image restoration. We propose a novel residual spectral matching criterion that incorporates the numerical but also locational information of residuals. We derive optimal statistical properties by analyzing the spectral properties of sparse random matrices and bounding the effects of low-rank perturbations and partial observations.
  arXiv  Detail & Related papers  (2024-12-13T09:42:42Z)
• Hodge-Aware Contrastive Learning [101.56637264703058]
  Simplicial complexes prove effective in modeling data with multiway dependencies. We develop a contrastive self-supervised learning approach for processing simplicial data.
  arXiv  Detail & Related papers  (2023-09-14T00:40:07Z)
• Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing [28.91482208876914]
  We consider the problem of parameter estimation in a high-dimensional generalized linear model. Despite their wide use, a rigorous performance characterization, as well as a principled way to preprocess the data, are available only for unstructured designs.
  arXiv  Detail & Related papers  (2023-08-28T11:49:23Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Precise Asymptotics for Spectral Methods in Mixed Generalized Linear Models [31.58736590532443]
  We consider the problem of estimating two statistically independent signals in a mixed generalized linear model. Our characterization exploits a mix of tools from random matrices, free probability and the theory of approximate message passing algorithms.
  arXiv  Detail & Related papers  (2022-11-21T11:35:25Z)
• Spectral Decomposition Representation for Reinforcement Learning [100.0424588013549]
  We propose an alternative spectral method, Spectral Decomposition Representation (SPEDER), that extracts a state-action abstraction from the dynamics without inducing spurious dependence on the data collection policy. A theoretical analysis establishes the sample efficiency of the proposed algorithm in both the online and offline settings. An experimental investigation demonstrates superior performance over current state-of-the-art algorithms across several benchmarks.
  arXiv  Detail & Related papers  (2022-08-19T19:01:30Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• Machine Learning for Vibrational Spectroscopy via Divide-and-Conquer Semiclassical Initial Value Representation Molecular Dynamics with Application to N-Methylacetamide [56.515978031364064]
  A machine learning algorithm for partitioning the nuclear vibrational space into subspaces is introduced. The subdivision criterion is based on Liouville's theorem, i.e. best preservation of the unitary of the reduced dimensionality Jacobian determinant. The algorithm is applied to the divide-and-conquer semiclassical calculation of the power spectrum of 12-atom trans-N-Methylacetamide.
  arXiv  Detail & Related papers  (2021-01-11T14:47:33Z)
• Spectral Methods for Data Science: A Statistical Perspective [37.2486912080998]
  Spectral methods have emerged as a simple yet surprisingly effective approach for extracting information from massive, noisy and incomplete data. This book aims to present a systematic, comprehensive, yet accessible introduction to spectral methods from a modern statistical perspective.
  arXiv  Detail & Related papers  (2020-12-15T18:40:56Z)

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.