AI Paper Atlas

Research map / Learning theory and algorithms / Sample complexity

The Fisher Dimension: Instance-Dependent Complexity for Causal Discovery

Luong Doan, Khanh Nguyen Quoc, Duc Hai Nguyen, Mai Phan Quoc Hung, Phong Ho, Nhung Duong, Tuan Do

ICML 2026 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of learning distributions

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 changedWhereMeasuredEffect
use Fisher dimension predictor instead of structural proxies for tree graphsFisher dimension · Tree graphs (d=10)Spearman correlation with n*: 0.88Improved
use Fisher dimension predictor instead of structural proxies for chain graphsFisher dimension · Chain graphs (d=10)Spearman correlation with n*: 0.93Improved
use average Markov blanket size instead of Fisher dimensionFisher dimension · Erdos-Renyi graphs (d=10)Spearman correlation with n*: 0.37 -> 0.58Hurt
move from structured families (tree, chain) to Erdos-Renyi graphsFisher dimension predictor · d=10 graphsSpearman rho: 0.91 -> 0.66Hurt
move from chain to Erdos-Renyi graphsFisher dimension predictor · d=10 graphsPearson r: 0.92 -> 0.55Hurt
Erdos-Renyi low-F cell versus medium-F cellFisher dimension prediction · Erdos-Renyi graphsfraction within factor 2: 55% -> 80%Mixed
increase graph size d from 5 to 20PC algorithm · Chain graphsempirical sample complexity n*: 1,267 -> 4,367Hurt
increase graph size d from 5 to 20PC algorithm · Erdos-Renyi graphsempirical sample complexity n*: 863 -> 10,000Hurt
increase graph size d from 5 to 20PC algorithm · Tree graphsempirical sample complexity n*: 1,383 -> 7,800Hurt
overall agreement of prediction across all cellsFisher dimension prediction · all graph familiesfraction within factor 2: 85%Improved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy