Statistical-computational trade-offs in tensor PCA and related problems via communication complexity

DOI10.1214/23-AOS2331arXiv2204.07526OpenAlexW4392591378MaRDI QIDQ6151966FDOQ6151966

Authors: Rishabh Dudeja, Daniel Hsu 

Publication date: 11 March 2024

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: Tensor PCA is a stylized statistical inference problem introduced by Montanari and Richard to study the computational difficulty of estimating an unknown parameter from higher-order moment tensors. Unlike its matrix counterpart, Tensor PCA exhibits a statistical-computational gap, i.e., a sample size regime where the problem is information-theoretically solvable but conjectured to be computationally hard. This paper derives computational lower bounds on the run-time of memory bounded algorithms for Tensor PCA using communication complexity. These lower bounds specify a trade-off among the number of passes through the data sample, the sample size, and the memory required by any algorithm that successfully solves Tensor PCA. While the lower bounds do not rule out polynomial-time algorithms, they do imply that many commonly-used algorithms, such as gradient descent and power method, must have a higher iteration count when the sample size is not large enough. Similar lower bounds are obtained for Non-Gaussian Component Analysis, a family of statistical estimation problems in which low-order moment tensors carry no information about the unknown parameter. Finally, stronger lower bounds are obtained for an asymmetric variant of Tensor PCA and related statistical estimation problems. These results explain why many estimators for these problems use a memory state that is significantly larger than the effective dimensionality of the parameter of interest.

Full work available at URL: https://arxiv.org/abs/2204.07526

Recommendations

• Statistical query lower bounds for tensor PCA
• Statistical thresholds for tensor PCA
• Statistical and computational trade-offs in estimation of sparse principal components
• Spectral algorithms for tensor completion
• Algorithmic thresholds for tensor PCA

zbMATH Keywords

tensorsstatistical-computational trade-offs

Mathematics Subject Classification ID

Parametric inference under constraints (62F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Tensor SVD: Statistical and Computational Limits
• Concentration inequalities. A nonasymptotic theory of independence
• The space complexity of approximating the frequency moments
• Lattice-based Cryptography
• Efficient noise-tolerant learning from statistical queries
• In search of non-Gaussian components of a high-dimensional distribution
• Notes on computational-to-statistical gaps: predictions using statistical physics
• On Bayes risk lower bounds
• The landscape of the spiked tensor model
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Algorithmic thresholds for tensor PCA
• Statistical query lower bounds for tensor PCA
• Extractor-based time-space lower bounds for learning
• Sum-of-squares certificates for maxima of random tensors on the sphere
• Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints
• Communication lower bounds for statistical estimation problems via a distributed data processing inequality
• Fast learning requires good memory: a time-space lower bound for parity learning
• Statistical algorithms and a lower bound for detecting planted cliques
• Efficient algorithms and lower bounds for robust linear regression
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• On the complexity of random satisfiability problems with planted solutions
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• Computational barriers to estimation from low-degree polynomials
• Time-space hardness of learning sparse parities
• Non-Gaussian component analysis using entropy methods
• Entropy samplers and strong generic lower bounds for space bounded learning
• Title not available (Why is that?)
• Memory-sample tradeoffs for linear regression with small error
• Continuous LWE

Cited In (1)

• Statistical query lower bounds for tensor PCA

This page was built for publication: Statistical-computational trade-offs in tensor PCA and related problems via communication complexity

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