---

[CANCELLED] January 12: Roman Vershynin (UC Irvine) [Undergraduate lecture]

January 19: Grigory Franguridi, 2PM, (USC Center for Economic and Social Research)

Estimation of panels with attrition and refreshment samples

January 26: Mahdi Soltanolkotabi (USC)

Foundations for feature learning via gradient descent

One of the key mysteries in modern learning is that a variety of models such as deep neural networks when  trained via (stochastic) gradient descent can extract useful features and learn high quality representations directly from data simultaneously with fitting the labels. This feature learning capability is also at the forefront of the recent success of a variety of contemporary paradigms such as transformer architectures, self-supervised and transfer learning. Despite a flurry of exciting activity over the past few years, existing theoretical results are often too crude and/or pessimistic to explain feature/representation learning in practical regimes of operation or serve as a guiding principle for practitioners. Indeed, existing literature often requires unrealistic hyperparameter choices (e.g. very small step sizes, large initialization or wide models).  In this talk I will focus on demystifying this feature/representation learning phenomena for a variety of problems spanning single index models, low-rank factorization, matrix reconstruction, and neural networks. Our results are based on an intriguing spectral bias phenomena for gradient descent, that puts the iterations on a particular trajectory towards solutions that are not only globally optimal but also generalize well by simultaneously finding good features/representations of the data while fitting to the labels. The proofs combine ideas from high-dimensional probability/statistics, optimization and nonlinear control to develop a precise analysis of model generalization along the trajectory of gradient descent. Time permitting, I will explain the implications of these theoretical results for more contemporary use cases including transfer learning, self-attention, prompt-tuning via transformers and simple self-supervised learning settings.

February 2: Timothy Armstrong (USC)

Robust Estimation and Inference in Panels with Interactive Fixed Effects

We consider estimation and inference for a regression coefficient in panels with interactive fixed effects (i.e., with a factor structure). We show that previously developed estimators and confidence intervals (CIs) might be heavily biased and size-distorted when some of the factors are weak. We propose estimators with improved rates of convergence and bias-aware CIs that are uniformly valid regardless of whether the factors are strong or not. Our approach applies the theory of minimax linear estimation to form a debiased estimate using a nuclear norm bound on the error of an initial estimate of the interactive fixed effects. We use the obtained estimate to construct a bias-aware CI taking into account the remaining bias due to weak factors. In Monte Carlo experiments, we find a substantial improvement over conventional approaches when factors are weak, with little cost to estimation error when factors are strong.

Paper link: Timothy B. Armstrong, Martin Weidner, Andrei Zeleneev. https://arxiv.org/abs/2210.06639

February 9: Yuehao Bai (USC)

On the Efficiency of Finely Stratified Experiments

This paper studies the efficient estimation of a large class of treatment effect parameters that arise in the analysis of experiments. Here, efficiency is understood to be with respect to a broad class of treatment assignment schemes for which the marginal probability that any unit is assigned to treatment equals a pre-specified value, e.g., one half. Importantly, we do not require that treatment status is assigned in an i.i.d. fashion, thereby accommodating complicated treatment assignment schemes that are used in practice, such as stratified block randomization and matched pairs. The class of parameters considered are those that can be expressed as the solution to a restriction on the expectation of a known function of the observed data, including possibly the pre-specified value for the marginal probability of treatment assignment. We show that this class of parameters includes, among other things, average treatment effects, quantile treatment effects, local average treatment effects as well as the counterparts to these quantities in experiments in which the unit is itself a cluster. In this setting, we establish two results. First, we derive a lower bound on the asymptotic variance of estimators of the parameter of interest in the form of a convolution theorem. Second, we show that the na ̈ıve method of moments estimator achieves this bound on the asymptotic variance quite generally if treatment is assigned using a “finely stratified” design. By a “finely stratified” design, we mean experiments in which units are divided into groups of a fixed size and a proportion within each group is assigned to treatment uniformly at random so that it respects the restriction on the marginal probability of treatment assignment. In this sense, “finely stratified” experiments lead to efficient estimators of treatment effect parameters “by design” rather than through ex post covariate adjustment.

Paper link: Yuehao Bai, Jizhou Liu, Azeem M. Shaikh, Max Tabord-Meehan
https://arxiv.org/abs/2307.15181

February 23: Tryphon Georgiou (UC Irvine)

Stochastic Control meets Non-equilibrium Thermodynamics: Fundamental limits of power generation in thermodynamic engines

Thermodynamics was born in the 19th century in quest of a way to quantify efficiency of steam engines at the dawn of the industrial age. In the time since, thermodynamics has impacted virtually all other areas in science, from chemistry and biology to the physics of black holes, and yet, progress beyond the classical quasi-static limit towards finite-time thermodynamic transitions has been slow; finite-time is of essence for non-vanishing power generation. In recent years a deeper understanding of non-equilibrium processes has been achieved based on stochastic models with degrees of freedom (state variables) that are subject to Brownian excitation that models heat baths. Within this framework we will explain energy transduction, we will give insights on how anisotropy in thermal or chemical potentials can be tapped for power generation in engineered and physical processes, and we will highlight fundamental bounds on the amount of power that can drawn during finite-time thermodynamic transitions.

The talk is based on joint works with Rui Fu (UCI), Olga Movilla (UCI), Amir Taghvaei (UCI) and Yongxin Chen (GaTech). Research funding by AFOSR, ARO and NSF is gratefully acknowledged.

Monday February 26, 3:30PM, KAP 427: Yongtao Guan (Chinese University of Hong Kong, Shenzhen)

Group Network Hawkes Process

In this work, we study the event occurrences of individuals interacting in a network. To characterize the dynamic interactions among the individuals, we propose a group network Hawkes process (GNHP) model whose network structure is observed and fixed. In particular, we introduce a latent group structure among individuals to account for the heterogeneous user-specific characteristics. A maximum likelihood approach is proposed to simultaneously cluster individuals in the network and estimate model parameters. A fast EM algorithm is subsequently developed by utilizing the branching representation of the proposed GNHP model. Theoretical properties of the resulting estimators of group memberships and model parameters are investigated under both settings when the number of latent groups G is over-specified or correctly specified. A data-driven criterion that can consistently identify the true G under mild conditions is derived. Extensive simulation studies and an application to a data set collected from Sina Weibo are used to illustrate the effectiveness of the proposed methodology.

March 1: Morris Yau (MIT)

Are Neural Networks Optimal Approximation Algorithms

In this talk, we discuss the power of neural networks to compute solutions to NP-hard optimization problems focusing on the class of constraint satisfaction problems (boolean sat, Sudoku, etc.).  We find there is a graph neural network architecture (OptGNN) that captures the optimal approximation algorithm for constrainst satisfaction, up to complexity theoretic assumptions via tools in semidefinite programming.  Furthermore, OptGNN can act as a convex program solver and hence output a dual (a bound) on the optimality of a combinatorial problem.  Evaluating OptGNN on benchmarks in the neural combinatorial optimization literature, we find our approach is competitive with the state of the art unsupervised neural baselines.  We discuss further connections between neural networks and computation, and point to directions for future work.

March 8: Annie Qu (UC Irvine)

A Model-Agnostic Graph Neural Network for Integrating Local and Global Information

