mlsanityData to 14 Oct 2026

Estimating Higher-Order Mixed Memberships via the ℓ2,∞ Tensor Perturbation Bound

arXiv 2212.08642 ↗First posted 16 Dec 2022math.ST math.OC stat.MEcited by 8

Not on the map. Why?

Abstract (arXiv)

Higher-order multiway data is ubiquitous in machine learning and statistics and often exhibits community-like structures, where each component (node) along each different mode has a community membership associated with it. In this paper we propose the tensor mixed-membership blockmodel, a generalization of the tensor blockmodel positing that memberships need not be discrete, but instead are convex combinations of latent communities. We establish the identifiability of our model and propose a computationally efficient estimation procedure based on the higher-order orthogonal iteration algorithm (HOOI) for tensor SVD composed with a simplex corner-finding algorithm. We then demonstrate the consistency of our estimation procedure by providing a per-node error bound, which showcases the effect of higher-order structures on estimation accuracy. To prove our consistency result, we develop the ℓ2,∞ tensor perturbation bound for HOOI under independent, heteroskedastic, subgaussian noise that may be of independent interest. Our analysis uses a novel leave-one-out construction for the iterates, and our bounds depend only on spectral properties of the underlying low-rank tensor under nearly optimal signal-to-noise ratio conditions such that tensor SVD is computationally feasible. Finally, we apply our methodology to real and simulated data, demonstrating some effects not identifiable from the model with discrete community memberships.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 22 of its 37 references that are in the map. First posted on arXiv 16 Dec 2022.

Builds on

22 of 37 references.

References · 22

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  2. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 112
  3. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  4. 2017Tensor SVD: Statistical and Computational Limitscited by 53
  5. 2019Optimality of Spectral Clustering in the Gaussian Mixture Modelcited by 42
  6. 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
  7. 2014Layer aggregation and reducibility of multilayer interconnected networkscited by 34
  8. 2018Heteroskedastic PCA: Algorithm, Optimality, and Applicationscited by 34
  9. 2017Near-optimal bounds for phase synchronizationcited by 32
  10. 2020Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decompositioncited by 30
  11. 2020Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limitscited by 30
  12. 2019Community Detection for Hypergraph Networks via Regularized Tensor Power Iterationcited by 27
10 more
  1. 2020Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limitcited by 23
  2. 2017Estimating Mixed Memberships with Sharp Eigenvector Deviationscited by 22
  3. 2017Mixed Membership Estimation for Social Networkscited by 21
  4. 2021Inference for Heteroskedastic PCA with Missing Datacited by 21
  5. 2019Multiway clustering via tensor block modelscited by 17
  6. 2022Leave-one-out Singular Subspace Perturbation Analysis for Spectral Clusteringcited by 15
  7. 2021Entrywise Estimation of Singular Vectors of Low-Rank Matrices with Heteroskedasticity and Dependencecited by 12
  8. 2016Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completioncited by 10
  9. 2020A Sharp Blockwise Tensor Perturbation Bound for Orthogonal Iterationcited by 5
  10. 2020An ℓp theory of PCA and spectral clusteringcited by 4

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 3; 2025: 3.

8 papers.

  1. 2024Valid Conformal Prediction for Dynamic GNNscited by 6
  2. 2023Heteroskedastic Tensor Clusteringcited by 3
  3. 2024On the Robustness of the Successive Projection Algorithmcited by 3
  4. 2023Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Modelcited by 2
  5. 2025Identifiability of Nonnegative Tucker Decompositions -- Part I: Theorycited by 2
  6. 2024Signed Diverse Multiplex Networks: Clustering and Inferencecited by 1
  7. 2025Perfect Clustering in Nonuniform Hypergraphscited by 0
  8. 2025Perfect Clustering in Very Sparse Diverse Multiplex Networkscited by 0