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

• 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.