Statistical query lower bounds for tensor PCA

MaRDI QIDQ4999009zbMATH OpenFDO

Authors Rishabh Dudeja, Daniel Hsu

Publication date 9 July 2021

Full work available at URL https://arxiv.org/abs/2008.04101, https://jmlr.csail.mit.edu/papers/v22/20-837.html

zbMATH Keywords

computational complexitycomputational-statistical gapsmatrix/tensor estimationstatistical query (SQ) modeltensor PCA

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Statistical thresholds for tensor PCA
• Statistical limits of spiked tensor models
• Spectral algorithms for tensor completion
• The landscape of the spiked tensor model

Cites work

• An introduction to matrix concentration inequalities
• Analysis of Boolean Functions
• Conditional Expectation and Unbiased Sequential Estimation
• Dealing with range anxiety in mean estimation via statistical queries
• Efficient algorithms and lower bounds for robust linear regression
• Efficient noise-tolerant learning from statistical queries
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• On the complexity of random satisfiability problems with planted solutions
• On the distribution of the largest eigenvalue in principal components analysis
• Statistical algorithms and a lower bound for detecting planted cliques
• Tensor decompositions for learning latent variable models
• Tensor SVD: Statistical and Computational Limits
• The landscape of the spiked tensor model
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis

Cited in

(10)

• Bounds on the quality of the PCA bounding boxes
• Tensor clustering with planted structures: statistical optimality and computational limits
• Inference for low-rank tensors -- no need to debias
• Computational barriers to estimation from low-degree polynomials
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Statistical Query Lower Bounds for Tensor PCA
• Clustering a mixture of Gaussians with unknown covariance
• SQ lower bounds for random sparse planted vector problem
• Tensor-on-tensor regression: Riemannian optimization, over-parameterization, statistical-computational gap and their interplay
• Tensor graphical Lasso for cryptocurrency portfolio analytics

This page was built for publication: Statistical query lower bounds for tensor PCA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4999009)