Computer Science

An overview of the classical strategies (constraint-based algorithms, score-based algorithms) in learning causal DAGs. Relevant graphical and statistical concepts will be discussed, including Markov equivalence, faithfulness, conditional independence testing, consistency of the BIC score for selection, and theoretical properties of methods such as the PC algorithm and GES algorithm.

An overview of the classical strategies (constraint-based algorithms, score-based algorithms) in learning causal DAGs. Relevant graphical and statistical concepts will be discussed, including Markov equivalence, faithfulness, conditional independence testing, consistency of the BIC score for selection, and theoretical properties of methods such as the PC algorithm and GES algorithm.

This lecture will introduce Bayesian networks and their causal interpretation as causal graphical models, d-separation, the do-calculus, and the Shpitser-Pearl ID algorithm. We'll start by introducing Bayesian networks, causal graphical models, and interventions. We'll then show that two Bayesian networks with the same skeletons and v-structures represent the same conditional independence assumptions and prove that the d-separations present in any Bayesian network exhaust all the conditional independence assumptions that are guaranteed to hold in any distribution that factorizes according to that network. We then turn to causal models and introduce the do-calculus. We show the soundness of each of the rules of the do-calculus. Finally, we describe the Shpitser-Pearl algorithm for identifying causal effects in semi-Markovian models and, time-permitting, prove that the ID algorithm is complete for identifying causal effects; that is, a causal effect is identifiable if and only if the ID algorithm terminates successfully.

This lecture will introduce Bayesian networks and their causal interpretation as causal graphical models, d-separation, the do-calculus, and the Shpitser-Pearl ID algorithm. We'll start by introducing Bayesian networks, causal graphical models, and interventions. We'll then show that two Bayesian networks with the same skeletons and v-structures represent the same conditional independence assumptions and prove that the d-separations present in any Bayesian network exhaust all the conditional independence assumptions that are guaranteed to hold in any distribution that factorizes according to that network. We then turn to causal models and introduce the do-calculus. We show the soundness of each of the rules of the do-calculus. Finally, we describe the Shpitser-Pearl algorithm for identifying causal effects in semi-Markovian models and, time-permitting, prove that the ID algorithm is complete for identifying causal effects; that is, a causal effect is identifiable if and only if the ID algorithm terminates successfully.

This lecture will introduce Bayesian networks and their causal interpretation as causal graphical models, d-separation, the do-calculus, and the Shpitser-Pearl ID algorithm. We'll start by introducing Bayesian networks, causal graphical models, and interventions. We'll then show that two Bayesian networks with the same skeletons and v-structures represent the same conditional independence assumptions and prove that the d-separations present in any Bayesian network exhaust all the conditional independence assumptions that are guaranteed to hold in any distribution that factorizes according to that network. We then turn to causal models and introduce the do-calculus. We show the soundness of each of the rules of the do-calculus. Finally, we describe the Shpitser-Pearl algorithm for identifying causal effects in semi-Markovian models and, time-permitting, prove that the ID algorithm is complete for identifying causal effects; that is, a causal effect is identifiable if and only if the ID algorithm terminates successfully.

This lecture will introduce Bayesian networks and their causal interpretation as causal graphical models, d-separation, the do-calculus, and the Shpitser-Pearl ID algorithm. We'll start by introducing Bayesian networks, causal graphical models, and interventions. We'll then show that two Bayesian networks with the same skeletons and v-structures represent the same conditional independence assumptions and prove that the d-separations present in any Bayesian network exhaust all the conditional independence assumptions that are guaranteed to hold in any distribution that factorizes according to that network. We then turn to causal models and introduce the do-calculus. We show the soundness of each of the rules of the do-calculus. Finally, we describe the Shpitser-Pearl algorithm for identifying causal effects in semi-Markovian models and, time-permitting, prove that the ID algorithm is complete for identifying causal effects; that is, a causal effect is identifiable if and only if the ID algorithm terminates successfully.

For different parameterizations (mappings from parameters to predictors), we study the regularization cost in predictor space induced by l_2 regularization on the parameters (weights).  We focus on linear neural networks as parameterizations of linear predictors and identify the representation cost of certain sparse linear ConvNets and residual networks.  In order to get a better understanding of how the architecture and parameterization affect the representation cost, we also study the reverse problem, identifying which regularizers on linear predictors (e.g., l_p quasi-norms, group quasi-norms, the k-support-norm, elastic net) can be the representation cost induced by simple l_2 regularization, and designing the parameterizations that do so.

In this short talk, I will share some recent progress on the hardness of learning shallow RELU neural networks (Relu-NN) and polynomially small adversarial noise. We will present a result that efficiently learning an 1-hidden layer Relu-NN under Gaussian input and adversarial noise is "cryptographically hard", in the sense that it implies a polynomial-time quantum algorithm for the worst-case shortest vector problem.

This talk will be very informal: I will discuss ongoing research with open questions and partial results. We study the asymptotic consistency of modern interpolating methods, including deep networks, in both classification and regression settings. That is, we consider learning methods which scale the data size while simultaneously scaling the model size, in a way which always interpolates the train set. We present empirical evidence that, perhaps contrary to intuitions in theory, many natural interpolating learning methods are *inconsistent* for a wide variety of distributions. That is, they do not approach Bayes-optimality even in the limit of infinite data. The message is, in settings with nonzero Bayes risk, overfitting is not benign: interpolating the noise significantly harms the classifier, to the point of preventing consistency. This work is motivated by: (1) understanding differences between the overparameterized and underparameterized regime, (2) guiding theory towards more "realistic" assumptions to capture deep learning practice, and (3) understanding common structure shared by "natural" interpolating methods. Based on joint work with: Neil Mallinar, Amirhesam Abedsoltan, Gil Kur, and Misha Belkin. And is a follow-up work to the paper "Distributional Generalization", joint with Yamini Bansal.

It is well known that, at a random initialization, as their width approaches infinity, neural networks can be well approximated by Gaussian processes. We quantify this phenomenon by providing non-asymptotic convergence rates in the space of continuous functions. In the process, we study the Central Limit Theorem in high and infinite dimensions, as well as anti-concentration properties of polynomials with random variables

We obtain limiting spectral distribution of empirical conjugate kernel and neural tangent kernel matrices for two-layer neural networks with deterministic data and random weights. When the width of the network grows faster than the size of the dataset, a deformed semicircle law appears. In this regime, we also calculate the asymptotic test and training errors for random feature regression. Joint work with Zhichao Wang (UCSD).

We consider a class of supervised learning problems whereby we are given n data points (y_i,x_i), with x_i a d-dimensional dfeature factor, y_i a response, and the model is parametrized by a vector of dimension kd. We consider the high-dimensional asymptotics in which n,d diverge, with n/d and k of order one. As a special case, this class of models includes neural networks with k hidden neurons. I will present two sets of results: 1. Universality of certain properties of empirical risk minimizers with respect to the distribution of the feature vectors x_i. 2. A sharp asymptotic characterization of gradient flow in terms of a one-dimensional stochastic process. [Based on joint work with Michael Celentano, Chen Cheng, Basil Saeed]