PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian estimation from few samples: community detection and related problems

Samuel B. Hopkins, David Steurer

arXiv:1710.00264v1cs.DScs.CCcs.LGmath.PRstat.ML

TL;DR

The paper asks how to estimate high-dimensional Bayesian parameters efficiently from few samples and whether efficient and inefficient methods require different sample sizes. It develops a low-degree-polynomial meta-algorithm combined with semidefinite programming and robust tensor decomposition, recovering strong stochastic-block-model guarantees and providing evidence for computational thresholds beyond Kesten–Stigum.

  • Problem

    The paper studies efficient parameter estimation from scarce samples and whether Bayesian problems exhibit gaps between efficient and information-theoretic sample complexity.

    Source: §1 · pp. 4–5, §1.4 · p. 19

  • Method

    The meta-algorithm computes low-degree polynomial approximations to posterior moments and uses convex programming, eigenvector methods, or robust tensor decomposition to recover parameters.

    Source: §1 · p. 5, §1.1 · pp. 6, 8

  • Results

    The method recovers best-known stochastic-block-model guarantees, strengthens recovery for richer and overlapping community structures, and yields evidence for computational thresholds beyond Kesten–Stigum.

    Source: §1 · pp. 4–6

  • Takeaways & Limitations

    Low-degree posterior-moment approximations provide a common framework for efficient Bayesian estimation and for studying precise computational sample thresholds.

    Source: §1 · pp. 4–5, §1.4 · p. 22

    The paper prioritizes polynomial-versus-exponential distinctions over near-linear runtime, using self-avoiding-walk polynomials whose evaluation has comparatively large polynomial running time.

    Source: §1.1 · p. 8

Abstract

from arXiv · show

We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constructions for sum-of-squares and related to the method of moments. Our focus is on sample complexity bounds that are as tight as possible (up to additive lower-order terms) and often achieve statistical thresholds or conjectured computational thresholds. Our algorithm recovers the best known bounds for community detection in the sparse stochastic block model, a widely-studied class of estimation problems for community detection in graphs. We obtain the first recovery guarantees for the mixed-membership stochastic block model (Airoldi et el.) in constant average degree graphs---up to what we conjecture to be the computational threshold for this model. We show that our algorithm exhibits a sharp computational threshold for the stochastic block model with multiple communities beyond the Kesten--Stigum bound---giving evidence that this task may require exponential time. The basic strategy of our algorithm is strikingly simple: we compute the best-possible low-degree approximation for the moments of the posterior distribution of the parameters and use a robust tensor decomposition algorithm to recover the parameters from these approximate posterior moments.

1 Introduction

This section develops and applies a low-degree-polynomial, tensor-based framework for Bayesian estimation and community detection, with emphasis on mixed-membership models, efficient recovery, and sharp algorithmic thresholds. It also compares the framework with replica and cavity methods in studying information–computation gaps and open questions about their coinciding predictions.

1.1 Meta-algorithm and meta-theorems for Bayesian estimation

  • The framework recovers the best previous stochastic-block-model bounds [Mas14, MNS15a, AS16a] and gives the first nontrivial mixed-membership recovery algorithm, though its initial guarantees are weak.Low-degree polynomials based on self-avoiding walks yield simpler analyses but incur larger polynomial running times than near-linear non-backtracking methods.Source: §1 · p. 4, §1.1 · pp. 8–9

1 Introduction

  • Unlike prior convex-programming uses for maximum-likelihood relaxations, this work uses sum-of-squares semidefinite programming to drive method-of-moments estimation and entropy-maximizing tensor decomposition.The framework combines ideas from belief propagation, non-backtracking or self-avoiding walks, method of moments, and tensor decomposition [Mas14, MNS15a, AS16a, AGH+14, AGHK14, BKS15].Source: §1 · pp. 4–5
  • When exponential running time is allowed, the meta-algorithm achieves correlation at least δO(1) whenever any estimator achieves correlation δ.For degree D, the resulting circuit has size nO(D), and D up to n captures information-theoretically possible estimation.Source: §1 · p. 5, §1.1 · p. 8
  • Lower bounds show that no captured algorithm recovers k-community block-model communities below the Kesten–Stigum threshold, supporting a computational phase transition there.The meta-algorithm is intended to capture low-sample-complexity Bayesian inference procedures more precisely than generic sum-of-squares lower bounds.Source: §1 · pp. 5–6

