Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures

• URL: http://arxiv.org/abs/2201.09040v1
• Date: Sat, 22 Jan 2022 12:43:25 GMT
• Title: Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures
• Authors: Zhongyuan Lyu and Dong Xia
• Abstract summary: We propose a low-rank Gaussian mixture model (LrMM) assuming each matrix-valued observation has a planted low-rank structure. We prove the minimax optimality of a maximum likelihood estimator which, in general, is computationally infeasible. Our results reveal multiple phase transitions in the minimax error rates and the statistical-to-computational gap.
• Score: 12.868722327487752
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Structural matrix-variate observations routinely arise in diverse fields such as multi-layer network analysis and brain image clustering. While data of this type have been extensively investigated with fruitful outcomes being delivered, the fundamental questions like its statistical optimality and computational limit are largely under-explored. In this paper, we propose a low-rank Gaussian mixture model (LrMM) assuming each matrix-valued observation has a planted low-rank structure. Minimax lower bounds for estimating the underlying low-rank matrix are established allowing a whole range of sample sizes and signal strength. Under a minimal condition on signal strength, referred to as the information-theoretical limit or statistical limit, we prove the minimax optimality of a maximum likelihood estimator which, in general, is computationally infeasible. If the signal is stronger than a certain threshold, called the computational limit, we design a computationally fast estimator based on spectral aggregation and demonstrate its minimax optimality. Moreover, when the signal strength is smaller than the computational limit, we provide evidences based on the low-degree likelihood ratio framework to claim that no polynomial-time algorithm can consistently recover the underlying low-rank matrix. Our results reveal multiple phase transitions in the minimax error rates and the statistical-to-computational gap. Numerical experiments confirm our theoretical findings. We further showcase the merit of our spectral aggregation method on the worldwide food trading dataset.

Related papers

• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Quantized Low-Rank Multivariate Regression with Random Dithering [23.81618208119832]
  Low-rank multivariate regression (LRMR) is an important statistical learning model. We focus on the estimation of the underlying coefficient matrix. We employ uniform quantization with random dithering, i.e., we add appropriate random noise to the data before quantization. We propose the constrained Lasso and regularized Lasso estimators, and derive the non-asymptotic error bounds.
  arXiv  Detail & Related papers  (2023-02-22T08:14:24Z)
• Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model [12.868722327487752]
  We propose a low-rank mixture model (LrMM) to treat matrix-valued observations. A computationally efficient clustering method is designed by integrating Lloyd's algorithm and low-rank approximation. Our method outperforms others in the literature on real-world datasets.
  arXiv  Detail & Related papers  (2022-07-11T03:16:10Z)
• Gaining Outlier Resistance with Progressive Quantiles: Fast Algorithms and Theoretical Studies [1.6457778420360534]
  A framework of outlier-resistant estimation is introduced to robustify arbitrarily loss function. A new technique is proposed to alleviate the requirement on starting point such that on regular datasets the number of data reestimations can be substantially reduced. The obtained estimators, though not necessarily globally or even globally, enjoymax optimality in both low dimensions.
  arXiv  Detail & Related papers  (2021-12-15T20:35:21Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Entropy Minimizing Matrix Factorization [102.26446204624885]
  Nonnegative Matrix Factorization (NMF) is a widely-used data analysis technique, and has yielded impressive results in many real-world tasks. In this study, an Entropy Minimizing Matrix Factorization framework (EMMF) is developed to tackle the above problem. Considering that the outliers are usually much less than the normal samples, a new entropy loss function is established for matrix factorization.
  arXiv  Detail & Related papers  (2021-03-24T21:08:43Z)
• Over-the-Air Statistical Estimation [4.082216579462796]
  We study schemes and lower bounds for distributed minimax statistical estimation over a Gaussian multiple-access channel (MAC) under squared error loss. We show that estimation schemes that leverage the physical layer offer a drastic reduction in estimation error over digital schemes relying on a physical-layer abstraction.
  arXiv  Detail & Related papers  (2021-03-06T03:07:22Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation [35.035853993422506]
  We analyze the approximate message passing algorithm in a sparse regime. We find all-or-nothing phase transitions for the minimum and mean-square errors. In the sparse regime the statistical-to-algorithmic gap diverges indicating that sparse recovery is hard for approximate message passing.
  arXiv  Detail & Related papers  (2020-06-14T18:38:34Z)
• 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)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)

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.