A polynomial-time algorithm for learning nonparametric causal graphs

• URL: http://arxiv.org/abs/2006.11970v2
• Date: Tue, 10 Nov 2020 21:35:55 GMT
• Title: A polynomial-time algorithm for learning nonparametric causal graphs
• Authors: Ming Gao, Yi Ding, Bryon Aragam
• Abstract summary: The analysis is model-free and does not assume linearity, additivity, independent noise, or faithfulness. We impose a condition on the residual variances that is closely related to previous work on linear models with equal variances.
• Score: 18.739085486953698
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We establish finite-sample guarantees for a polynomial-time algorithm for learning a nonlinear, nonparametric directed acyclic graphical (DAG) model from data. The analysis is model-free and does not assume linearity, additivity, independent noise, or faithfulness. Instead, we impose a condition on the residual variances that is closely related to previous work on linear models with equal variances. Compared to an optimal algorithm with oracle knowledge of the variable ordering, the additional cost of the algorithm is linear in the dimension $d$ and the number of samples $n$. Finally, we compare the proposed algorithm to existing approaches in a simulation study.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data [17.657917523817243]
  We develop and analyze algorithms for instrumental variable regression by viewing the problem as a conditional optimization problem. In the context of least-squares instrumental variable regression, our algorithms neither require matrix inversions nor mini-batches. We derive rates of convergence in expectation, that are of order $mathcalO(log T/T)$ and $mathcalO (1/T1-iota)$ for any $iota>0$.
  arXiv  Detail & Related papers  (2024-05-29T19:21:55Z)
• Efficient Interpretable Nonlinear Modeling for Multiple Time Series [5.448070998907116]
  This paper proposes an efficient nonlinear modeling approach for multiple time series. It incorporates nonlinear interactions among different time-series variables. Experimental results show that the proposed algorithm improves the identification of the support of the VAR coefficients in a parsimonious manner.
  arXiv  Detail & Related papers  (2023-09-29T11:42:59Z)
• The Power of Learned Locally Linear Models for Nonlinear Policy Optimization [26.45568696453259]
  This paper conducts a rigorous analysis of a simplified variant of this strategy for general nonlinear systems. We analyze an algorithm which iterates between estimating local linear models of nonlinear system dynamics and performing $mathttiLQR$-like policy updates.
  arXiv  Detail & Related papers  (2023-05-16T17:13:00Z)
• Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
  We propose an online learning algorithm for a class of machine learning models under a separable approximation framework. We show that the proposed algorithm produces more robust and test performance when compared to other popular learning algorithms.
  arXiv  Detail & Related papers  (2023-05-12T13:53:03Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  parameter-free algorithms are online learning algorithms that do not require setting learning rates. We propose new parameter-free algorithms that can take advantage of truncated linear models through a new update that has an "implicit" flavor. Based on a novel decomposition of the regret, the new update is efficient, requires only one gradient at each step, never overshoots the minimum of the truncated model, and retains the favorable parameter-free properties.
  arXiv  Detail & Related papers  (2022-03-19T13:39:49Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  Two timescale approximation (SA) has been widely used in value-based reinforcement learning algorithms. We study the non-asymptotic convergence rate of two timescale linear and nonlinear TDC and Greedy-GQ algorithms.
  arXiv  Detail & Related papers  (2020-11-10T11:36:30Z)
• Adaptive Online Estimation of Piecewise Polynomial Trends [23.91519151164528]
  We consider the framework of non-stationary optimization with squared error losses and noisy gradient feedback. Motivated from the theory of non-parametric regression, we introduce a new variational constraint. We show that the same policy is minimax optimal for several other non-parametric families of interest.
  arXiv  Detail & Related papers  (2020-09-30T19:30:28Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)
• Multiscale Non-stationary Stochastic Bandits [83.48992319018147]
  We propose a novel multiscale changepoint detection method for the non-stationary linear bandit problems, called Multiscale-LinUCB. Experimental results show that our proposed Multiscale-LinUCB algorithm outperforms other state-of-the-art algorithms in non-stationary contextual environments.
  arXiv  Detail & Related papers  (2020-02-13T00:24:17Z)
• WICA: nonlinear weighted ICA [72.02008296553318]
  Independent Component Analysis (ICA) aims to find a coordinate system in which the components of the data are independent. We construct a new nonlinear ICA model, called WICA, which obtains better and more stable results than other algorithms.
  arXiv  Detail & Related papers  (2020-01-13T10:38:03Z)

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.