Negar Kiyavash

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Negar Kiyavash, Ehsan Mokhtarian, Saber Salehkaleybar

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skeleton of causal graphs with cycles may not be possible from merely the observational distribution. Furthermore, intervening on a variable in such graphs does not necessarily lead to orienting all the edges incident to it. In this paper, we propose an experiment design approach that can learn both cyclic and acyclic graphs and hence, unifies the task of experiment design for both types of graphs. We provide a lower bound on the number of experiments required to guarantee the unique identification of the causal graph in the worst case, showing that the proposed approach is order-optimal in terms of the number of experiments up to an additive logarithmic term. Moreover, we extend our result to the setting where the size of each experiment is bounded by a constant. For this case, we show that our approach is optimal in terms of the size of the largest experiment required for uniquely identifying the causal graph in the worst case.

2022

A Wasserstein-based measure of conditional dependence

Seyed Jalal Etesami, Negar Kiyavash, Kun Zhang

Measuring conditional dependencies among the variables of a network is of great interest to many disciplines. This paper studies some shortcomings of the existing dependency measures in detecting direct causal influences or their lack of ability for group selection to capture strong dependencies and accordingly introduces a new statistical dependency measure to overcome them. This measure is inspired by Dobrushin’s coefficients and based on the fact that there is no dependency between X and Y given another variable Z, if and only if the conditional distribution of Y given 𝑋=𝑥 and 𝑍=𝑧 does not change when X takes another realization 𝑥′ while Z takes the same realization z. We show the advantages of this measure over the related measures in the literature. Moreover, we establish the connection between our measure and the integral probability metric (IPM) that helps to develop estimators of the measure with lower complexity compared to other relevant information theoretic-based measures. Finally, we show the performance of this measure through numerical simulations.

2022

Causal Discovery in Probabilistic Networks with an Identifiable Causal Effect

Sina Akbari, Seyed Jalal Etesami, Fateme Jamshidi, Negar Kiyavash, Ehsan Mokhtarian

Causal identification is at the core of the causal inference literature, where complete algorithms have been proposed to identify causal queries of interest. The validity of these algorithms hinges on the restrictive assumption of having access to a correctly specified causal structure. In this work, we study the setting where a probabilistic model of the causal structure is available. Specifically, the edges in a causal graph are assigned probabilities which may, for example, represent degree of belief from domain experts. Alternatively, the uncertainly about an edge may reflect the confidence of a particular statistical test. The question that naturally arises in this setting is: Given such a probabilistic graph and a specific causal effect of interest, what is the subgraph which has the highest plausibility and for which the causal effect is identifiable? We show that answering this question reduces to solving an NP-hard combinatorial optimization problem which we call the edge ID problem. We propose efficient algorithms to approximate this problem, and evaluate our proposed algorithms against real-world networks and randomly generated graphs. 27 pages, 9 figures, NeurIPS conference, causal identification, causal discovery, probabilistic models

2022

Minimum Cost Intervention Design for Causal Effect Identification

Sina Akbari, Seyed Jalal Etesami, Negar Kiyavash

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the causal effect. In this work, we consider the problem of designing the collection of interventions with the minimum cost to identify the desired effect. First, we prove that this problem is NP-hard, and subsequently propose an algorithm that can either find the optimal solution or a logarithmic-factor approximation of it. This is done by establishing a connection between our problem and the minimum hitting set problem. Additionally, we propose several polynomial-time heuristic algorithms to tackle the computational complexity of the problem. Although these algorithms could potentially stumble on sub-optimal solutions, our simulations show that they achieve small regrets on random graphs. 32 pages, 10 figures, ICML2022

PMLR2022

Revisiting the General Identifiability Problem

Seyed Jalal Etesami, Yaroslav Kivva, Negar Kiyavash, Ehsan Mokhtarian

We revisit the problem of general identifiability originally introduced in [Lee et al., 2019] for causal inference and note that it is necessary to add positivity assumption of observational distribution to the original definition of the problem. We show that without such an assumption the rules of do-calculus and consequently the proposed algorithm in [Lee et al., 2019] are not sound. Moreover, adding the assumption will cause the completeness proof in [Lee et al., 2019] to fail. Under positivity assumption, we present a new algorithm that is provably both sound and complete. A nice property of this new algorithm is that it establishes a connection between general identifiability and classical identifiability by Pearl [1995] through decomposing the general identifiability problem into a series of classical identifiability sub-problems.