1.1 Meta-algorithm and meta-theorems for Bayesian estimation

  • The meta-algorithm estimates posterior moments with optimal low-degree polynomials, then applies spectral, semidefinite-programming, or robust tensor-decomposition methods to recover hidden parameters.Higher moments overcome posterior symmetries: second moments suffice for disjoint communities, while overlapping communities require third moments.Source: §1.1 · p. 7
  • Tensor estimation removes the arbitrary choice of one community by estimating M = Σ_i y_i y_i^T, improving error dependence from kO(1) to the distance δ above threshold.This approach targets all community vectors and is especially important for overlapping community structures.Source: §1 · p. 4, §1.1 · p. 9
  • The meta-algorithm estimates hidden variables from low-degree approximations to posterior moments, using third moments to handle highly symmetric posteriors without worsening error.Its theorem assumes exchangeable orthonormal latent vectors and a degree-D polynomial approximation, yielding an n^O(D)-size circuit and a polynomial-length candidate list.Source: §1.1 · p. 10
  • The tensor decomposition method is robust to weak correlations with multiple orthogonal tensors, producing a list that can recover components from each correlated tensor.An entropy-maximization program provides list-decoding-style guarantees when the input tensor is only δ-correlated with several orthogonal tensors.Source: §1.1 · p. 11

1.2 Detecting overlapping communities

  • The threshold reflects the Dirichlet overlap parameter because probability vectors are concentrated on roughly α + 1 coordinates, and the analysis extends to distributions with the same property.The model interpolates between mixed-membership communities and disjoint communities as α approaches zero.Source: §1.2 · pp. 12–13
  • ε^2d > k^2(α + 1)^2 enables an n^1/poly(δ)-time algorithm to output mixed-membership labels with significant correlation.The achieved correlation depends on the distance δ from threshold and is independent of n and k except through δ; for α = 0, constant correlation holds when ε^2d/k^2 is bounded away from 1 above.Source: §1.2 · p. 14
  • The authors conjecture that below ε^2d < k^2(α + 1)^2 no polynomial-time algorithm achieves correlation bounded away from zero.For disjoint communities, this extends the conjectured Kesten–Stigum computational barrier and implies a computation-information gap for sufficiently large k.Source: §1.2 · pp. 14–15
  • Tensor methods avoid an inherent 1/k correlation loss incurred when prior matrix-based algorithms extract community estimates from a matrix estimator.The paper also contrasts its joint polynomial computations with the method of moments, whose earlier mixed-membership algorithm required denser graphs.Source: §1.1 · p. 12, §1.2 · pp. 15–16
  • For mixed-membership models with W entries 1 − ε and ε, the algorithm’s labeling correlation depends only on δ, allowing k to grow with n without correlation loss when average degree grows accordingly.This improves prior guarantees even in the disjoint-community setting.Source: §1.2 · p. 16

1.3 Low-correlation tensor decomposition

  • Theorem 1.8 gives a randomized polynomial-time tensor decomposition algorithm that outputs vectors correlated with orthonormal components under its stated tensor condition, with guarantees holding in expectation.With an oracle answering fourth-moment queries, it outputs just k orthonormal vectors up to permutation.Source: §1.3 · p. 17
  • The tensor method handles substantially larger error than prior approaches, including error whose Euclidean norm is a constant factor 1/δ larger than the target tensor’s norm.It uses a novel maximum-entropy convex program to avoid overfitting to error tensors; oracle access can be implemented by holdout-set or cross-validation methods in learning applications.Source: §1.3 · pp. 17–18

