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

DOI10.1214/23-aos2331arXiv2204.07526OpenAlexW4392591378MaRDI QIDQ6151966

Daniel Hsu, Rishabh Dudeja

Publication date: 11 March 2024

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

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

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic thresholds for tensor PCA
• The space complexity of approximating the frequency moments
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Computational barriers to estimation from low-degree polynomials
• On Bayes Risk Lower Bounds
• Efficient noise-tolerant learning from statistical queries
• Lattice-based Cryptography
• Tensor SVD: Statistical and Computational Limits
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Fast Learning Requires Good Memory
• Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
• Time-space hardness of learning sparse parities
• Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints
• HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
• The Landscape of the Spiked Tensor Model
• Non-Gaussian component analysis using entropy methods
• Memory-sample tradeoffs for linear regression with small error
• Extractor-based time-space lower bounds for learning
• Efficient Algorithms and Lower Bounds for Robust Linear Regression
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Communication lower bounds for statistical estimation problems via a distributed data processing inequality
• Continuous LWE

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