Graph neural networks (GNNs) have achieved promising performance in a variety of graph focused tasks. Despite their success, the two major limitations of existing GNNs are the capability of learning various-order representations and providing interpretability of such deep learning-based black-box models. To tackle these issues, we propose a novel Model-agnostic Graph Neural Network (MaGNet) framework. The proposed framework is able to extract knowledge from high-order neighbors, sequentially integrates information of various orders, and offers explanations for the learned model by identifying influential compact graph structures. In particular, MaGNet consists of two components: an estimation model for the latent representation of complex relationships under graph topology, and an interpretation model that identifies influential nodes, edges, and important node features. Theoretically, we establish the generalization error bound for MaGNet via empirical Rademacher complexity and showcase its power to represent the layer-wise neighborhood mixing. We conduct comprehensive numerical studies using both simulated data and a real-world case study on investigating the neural mechanisms of the rat hippocampus,
demonstrating that the performance of MaGNet is competitive with state-of-the-art methods.

March 15: no talk [spring break]

March 22: Xiaowu Dai (UCLA)

Kernel ordinary differential equations

The ordinary differential equation (ODE) is widely used in modelling biological and physical processes in science. A new reproducing kernelbased approach is proposed for the estimation and inference of ODE given noisy observations. The functional forms in ODE are not assumed to be known or restricted to be linear or additive, and pairwise interactions are allowed. Sparse estimation is performed to select individual functionals and construct confidence intervals for the estimated signal trajectories. The estimation optimality and selection consistency of kernel ODE are established under both the low-dimensional and high-dimensional settings, where the number of unknown functionals can be smaller or larger than the sample size. The proposal tackles several important problems that are not yet fully addressed in smoothing spline analysis of variance (SS-ANOVA) framework, and extends the existing methods of dynamic causal modeling.

March 29: Kengo Kato (Cornell)

Entropic optimal transport: limit theorems and algorithms

In this talk, I will discuss my recent work on entropic optimal transport (EOT). In the first part, I will discuss limit theorems for EOT maps, dual potentials, and the Sinkhorn divergence. The key technical tool we use is a first and second-order Hadamard differentiability analysis of EOT potentials with respect to the marginals, from which the limit theorems, bootstrap consistency, and asymptotic efficiency of the empirical estimators follow. The second part concerns the entropic Gromov-Wasserstein (EGW) distance, which serves as a computationally efficient proxy for the Gromov-Wasserstein distance. By leveraging a variational representation that ties the EGW problem with a series of EOT problems, we derive stability results of EGW with respect to the auxiliary matrix, which enables us to develop efficient algorithms for solving the EGW problem. This talk is based on joint work with Ziv Goldfeld, Gabriel Rioux, and Ritwik Sadhu.

April 5: Weixuan Xia (USC)

Set-Valued Stochastic Integrals and Convoluted Lévy Processes

In this talk, I will discuss set-valued Volterra-type stochastic integrals driven by Lévy processes. I will explain the definition of set-valued convoluted stochastic integrals by taking the closed decomposable hull of integral functionals over time, thereby extending classical definitions to convoluted integrals with square-integrable kernels. Two key insights include: (1) Aside from established results for set-valued Itô integrals, while set-valued stochastic integrals with respect to a finite-variation Poisson random measure are guaranteed to be integrally bounded for bounded integrands, this is not true when the random measure represents infinite variation; (2) It is a mutual effect of kernel singularity and jumps that the set-valued convoluted integrals are possibly explosive and can take extended vector values. These findings carry significant implications for the construction of set-valued fractional dynamical systems. Additionally, I will explore two classes of set-monotone processes for practical interests in economic and financial modeling.

April 12: Yosi Rinott (The Hebrew University of Jerusalem)

On the behavior of posterior probabilities with additional data: monotonicity and nonmonotonicity, asymptotic rates, log-concavity, and Turán’s inequality

Given a parametric model, a prior, and data, Bayesian statisticians quantify their belief that the true parameter is ϑ₀ by its posterior probability. The starting question of this paper is whether the posterior at ϑ₀ increases when the data are generated under ϑ₀, and how it behaves when the data come from ϑ ≠ ϑ₀. Can it decrease and then increase, and thus additional data may mislead Bayesian statisticians?

For data arriving sequentially, we consider monotonicity properties of the posterior probabilities as a function of the sample size with respect to certain stochastic orders, specifically starting with likelihood ratio dominance.
When the data is generated by ϑ ≠ ϑ₀ , Doob’s consistency theorem says that the posterior at ϑ₀converges a.s. to zero and therefore its expectation converges to zero. We obtain precise asymptotic rates of the latter convergence for observations from an exponential family and show that the expectation of the ϑ₀ -posterior under  ϑ ≠ ϑ₀ is eventually strictly decreasing. Finally, we show that in a number of interesting cases this expectation is a log-concave function of the sample size, and thus unimodal. In the Bernoulli case we obtain this result by developing an inequality that is related to Turán’s inequality for Legendre polynomials.

The talk is based on a joint work with Sergiu Hart.

April 19: Andrew Holbrook (UCLA, Department of Biostatistics)

Quantum Markov chain Monte Carlo(s)

I discuss how one can use quantum circuits to accelerate multiproposal MCMC and point to promising avenues of future research, including quantum HMC,  quantum-accelerated nonreversible MCMC and quantum-accelerated locally-balanced MCMC.

April 26: Sui Tang (UCSB)

Learning interaction kernels in particle and agent based systems 

Interacting particle systems showcase a variety of collective behaviors and are fundamental to many scientific and engineering domains, such as the flocking of birds and the milling of fish. These systems are typically modeled using differential equations to elucidate how individual behaviors drive collective dynamics, an essential inquiry across multiple disciplines. Although recent theoretical and numerical studies have successfully replicated many qualitative collective patterns seen in nature, there is still a notable deficiency in quantitatively matching these models with empirical data.

We explore the data-driven discovery of latent interaction kernels from observed trajectory data in particle and agent-based systems. We discuss recent findings in stochastic systems where interaction kernels are derived from pairwise distances and introduce a nonparametric inference strategy using a regularized maximum likelihood estimator for precise kernel estimation. We show this approach can achieve near-optimal convergence rates, regardless of the state space dimensionality when dealing with multiple trajectory data. Additionally, we conduct error analysis related to discrete-time observations and validate our methodology through numerical experiments on models such as stochastic opinion dynamics and the Lennard-Jones potential. Moreover, we also consider microscopic models and  advance our approach to estimate nonlocal interaction potentials in  aggregation-diffusion equations from noisy data, using sparsity-promoting techniques. This research is conducted in collaboration with Fei Lu, Mauro Maggioni, Jose A. Carrillo, Gissell Estrada-Rodriguez, and Laszlo Mikolas.

 

---

Fall 2023:

 

---

Spring 2023:

A Generalized Kyle-Back Insider Trading Model with Dynamic Information

n this project, we consider a class of generalized Kyle-Back strategic insider trading models in which the insider is able to use the dynamic information obtained by observing the instantaneous movement of an underlying asset that is allowed to be influenced by its market price. Since such a model will be largely outside the Gaussian paradigm, we shall try to Markovize it by introducing an auxiliary (factor) diffusion process, in the spirit of the weighted total order process, as a part of the “pricing rule”. As the main technical tool in solving the Kyle-Back equilibrium in such a setting, we study a class of Stochastic Two-Point Boundary Value Problem (STPBVP), which resembles the dynamic Markov bridge in the literature, but without insisting on its local martingale requirement. In the case when the solution of the STPBVP has an affine structure, we show that the pricing rule functions, whence the Kyle-Back equilibrium, can be determined by the decoupling field of a forward-backward SDE obtained via a non-linear filtering approach, along with a set of compatibility conditions. This is a joint work with Jin Ma.