1.4 Information-computation gaps and concrete lower bounds

  • The algorithm estimates communities in the k-community α-mixed-membership stochastic block model when average degree d ≥ (1 + δ)k^2(α + 1)^2/ε^2 for any constant δ > 0.The stated guarantee targets sample complexity up to low-order additive terms.Source: §1.4 · p. 19
  • The meta-algorithm uses low-degree posterior moments both to characterize efficient estimation and to locate computational thresholds: below a critical sample level, failure of all constant-correlation low-degree estimators rules out algorithms captured by the framework.For the k-community stochastic block model, the work proves an unconditional low-degree lower bound below the Kesten–Stigum threshold, providing evidence of a gap from the information-theoretic threshold; more generally, it proposes examining the low-degree projection’s 2-norm of a relative-density Fourier transform.Source: §1.4 · pp. 20–22
  • Replica and cavity methods apply across many Bayesian estimation problems and predicted sharp stochastic-block-model thresholds, along with analogous phenomena elsewhere.Source: §1.4 · p. 22
  • Rigorous analysis is more difficult for these methods, especially belief propagation, which often yields only a rigorously analyzable modified form called linearized BP.Source: §1.4 · p. 22
  • The authors’ methods use essentially the same low-degree-polynomial algorithm to predict thresholds, design algorithms, and prove lower bounds, motivating comparison with replica and cavity predictions.Source: §1.4 · p. 22
  • Explaining why replica-and-cavity predictions so often match those of the low-degree-polynomial meta-algorithm remains an open problem.Source: §1.4 · p. 22

2 Techniques

This section develops techniques for constructing and analyzing low-degree estimators of hidden moments, including convex projection, tensor decomposition, and efficient polynomial evaluation. It also illustrates these ideas in spiked Wigner matrices through polynomial and self-avoiding-path estimators.

2 Techniques

  • For the basic stochastic block model, path averaging heuristically reaches variance at most 1 above Kesten–Stigum when ℓ⩾log1+δ n.Self-avoiding paths provide the approximate pairwise independence needed to make this heuristic algorithmic.Source: §2 · p. 23

2.1 Approximately pairwise-independent estimators

  • Above the Kesten–Stigum threshold, averaging self-avoiding-walk estimators gives constant-correlation estimates of community-label products for logarithmic path lengths.This avoids the failure of powers of the centered adjacency matrix near the threshold.Source: §2.1 · pp. 23–24

2.2 Low-degree estimators for higher-order moments

  • Self-avoiding long-armed 3-stars estimate overlapping communities’ third-moment tensors with constant correlation precisely up to the Kesten–Stigum bound.Second moments only identify the subspace because of the rotation problem, whereas third moments enable recovery of the component vectors [Har70, LRA93].Source: §2.2 · pp. 24–25

2.3 Correlation-preserving projection

  • Theorem 2.3 projects a correlated approximation into a convex constraint set while preserving correlation and guaranteeing ∥Q∥⩾δ∥Y∥.The construction minimizes norm subject to membership in the convex set and a correlation constraint.Source: §2.3 · p. 25

2.4 Low-correlation tensor decomposition

  • Sum-of-squares pseudo-moments and Jennrich’s algorithm recover vectors from tensors having only tiny correlation with an unknown orthogonal tensor [BKS15, MSS16].The method obtains a short list containing vectors with δO(1) correlation and recovers constant-correlation estimates for a constant fraction of components.Source: §2.4 · p. 26

2.5 From quasi-polynomial time to polynomial time

  • Color coding evaluates colorful-path polynomials in nO(1)·exp(ℓ) time, and averaging over exp(O(ℓ)) random colorings produces a low-variance estimator.This converts logarithmic-degree quasi-polynomial evaluations into polynomial-time computation when ℓ=O(log n).Source: §2.5 · p. 27

2.6 Illustration: push-out effect in spiked Wigner matrices

  • For spiked Wigner matrices, the framework gives efficient estimation as soon as λ>1, providing a simpler but less efficient alternative analysis of the push-out effect [BAP+05].The resulting algorithm has running time nlog n/δO(1) when λ⩾1+δ.Source: §2.6 · p. 28
  • A different polynomial than in establishes the theorem while substantially simplifying the analysis.Source: §2.6 · p. 28
  • The method uses self-avoiding paths whose averaged estimator is unbiased for vivj and approximately pairwise independent.Source: §2.6 · p. 28
  • The algorithm is much slower than the eigenvector-based method, although it follows from the meta-theorem with little innovation.Color coding improves its running time from n^log n/δ^O(1) to n^1/δ^O(1).Source: §2.6 · p. 28

