On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery

• URL: http://arxiv.org/abs/2310.13553v1
• Date: Fri, 20 Oct 2023 14:52:25 GMT
• Title: On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery
• Authors: Fateme Jamshidi, Luca Ganassali, Negar Kiyavash
• Abstract summary: 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.
• Score: 21.12645737093305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by conditional independence testing, an essential step in constraint-based causal discovery algorithms, we study the nonparametric Von Mises estimator for the entropy of multivariate distributions built on a kernel density estimator. We establish an exponential concentration inequality for this estimator. We design a test for conditional independence (CI) based on our estimator, called VM-CI, which achieves optimal parametric rates under smoothness assumptions. Leveraging the exponential concentration, we prove a tight upper bound for the overall error of VM-CI. This, in turn, allows us to characterize the sample complexity of any constraint-based causal discovery algorithm that uses VM-CI for CI tests. To the best of our knowledge, this is the first sample complexity guarantee for causal discovery for continuous variables. Furthermore, we empirically show that VM-CI outperforms other popular CI tests in terms of either time or sample complexity (or both), which translates to a better performance in structure learning as well.

Related papers

• Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding [21.842487278479403]
  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. Our closeness test attains optimal parametric rates under smoothness assumptions.
  arXiv  Detail & Related papers  (2025-03-10T15:49:58Z)
• 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)
• Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests [5.3595271893779906]
  Federated learning has attracted significant recent attention due to its applicability across a wide range of settings where data is collected and analyzed across disparate locations. We study federated nonparametric goodness-of-fit testing in the white-noise-with-drift model under distributed differential privacy (DP) constraints.
  arXiv  Detail & Related papers  (2024-06-10T19:25:19Z)
• Approximate Global Convergence of Independent Learning in Multi-Agent Systems [19.958920582022664]
  We study two representative algorithms, independent $Q$-learning and independent natural actor-critic, within value-based and policy-based frameworks. The results imply a sample complexity of $tildemathcalO(epsilon-2)$ up to an error term that characterizes the fundamental limit of IL in achieving global convergence.
  arXiv  Detail & Related papers  (2024-05-30T08:20:34Z)
• Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning [20.491176017183044]
  This paper tackles the multi-objective reinforcement learning (MORL) problem. It introduces an innovative actor-critic algorithm named MOAC which finds a policy by iteratively making trade-offs among conflicting reward signals.
  arXiv  Detail & Related papers  (2024-05-05T23:52:57Z)
• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity. An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
  arXiv  Detail & Related papers  (2023-11-01T04:41:16Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Non-Stochastic CDF Estimation Using Threshold Queries [3.6576781735746513]
  We tackle the problem of estimating an empirical distribution in a setting with two challenges. First, the algorithm does not directly observe the data; instead, it only asks a limited number of threshold queries about each sample. Second, the data are not assumed to be independent and identically distributed; instead, we allow for an arbitrary process generating the samples.
  arXiv  Detail & Related papers  (2023-01-13T18:00:57Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities [8.010966370223985]
  We show that the sample complexity of simple binary hypothesis testing under communication constraints is at most a logarithmic factor larger than in the unconstrained setting. Our framework extends to robust hypothesis testing, where the distributions are corrupted in the total variation distance.
  arXiv  Detail & Related papers  (2022-06-06T17:42:11Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

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.