Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding

• URL: http://arxiv.org/abs/2503.07475v1
• Date: Mon, 10 Mar 2025 15:49:58 GMT
• Title: Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding
• Authors: Fateme Jamshidi, Sina Akbari, Negar Kiyavash,
• Abstract summary: We analyze the sample complexity of distinguishing whether two multidimensional continuous distributions are identical or differ by at least $epsilon$ in terms of Kullback-Leibler divergence under non-parametric assumptions.<n>Our closeness test attains optimal parametric rates under smoothness assumptions.
• Score: 21.842487278479403
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of closeness testing for continuous distributions and its implications for causal discovery. Specifically, we analyze the sample complexity of distinguishing whether two multidimensional continuous distributions are identical or differ by at least $\epsilon$ in terms of Kullback-Leibler (KL) divergence under non-parametric assumptions. To this end, we propose an estimator of KL divergence which is based on the von Mises expansion. Our closeness test attains optimal parametric rates under smoothness assumptions. Equipped with this test, which serves as a building block of our causal discovery algorithm to identify the causal structure between two multidimensional random variables, we establish sample complexity guarantees for our causal discovery method. To the best of our knowledge, this work is the first work that provides sample complexity guarantees for distinguishing cause and effect in multidimensional non-linear models with non-Gaussian continuous variables in the presence of unobserved confounding.

Related papers

• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Detecting Unobserved Confounders: A Kernelized Regression Approach [46.52607207396279]
  Kernel Regression Confounder Detection (KRCD) is a novel method for detecting unobserved confounding in nonlinear observational data under single-environment conditions.<n>Test statistic whose significant deviation from zero indicates unobserved confounding.<n>Experiments on synthetic benchmarks and the Twins dataset demonstrate that KRCD not only outperforms existing baselines but also achieves superior computational efficiency.
  arXiv  Detail & Related papers  (2026-01-01T04:26:02Z)
• Identification of Causal Direction under an Arbitrary Number of Latent Confounders [54.76982125821112]
  In real-world scenarios, observed variables may be affected by multiple latent variables simultaneously.<n>We make use of the joint higher-order cumulant matrix of the observed variables constructed in a specific way.<n>We show that, surprisingly, causal asymmetry between two observed variables can be directly seen from the rank deficiency properties of such higher-order cumulant matrices.
  arXiv  Detail & Related papers  (2025-10-26T15:10:00Z)
• Assessing One-Dimensional Cluster Stability by Extreme-Point Trimming [0.0]
  We develop a probabilistic method for assessing the tail behavior and geometric stability of one-dimensional i.i.d. samples.<n>We derive analytical expressions, including finite-sample corrections, for the expected shrinkage under both the uniform and Gaussian hypotheses.<n>We further integrate our criterion into a clustering pipeline (e.g. DBSCAN), demonstrating its ability to validate one-dimensional clusters without any density estimation or parameter tuning.
  arXiv  Detail & Related papers  (2025-08-29T21:52:15Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies [7.70133333709347]
  We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output.
  arXiv  Detail & Related papers  (2024-05-02T16:15:46Z)
• On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery [21.12645737093305]
  conditional independence testing is an essential step in constraint-based causal discovery algorithms. We design a test for conditional independence based on our estimator, called VM-CI, which achieves optimal parametric rates. We empirically show that VM-CI outperforms other popular CI tests in terms of either time or sample complexity.
  arXiv  Detail & Related papers  (2023-10-20T14:52:25Z)
• Learning Linear Causal Representations from Interventions under General Nonlinear Mixing [52.66151568785088]
  We prove strong identifiability results given unknown single-node interventions without access to the intervention targets. This is the first instance of causal identifiability from non-paired interventions for deep neural network embeddings.
  arXiv  Detail & Related papers  (2023-06-04T02:32:12Z)
• Bootstrapped Edge Count Tests for Nonparametric Two-Sample Inference Under Heterogeneity [5.8010446129208155]
  We develop a new nonparametric testing procedure that accurately detects differences between the two samples. A comprehensive simulation study and an application to detecting user behaviors in online games demonstrates the excellent non-asymptotic performance of the proposed test.
  arXiv  Detail & Related papers  (2023-04-26T22:25:44Z)
• Targeted Separation and Convergence with Kernel Discrepancies [61.973643031360254]
  kernel-based discrepancy measures are required to (i) separate a target P from other probability measures or (ii) control weak convergence to P. In this article we derive new sufficient and necessary conditions to ensure (i) and (ii) For MMDs on separable metric spaces, we characterize those kernels that separate Bochner embeddable measures and introduce simple conditions for separating all measures with unbounded kernels.
  arXiv  Detail & Related papers  (2022-09-26T16:41:16Z)
• On the Sample Complexity of Causal Discovery and the Value of Domain Expertise [0.0]
  Causal discovery methods seek to identify causal relations between random variables from purely observational data. In this paper, we analyze the sample complexity of causal discovery algorithms without a CI oracle. Our methods allow us to quantify the value of domain expertise in terms of data samples.
  arXiv  Detail & Related papers  (2021-02-05T16:26:17Z)
• The Hidden Uncertainty in a Neural Networks Activations [105.4223982696279]
  The distribution of a neural network's latent representations has been successfully used to detect out-of-distribution (OOD) data. This work investigates whether this distribution correlates with a model's epistemic uncertainty, thus indicating its ability to generalise to novel inputs.
  arXiv  Detail & Related papers  (2020-12-05T17:30:35Z)
• Analysis of Discriminator in RKHS Function Space for Kullback-Leibler Divergence Estimation [5.146375037973682]
  We study a generative adversarial network based approach that uses a neural network discriminator to estimate Kullback Leibler (KL) divergence. We argue that high fluctuations in the estimates are a consequence of not controlling the complexity of the discriminator function space.
  arXiv  Detail & Related papers  (2020-02-25T21:44:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.