3 Warmup: stochastic block model with two communities

The meta-algorithm recovers the information-theoretic partial-recovery threshold in the two-community stochastic block model using low-degree path estimators and correlation-preserving optimization. The warmup analyzes a quasi-polynomial implementation and explains how color-coding yields polynomial time for constant δ.

3 Warmup: stochastic block model with two communities

  • ε^2d > 1 suffices for partial recovery in the two-community stochastic block model, matching the best previous algorithms and the information-theoretic threshold.Source: §3 · pp. 29, 30, 32
  • The warmup’s algorithm estimates the hidden labeling’s second moment with a self-avoiding-walk polynomial, then uses minimum-Frobenius-norm semidefinite optimization and Gaussian sign rounding.Source: §3 · pp. 30–31
  • The second algorithmic step is the main departure from prior self-avoiding-walk methods, replacing direct spectral recovery with a semidefinite-programming-based rounding procedure.Source: §3 · pp. 30–31
  • The initial self-avoiding-path computation is quasi-polynomial, but color-coding evaluates it in n^O(1)+1/δ^O(1) time, while the convex optimization is polynomial-time.Source: §3 · pp. 30–31

3.1 Low-degree estimate for posterior second moment

  • The self-avoiding-walk matrix has constant correlation with yy^T when ε^2d > 1, providing the input required by the meta-theorem.Source: §3 · p. 31, §3.1 · pp. 33–34
  • Each simple path supplies an unbiased estimator of y_i y_j; averaging logarithmic-length paths reduces variance despite only approximate pairwise independence.Source: §3.1 · p. 32

4 Matrix estimation for generalized block models

The section develops matrix estimation for generalized block models and applies it to mixed-membership graphs. Its spectral estimator yields partial recovery under eigenvalue conditions, while the mixed-membership guarantee depends on both signal strength and the number of communities.

4 Matrix estimation for generalized block models

  • Theorem 4.1 gives an n^poly(1/δ)-time algorithm that outputs a matrix P estimating pairwise similarities from a generalized block-model graph.The model assumes a finite-rank symmetric kernel with stochasticity, niceness, and spectral conditions.Source: §4 · pp. 34–35
  • For the k-community stochastic block model, λ2^2 > 1 matches the Kesten–Stigum condition; when λ2^2 > 1 + δ, thresholding a suitable eigenvector yields the guarantees of Abbe and Sandon.A random vector in the span of the top k/δ^O(1) eigenvectors has correlation (δ/k)^O(1) with some centered community indicator vector vs.Source: §4 · p. 35

4.1 Matrix estimation for the mixed-membership model

  • This preliminary mixed-membership guarantee weakens as k grows because recovery accuracy depends on both the signal-to-noise ratio and the number of communities.The supplied discussion states that the matrix-estimation algorithm no longer solves partial recovery when k is super-constant.Source: §4 · p. 35, §4.1 · p. 35
  • Theorem 4.3 provides constant-degree partial recovery in n^O(1)+1/δ^O(1) time, producing a vector with squared correlation at least (δ/k)^O(1) with a centered membership vector.The guarantee is obtained by combining matrix estimation with spectral rounding.Source: §4.1 · pp. 36–37
  • In the mixed-membership model, the kernel has second eigenvalue ε with multiplicity k−1, so Theorem 4.1 supplies a matrix-estimation route to membership recovery.The construction represents memberships as simplex-valued labels and uses the corresponding centered membership vectors.Source: §4.1 · p. 36

4.2 Proof of Theorem 4.1

  • The proof estimates eigenspace projectors using polynomials over self-avoiding paths of length at least C log n/δ^O(1), evaluated efficiently by color coding.A sufficiently large path length makes the polynomial estimator spectrally close to the target matrix.Source: §4.2 · p. 38

