























Abstract:We establish a fundamental connection between optimal structure learning and optimal conditional independence testing by showing that the minimax optimal rate for structure learning problems is determined by the minimax rate for conditional independence testing in these problems. This is accomplished by establishing a general reduction between these two problems in the case of poly-forests, and demonstrated by deriving optimal rates for several examples, including Bernoulli, Gaussian and nonparametric models. Furthermore, we show that the optimal algorithm in these settings is a suitable modification of the PC algorithm. This theoretical finding provides a unified framework for analyzing the statistical complexity of structure learning through the lens of minimax testing.
From: Ming Gao [view email]
[v1]
Tue, 8 Jul 2025 05:39:59 UTC (68 KB)
[v2]
Fri, 3 Oct 2025 02:52:15 UTC (69 KB)
[v3]
Sat, 13 Jun 2026 02:15:52 UTC (75 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。