Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity

• URL: http://arxiv.org/abs/2204.07526v2
• Date: Sat, 20 Jan 2024 20:00:12 GMT
• Title: Statistical-Computational Trade-offs in Tensor PCA and Related Problems via Communication Complexity
• Authors: Rishabh Dudeja and Daniel Hsu
• Abstract summary: This paper derives computational lower bounds on the run-time of memory bounded algorithms for PCA using communication complexity. While the lower bounds do not rule out iteration-time algorithms, they do imply that many commonly-used algorithms, such as gradient descent and power method, must have a higher count when the sample size is not large enough.
• Score: 19.939448881052453
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Quasi-Newton Updating for Large-Scale Distributed Learning [0.32228025627337864]
  We develop a distributed quasi-Newton (DQN) framework with excellent statistical, computation, and communication efficiency. No Hessian matrix inversion or communication is needed in the DQN method. We theoretically demonstrate that the resulting estimator is statistically efficient over a small number of iterations under mild conditions.
  arXiv  Detail & Related papers  (2023-06-07T02:33:20Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
  Gaussian processes scale prohibitively with the size of the dataset. Many approximation methods have been developed, which inevitably introduce approximation error. This additional source of uncertainty, due to limited computation, is entirely ignored when using the approximate posterior. We develop a new class of methods that provides consistent estimation of the combined uncertainty arising from both the finite number of data observed and the finite amount of computation expended.
  arXiv  Detail & Related papers  (2022-05-30T22:16:25Z)
• Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
  Independent component analysis (ICA) has been a popular dimension reduction tool in statistical machine learning and signal processing. In this paper, we present a by-product online tensorial algorithm that estimates for each independent component.
  arXiv  Detail & Related papers  (2020-12-28T18:52:37Z)
• Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem [13.808053718325635]
  We consider the problem of recovery a planted $k$-densest sub-hypergraph on $d$-uniform hypergraphs. This fundamental problem appears in different contexts, e.g., community detection, average-case complexity, and neuroscience applications.
  arXiv  Detail & Related papers  (2020-11-23T16:02:12Z)
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
  We study two of the most popular restricted computational models, the statistical query framework and low-degree corollas, in the context of high-dimensional hypothesis testing. Under mild conditions on the testing problem, the two classes of algorithms are essentially equivalent in power. Asries, we obtain new statistical query lower bounds for sparse PCA, tensor PCA and several variants of the planted clique problem.
  arXiv  Detail & Related papers  (2020-09-13T22:55:18Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  We study the power of low-degrees for the task of detecting the presence of hidden structures. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
  arXiv  Detail & Related papers  (2020-08-05T17:52:10Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  We develop a framework that yields statistical accuracy based on interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (instability) when applied to an empirical object based on $n$ samples. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models.
  arXiv  Detail & Related papers  (2020-05-22T22:30:52Z)
• Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits [9.427635404752936]
  We focus on two clustering models, constant high-order clustering (CHC) and rank-one higher-order clustering (ROHC) We identify the boundaries of signal-to-noise ratio for which CHC and ROHC detection/recovery are statistically possible. We propose algorithms that achieve reliable detection and recovery when the signalto-noise ratio is above these thresholds.
  arXiv  Detail & Related papers  (2020-05-21T15:53:44Z)
• An Optimal Statistical and Computational Framework for Generalized Tensor Estimation [10.899518267165666]
  This paper describes a flexible framework for low-rank tensor estimation problems. It includes many important instances from applications in computational imaging, genomics, and network analysis.
  arXiv  Detail & Related papers  (2020-02-26T01:54:35Z)

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.