5.1 Main theorem and algorithm

The main algorithm targets mixed-membership recovery by combining low-degree polynomial estimates, tensor lifting and decomposition, cross-validation, sign checks, and cleanup. It operates across large-, small-, and tiny-δ regimes under subpolynomial parameter assumptions.

5.1 Main theorem and algorithm

  • Theorem 5.1 gives an n^O(1)+1/δ^O(1)-time algorithm that outputs probability-vector memberships for the mixed-membership block model under ε^2d > 0 and k, α ≤ n^o(1).The theorem covers the stated parameter regimes, with ε^2d ≤ n^o(1) imposed for technical convenience.Source: §5.1 · p. 40, (Recall the definition of correlation… · p. 41

(Recall the definition of correlation from (1.5).)29

  • The large-, small-, and tiny-δ cases use different procedures, selected according to δ relative to constants and powers of k.The tiny regime applies when δ ≤ 1/k^1/C, whereas the small regime is identified as the main regime of interest for growing k.Source: (Recall the definition of correlation… · p. 41

5.1 Main theorem and algorithm

  • The restriction ε^2d ≤ n^o(1) is technical rather than substantive because recovery becomes easier as ε^2d increases.The same qualification is stated for the main theorem and its matrix-estimation subroutine.Source: (Recall the definition of correlation… · pp. 41–42

Finally let

(Recall the definition of correlation from (1.5).)29

  • The algorithm estimates a degree O(log n/δ^O(1)) third-order tensor polynomial, lifts it to a fourth-order tensor, and applies low-correlation tensor decomposition.Cross-validation on a holdout set tests candidate directions before cleanup.Source: (Recall the definition of correlation… · pp. 41, 43

Finally let

  • In the small-δ regime, the final recovery guarantee achieves expected corr(σ, τ) ≥ δ^O(1).Tensor decomposition recovers correlated directions, sign checking strengthens their correlations, and cleanup converts them into probability vectors.Source: Finally let · pp. 44, 46

5.2 Low-degree estimate for posterior third moment

This section constructs a low-degree polynomial estimator for the posterior third-moment tensor using long three-armed stars. Unbiased star products and approximate conditional independence control the estimator’s mean and variance.

5.2 Low-degree estimate for posterior third moment

  • The method estimates the tensor Σ_s v_s^⊗3, which captures third moments of centered membership vectors and feeds the main tensor-decomposition algorithm.Second-moment estimates are combined with the third-moment estimator to form the polynomial used later.Source: §5.2 · pp. 46, 48
  • A three-armed star consists of three self-avoiding length-ℓ paths joined at one center and ending at distinct vertices i, j, and k.The construction uses centered edge indicators along these paths.Source: §5.2 · p. 47, Figure 1 · p. 47

5.2.1 Details of unbiased estimator

  • Lemma 5.13 shows that each star product is an unbiased estimator of a scaled entry of the membership third-moment tensor.The scaling constant C3 depends on Dirichlet parameters through third moments.Source: §5.2 · p. 47

5.2 Low-degree estimate for posterior third moment

  • For sufficiently long arms, Lemma 5.14 establishes approximate conditional independence of star estimators after conditioning on the terminal memberships.The required arm length is ℓ ≥ C log n/δ^O(1), under the stated growth assumptions on ε^2d, k, and α0.Source: §5.2 · p. 47
  • The resulting tensor-valued polynomial is a good estimator because entries with distinct indices contain nearly all of the tensor’s squared norm.Diagonal and repeated-index entries are set to zero in the constructed estimator.Source: §5.2 · p. 48

5.2.2 Details of approximate conditional independence

  • Star-pair contributions are separated by intersection pattern: pairs sharing only i, j, k overlap only there, path-like intersections are bounded separately, and other patterns share more vertices than edges.Under k, α0 = n^o(1) and ε^2d ≤ n^1−Ω(1), the total contribution is o(c|STARℓ(i, j, k)|^2).Source: §5.2.2 · pp. 49–51

5.3 Cross validation

Cross-validation uses a holdout set of vertices to evaluate candidate community-membership vectors, with concentration bounds establishing moment-estimation guarantees. The proof combines Bernstein’s inequality with variance, tail, and inner-product bounds.

5.3 Cross validation

  • Holdout vertices are used to cross-validate candidate community-membership vectors through standard concentration inequalities.This strategy supports the proof of the estimator guarantees in Lemma 5.8 and related results.Source: §5.3 · p. 51
  • Bernstein’s inequality is applied to independent random variables derived from ⟨G_a, v⊗3⟩ to prove the S3 portion of Lemma 5.8.The S4 portion and Lemma 5.9 are described as analogous, using Dirichlet-moment facts and conversions between v- and w-moment estimators.Source: §5.3 · p. 52
  • The proof applies Proposition 5.22 to n1 random variables and uses Fact 5.20’s variance bound; choosing t = n3/2−γ′ yields n1t2/n3 ≥ nγ under n1 ≥ nΩ(1).Source: §5.3 · p. 52
  • Auxiliary facts bound the relevant quantities using Cauchy–Schwarz and exponential degree tails, completing the technical estimates for Lemma 5.8.These bounds apply uniformly over unit vectors and simplex-valued parameters under the stated growth conditions on k and the constants.Source: §5.3 · pp. 51–53

5.4 Producing probability vectors

This section proves that correlated input vectors can be transformed into probability-vector outputs through matching, projection, and normalization arguments. The resulting polynomial-time algorithm returns probability vectors under event E, with guarantees that preserve nontrivial correlation across both moderate- and large-correlation regimes.

Algorithm guarantee

  • A polynomial-time algorithm takes vectors x1, ..., xk and, when event E holds, returns probability vectors τ1, ..., τn.The theorem assumes δ ⩾ 1/k^(1/C) and α, k ⩽ n^o(1).Source: §5.4 · p. 53

Matching lemmas

  • The matching arguments distinguish moderate δ from δ close to 1, using orthogonality to obtain distinct good matches before extending them to a perfect permutation.Fact 5.24 handles the general regime, while Fact 5.25 supplies the near-one guarantee.Source: §5.4 · pp. 54–55

Large-correlation case

  • When δ is close to 1, a permutation matching gives ⟨x,π·w⟩ ⩾ (1−9ε)∥x∥∥w∥, and Euclidean projection preserves a corresponding 1−O(c) correlation.The proof first matches at least δ^4k vectors and then projects into shifted centered probability-vector matrices.Source: §5.4 · pp. 55–56

Correlation transfer

  • Fact 5.26 transfers correlation from a shifted matrix w to the centered matrix v, enabling Fact 5.23 to convert the result into probability-vector rows.The transfer uses coordinate-wise additive shifts and preserves the relevant inner product.Source: §5.4 · pp. 53, 55

Moderate-correlation case

  • For moderate δ, matching correlated vectors followed by correlation-preserving projection yields a matrix y with ⟨y,w⟩ ⩾ δ^O(1)∥y∥∥w∥ and ∥y∥ ⩾ δ^O(1)∥w∥.The projection maps x into matrices whose rows are shifted probability vectors.Source: §5.4 · p. 55

5.5 Remaining lemmas

The remaining lemmas establish concentration and correlation properties for centered Dirichlet samples and complete the probability-vector construction in separate regimes of δ. The proof uses standard concentration and correlation-preserving projection when δ is bounded away from one, and convexity when δ approaches one.

Dirichlet concentration

  • For centered Dirichlet samples, standard calculations and matrix concentration show that the relevant empirical covariance matrix has eigenvalues 1 ± n^−Ω(1) under k, α ⩽ n^o(1).The centered samples are obtained by subtracting the appropriate mean from Dirichlet vectors.Source: §5.5 · p. 56

Projection regime

  • When δ < 1−Ω(1), the proof combines standard concentration with Theorem 2.3 on correlation-preserving projection to obtain the lemma.The argument uses δ^2/2 ⩾ δ^O(1).Source: §5.5 · p. 56

Near-one regime

  • When δ ⩾ 1−o(1), the centered vectors and their projections remain o(1)-close in norm, so convexity yields the corresponding probability-simplex guarantee.This handles the near-perfect-correlation regime separately from the bounded-away-from-one case.Source: §5.5 · p. 56

6 Lower bounds against low-degree polynomials at the Kesten-Stigum threshold

This section proves low-degree lower bounds for partial community recovery at and below the Kesten–Stigum threshold. It bounds the low-degree Fourier spectrum using graph-structure decompositions and then transfers that bound to estimating whether two vertices share a community.

6 Lower bounds against low-degree polynomials at the Kesten-Stigum threshold

  • The section develops two lower bounds for k-community partial-recovery algorithms based on low-degree polynomials.The results target the Kesten–Stigum threshold regime.Source: §6 · p. 56

6.1 Low-degree Fourier spectrum of the k-community block model

  • Theorem 6.1 analyzes the low-degree Fourier spectrum of the k-community block model, including the regime ε^2d < (1−δ)k^2.The complementary regime ε^2d > (1+δ)k^2 is handled by calculations analogous to Section 5 when ℓ ≫ log(n).Source: §6.1 · pp. 56–57
  • The graph-counting bounds imply that the low-degree spectrum is small in the below-threshold regime, after summing over graph sizes and using the cycle and non-cycle estimates.The proof concludes the required spectral bound by combining these structural contributions.Source: §6.1 · pp. 57, 60
  • Graphs contributing to the Fourier expansion are restricted to structures with minimum degree at least two, then partitioned into unions of cycles and non-cycle components.This decomposition supports separate bounds on cycle contributions and on graphs without cycle components.Source: §6.1 · pp. 57–58
  • Fact 6.3 bounds the probability of label patterns on connected minimum-degree-two graphs by the number of vertices with specified disagreement structure.The bound is at most k^−m, or k^−(t−1) when all t vertices disagree in the specified pattern.Source: §6.1 · p. 58
  • A coding argument bounds the number of relevant graphs by encoding vertex orderings, removed pairs, and nonconsecutive edges, with R ⩽ 2(E−V).The resulting encoding uses at most V log n + 6(E−V) log V bits.Source: §6.1 · pp. 58–60

6.2 Lower bound for estimating communities

  • For estimating whether vertices i and j share a community, any function correlated with the indicator must have degree at least n^c(d,ε,k) when ε^2d < (1−δ)k^2.The result follows by projecting the indicator onto degree-ℓ polynomials and applying Theorem 6.1 to show the projection norm is o(1) below this degree.Source: §6.2 · p. 61
  • The estimating-communities proof expands the centered indicator in the biased Fourier basis and shows that only connected graph structures containing i and j can contribute materially.Graphs with degree-one vertices or without i or j make zero contribution in the relevant expansion.Source: §6.2 · p. 61

7 Tensor decomposition from constant correlation

This section develops and supports a polynomial-time tensor decomposition framework based on sum-of-squares methods, random contractions, and convex-program lifting. It establishes correlation guarantees and extends correlated 3-tensor decompositions to 4-tensors, with analyses covering different correlation regimes and oracle implementations.

7 Tensor decomposition from constant correlation

  • Theorem 7.2 yields, in n^O(1) time, a vector orthogonal to previously recovered directions that correlates with δ^O(1)m target vectors.The algorithm constructs a degree-4 pseudodistribution, contracts it with a Gaussian vector to form a positive-semidefinite matrix, and samples from the span of its top 32/δ^2 eigenvectors.Source: §7 · pp. 62, 64
  • Corollary 7.3 gives a randomized n^poly(1/δ)-time decomposition whose output correlates with at least δ^O(1)m components with high probability.For δ ⩽ 1 −Ω(1), it uses n^1/poly(δ) adaptive oracle queries; the queries can also be made nonadaptively using a polynomial-size lookup table.Source: §7 · p. 62

7.1 Proofs of Lemmas

  • The proof’s first lemma finds a polynomial-time degree-4 pseudodistribution with substantial fourth-moment mass on the target directions, even after enforcing orthogonality constraints.The construction uses a maximum-entropy Sum-of-Squares relaxation and shows that at least a δ-fraction of the target vectors receive nontrivial fourth-moment weight.Source: §7 · pp. 63–64, §7.1 · pp. 66–67
  • The second lemma shows that each relevant contraction matrix is positive semidefinite and has at most 4/δ eigenvalues larger than δ.Thus, a target direction with nontrivial correlation with the pseudodistribution is concentrated in a low-dimensional leading eigenspace.Source: §7 · p. 64, §7.1 · p. 67
  • A Gaussian contraction approximates one of these target contractions with inverse-polynomial probability, while the remaining terms have small spectral norm.The argument expands the Gaussian into a target-direction component and an independent orthogonal component, then controls cross terms using decoupling and spectral concentration ideas related to.Source: §7 · p. 65, §7.1 · p. 67
  • The preceding lemmas are completed using pseudoexpectation Cauchy–Schwarz, together with Lemma 7.10.Source: §7.1 · p. 68

7.2 Lifting 3-tensors to 4-tensors

  • The lifting guarantee is formulated for orthonormal a1, …, am, with input correlation ⟨B,A3⟩ ≥ δ·∥A3∥·∥B∥ and output correlation at least δ^O(1)·∥A4∥·∥B′∥.Source: §7.2 · p. 69
  • A polynomial-time sum-of-squares algorithm solves the 3-to-4 lifting problem, preserving correlation up to a δ^O(1) factor.Given orthonormal components and a tensor B correlated with the third-order tensor A3, it outputs B′ correlated with A4.Source: §7.2 · p. 69
  • The proof optimizes fourth moments over degree-4 pseudodistributions, using the uniform distribution on the orthonormal components as a feasible comparison.For δ < 1 − Ω(1), the program constrains the fourth-moment norm; for δ ≥ 1 − o(1), it projects a normalized B direction into the same convex set.Source: §7.2 · p. 69

A.1 Probability and linear algebra tools

This section assembles probability and linear-algebra tools, including concentration arguments, polynomial approximations, and basic proof techniques.

A.1 Probability and linear algebra tools

  • Fact A.1 develops an inequality for jointly distributed vector-valued random variables under a norm-boundedness assumption.The proof uses indicator variables, Cauchy–Schwarz, and rearrangement of inequalities.Source: §A.1 · pp. 74–75
  • Proposition 5.22 truncates each variable into bounded and tail components before applying Bernstein’s inequality and a union bound.The argument separately controls the truncated contribution and the event on which the variables are approximated.Source: §A.1 · p. 74
  • Fact A.2 relates real-valued random variables to degree-D polynomial approximations on all but an asymptotically negligible subset of coordinates.The vector P(X) is formed by evaluating the coordinatewise polynomials p_i(X), and the proof is based on Cauchy–Schwarz.Source: §A.1 · p. 75

A.2 Tools for symmetric and Dirichlet priors

This section analyzes symmetric and Dirichlet priors using permutation symmetry, matrix decompositions, Johnson-scheme eigenstructure, and explicit Dirichlet moments.

A.2 Tools for symmetric and Dirichlet priors

  • For symmetric random vectors, the relevant moment matrix can be block-diagonalized after exploiting orthogonality to the all-1’s vector.The top block has the form cI_d + c′J, while the bottom block belongs to the Johnson scheme.Source: §A.2 · p. 75
  • Standard Johnson-scheme eigenvector results complete the moment calculation for the lower block and determine constants used later for Dirichlet distributions.The construction begins from M = (X ⊗ X)(X ⊗ X)^⊤ and modifies rows and columns by vectors involving the all-1’s direction.Source: §A.2 · p. 75
  • Fact A.3 introduces the symmetric Dirichlet distribution with parameter α and uses its density to compute moments.The derivation recalls the Dirichlet density and illustrates the calculation for second moments, with the general formula obtained similarly.Source: §A.2 · pp. 75–76
  • The analysis also uses the projector Π onto the subspace orthogonal to the all-1’s vector.This projector isolates the coordinate directions relevant to the symmetric-prior calculations.Source: §A.2 · p. 76

Related papers

Loading 1710.00264v1…