Fundamental limits of Non-Linear Low-Rank Matrix Estimation

• URL: http://arxiv.org/abs/2403.04234v1
• Date: Thu, 7 Mar 2024 05:26:52 GMT
• Title: Fundamental limits of Non-Linear Low-Rank Matrix Estimation
• Authors: Pierre Mergny, Justin Ko, Florent Krzakala, Lenka Zdeborov\'a
• Abstract summary: Bayes-optimal performances are characterized by an equivalent Gaussian model with an effective prior. We show that to reconstruct the signal accurately, one requires a signal-to-noise ratio growing as $Nfrac 12 (1-1/k_F)$, where $k_F$ is the first non-zero Fisher information coefficient of the function.
• Score: 18.455890316339595
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of estimating a low-rank matrix from non-linear and noisy observations. We prove a strong universality result showing that Bayes-optimal performances are characterized by an equivalent Gaussian model with an effective prior, whose parameters are entirely determined by an expansion of the non-linear function. In particular, we show that to reconstruct the signal accurately, one requires a signal-to-noise ratio growing as $N^{\frac 12 (1-1/k_F)}$, where $k_F$ is the first non-zero Fisher information coefficient of the function. We provide asymptotic characterization for the minimal achievable mean squared error (MMSE) and an approximate message-passing algorithm that reaches the MMSE under conditions analogous to the linear version of the problem. We also provide asymptotic errors achieved by methods such as principal component analysis combined with Bayesian denoising, and compare them with Bayes-optimal MMSE.

Related papers

• Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods [24.06775799553418]
  We study the matrix denoising problem of estimating the singular vectors of a rank-$1$ signal corrupted by noise with both column and row correlations. Our work establishes the information-theoretic and algorithmic limits of matrix denoising with doubly heteroscedastic noise.
  arXiv  Detail & Related papers  (2024-05-22T18:38:10Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  This paper studies minimax optimization problems defined over infinite-dimensional function classes of overparametricized two-layer neural networks. We address (i) the convergence of the gradient descent-ascent algorithm and (ii) the representation learning of the neural networks. Results show that the feature representation induced by the neural networks is allowed to deviate from the initial one by the magnitude of $O(alpha-1)$, measured in terms of the Wasserstein distance.
  arXiv  Detail & Related papers  (2024-04-18T16:46:08Z)
• Max-affine regression via first-order methods [7.12511675782289]
  The max-affine model ubiquitously arises in applications in signal processing and statistics. We present a non-asymptotic convergence analysis of gradient descent (GD) and mini-batch gradient descent (SGD) for max-affine regression.
  arXiv  Detail & Related papers  (2023-08-15T23:46:44Z)
• 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)
• Asymptotic consistency of the WSINDy algorithm in the limit of continuum data [0.0]
  We study the consistency of the weak-form sparse identification of nonlinear dynamics algorithm (WSINDy) We provide a mathematically rigorous explanation for the observed robustness to noise of weak-form equation learning.
  arXiv  Detail & Related papers  (2022-11-29T07:49:34Z)
• 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)
• Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency [59.48096489854697]
  The problem of estimating a linear functional based on observational data is canonical in both the causal inference and bandit literatures. We prove non-asymptotic upper bounds on the mean-squared error of such procedures. We establish its instance-dependent optimality in finite samples via matching non-asymptotic local minimax lower bounds.
  arXiv  Detail & Related papers  (2022-09-26T23:50:55Z)
• Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization [4.7464518249313805]
  Sub-gradient method (SubGM) is used to recover a low-rank matrix from a limited number of measurements. We show that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values.
  arXiv  Detail & Related papers  (2022-02-17T17:50:04Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)

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.