We study differentially private (DP) stochastic optimization (SO) with loss functions whose worst-case Lipschitz parameter over all data points may be extremely large. To date, the vast majority of work on DP SO assumes that the loss is uniformly Lipschitz continuous over data (i.e. stochastic gradients are uniformly bounded over all data points). While this assumption is convenient, it often leads to pessimistic excess risk bounds. In many practical problems, the worst-case (uniform) Lipschitz parameter of the loss over all data points may be extremely large due to outliers. In such cases, the error bounds for DP SO, which scale with the worst-case Lipschitz parameter of the loss, are vacuous. To address these limitations, this work provides near-optimal excess risk bounds that do not depend on the uniform Lipschitz parameter of the loss. Building on a recent line of work (Wang et al., 2020; Kamath et al., 2022), we assume that stochastic gradients have bounded 𝑘-th order moments for some 𝑘≥2. Compared with works on uniformly Lipschitz DP SO, our excess risk scales with the 𝑘-th moment bound instead of the worst-case Lipschitz parameter of the loss, allowing for significantly faster rates in the presence of outliers and/or heavy-tailed data. For convex and strongly convex loss functions, we provide the first asymptotically optimal excess risk bounds (up to a logarithmic factor). In contrast to (Wang et al., 2020; Kamath et al., 2022), our bounds do not require the loss function to be differentiable/smooth. We also devise an accelerated algorithm for smooth losses that runs in linear time and has excess risk that is tight in certain practical parameter regimes. Additionally, our work is the first to address non-convex non-uniformly Lipschitz loss functions satisfying the Proximal-PL inequality; this covers some practical machine learning models. Our Proximal-PL algorithm has near-optimal excess risk.

We investigate the problem of constructing m x d integer matrices with small entries and d large comparing to m so that for all vectors x in Z^d with at most s ≤ m nonzero coordinates the image vector Ax is not 0. Such constructions allow for robust recovery of the original vector x from its image Ax. This problem is motivated by the compressed sensing paradigm and has numerous potential applications ranging from wireless communications to medical imaging. We discuss existence of such matrices for appropriate choices of d as a function of m. In addition to some probabilistic arguments, we demonstrate a deterministic construction of a family of such matrices stemming from a certain geometric covering problem. We also discuss a connection of our constructions to a simple variant of the Tarski plank problem. This talk is based on joint works with B. Sudakov and D. Needell, as well as with A. Hsu.

June 6: Jasper Lee (UW Madison) [in person]

---

Aug 26: [No seminar]

Sep 2: [No seminar]

Sep 9: Daniel Kane (UCSD) [zoom]

Ak Testing of Distributions

We introduce the theory of distribution testing with a focus on tests for one-dimensional, structured distributions. In order to produce efficient testers, we introduce the theory of A_k distance and discuss the known results for optimal testers with respect to A_k distance, showing that it produces near-optimal testers for many distribution families.

Sep 16: Ken Alexander (USC) [in-person]

Disjointness of geodesics for first passage percolation in the plane

First passage percolation may be viewed as a way of creating a random metric on the integer lattice.  Random passage times (iid) are assigned to the edges of the lattice, and the distance from $x$ to $y$ is defined to be the smallest sum of passage times among all paths from $x$ to $y$.  We consider geodesics (shortest paths) in this context; specifically, what is the probability that two close–by nearly–parallel geodesics are disjoint?  More precisely, if the geodesics have end-to-end distance $L$ and the endpoints are separated by distance $a$ at one end and $b$ at the other, how does the disjointness probability vary with $L,a,b$?  We answer this question, at least at the level of the proper exponents for $L,a,$ and $b$.

MONDAY Sep 19 [Joint with CAMS]: Nathan Glatt Holtz (Tulane)

A unified framework for Metropolis-Hastings Type Monte Carlo methods.

The efficient generation of random samples is a central task within many of the quantitative sciences. The workhorse of Bayesian statistics and statistical physics, Markov chain Monte Carlo (MCMC) comprises a large class of algorithms for sampling from arbitrarily complex and/or high-dimensional probability distributions. The Metropolis-Hastings method (MH) stands as the seminal MCMC algorithm, and its basic operation underlies most of the MCMC techniques developed to this day.

Sep 23: Tom Hutchcroft (Caltech) [in-person]

Critical behaviour in hierarchical percolation

Statistical mechanics models undergoing a phase transition often exhibit rich, fractal-like behaviour at their critical points, which are described in part by critical exponents – the indices governing the power-law growth or decay of various quantities of interest. These exponents are expected to depend on the dimension but not on the microscopic details of the model such as the choice of lattice. After much progress over the last thirty years we now understand two-dimensional and high-dimensional models rather well, but intermediate dimensions such as three remain mysterious. I will discuss these issues in the context of hierarchical percolation, a simplified version of percolation on Z^d for which, in forthcoming work, I establish a fairly good description of the critical behaviour in all dimensions.

THURSDAY Sep 29: Lisa Sauermann (MIT), 12PM NOON [zoom]  [note the NONSTANDARD DAY/TIME]

Anticoncentration in Ramsey graphs and a proof of the Erdös-McKay Conjecture

This talk will discuss recent joint work with Matthew Kwan, Ashwin Sah, and Mehtaab Sawhney, proving an old conjecture of Erdös and McKay (for which Erdős offered $100). This conjecture concerns Ramsey graphs, which are (roughly speaking) graphs without large complete or empty subgraphs. In order to prove the conjecture, we study edge-statistics in Ramsey graphs, i.e. we study the distribution of the number of edges in a random vertex subset of a Ramsey graph. After discussing some background on Ramsey graphs, the talk will explain our results and give an overview of our proof approach.

Sep 30: Simo Ndaoud (ESSEC) [in-person]

Adaptive robustness and sub-Gaussian deviations in sparse linear regression through Pivotal Double SLOPE

October 7: Guang Cheng (UCLA)  [in-person]

A Statistical Journey through Trustworthy AI

Our lab believes that the next generation of AI is mainly driven by trustworthiness, beyond performance. This talk attempts to offer statistical perspectives to embrace three challenges in trustworthy AI: privacy, robustness and fairness. Specifically, we consider privacy protection by machine un-learning, enhance adversarial robustness by utilizing artificially generated data, and establish fair Bayes-optimal classifiers. These results demonstrate the unique value of statisticians in studying trustworthy AI from empirical, methodological or theoretical aspects.

October 14: [Fall break]

October 21: Wen (Rick) Zhou (Colorado State)  [in-person]

High dimensional clustering via latent semiparametric mixture models.

Cluster analysis is a fundamental task in machine learning. Several clustering algorithms have been extended to handle high-dimensional data by incorporating a sparsity constraint in the estimation of a mixture of Gaussian models. Though it makes some neat theoretical analysis possible, this type of approach is arguably restrictive for many applications. In this work we propose a novel latent variable transformation mixture model for clustering in which we assume that after some unknown monotone transformations the data follows a mixture of Gaussians. Under the assumption that the optimal clustering admits a sparsity structure, we develop a new clustering algorithm named CESME for high-dimensional clustering. The use of unspecified transformation makes the model far more flexible than the classical mixture of Gaussians. On the other hand, the transformation also brings quite a few technical challenges to the model estimation as well as the theoretical analysis of CESME. We offer a comprehensive analysis of CESME including identifiability, initialization, algorithmic convergence, and statistical guarantees on clustering. In addition, the convergence analysis has revealed an interesting algorithmic phase transition for CESME, which has also been noted for the EM algorithm in literature. Leveraging such a transition, a data-adaptive procedure is developed and substantially improves the computational efficiency of CESME. Extensive numerical study and real data analysis show that CESME outperforms the existing high-dimensional clustering algorithms including CHIME, sparse spectral clustering, sparse K-means, sparse convex clustering, and IF-PCA.

