Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations

• URL: http://arxiv.org/abs/2111.04681v2
• Date: Sat, 11 Jan 2025 00:06:43 GMT
• Title: Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• Authors: Chanwoo Lee, Miaoyan Wang,
• Abstract summary: We develop a family of smooth tensor models up to arbitrary index permutations. We show that a constrained least-squares estimator in the block-wise family achieves the minimax error bound. We also provide an efficient-time Borda count algorithm that achieves provably optimal rate.
• Score: 12.983290324156114
• License:
• Abstract: We consider the problem of structured tensor denoising in the presence of unknown permutations. Such data problems arise commonly in recommendation system, neuroimaging, community detection, and multiway comparison applications. Here, we develop a general family of smooth tensor models up to arbitrary index permutations; the model incorporates the popular tensor block models and Lipschitz hypergraphon models as special cases. We show that a constrained least-squares estimator in the block-wise polynomial family achieves the minimax error bound. A phase transition phenomenon is revealed with respect to the smoothness threshold needed for optimal recovery. In particular, we find that a polynomial of degree up to $(m-2)(m+1)/2$ is sufficient for accurate recovery of order-$m$ tensors, whereas higher degree exhibits no further benefits. This phenomenon reveals the intrinsic distinction for smooth tensor estimation problems with and without unknown permutations. Furthermore, we provide an efficient polynomial-time Borda count algorithm that provably achieves optimal rate under monotonicity assumptions. The efficacy of our procedure is demonstrated through both simulations and Chicago crime data analysis.

Related papers

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
  We develop novel modifications of nearest-neighbor and matching estimators which converge at the parametric $sqrt n $-rate. We stress that our estimators do not involve nonparametric function estimators and in particular do not rely on sample-size dependent parameters smoothing.
  arXiv  Detail & Related papers  (2024-07-11T13:28:34Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• TERM Model: Tensor Ring Mixture Model for Density Estimation [48.622060998018206]
  In this paper, we take tensor ring decomposition for density estimator, which significantly reduces the number of permutation candidates. A mixture model that incorporates multiple permutation candidates with adaptive weights is further designed, resulting in increased expressive flexibility. This approach acknowledges that suboptimal permutations can offer distinctive information besides that of optimal permutations.
  arXiv  Detail & Related papers  (2023-12-13T11:39:56Z)
• Estimating Higher-Order Mixed Memberships via the $\ell_{2,\infty}$ Tensor Perturbation Bound [8.521132000449766]
  We propose the tensor mixed-membership blockmodel, a generalization of the tensor blockmodel. We establish the identifiability of our model and propose a computationally efficient estimation procedure. We apply our methodology to real and simulated data, demonstrating some effects not identifiable from the model with discrete community memberships.
  arXiv  Detail & Related papers  (2022-12-16T18:32:20Z)
• Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications [26.602371644194143]
  We show that this fundamental tensor problem is NP-hard for any tensor rank higher than one. For low-enough ranks, the proposed continuous reformulation is amenable to low-complexity gradient-based optimization. We demonstrate promising results on a number of hard problems, including low density parity check codes and general decoding parity check codes.
  arXiv  Detail & Related papers  (2022-10-16T11:53:42Z)
• Convergence bounds for nonlinear least squares and applications to tensor recovery [0.0]
  We consider the problem of approximating a function in general nonlinear subsets of $L2$ when only a weighted Monte Carlo estimate of the $L2$-norm can be computed. A critical analysis of our results allows us to derive a sample efficient algorithm for the model set of low-rank tensors.
  arXiv  Detail & Related papers  (2021-08-11T14:14:02Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements [30.395874385570007]
  A fundamental task is to faithfully recover tensors from highly incomplete measurements. We develop an algorithm to directly recover the tensor factors in the Tucker decomposition. We show that it provably converges at a linear independent rate of the ground truth tensor for two canonical problems.
  arXiv  Detail & Related papers  (2021-04-29T17:44:49Z)
• Enhanced nonconvex low-rank approximation of tensor multi-modes for tensor completion [1.3406858660972554]
  We propose a novel low-rank approximation tensor multi-modes (LRATM) A block-bound method-based algorithm is designed to efficiently solve the proposed model. Numerical results on three types of public multi-dimensional datasets have tested and shown that our algorithm can recover a variety of low-rank tensors.
  arXiv  Detail & Related papers  (2020-05-28T08:53:54Z)
• 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)

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.