Research map / Learning theory and algorithms / Sample complexity
Low Degree Hardness for Broadcasting on Trees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that for broadcasting on trees below the Kesten-Stigum bound (d·λ²<1), any polynomial of Efron-Stein degree up to c·ℓ/(1+log R) (or fractal capacity analog) has exponentially vanishing correlation with the root.
Problem
Whether the Kesten-Stigum threshold d λ² = 1 is sharp for low-degree polynomial reconstruction of the root in broadcasting on trees, beyond the special case λ=0 previously established.
Approach
Introduces a fractal-capacity hierarchy of leaf subsets built by branch decomposition, and proves by induction on this hierarchy that the conditional variance of such functions given the root decays exponentially with depth when d λ² < 1, handling the non-product (Markov-dependent) structure of the leaves.
Key results
- For dλ²<1, any function of leaves with Efron-Stein degree ≤ c·ℓ/(1+log R) satisfies Var(E[f|X_ρ]) ≤ (max{dλ², λ})^{ℓ/4} Var(f).
- Correlation with the root decays as (max{dλ², λ})^{ℓ/8} for such low-degree polynomials.
- Result extends the λ=0 result of Kohler-Mossel to general Markov chains below the Kesten-Stigum bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict the estimator to Efron-Stein degree ≤ cℓ/(1+log(R)) | Root inference in broadcasting on trees · Broadcasting on trees, dλ² < 1 | root correlation: Corr(f(XL), g(Xρ)) ≤ (max{dλ2, λ})ℓ/8 | Hurt |
| Restrict the function to fractal capacity ≤ cℓ/(1+log(R)) | Root inference in broadcasting on trees · Broadcasting on trees, dλ² < 1 | conditional variance ratio: Var(E[f(XL) | Xρ]) ≤ (max{dλ2, λ})ℓ/4Var(f(XL)) | Hurt |
Limitations
- Degree bound is c·ℓ/(1+log R), which depends on the tree's growth factor R and only applies to degree up to order ℓ.
- Technical difficulty when some entries of the transition matrix are zero; full general case relies on deferred proofs.
Experimental setup
Metrics: variance of conditional expectation correlation with root
Builds on: Kesten-Stigum bound Kohler and Mossel low-degree broadcasting result Moitra Mossel Sandon chain construction Efron-Stein decomposition
Closest papers by meaning
- Sample Complexity of Branch-length Estimation by Maximum Likelihood (ICML 2025 · similarity 0.85)
- On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.83)
- Replicability in Learning: Geometric Partitions and KKM-Sperner Lemma (NeurIPS 2024 · similarity 0.82)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.82)
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.82)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.