Leveraging Independence to Design Algorithms for Dependent Data: Two Vignettes

  • 10



Name of the Speaker: Dr. Dheeraj Nagaraj
Name of the Organizer: Krishna Jagannathan
Venue: ESB 244 (Seminar Hall)
Date/Time: Wednesday August 10 at 3PM

Learning with dependent data with streaming algorithms is very important in real world applications from time series forecasting to reinforcement learning and control systems. Here the data is often assumed to be Markovian. The limits of learning and the principles behind algorithm design in this context are poorly understood compared to the i.i.d. data setting. In many important cases we can utilize independence in the noise process to obtain algorithms and guarantees which perform near optimally with Markovian data, matching the rates obtained with i.i.d. data. In this talk, I will consider two questions with this theme:

1. Linear (and Generalized Linear) System Identification in the streaming setting.
2. Random batch methods for interacting particle systems.

We will introduce novel algorithms like reverse experience replay and covariance corrected random batch methods and sketch how they work by utilizing independence present within these data sets.

Bio: Dheeraj Nagaraj is a Research Scientist at Google Research, Bangalore. Prior to this, he received his PhD in EECS at MIT, advised by Prof. Guy Bresler. His research focuses on various topics in applied probability theory and theoretical machine learning - including stochastic optimization, random graphs, and reinforcement learning.