arXiv preprint ·
FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study fully online fixed-confidence causal discovery without any historical observational data. Starting from zero samples, the learner sequentially selects interventions to recover both the causal DAG and its edge weights under a linear-Gaussian structural equation model. We establish an instance-dependent lower bound for any $(ε,δ)$-correct algorithm and propose \textsc{FOCUS}, which adaptively allocates interventions through an online max--min game. A key contribution is a computable concentration inequality for the accumulated KL divergence involving causal parameters shared across interventions. We prove that \textsc{FOCUS} is $(ε,δ)$-correct and that its expected stopping time matches the lower bound in its $Θ(\log(1/δ))$ dependence up to an instance-dependent constant. Experiments demonstrate improved structure and edge-weight recovery and confirm the predicted stopping-time trend. Our codes are available on https://anonymous.4open.science/r/FOCUS_code-76E5
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning (Statistics)
Emergent One-Third Scaling Law as Attention Tries to Concentrate
Byzantine-Robust Federated RAG via Aligned Calibration and Fixed-Membership Conformal Prediction
How Reusable Are Benchmarks with Richer Feedback?
Plug-and-Play Methods Provably Converge Even with Improperly Trained Denoisers: Convergence by Architectural Design
REALM: Regime-Switching, Explainable, and Activation-Induced Linear Models
Get the few papers worth your time in Machine Learning (Statistics) every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.