Chaire en Business Analytics

Chair

Related publications (15)

The KDD 2021 Workshop on Causal Discovery (CD2021)

Negar Kiyavash, Huan Liu

As a basic and effective tool for explanation, prediction and decision making, causal relationships have been utilized in almost all disciplines. Traditionally, causal relationships are identified by making use of interventions or randomized controlled experiments. However, conducting such experiments is often expensive or even impossible due to cost or ethical concerns. Therefore, there has been an increasing interest in discovering causal relationships based on observational data, and in the past few decades, significant contributions have been made to this field by computer scientists. Inspired by such achievements and following the success of CD 2016 - CD 2020, CD 2021 continues to serve as a forum for researchers and practitioners in data mining and other disciplines to share their recent research in causal discovery in their respective fields and to explore the possibility of interdisciplinary collaborations in the study of causality. Based on the platform of KDD, this workshop is especially interested in attracting contributions that link data mining/machine learning research with causal discovery, and solutions to causal discovery in large scale datasets.

ASSOC COMPUTING MACHINERY2021

Trace norm regularization for multi-task learning with scarce data

Nicolas Henri Bernard Flammarion, Mikhail Konobeev

Multi-task learning leverages structural similarities between multiple tasks to learn despite very few samples. Motivated by the recent success of neural networks applied to data-scarce tasks, we consider a linear low-dimensional shared representation model. Despite an extensive literature, existing theoretical results either guarantee weak estimation rates or require a large number of samples per task. This work provides the first estimation error bound for the trace norm regularized estimator when the number of samples per task is small. The advantages of trace norm regularization for learning data-scarce tasks extend to meta-learning and are confirmed empirically on synthetic datasets.

2022

, ,

The classical electromagnetic time reversal (EMTR) fault location method in power systems can be time consuming, especially when a high location accuracy is desired. To cope with this issue, the concept of EMTR in mismatched media has recently been introduced, substantially improving the fault location efficiency. In this paper, we present a theoretical study and rigorous demonstration of the mismatched-media-based mirrored minimum energy property. Firstly, we infer a direct-reversed-time transfer function and present a theorem according to which, at the fault switching frequency and its odd harmonics, the mirror-image point of the fault location with respect to the line center corresponds to a local minimum of the squared modulus of the transfer function. Next, it is proved that the mirrored minimum energy property is a corollary of this theorem. Based on these theoretical findings, we propose an algorithm that uses the reversed-time voltage energy as a fault location metric in the frequency domain, instead of the original time-domain approach. We further propose applying a data-driven strategy to maximize the computation efficiency of the algorithm. The applicability and robustness of the frequency-domain fault location metric, together with the computational efficiency of the accelerating algorithm, are numerically and experimentally validated.

2021

A Catalyst Framework for Minimax Optimization

Negar Kiyavash

We introduce a generic two-loop scheme for smooth minimax optimization with strongly-convex-concave objectives. Our approach applies the accelerated proximal point framework (or Catalyst) to the associated dual problem and takes full advantage of existing gradient-based algorithms to solve a sequence of well-balanced strongly-convex-strongly-concave minimax problems. Despite its simplicity, this leads to a family of near-optimal algorithms with improved complexity over all existing methods designed for strongly-convex-concave minimax problems. Additionally, we obtain the first variance-reduced algorithms for this class of minimax problems with finite-sum structure and establish faster convergence rate than batch algorithms. Furthermore, when extended to the nonconvex-concave minimax optimization, our algorithm again achieves the state-of-the-art complexity for finding a stationary point. We carry out several numerical experiments showcasing the superiority of the Catalyst framework in practice.

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2020

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

The Devil is in the Detail: A Framework for Macroscopic Prediction via Microscopic Models

Negar Kiyavash

