On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors

• URL: http://arxiv.org/abs/2107.09660v1
• Date: Tue, 20 Jul 2021 17:45:55 GMT
• Title: On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors
• Authors: Arnab Auddy and Ming Yuan
• Abstract summary: We study the estimation of a rank-one spiked tensor in the presence of heavy tailed noise. Our results highlight some of the fundamental similarities and differences in the tradeoff between statistical and computational efficiencies.
• Score: 10.166435679260015
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the estimation of a rank-one spiked tensor in the presence of heavy tailed noise. Our results highlight some of the fundamental similarities and differences in the tradeoff between statistical and computational efficiencies under heavy tailed and Gaussian noise. In particular, we show that, for $p$ th order tensors, the tradeoff manifests in an identical fashion as the Gaussian case when the noise has finite $4(p-1)$ th moment. The difference in signal strength requirements, with or without computational constraints, for us to estimate the singular vectors at the optimal rate, interestingly, narrows for noise with heavier tails and vanishes when the noise only has finite fourth moment. Moreover, if the noise has less than fourth moment, tensor SVD, perhaps the most natural approach, is suboptimal even though it is computationally intractable. Our analysis exploits a close connection between estimating the rank-one spikes and the spectral norm of a random tensor with iid entries. In particular, we show that the order of the spectral norm of a random tensor can be precisely characterized by the moment of its entries, generalizing classical results for random matrices. In addition to the theoretical guarantees, we propose estimation procedures for the heavy tailed regime, which are easy to implement and efficient to run. Numerical experiments are presented to demonstrate their practical merits.

Related papers

• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Optimizing the Noise in Self-Supervised Learning: from Importance Sampling to Noise-Contrastive Estimation [80.07065346699005]
  It is widely assumed that the optimal noise distribution should be made equal to the data distribution, as in Generative Adversarial Networks (GANs) We turn to Noise-Contrastive Estimation which grounds this self-supervised task as an estimation problem of an energy-based model of the data. We soberly conclude that the optimal noise may be hard to sample from, and the gain in efficiency can be modest compared to choosing the noise distribution equal to the data's.
  arXiv  Detail & Related papers  (2023-01-23T19:57:58Z)
• Error Analysis of Tensor-Train Cross Approximation [88.83467216606778]
  We provide accuracy guarantees in terms of the entire tensor for both exact and noisy measurements. Results are verified by numerical experiments, and may have important implications for the usefulness of cross approximations for high-order tensors.
  arXiv  Detail & Related papers  (2022-07-09T19:33:59Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  We show that deviating from this assumption can actually lead to better statistical estimators. In particular, the optimal noise distribution is different from the data's and even from a different family.
  arXiv  Detail & Related papers  (2022-03-02T13:59:20Z)
• Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation [50.85788484752612]
  Noise-contrastive estimation (NCE) is a statistically consistent method for learning unnormalized probabilistic models. It has been empirically observed that the choice of the noise distribution is crucial for NCE's performance. In this work, we formally pinpoint reasons for NCE's poor performance when an inappropriate noise distribution is used.
  arXiv  Detail & Related papers  (2021-10-21T16:57:45Z)
• Denoising Score Matching with Random Fourier Features [11.60130641443281]
  We derive analytical expression for the Denoising Score matching using the Kernel Exponential Family as a model distribution. The obtained expression explicitly depends on the noise variance, so the validation loss can be straightforwardly used to tune the noise level.
  arXiv  Detail & Related papers  (2021-01-13T18:02:39Z)
• TenIPS: Inverse Propensity Sampling for Tensor Completion [34.209486541525294]
  We study the problem of completing a partially observed tensor with MNAR observations. We assume that both the original tensor and the tensor of propensities have low multilinear rank. The algorithm first estimates the propensities using a convex relaxation and then predicts missing values using a higher-order SVD approach.
  arXiv  Detail & Related papers  (2021-01-01T22:13:19Z)
• Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks [13.879536370173506]
  We study symmetric spiked matrix models with respect to a general class of noise distributions. We exhibit an estimator that works for heavy-tailed noise up to the BBP threshold that is optimal even for Gaussian noise. Our estimator can be evaluated in time by counting self-avoiding walks via a color-coding technique.
  arXiv  Detail & Related papers  (2020-08-31T16:57:20Z)
• Sparse Nonnegative Tensor Factorization and Completion with Noisy Observations [22.928734507082574]
  We study the sparse nonnegative tensor factorization and completion problem from partial and noisy observations. We show that the error bounds of the estimator of the proposed model can be established under general noise observations.
  arXiv  Detail & Related papers  (2020-07-21T07:17:52Z)
• Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality [92.35257908210316]
  We study the problem of estimating a low-rank tensor given incomplete and corrupted observations. We find that it attains unimprovable rates $ell-2$ accuracy.
  arXiv  Detail & Related papers  (2020-06-15T17:47:13Z)
• Tensor denoising and completion based on ordinal observations [11.193504036335503]
  We consider the problem of low-rank tensor estimation from possibly incomplete, ordinal-valued observations. We propose a multi-linear cumulative link model, develop a rank-constrained M-estimator, and obtain theoretical accuracy guarantees. We show that the proposed estimator is minimax optimal under the class of low-rank models.
  arXiv  Detail & Related papers  (2020-02-16T07:09: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.