2022

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

Negar Kiyavash, Saber Salehkaleybar, Patrick Thiran

We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with

1\le\alpha\le2

which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that the total sample complexity of SCRN in achieving

\epsilon

-global optimum is

\mathcal{O}(\epsilon^{-7/(2\alpha)+1})

for

1\le\alpha< 3/2

and

\mathcal{\tilde{O}}(\epsilon^{-2/(\alpha)})

for

3/2\le\alpha\le 2

. SCRN improves the best-known sample complexity of stochastic gradient descent. Even under a weak version of gradient dominance property, which is applicable to policy-based reinforcement learning (RL), SCRN achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the average sample complexity of SCRN can be reduced to

{\mathcal{O}}(\epsilon^{-2})

for

\alpha=1

using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.

NeurIPS2022

A Variational Inference Approach to Learning Multivariate Wold Processes

Seyed Jalal Etesami, Matthias Grossglauser, Negar Kiyavash, Patrick Thiran, William Trouleau

Temporal point-processes are often used for mathematical modeling of sequences of discrete events with asynchronous timestamps. We focus on a class of temporal point-process models called multivariate Wold processes (MWP). These processes are well suited to model real-world communication dynamics. Statistical inference on such processes often requires learning their corresponding parameters using a set of observed timestamps. In this work, we relax some of the restrictive modeling assumptions made in the state-of-the-art and introduce a Bayesian approach for inferring the parameters of MWP. We develop a computationally efficient variational inference algorithm that allows scaling up the approach to high-dimensional processes and long sequences of observations. Our experimental results on both synthetic and real-world datasets show that our proposed algorithm outperforms existing methods.

PMLR2021

Optimal Adversarial Policies in the Multiplicative Learning System With a Malicious Expert

Seyed Jalal Etesami, Negar Kiyavash

We consider a learning system based on the conventional multiplicative weight ( MW) rule that combines experts' advice to predict a sequence of true outcomes. It is assumed that one of the experts is malicious and aims to impose the maximum loss on the system. The system's loss is naturally defined to be the aggregate absolute difference between the sequence of predicted outcomes and the true outcomes. We consider this problem under both offline and online settings. In the offline setting where the malicious expert must choose its entire sequence of decisions a priori, we show somewhat surprisingly that a simple greedy policy of always reporting false prediction is asymptotically optimal with an approximation ratio of 1+ O(root ln N/N), where N is the total number of prediction stages. In particular, we describe a policy that closely resembles the structure of the optimal offline policy. For the online setting where the malicious expert can adaptively make its decisions, we show that the optimal online policy can be efficiently computed by solving a dynamic program in O(N-3). We also discuss a generalization of our model to multi-expert settings. Our results provide a new direction for vulnerability assessment of commonly-used learning algorithms to internal adversarial attacks.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

Negar Kiyavash, Saber Salehkaleybar, Patrick Thiran

We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with

1\le\alpha\le2

\epsilon

-global optimum is

\mathcal{O}(\epsilon^{-7/(2\alpha)+1})

for

1\le\alpha< 3/2

and

\mathcal{\tilde{O}}(\epsilon^{-2/(\alpha)})

for

3/2\le\alpha\le 2

{\mathcal{O}}(\epsilon^{-2})

for

\alpha=1

using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.

NeurIPS2022

Negar Kiyavash

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

A Wasserstein-based measure of conditional dependence

Causal Discovery in Probabilistic Networks with an Identifiable Causal Effect

Minimum Cost Intervention Design for Causal Effect Identification

Revisiting the General Identifiability Problem

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

A Variational Inference Approach to Learning Multivariate Wold Processes

Editorial

Optimal Adversarial Policies in the Multiplicative Learning System With a Malicious Expert

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Minimum Cost Intervention Design for Causal Effect Identification

Revisiting the General Identifiability Problem

A Wasserstein-based measure of conditional dependence

Causal Discovery in Probabilistic Networks with an Identifiable Causal Effect

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

Editorial

Optimal Adversarial Policies in the Multiplicative Learning System With a Malicious Expert

A Variational Inference Approach to Learning Multivariate Wold Processes