Research map / Learning theory and algorithms / Sample complexity
SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SGA instead of the IS_NON_STAR procedure | partial recovery of Ising tree structures · 12-node chain, noiseless, ρ=0.8 | error probability | Helped |
| Use SGA instead of Chow-Liu | partial recovery of Ising tree structures · 12-node chain, noiseless, ρ=0.8 | error probability | Hurt |
| Use SGA instead of the IS_NON_STAR procedure | partial recovery of Ising tree structures · 12-node chain, noisy, ρ=0.8, alternate nodes noisy with q_max=0.2 | error probability | Helped |
| Use Chow-Liu on non-identically noisy observations | partial recovery of Ising tree structures · 12-node chain, noisy, ρ=0.8, alternate nodes noisy with q_max=0.2 | error probability: roughly equal to~$1$ | Hurt |
| Use SGA instead of the IS_NON_STAR procedure | partial recovery of Ising tree structures · 12-node hybrid tree, noiseless and noisy, ρ=0.8 and ρ=0.6 | error probability | Helped |
| Use Chow-Liu on non-identically noisy observations | partial recovery of Ising tree structures · 12-node hybrid tree, noisy, ρ=0.8, even nodes noisy with q_max=0.2 | error probability: ≈ 1 | Hurt |
| Use SGA instead of the IS_NON_STAR procedure | partial recovery of Ising tree structures · 12-node star, noiseless and noisy, ρ=0.6 | error probability | Helped |
| Use SGA instead of the IS_NON_STAR procedure | 4-node homogeneous Markov chain · noiseless, ρ < 0.6 | error exponent | Helped |
| Use SGA instead of the IS_NON_STAR procedure | 4-node homogeneous Markov chain · noiseless, ρ > 0.71 | error exponent | Hurt |
| Use SGA instead of the IS_NON_STAR procedure | 4-node homogeneous Markov chain · ρ=0.74, noise near q_max=0 | error exponent | Hurt |
| Use SGA instead of the IS_NON_STAR procedure | 4-node homogeneous Markov chain · ρ=0.74, relatively higher q_max | error exponent | Helped |
| Use SGA instead of the IS_NON_STAR procedure | 4-node homogeneous star · noiseless, all ρ | error exponent | Helped |
Closest papers by meaning
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.88)
- Learning Gaussian DAG Models without Condition Number Bounds (ICML 2025 · similarity 0.86)
- TreeVI: Reparameterizable Tree-structured Variational Inference for Instance-level Correlation Capturing (NeurIPS 2024 · similarity 0.86)
- Sample Complexity of Branch-length Estimation by Maximum Likelihood (ICML 2025 · similarity 0.85)
- Is Noise Conditioning Necessary? A Unified Theory of Unconditional Graph Diffusion Models (NeurIPS 2025 · similarity 0.84)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.84)
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.