Research map / Learning theory and algorithms / Sample complexity
Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
Goutham Rajendran, Bohdan Kivva, Ming Gao, Bryon Aragam
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 vertex-greedy GFBS instead of edge-greedy GES | DAG structure learning · Counterexample with equal residual variances (Gaussian BIC) | runs with correct DAG: GES fails all the time; GFBS succeeded in all 100 | Improved |
| use GFBS instead of GES on re-weighted counterexample (0.9 weights) | DAG structure learning · Counterexample X3 = 0.9 X1 + 0.9 X2 + N3 | correct DAG output: GES always wrong in 100 runs; GFBS always correct | Improved |
| use GFBS (Bregman score) versus Gobnilp global optimum with large samples | GFBS · synthetic d=5 graphs (MC, ER, SF; LIN, SIN, AGP, NGP) | score of output DAG | No clear effect |
| use Itakura-Saito score phi=-log x in finite samples | GFBS · IS score, d=5 | score of output DAG | Mixed |
Closest papers by meaning
- DAGs with NO TEARS: Continuous Optimization for Structure Learning (NeurIPS 2018 · similarity 0.90)
- Markov Equivalence and Consistency in Differentiable Structure Learning (NeurIPS 2024 · similarity 0.88)
- Boosting Causal Structure Learning: An Asymmetric Exponential Modulation Gaussian-Based Adaptive Sample Reweighting Framework (AAAI 2025 · similarity 0.88)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.88)
- CoLiDE: Concomitant Linear DAG Estimation (ICLR 2024 · similarity 0.87)
- On the Expressive Power of Tree-Structured Probabilistic Circuits (NeurIPS 2024 · similarity 0.87)
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.
