ORIE Colloquium: Devavrat Shah (MIT) - Time Series as A Matrix

Location

Frank H. T. Rhodes Hall 253

Description

We consider the task of interpolating and forecasting a time series in the presence of noise and missing data. As the main contribution of this work, we introduce an algorithm that transforms the observed time series into a matrix, utilizes matrix estimation as a black-box to simultaneously recover missing values and de-noise observed entries, and perform linear regression to make predictions. We argue that this method provides meaningful imputation and forecasting for a large class of models: finite sum of harmonics (which approximate stationary processes), non-stationary sub-linear trends, Linear-Time-Invariant (LTI) systems (which includes finite-order polynomials), and their additive mixtures. In general, our algorithm recovers the hidden state of dynamics based on its noisy observations, like that of a Hidden Markov Model (HMM), provided the dynamics obey the above stated models. As an important application, it provides a robust algorithm for "synthetic control'' for causal inference. Time permitting, we'll discuss its implications for the game of Cricket. This is based on joint works with Anish Agarwal, Muhammad Amjad and Dennis Shen (all at MIT).


Bio:
Devavrat Shah is a professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS) and Operations Research Center (ORC), and the Director of the newly formed Statistics and Data Center in IDSS. His research focus is on theory of large complex networks, which includes network algorithms, stochastic networks, network information theory and large-scale statistical inference. Prof. Shah was awarded the first ACM SIGMETRICS Rising Star Award 2008 for his work on network scheduling algorithms. He received the 2010 Erlang Prize from INFORMS, which is given to a young researcher for outstanding contributions to applied probability. He is currently an associate editor of Operations Research. Prof. Shah’s research is driven by a desire to engineer a socially integrated network where a typical user may connect through a smart-phone, socialize through Facebook, learn from Wikipedia and help bring socio-political change through Twitter. Such a “social network” is in dire need of better network infrastructure; a typical user is anxious for help to be able to cope with the information overload; and scalable computational systems are required to process large amounts of data. As a network theorist, his contributions towards addressing these challenges involve designing better wireless access network and processing social data and scalable algorithms that can operate in data center like facility.