Oct 28: Çağın Ararat (Bilkent) [in-person]

Set-valued martingales and backward stochastic differential equations

Motivated by the connection between univariate dynamic risk measures and backward stochastic differential equations, we start building a theory for set-valued backward stochastic differential equations (SV-BSDE). As a first step for this purpose, we formulate a simple SV-BSDE with a compact-valued driver function and study the well-posedness of this SV-BSDE. A key tool in establishing well-posedness is the availability of a stochastic integral representation for set-valued martingales. We prove a new martingale representation theorem which, in contrast to the available literature, allows the initial value of the martingale to be nontrivial. This is a joint work with Jin Ma and Wenqian Wu.

November 4: Qiyang Han (Rutgers University)  [in-person]

Universality of regularized regression estimators in high dimensions

The Convex Gaussian Min-Max Theorem (CGMT) has emerged as a prominent theoretical tool for analyzing the precise stochastic behavior of various statistical estimators in the so-called high dimensional proportional regime, where the sample size and the signal dimension are of the same order. However, a well recognized limitation of the existing CGMT machinery rests in its stringent requirement on the exact Gaussianity of the design matrix, therefore rendering the obtained precise high dimensional asymptotics largely a specific Gaussian theory in various important statistical models. This work provides a structural universality framework for a broad class of regularized regression estimators that is particularly compatible with the CGMT machinery. Here universality means that if a `structure’ is satisfied by the regression estimator $\hat{\mu}_G$ for a standard Gaussian design $G$, then it will also be satisfied by $\hat{\mu}_A$ for a general non-Gaussian design $A$ with independent entries. In particular, we show that with a good enough $\ell_\infty$ bound for the regression estimator $\hat{\mu}_A$, any `structural property’ that can be detected via the CGMT for $\hat{\mu}_G$ also holds for $\hat{\mu}_A$ under a general design $A$ with independent entries. As a proof of concept, we demonstrate our new universality framework in three key examples of regularized regression estimators: the Ridge, Lasso and regularized robust regression estimators, where new universality properties of risk asymptotics and/or distributions of regression estimators and other related quantities are proved. As a major statistical implication of the Lasso universality results, we validate inference procedures using the degrees-of-freedom adjusted debiased Lasso under general design and error distributions. This talk is based on joint work with Yandi Shen (Chicago).

Nov 18: Melih Iseri (USC)

Set Valued HJB Equations

In this talk we introduce a notion of set valued PDEs. The set values have been introduced for many applications, such as time inconsistent stochastic optimization problems, multivariate dynamic risk measures, and nonzero sum games with multiple equilibria. One crucial property they enjoy is the dynamic programming principle (DPP). Together with the set valued Itô formula, which is a key component, DPP induces the PDE. In the context of multivariate optimization problems, we introduce the set valued Hamilton-Jacobi-Bellman equations and established its wellposedness. In the standard scalar case, our set valued PDE reduces back to the standard HJB equation.

Our approach is intrinsically connected to the existing theory of surface evolution equations, where a well-known example is mean curvature flows. Roughly speaking, those equations can be viewed as first order set valued ODEs, and we extend them to second order PDEs. Another difference is that, due to different applications, those equations are forward in time (with initial conditions), while we consider backward equations (with terminal conditions).

November 25: [Thanksgiving break]

TBD

December 2: Uwe Schmock (TU Wien)

