After the 2007-09 financial crisis, there has been a growing interest in measuring systemic risk, broadly defined as the risk of widespread failure of the entire financial system. In a highly interlinked financial market, a large body of recent works have proposed to use network connectivity amongst financial institutions to assess their systemic importance. In this work, we will present some graphical modeling techniques for learning interactions among the components of a large dynamic system from multivariate time series data, where the core idea is to learn from lead-lag relationships (commonly known as Granger causality) between time series in addition to their co-movements. In the context of modeling networks of interactions amongst financial institutions and measuring systemic risk, we will demonstrate how linear and quantile-based Granger causality analyses using vector autoregressive (VAR) models can provide insight. We will present some non-asymptotic statistical theory for our proposed algorithms, estimate these graphical models using stock returns of large financial institutions in U.S. and India, and demonstrate their usefulness in detecting systemically risky periods and institutions. This is joint work with Kara Karpman and Diganta Mukherjee.

Bio:

I am broadly interested in developing statistical machine learning methods for structure learning and prediction of complex, high-dimensional systems arising in biological and social sciences. I am currently working in two areas: (a) network modeling of high-dimensional time series; and (b) detecting high-order interactions in complex biological systems using randomized tree ensembles. I also work closely with scientists and economists on a wide range of problems including prostate cancer progression, large scale metabolomics, and systemic risk monitoring in financial markets. Before joining Cornell, I was a postdoctoral scholar (2014-2016) in the Department of Statistics, UC Berkeley and the Biosciences Division, Lawrence Berkeley National Laboratory . I received my PhD (2014) from the Department of Statistics, University of Michigan , and my bachelors (2006) and masters (2008) in Statistics from Indian Statistical Institute, Kolkata.

The fundamental problems of pricing high-dimensional path-dependent options and optimal stopping are central to applied probability, financial engineering, operations research, and stochastic control. Modern approaches, often relying on ADP, simulation, and/or duality, typically have limited rigorous guarantees, which may scale poorly and/or require previous knowledge of good basis functions. A key difficulty with many approaches is that to yield stronger guarantees, they would necessitate the computation of deeply nested conditional expectations, with the depth scaling with the time horizon T.

We overcome this fundamental obstacle by providing an algorithm which can trade-off between the guaranteed quality of approximation and the level of nesting required in a principled manner. We develop a novel pure-dual approach, inspired by a connection to network flows. This leads to a representation for the optimal value as an infinite sum for which : 1. each term is the expectation of an elegant recursively defined infimum; 2. the first k terms only require k levels of nesting; and 3. truncating at the first k terms yields a (normalized) error of 1/k. This enables us to devise simple randomized and data-driven algorithms and stopping strategies whose runtimes are effectively independent of the dimension, beyond the need to simulate sample paths of the underlying process. Our method allows one to elegantly trade-off between accuracy and runtime through a parameter epsilon controlling the associated performance guarantee (analogous to the notion of PTAS in the theory of approximation algorithms), with computational and sample complexity both polynomial in T (and effectively independent of the dimension) for any fixed epsilon, in contrast to past methods typically requiring a complexity scaling exponentially. Joint work with Ph.D. student Yilun Chen.

Bio:

David A. Goldberg (https://people.orie.cornell.edu/dag369/ ) is an Associate Professor in Cornell's ORIE department. Previously, he was the A. Russell Chandler III Associate Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. He received his Ph.D. in Operations Research at MIT in 2011, and his B.S. in Computer Science (minors in Operations Research and Applied Math) from Columbia University in 2006. Goldberg’s research is in applied probability, on topics including : optimal stopping, control, and options pricing; inventory and queueing models; asymptotic analysis and large deviations; combinatorial optimization; robust optimization; and multi-arm bandits. His work has been recognized with accolades including an NSF CAREER award, 2018 INFORMS Finance Student Paper Competition finalist, 2015 Nicholson Competition first place, 2015 JFIG Competition second place, and 2014 MSOM and 2010 Nicholson Competitions finalist. He is also an associate editor for the journals Operations Research, Stochastic Models, and Queueing Systems, and past member of the INFORMS Applied Probability Society Council.

Optimal transport (OT), and in particular the Wasserstein distance, has seen a surge of interest and applications in machine learning (ML). This popularity is driven by many advantageous properties of the Wasserstein distance, such as its robustness to mismatched supports, the fact it is a metric on the space of probability measures, and that it metrizes weak* convergence. At the heart of ML is the ability to empirically approximate a probability measure using data generated from it. Unfortunately, empirical approximation under Wasserstein distances suffers from a severe `curse of dimensionality', namely, convergence at rate n^{-1/d}, which drastically deteriorate with dimension. Given high dimensionality of modern ML tasks, this is highly problematic. As a result, entropically regularized OT has become a common workaround, but while it enjoys fast algorithms and better statistical properties, it looses the Wasserstein metric structure.

This talk proposes a novel Gaussian-smoothed OT (GOT) framework, that achieves the best of both worlds: preserving the Wasserstein metric structure while alleviating the empirical approximation curse of dimensionality. GOT is simply the Wasserstein distance between the measures of interest after each is smoothed by (convolved with) an isotropic Gaussian kernel. It inherits all the metric properties of classic Wasserstein distances, and is a well-behaved (continuous and monotonic) function of the Gaussian-smoothing parameter. Furthermore, as the smoothing parameter shrinks to zero, GOT $\Gamma$-converges towards classic OT (with convergence of optimizers), thus serving as a natural extension. For the statistical point of view, empirical approximation under GOT attains a O(n^{-1/2}) convergence rate in all dimensions, thus alleviating the curse of dimensionality. A discussion of how this GOT fast convergence enables measuring information flows in deep neural networks and applications to generative modeling will follow.

Bio:

Ziv Goldfeld is an assistant professor in the School of Electrical and Computer Engineering at Cornell University. Before that, he was a postdoctoral researcher in the Laboratory for Information and Decision Systems (LIDS) at MIT. Ziv received his B.Sc., M.Sc. and Ph.D. in the Department of Electrical and Computer Engineering at Ben Gurion University of the Negev, Israel.

Ziv's research interests include statistical machine learning, information theory, high-dimensional and nonparametric statistic, applied probability and interacting particle systems. Recently, he focused on information-theoretic analysis of deep neural networks (DNNs), convergence rates of empirical measures smoothed by Gaussian kernels, and data storage in stochastic Ising models. Other interest include physical layer security, cooperation in multiuser information-theoretic problems and multiuser channel and source duality.

Ziv is a recipient of the Rothschild postdoctoral fellowship, the Ben Gurion postdoctoral fellowship, the Feder Award, the best student paper award in the IEEE 28th Convention of Electrical and Electronics Engineers in Israel, the Lev-Zion fellowship and the Minerva Short-Term Research Grant.

]]>The need to reason about uncertainty in large, complex, and multi-modal datasets has become increasingly common. The ability to transform samples from one distribution P to another distribution Q enables the solution to many problems in operations research. Performing such transformations, in general, still comprises computational difficulties, especially in high dimensions. Here, we consider the problem of computing such "measure transport maps" efficiently and at scale. Under the mild assumptions that P need not be known but can be sampled from, that the density of Q is known up to a proportionality constant, and that Q is log-concave, we provide a convex optimization formulation. This approach, involving sequentially solving quadratically regularized relative entropy minimization problems, is inspired by variational formulations in non-equilibrium thermodynamics and allows for sequential construction of transport maps with exponential convergence in relative entropy. We provide an empirical risk minimization formulation using maps parametrized by polynomial chaos along with an iterative and convergent algorithm that has been efficiently implemented in GPUs and Amazon Web Services architectures. We provide examples of this framework, within the context of healthcare applications pertaining, to Bayesian inference, Thompson sampling for online decision making, and generative modeling.

Bio:

Todd P. Coleman received B.S. degrees in electrical engineering (summa cum laude), as well as computer engineering (summa cum laude) from the University of Michigan. He received M.S. and Ph.D. degrees from MIT in electrical engineering (minor in mathematics), and did postdoctoral studies at MIT in neuroscience. He is currently a Professor in the Department of Bioengineering at UCSD, where he directs the Neural Interaction Laboratory. Dr. Coleman’s research is very multi-disciplinary, using tools from applied probability, physiology, and bioelectronics. His research spans from developing fundamental information theory and machine learning techniques to partnering with clinicians and solving important healthcare challenges. He has been selected as a National Academy of Engineering Gilbreth Lecturer, as a TEDMED speaker, and as a Fellow of the American Institute for Medical and Biological Engineering.

Spreading processes, as in infectious diseases, social behaviors, or computer viruses, impact biological, social, and technological systems. To manage spreading in a systematic way, models are needed that predict spreading dynamics in terms of a few parameters. We study a spreading model in which interacting agents can adapt susceptibility to a spreading process after first exposure. The model is motivated by an investigation of foraging behavior by desert harvester ants. Using an analytically tractable model that predicts behaviors exhibited in field data, we showed how resilience of colony foraging rates to changing temperature and humidity can be explained by ants modifying their susceptibility to the spread of foraging, once exposed to outside conditions.

To generalize these results, we propose and analyze a network model with adaptive susceptibility and agent heterogeneity. We show how four dynamic regimes are distinguished by four numbers that depend on network structure and heterogeneity. We prove features of the geometry of solutions that dictate both transient and steady-state possibilities. For example, in the bistable regime, not captured in traditional models, there can be a rapid cascade after a long period of quiescence. We use our analytical results to design control strategies that suppress or promote spreading.

This is joint work with Renato Pagliara and (for the ant foraging study) Deborah Gordon.

Bio:

Naomi Ehrich Leonard is Edwin S. Wilsey Professor of Mechanical and Aerospace Engineering and associated faculty in Applied and Computational Mathematics at Princeton University. She is a MacArthur Fellow, and Fellow of the American Academy of Arts and Sciences, SIAM, IEEE, IFAC, and ASME. She received her BSE in Mechanical Engineering from Princeton University and her PhD in Electrical Engineering from the University of Maryland. Her research is in control and dynamics with application to multi-agent systems, mobile robotic sensor networks, collective animal behavior, and human decision dynamics.

"Bandits with Knapsacks" (BwK) is a general model for multi-armed bandits under supply/budget constraints, with motivating examples ranging from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. The objective now is to minimize the "competitive ratio": the ratio of the benchmark reward to algorithm's reward, as regret minimization is no longer feasible.

We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new algorithm for the stochastic version of the problem, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version, and use it as a subroutine to solve the latter. This approach also leads to several extensions, both for stochastic and adversarial versions.

Joint work with Nicole Immorlica, Karthik A. Sankararaman, and Robert Schapire.

Bio:

Alex Slivkins is a Principal Researcher at Microsoft Research New York City. Previously he was a researcher at MSR Silicon Valley after receiving his Ph.D. from Cornell and a brief postdoc at Brown. His research interests are in algorithms and theoretical computer science, spanning machine learning theory, algorithmic economics, and networks. Alex is particularly interested in exploration-exploitation tradeoff and online machine learning, and their manifestations in mechanism design and human computation. His work has been recognized with the best paper award at ACM EC 2010, the best paper nomination at WWW 2015, and the best student paper award at ACM PODC 2005. He is finishing a book, Introduction to Multi-armed Bandits, to be published with Foundations and Trends in Machine Learning.