Macroscopic data aggregated from microscopic events are pervasive in machine learning, such as country-level COVID-19 infection statistics based on city-level data. Yet, many existing approaches for predicting macroscopic behavior only use aggregated data, leaving a large amount of fine-grained microscopic information unused. In this paper, we propose a principled optimization framework for macroscopic prediction by fitting microscopic models based on conditional stochastic optimization. The framework leverages both macroscopic and microscopic information, and adapts to individual microscopic models involved in the aggregation. In addition, we propose efficient learning algorithms with convergence guarantees. In our experiments, we show that the proposed learning framework clearly outperforms other plug-in supervised learning approaches in real-world applications, including the prediction of daily infections of COVID-19 and medicare claims.

2020

A Catalyst Framework for Minimax Optimization

Negar Kiyavash

We introduce a generic \emph{two-loop} scheme for smooth minimax optimization with strongly-convex-concave objectives. Our approach applies the accelerated proximal point framework (or Catalyst) to the associated \emph{dual problem} and takes full advantage of existing gradient-based algorithms to solve a sequence of well-balanced strongly-convex-strongly-concave minimax problems. Despite its simplicity, this leads to a family of near-optimal algorithms with improved complexity over all existing methods designed for strongly-convex-concave minimax problems. Additionally, we obtain the first variance-reduced algorithms for this class of minimax problems with finite-sum structure and establish even faster convergence rate. Furthermore, when extended to the nonconvex-concave minimax optimization, our algorithm again achieves the state-of-the-art complexity for finding a stationary point. We carry out several numerical experiments showcasing the superiority of the Catalyst framework in practice.

2020

Graph Signal Processing: Foundations and Emerging Directions [From the Guest Editors]

Negar Kiyavash, Dimitri Nestor Alice Van De Ville

The articles in this special section focus on graph signal processing. Generically, the networks that sustain our societies can be understood as complex systems formed by multiple nodes, where global network behavior arises from local interactions between connected nodes. More succinctly, a network or a graph can be defined as a structure that encodes relationships between pairs of elements of a set. The simplicity of this definition drives the application of graphs and networks to a wide variety of disciplines, such as biology, medicine, psychology, sociology, economics, engineering, computer science, and so on.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

, ,

A directed acyclic graph (DAG) is the most common graphical model for representing causal relationships among a set of variables. When restricted to using only observational data, the structure of the ground truth DAG is identifiable only up to Markov equivalence, based on conditional independence relations among the variables. Therefore, the number of DAGs equivalent to the ground truth DAG is an indicator of the causal complexity of the underlying structure–roughly speaking, it shows how many interventions or how much additional information is further needed to recover the underlying DAG. In this paper, we propose a new technique for counting the number of DAGs in a Markov equivalence class. Our approach is based on the clique tree representation of chordal graphs. We show that in the case of bounded degree graphs, the proposed algorithm is polynomial time. We further demonstrate that this technique can be utilized for uniform sampling from a Markov equivalence class, which provides a stochastic way to enumerate DAGs in the equivalence class and may be needed for finding the best DAG or for causal inference given the equivalence class as input.We also extend our counting and sampling method to the case where prior knowledge about the underlying DAG is available, and present applications of this extension in causal experiment design and estimating the causal effect of joint interventions.

AAAI Press2019

Learning Linear Non-Gaussian Causal Models in the Presence of Latent Variables

Negar Kiyavash, Saber Salehkaleybar, Kun Zhang

We consider the problem of learning causal models from observational data generated by linear non-Gaussian acyclic causal models with latent variables. Without considering the effect of latent variables, the inferred causal relationships among the observed variables are often wrong. Under faithfulness assumption, we propose a method to check whether there exists a causal path between any two observed variables. From this information, we can obtain the causal order among the observed variables. The next question is whether the causal effects can be uniquely identified as well. We show that causal effects among observed variables cannot be identified uniquely under mere assumptions of faithfulness and non-Gaussianity of exogenous noises. However, we are able to propose an efficient method that identifies the set of all possible causal effects that are compatible with the observational data. We present additional structural conditions on the causal graph under which causal effects among observed variables can be determined uniquely. Furthermore, we provide necessary and sufficient graphical conditions for unique identification of the number of variables in the system. Experiments on synthetic data and real-world data show the effectiveness of our proposed algorithm for learning causal models.

MICROTOME PUBL2020