We consider stochastic optimization problems in discrete time under distributional constraints. These problems are motivated by actuarial science, in particular to treat unit-linked insurance products with guarantees. They can also serve as benchmark models to account for customer behaviour, when the treatment as American option is not appropriate. The basic mathematical set-up is an adapted stochastic process (interpreted as pay-outs) and (possibly randomized) stopping times to optimize the expected pay-out. The difference to classical optimal stopping problems is our constraint concerning the distribution of the stopping times or, more generally, the adapted random probability measures. For these distribution-constrained optimization problems we prove the existence of an optimal strategy; the basic assumptions are suitable moment conditions. In special cases, optimal strategies are identified explicitly. Time permitting, also a continuous-time variant will be discussed. (The main part of this talk is based on joint work

---

January 14:

February 4: Allan Sly (Princeton)

Spread of infections in random walkers

We consider a class of interacting particle systems with two types, A and B which perform independent random walks at different speeds. Type A particles turn into type B when they meet another type B particle. This class of systems includes models of infections and multi-particle diffusion limited aggregation. I will describe new methods to understand growth processes in such models.

February 11: Thibaut Mastrolia (Berkeley)

Market Making and incentives design in the presence of a dark pool

We consider the issue of a market maker acting at the same time in the lit and dark pools of an exchange. The exchange wishes to establish a suitable fees policy to attract transactions on its venues. We first solve the stochastic control problem of the market maker without the intervention of the exchange. Then we derive the equations defining the optimal contract to be set between the market maker and the exchange. This contract depends on the trading flows generated by the market maker’s activity on the two venues. In both cases, we show existence and uniqueness, in the viscosity sense, of the solutions of the Hamilton-Jacobi-Bellman equations associated with the market maker and exchange’s problems. We finally design deep reinforcement learning algorithms enabling us to efficiently approximate the optimal controls of the market maker and the optimal incentives to be provided by the exchange.

Thursday, February 17: Nike Sun (MIT), 1PM PST

NOTE THE NONSTANDARD DAY AND TIME

Generalized Ising perceptron models

The perceptron is a toy model of a single-layer neural network that “stores” a collection of given patterns. We consider the model on the N-dimensional discrete cube with M=N*alpha patterns, with a general activation function U that is bounded above. For U bounded away from zero, or U a one-sided threshold function, it was shown by Talagrand (2000, 2011) that for small alpha, the free energy of the model converges in the large-N limit to the replica symmetric formula conjectured in the physics literature (Krauth and Mezard, 1989). We give a new proof of this result, which covers the more general class of all functions U that are bounded above and satisfy a certain variance bound.
Based on joint works with Jian Ding, Erwin Bolthausen, Shuta Nakajima, and Changji Xu.

 

Thursday, February 24: Josh Frisch (ENS), 12PM PST

NOTE THE NONSTANDARD DAY AND TIME

Harmonic functions on Linear Groups

The Poisson Boundary of a group is a probabilistic object which serves a dual role. It represents the space of asymptotic trajectories a random walk might take and it represents the possible space of bounded harmonic functions on a group. In this Talk I will give an introduction to the Poisson Boundary with emphasis on the question of when it is trivial or not. I will emphasize how this question depends on properties of the acting group. In particular I will discuss the case of linear groups. This is Joint work with Anna Erschler.

March 4: Shirshendu Ganguly (Berkeley)

Fractal geometry in models of random growth 

 

March 11: Andrew Ahn (Cornell)

Universality for Lyapunov Exponents of Random Matrix Products

Consider the discrete-time process formed by the singular values of products of random matrices, where time corresponds to the number of matrix factors. It is known due to Oseledets’ theorem that under general assumptions, the Lyapunov exponents converge as the number of matrix factors tend to infinity. In this talk, we consider random matrices with distributional invariance under right multiplication by unitary matrices, which include Ginibre matrices and truncated unitary matrices. The corresponding singular value process is Markovian with additional structure that admits study via integrable probability techniques. In this talk, I will discuss recent results, including joint work with Roger Van Peski, on the Lyapunov exponents in the setting where the number M matrix factors tend to infinity simultaneously with matrix sizes N. When this limit is tuned so that M and N grow on the same order, the limiting Lyapunov exponents can be described in terms of Dyson Brownian motion with a special drift vector, which in turn can be linked to a matrix-valued diffusion on the complex general linear group. We find that this description is universal, under general assumptions on the spectrum of the matrix factors.

March 18 [no talk, spring break]

March 25: Sangchul Lee (USC)

Pollution-sensitivity of bootstrap percolation

April 1: Rachel Wang (Sydney)

Global community detection using individual-centered partial networks

In statistical network modeling and inference, we often assume either the full network is available or multiple subgraphs can be sampled to estimate various global properties of the full network. However, in a real social network, people frequently make decisions based on their local view of the network alone. In this paper, we consider a partial information framework that characterizes the local network centered at a given individual by path length (or knowledge depth $L$) and gives rise to a partial adjacency matrix. Under $L=2$, we focus on the problem of (global) community detection using the popular stochastic block model (SBM) and its degree-corrected variant (DCSBM). We derive general properties of the eigenvalues and eigenvectors from the major term of the partial adjacency matrix and propose new spectral-based community detection algorithms for these two types of models, which can achieve almost exact recovery under appropriate conditions. Our settings in the DCSBM also allow us to interpret the efficiency of clustering using neighborhood features of the central node. Using simulated and real networks, we demonstrate the performance of our algorithms in inferring global community memberships using a partial network. In particular, we show that the clustering accuracy indicates different global structure is visible to different individuals.

Thursday, April 7: Ivan Corwin (Columbia), 12PM PST

NOTE THE NONSTANDARD DAY AND TIME

The ASEP speed process

Consider the asymmetric simple exclusion process (ASEP) on Z started with particles at negative integer sites, holes at positive integer sites and a lone second class particle at the origin. We prove that almost surely the second class particle achieves a limiting velocity as time goes to infinity which is uniform on the interval [-1,1]. This enables us to construct the ASEP speed process. Our work positively resolves a conjecture of Amir, Angel and Valko and extends the TASEP result of Mountford and Guiol. We rely on a combination of probabilistic couplings (in particular one due to Rezakhanlou) and effective hydrodynamic results (that we prove using tools from integrable probability). This is joint work with Amol Aggarwal and Promit Ghosal.

Thursday, April 14: Amol Aggarwal (Columbia) 12PM PST

NOTE THE NONSTANDARD DAY AND TIME

Universality Results in Random Lozenge Tilings

The statistical behavior of random tilings of large domains has been an intense topic of mathematical research for decades, partly since they highlight a central phenomenon in physics: local behaviors of highly correlated systems can be very sensitive to boundary conditions. Indeed, a salient feature of random tiling models is that the local densities of tiles can differ considerably in different regions of the domain, depending on the shape of the domain. Thus, a question of interest is how the shape of the domain affects the statistics of a random tiling. A general prediction in this context is that, while the family of possible domains is infinite-dimensional, the limiting statistics should only depend on a few parameters. In this talk, we will explain this universality phenomenon in the context of random lozenge tilings (equivalently, the dimer model on the hexagonal lattice). Various possible limiting local statistics can arise, depending on whether one probes the bulk of the domain; the edge of a facet; or the boundary of the domain. We will describe recent works that verify the universality of these statistics in each of these regimes.

April 22: J. E. Paguyo (USC)

Cycle structure of random parking functions

Parking functions were introduced by Konheim and Weiss in their study of the hash storage structure, and have since found many applications in combinatorics, probability, and computer science. Consider $n$ cars, each with a preferred parking spot in a one-way street with $n$ spots. Each car drives to its preferred spot and parks if possible, and otherwise takes the next available spot if it exists. A sequence of preferences is a parking function if all cars are able to park. In this talk, we discuss various combinatorial and probabilistic properties of random parking functions. In particular, we show that the joint distribution of cycle counts converges to a process of independent Poisson random variables. This partially answers a question of Diaconis and Hicks. Our proof uses a multivariate Stein’s method via exchangeable pairs, which also provides rates of convergence.

April 29: Robert Webber (Caltech)

Randomized low-rank approximation with higher accuracy and reduced costs

Randomized low-rank matrix approximation is one of the great success stories of randomized numerical linear algebra. It is a fast, scalable approach that has been widely adopted in scientific computing. However, the approach is most successful at approximating matrices with quickly decaying singular values since there can be significant random errors when the singular values decay slowly. Our ongoing work improves the accuracy of randomized low-rank matrix approximation for matrices with slow singular value decay. We study an emerging approach called ‘randomized block Krylov iteration’, which builds a rich approximation space from the output of repeated matrix-matrix multiplications. Our contributions are two-fold: first, we derive an efficient implementation of randomized block Krylov iteration that reduces the standard runtime by a half, and second, we establish error bounds that quantify the rapid convergence of randomized block Krylov iteration, demonstrating its advantage over alternative methods.

---

August 27:

September 3: Mehtaab Sawhney (MIT)

Approximate counting and sampling via local central limit theorems

We give deterministic approximate counting algorithms for the number of matchings and independent sets of a given size in bounded degree graphs. For matchings, the algorithm applies to any size bounded away from the maximum by a constant factor; for independent sets the algorithm applies to sizes up to the NP-hardness threshold. Our results are based on exploiting local central limit theorems as an algorithmic tool. For our results for independent sets, we prove a new local central limit theorem for the hard-core model.  (with Vishesh Jain, Will Perkins, and Ashwin Sah)

September 24: Sourav Chatterjee (Stanford)

Local KPZ growth in a class of random surfaces

One of the main difficulties in proving convergence of discrete models of surface growth to the Kardar-Parisi-Zhang (KPZ) equation in dimensions higher than one is that the correct way to take a scaling limit, so that the limit is nontrivial, is not known in a rigorous sense. The same problem has so far prevented the construction of nontrivial solutions of the KPZ equation in dimensions higher than one. To understand KPZ growth without being hindered by this issue, I will introduce a new concept in this talk, called “local KPZ behavior”, which roughly means that the instantaneous growth of the surface at a point decomposes into the sum of a Laplacian term, a gradient squared term, a noise term, and a remainder term that is negligible compared to the other three terms and their sum. The main result is that for a general class of surfaces, which contains the model of directed polymers in a random environment as a special case, local KPZ behavior occurs under arbitrary scaling limits, in any dimension.

October 1: Xinyu Wu (CMU)

Separations between classical and quantum computational complexity through stochastic calculus

The Forrelation problem is: given two random Boolean vectors x and y, decide if x and y are uniformly random or if x is uniformly random and y is the Walsh-Fourier transform of x. Variants of this problem show up as examples of functions hard for some classical complexity classes but easy for the corresponding quantum complexity classes. In this talk, I will present an approach to analyze the complexity of the Forrelation problem using techniques from stochastic calculus. Using this technique, I will give some simplified proofs of recent results by Raz-Tal and Girish-Raz-Zhan.

October 8: Ankur Moitra (MIT)

Rethinking Robustness: From Classification to Contextual Bandits

What does it mean for a learning algorithm to be robust? We could hope to tolerate adversarial corruptions, but this makes many simple learning tasks computationally intractable. We could assume a particular stochastic model for noise, but then our algorithms might be overtuning to this one distribution, which was only meant to be a simplifying assumption.

In this talk we will revisit some classic learning problems, like learning halfspaces, online regression and contextual bandits, in models that blend worst-case and average-case noise. We will give simple twists on old algorithms that allow them to enjoy strong provable robustness guarantees. Finally we explore some intriguing connections between robustness and fairness.

October 15: [no talk]  [Fall break]

October 22: Song Mei (UC Berkeley)

Local convexity of the TAP free energy and AMP convergence for Z2-synchronization

October 29: Deeparnab Chakrabarty (Dartmouth)

A polynomial lower bound on the number of rounds for efficient submodular function minimization

Submodular function minimization (SFM)  is a fundamental discrete optimization problem generalizing problems such as minimum cut problems in graphs and hypergraphs, and the matroid intersection problem. It is well-known and remarkable that a submodular function on an N-element universe can be minimized using only poly(N) evaluation queries. However, all such efficient algorithms have poly(N) rounds of adaptivity. A natural question is whether one can get efficient parallel SFM algorithms with much fewer rounds of adaptivity. Recently, in STOC 2020, Balkanski and Singer proved an Omega(log N/log log N) lower bound on the rounds of adaptivity. However, it left open the possibility of a polylogarithmic depth efficient algorithm; such algorithms are indeed known for efficient (approximate) submodular function *maximization* versions.

November 5: Gabor Lugosi (ICREA)

Learning the structure of graphical models by covariance queries

The dependence structure of high-dimensional distributions is often modeled by graphical models. The problem of learning the graph underlying such distributions has received a lot of attention in statistics and machine learning. In problems of very high dimension, it is often too costly even to store the sample covariance matrix. We propose a new model in which one can query single entries of the covariance matrix. We propose computationally efficient algorithms for structure recovery in Gaussian graphical models with computational complexity that is quasi-linear in the dimension. We present algorithms that work for trees and, more generally, for graphs of small treewidth. The talk is based on joint  work with Jakub Truszkowski, Vasiliki Velona, and Piotr Zwiernik.

Thursday, November 11, 10AM: Afonso Bandeira (ETH Zurich)

NOTE THE NONSTANDARD DAY AND TIME

Noncommutative Matrix Concentration Inequalities

Matrix Concentration inequalities for the spectrum of random matrices, such as Matrix Bernstein, have played an important role in many areas of pure and applied mathematics. These inequalities are intimately related to the celebrated noncommutative Khintchine inequality of Lust-Piquard and Pisier. In this talk we leverage ideas from Free Probability to remove the dimensional dependence in the noncommutative Khintchine in a range of instances, yielding sharp bounds in many settings of interest. As a byproduct we develop non-assymptotic matrix concentration inequalities that capture non-commutativity (or, to be more precise, “freeness”).
Joint work with March Boedihardjo and Ramon van Handel, more information at arXiv:2108.06312 [math.PR].

November 19: Nina Holden (ETH Zurich/ NYU) [talk via Zoom]

Conformal welding in Liouville quantum gravity: recent results and applications

November 26: [no talk] [Thanksgiving]

December 3: Melih Iseri (USC)

Set Values for Mean Field Games

---

January 15: Steven Heilman (USC)

Three Candidate Plurality is Stablest for Small Correlations

Suppose we model n votes in an election between two candidates as n i.i.d. uniform random variables in {-1,1}, so that 1 represents a vote for the first candidate, and -1 represents a vote for the other candidate.  Then, for each vote, we flip a biased coin (with fixed probability larger than 1/2 of landing heads).  If the coin lands tails, the vote is changed to the other candidate.  In an election where each voter has a small influence on the election’s outcome, and each candidate has an equal chance of winning, the majority function best preserves the election’s outcome, when comparing the original election vote to the corrupted vote.  This Majority is Stablest Theorem was proven in 2005 by Mossel-O’Donnell-Oleszkiewicz.  The corresponding statement for elections between three or more voters has remained open since its formulation in 2004 by Khot-Kindler-Mossel-O’Donnell.  We show that Plurality is Stablest for elections with three candidates, when the original and corrupted votes have a sufficiently small correlation.  In fact, this result is a corollary of a more general structure theorem that applies for elections with any number of candidates and any correlation parameter.

(joint with Alex Tarter)

January 22: Jimmy He (Stanford University)

Random walks on finite fields with deterministic jumps

Recently, Chatterjee and Diaconis showed that most bijections, if applied between steps of a Markov chain, cause the resulting chain to mix much faster. However, explicit examples of this speedup phenomenon are rare. I will discuss recent work studying such walks on finite fields where the bijection is algebraically defined, and give a near-linear mixing time. This work gives a large collection of examples where this speedup phenomenon occurs. These walks can be seen as a non-linear analogue of the Chung-Diaconis-Graham process, where the bijection is multiplication by a non-zero element of the finite field.

January 29: Hoi Nguyen (Ohio State University)

Universality results for the cokernels of random integral matrices

For various general random matrix models with integral entries we discuss the probability that the cokernels are isomorphic to a given finite abelian group, or when they are cyclic. We will show that these statistics are asymptotically universal, depending only on the symmetry class of the matrices.

Based on joint works with M. M. Wood.

February 5: Dmitrii Ostrovskii (USC)

Near-Optimal Model Discrimination

In the standard setup of parametric M-estimation with convex loss, we consider two population risk minimizers associated with two possible distributions of a random observation, and then ask the following question:

February 19: Nick Cook (Duke)

March 5: Paata Ivanisvili (NC State)

Exponential integrability for Gaussian measures

Let X be the standard Gaussian random vector. In this talk I will discuss conditions on a real valued test function f such that the exponential integral E exp(f(X)) is finite. Talagrand showed that if the exponential of the square of the gradient of f divided by 2 is integrable with respect to the standard Gaussian measure then this guarantees  finiteness of E exp(f(X)). In the joint work with Ryan Russell we sharpen this result, and we also provide  quantitative dimension independent bounds relating these two quantities.

March 12: Movie Screening: Secrets of the Surface, The Mathematical Vision of Maryam Mirzakhani [Wellness Day]

March 19: Jianfeng Zhang (USC)

Mean Field Game Master Equations with Non-separable Hamiltonians and Displacement Monotonicity

It is well known that the monotonicity condition is crucial for the global wellposedness of mean field game master equations. In the literature the monotonicity condition is proposed only for separable Hamiltonians. In this talk, we propose a structural condition on non-separable Hamiltonians, in the spirit of the so-called displacement monotonicity condition, and then establish the global wellposedness for such master equations.The talk is based on a joint work with Gangbo, Meszaros, and Mou.

April 9: Arash A. Amini (UCLA)

Adjusted chi-square test for degree-corrected block models

We propose a goodness-of-fit test for degree-corrected stochastic block models (DCSBM). The test is based on an adjusted chi-square statistic for measuring equality of means among groups of $n$ multinomial distributions with $d_1,\dots,d_n$ observations. In the context of network models, the number of multinomials, $n$, grows much faster than the number of observations, $d_i$, corresponding to the degree of node $i$, hence the setting deviates from classical asymptotics. We show that a simple adjustment allows the statistic to converge in distribution, under null, as long as the harmonic mean of $\{d_i\}$ grows to infinity.

When applied sequentially, the test can also be used to determine the number of communities. The test operates on a (row) compressed version of the adjacency matrix, conditional on the degrees, and as a result is highly scalable to large sparse networks. We incorporate a novel idea of compressing the rows based on a $(K+1)$-community assignment when testing for $K$ communities. This approach increases the power in sequential applications without sacrificing computational efficiency, and we prove its consistency in recovering the number of communities. Since the test statistic does not rely on a specific alternative, its utility goes beyond sequential testing and can be used to simultaneously test against a wide range of alternatives outside the DCSBM family.

The test can also be easily applied to Poisson count arrays in clustering or biclustering applications, as well as bipartite and directed networks. We show the effectiveness of the approach by extensive numerical experiments with simulated and real data. In particular, applying the test to the Facebook-100 dataset, a collection of one hundred social networks, we find that a DCSBM with a small number of communities (say $ < 25$) is far from a good fit in almost all cases. Despite the lack of fit, we show that the statistic itself can be used as an effective tool for exploring community structure, allowing us to construct a community profile for each network.

April 16: Ramon van Handel (Princeton University)

Vector concentration inequalities

How do classical concentration inequalities extend to functions taking values in normed spaces? Such questions arise in various settings (in functional analysis, random matrix theory, etc.), and are generally studied on a case by case basis. In the Gaussian case, however, Pisier discovered a powerful principle that explains in complete generality how vector-valued functions concentrate. Unfortunately, Pisier’s argument appears to be very specific to the Gaussian distribution, and until recently this phenomenon was not known to hold in any other setting.

In this talk, I will explain that Pisier’s principle is much more universal than expected: a completely analogous result holds under the classical (Bakry-Emery) conditions used in the theory of scalar concentration inequalities. Moreover, a modified form of this principle holds also in discrete settings (as was first observed, in the special case of the discrete cube, in joint work with Ivanisvili and Volberg that settled an old conjecture of Enflo in Banach space theory). These new inequalities provide very general tools for establishing concentration
properties of vector-valued functions.

April 23: Tselil Schramm (Stanford University)

Computational Barriers to Estimation from Low-Degree Polynomials

April 30: Mark Rychnovsky (Columbia)   [Wellness Day]

Extreme particles for sticky Brownian motions

Sticky Brownian motions behave as independent Brownian motions when they are separated and interact when they touch, so that the coincidence time has positive Lebesgue measure with positive probability. For a specific sticky interaction we show that as the number of particles, and the time the particles are allowed to evolve are simultaneously sent to infinity, the fluctuations of the extremal particle are given by the GUE Tracy-Widom distribution. The proof involves realizing a specific sticky interaction as the limit of an exactly solvable statistical mechanics model, the Beta random walk in random environment, and using this to derive exact integral formulas.

This is joint work with Guillaume Barraquand.

The $r$-parallel set of a measurable set $A$ is the set of all points whose distance from $A$ is at most $r$. In this talk, we discuss some recent results that establish upper bounds on the Euclidean and Gaussian surface areas of $r$-parallel sets. We also discuss a reverse form of the Brunn-Minkowski inequality for $r$-parallel sets, and as an aside a reverse entropy power inequality for Gaussian-smoothed random variables. We will conclude by presenting applications of our results to some problems of interest in theoretical machine learning.

Sep 04: Zhou Fan (Yale University)

This talk will present the methods and procedures used to produce the first image of a black hole from the Event Horizon Telescope, as well as discuss future developments for black hole imaging. It had been theorized for decades that a black hole would leave a “shadow” on a background of hot gas. Taking a picture of this black hole shadow would help to address a number of important scientific questions, both on the nature of black holes and the validity of general relativity. Unfortunately, due to its small size, traditional imaging approaches require an Earth-sized radio telescope. In this talk, I discuss techniques the Event Horizon Telescope Collaboration has developed to photograph a black hole using the Event Horizon Telescope, a network of telescopes scattered across the globe. Imaging a black hole’s structure with this computational telescope required us to reconstruct images from sparse measurements, heavily corrupted by atmospheric error. The talk will also discuss future developments, including new imaging techniques and how we are developing machine learning methods to help design future telescope arrays.

We examine statistical properties of integers when they are sampled using the Riemann zeta distribution and compare to similar properties when sampled according to “uniform” or harmonic distributions.  For example, as the variable in the Riemann zeta function approaches 1, central limit theorem, large and moderate deviations for the distinct number of prime factors for the sampled integer can be readily derived.

Sep 25: Philippe Sosoe (Cornell University)

Oct 2: James Lee (University of Washington)

Scaling exponents in stationary random media

Oct 9: Josh Starmer (StatQuest)

The Elements of StatQuest: How to clearly explain complicated sounding things.

Oct 16: Yosi Rinott (Hebrew University of Jerusalem)

215PM START. NON-STANDARD TIME

Statistical Aspects of Quantum Supremacy Demonstration

Quantum supremacy as presented by Google’s team in 2019, and as it is expected to be in the near future, consists of demonstrating that a quantum circuit is capable of generating bitstrings  from a distribution (which is itself random) that is considered hard to simulate on classical computers. This is called a sampling task (which is impractical for now). Quantum computers perform such a task with a great deal of noise, and  efficient statistical analysis is needed in order is to verify that indeed the right distribution was sampled, and to estimate the noise level or fidelity.  Some interesting statistical questions arise.  (joint with Gil Kalai)

Preprint available on arXiv: arXiv:1911.05122.

Nonzero sum games typically have multiple Nash equilibriums (or no equilibrium), and unlike the zero sum case, they may have different values at different equilibriums. Instead of focusing on the existence of individual equilibriums, we study the set of values over all equilibriums, which we call the set value of the game. The set value is unique by nature and always exists (with possible value $\emptyset$). Similar to the standard value function in control literature, it enjoys many nice properties such as regularity, stability, and more importantly the dynamic programming principle. We shall also discuss the possible extension to mean field games. The talk is based on a joint work with Feinstein and Rudloff as well as an ongoing joint work with Iseri.

Deep Learning is at the center of AI and a myriad of applications ranging from medical imaging to games. I will demonstrate some of these applications, briefly review the history of the field, and then discuss the mathematical foundations of deep learning, with an emphasis on recent progress (capacity theory, deep learning channel theory) and open questions.

We analyze a popular score-based DAG estimator that has been the subject of extensive empirical inquiry in recent years and is known to achieve state-of-the-art results. We give explicit finite-sample bounds that are valid in high-dimensional regime. The estimator is based around a difficult nonconvex optimization problem, and its analysis may be of independent interest given recent development in nonconvex optimization in machine learning. Our analysis introduces a novel strategy for reducing the nonconvex program to a polynomial collection of tractable neighborhood regression problems by exploiting a useful lattice property of conditional independence in the Gaussian case. This strategy overcomes the drawbacks of existing approaches, which either fail to guarantee structure consistency in high-dimensions (i.e. learning the correct graph with high probability), or rely on strong assumptions. We will discuss some related methods and algorithms developed recently for structure learning of DAGs.

In this talk, we introduce the notion of scaled minimaxity for sparse estimation in the high-dimensional linear regression model. Fixing the scale of the signal-to-noise ratio, we prove that the estimation error can be much smaller than the global minimax error. Taking advantage of the interplay between estimation and support recovery we achieve optimal performance for both problems simultaneously under orthogonal designs. We also construct a new optimal estimator for scaled minimax sparse estimation. Sharp results for the classical minimax risk are recovered as a consequence of our study.

For general designs, we first connect scaled minimax sparse estimation to the problem of de-biaising convex penalized estimators. Then, we introduce a new analysis framework based on non-convex algorithmic regularization where previous sharp results hold. The procedure we present achieves optimal statistical accuracy faster than, for instance, classical algorithms for the Lasso and eliminates the usual bias term whenever it is possible. As a consequence, we present a new iterative algorithm for high-dimensional linear regression that is scaled minimax optimal, fast and adaptive.

The Poisson boundary of a random walk on a group captures the uncertainty in the walk’s asymptotic behavior. It has long been known that all commutative groups are Choquet-Deny groups: namely, they have trivial Poisson boundaries for every random walk. More generally, it has been shown that all virtually nilpotent groups are Choquet-Deny. I will present a recent result showing that in the class of finitely generated groups, only virtually nilpotent groups are Choquet-Deny. This proves a conjecture of Kaimanovich and Vershik (1983), who suggested that groups of exponential growth are not Choquet-Deny. Our proof does not use the superpolynomial growth property of non-virtually nilpotent groups, but rather that they have have quotients with the infinite conjugacy class property (ICC). Indeed, we show that a countable discrete group is Choquet-Deny if and only if it has no ICC quotients.

   Two of cornerstone models of random matrix theory are the Gaussian Unitary Ensemble and the Ginibre Ensemble; both are matrices with Gaussian entries and (mostly) independent entries.  The analysis of the former began the modern field of random matrix theory with Wigner’s work in the 1950s.  The latter took 10 years longer, due to the far more subtle relationship between entries and eigenvalues of a non-normal matrix.

   From a dynamical viewpoint, these two ensembles can (and should!) be viewed as endpoints of Brownian motions: the former on the space of Hermitian matrices, the latter on the space of all matrices.  Both of these linear spaces happen to be Lie algebras: of the unitary group U(N) and the general linear group GL(N).  The Lie structure is one of the main reasons the eigenvalues have “nice” behavior.

   It is natural to study the corresponding question of the behavior of eigenvalues of Brownian motion on the Lie groups U(N) and GL(N).  Bulk (and some finer) statistics are now well-understood in the unitary case, but the general linear Brownian motion has proved a greater challenge.  In this talk, I will focus on my very recent joint work with Driver and Hall, identifying the large-N limit of the empirical eigenvalue distribution of the Brownian motion on GL(N).

   This talk will feature lots of pictures.

Optimization and sampling are arguably the computational backbones of Frequentist and Bayesian statistics respectively. In this talk the use of Stein’s identity for performing stochastic Zeroth-Order (ZO) non-convex optimization and sampling will be discussed. Specifically, we consider the case when the function (or density) under consideration is not available to us analytically, rather we are able to only obtain noisy evaluations. Using Stein’s identity, techniques for estimating the gradient and Hessian of a function (or density) will be introduced. Based on this, the following algorithms and the corresponding theoretical results will be discussed: (i) ZO stochastic gradient method in high-dimensions (ii) ZO Newton’s method for escaping saddle points (iii) ZO Euler and Ozaki discretized (Kinetic) Langevin Monte Carlo sampling. Some open questions about the proposed ZO Hessian matrix estimator and its connections to random matrix theory will also be discussed. References: https://arxiv.org/pdf/1809.06474.pdf and https://arxiv.org/pdf/1902.01373.pdf

We study a risk-sharing equilibrium where heterogenous agents trade subject to a quadratic transaction costs. The corresponding equilibrium asset prices and trading strategies are characterized by a system of fully-coupled forward-backward stochastic differential equations. We show that a unique solution exists provided that the agents’ preferences are sufficiently similar.  (Joint work in progress with Martin Herdegen and Dylan Possamai)

The most fundamental kind of functions studied in computer science are Boolean functions. Most Boolean functions oscillate a lot, which is analogous to the fact that “most” continuous functions on R are nowhere differentiable. A “smooth” Boolean function can be generated by taking the sign of some polynomial of low degree in n variables. Such functions are called polynomial threshold functions, and they are widely used in machine learning as classification devices. Surprisingly, we do not know how many low-degree polynomial threshold functions there exist! An approximate answer to this question has been known only for polynomials of degree 1, i.e. for linear functions. In a recent joint work with Pierre Baldi, we found a way to approximately count polynomial threshold functions of any fixed degree. This solves a problem of M. Saks that goes back to 1993 and much earlier. Our argument draws insights from analytical number theory, additive combinatorics, enumerative combinatorics, probability and discrete geometry. I will describe some of these connections, focusing particularly on a beautiful interplay of zeta and Mobius functions in number theory, hyperplane arrangements in enumerative combinatorics and random tensors in probability theory.

We study a two-type annihilating system in which particles are placed with equal density on the integer lattice. Particles perform simple random walk and annihilate when they contact a particle of different type. The occupation probability of the origin was known to exhibit anomalous behavior in low-dimension when particles have equal speeds. Describing the setting with asymmetric speeds has been open for over 20 years. We prove a lower bound that matches physicists’ conjectures and discuss partial progress towards an upper bound. Joint with Michael Damron, Hanbaek Lyu, Tobias Johnson, and David Sivakoff.

The Gaussian isoperimetric inequality states that if we want to partition R^n into two sets with prescribed Gaussian measure while minimizing the Gaussian surface area of the interface between the sets, then the optimal partition is obtained by cutting R^n with a hyperplane. We prove an extension to more than two parts. For example, the optimal way to partition R^3 into three parts involves cutting along three rays that meet at 120-degree angles at a common point. This is the Gaussian analogue of the famous Double Bubble Theorem in Euclidean space, which describes the shape that results from blowing two soap bubbles and letting them stick together.

I will talk about the beta orbital corners process, a natural interpolation (on the dimension of the base field) of orbital measures from random matrix theory. The new result is the convergence in probability of finitely many levels of the orbital corners process to a Gaussian process. Our approach is based on the study of asymptotics of a class of special functions (called the multivariate Bessel functions) via explicit formulas.

This talk discusses a general framework for exploiting the sparsity information in two-sample multiple testing problems. We propose to first construct a covariate sequence, in addition to the usual primary test statistics, to capture the sparsity structure, and then incorporate the auxiliary covariates in inference via a three-step algorithm consisting of grouping, adjusting and pooling (GAP). The GAP procedure provides a simple and effective framework for information pooling. An important advantage of GAP is its capability of handling various dependence structures such as those arise from multiple testing for high-dimensional linear regression, differential correlation analysis, and differential network analysis. We establish general conditions under which GAP is asymptotically valid for false discovery rate control, and show that these conditions are fulfilled in a range of applications. Numerical results demonstrate that existing methods can be much improved by the proposed framework. An application to a breast cancer study for identifying gene-gene interactions will be discussed if time permits.

Hamiltonian Monte Carlo (HMC) is a powerful sampling algorithm employed by several probabilistic programming languages. Its fully automatic implementations have made HMC a standard tool for applied Bayesian modeling. While its performance is often superior to alternatives under a wide range of models, one prominent weakness of HMC is its inability to handle discrete parameters. In this talk, I present discontinuous HMC, an extension that can efficiently explore discrete spaces involving ordinal parameters as well as target distributions with discontinuous densities. The proposed algorithm is based on two key ideas: embedding of discrete parameters into a continuous space and simulation of Hamiltonian dynamics on a piecewise smooth density function. The latter idea has been explored under special cases in the literature, but the extensions introduced here are critical in turning the idea into a general and practical sampling algorithm. When properly-tuned, discontinuous HMC is guaranteed to outperform a Metropolis-within-Gibbs algorithm as the two algorithms coincide under a specific (and sub-optimal) implementation of discontinuous HMC. We apply our algorithm to challenging posterior inference problems to demonstrate its wide applicability and competitive performance.

    To make the talk more accessible, I will start my talk with a review of the essential ideas and notions behind HMC. A brief review of Bayesian inference and Markov chain Monte Carlo will also be provided.