This is my old website. Please access my current website here.

I am a Research Scientist at Google AI, Bangalore, India. I work on various problems in theoretical machine learning([1]), applied probability and statistics. My current work focuses on designing learning algorithms for data with temporal dependence, theory of neural networks, random graphs and stochastic optimization algorithms. I recently completed my PhD at Lab for Information and Decision Systems (LIDS) at MIT advised by Prof. Guy Bresler. Prior to that I was an undergraduate student at IIT Madras.

Email: dheerajnagaraj[at]google[dot]com,

[1] “आकाशात् पतितं तोयं यथा गच्छति सागरम्” 

Publications:

Manuscripts:

• Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs (2021)
  preprint, under review
  with Naman Agarwal, Syomantak Chaudhuri, Prateek Jain and Praneeth Netrapalli.

Learning from Markovian Trajectories:

• Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems. (2021)
  NeurIPS 2021 (spotlight), to appear
  with Prateek Jain, Suhas Kowshik and Praneeth Netrapalli.
• Streaming Linear System Identification with Reverse Experience Replay (2021)
  NeurIPS 2021, to appear
  with Prateek Jain, Suhas Kowshik and Praneeth Netrapalli.

• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms. (2020)
  NeurIPS 2020 (spotlight)
  with Guy Bresler, Prateek Jain, Praneeth Netrapalli, Xian Wu

Probability and Statistics:

• Phase Transition for Detecting Latent Geometry in Random Graphs. (2020)
  Probability Theory and Related Fields
  arXiv preprint: arxiv:1910.14167
  with Matthew Brennan and Guy Bresler
• Stein’s Method for Stationary Distributions of Markov Chains and Application to Ising Models. (2019)
  Annals of Applied Probability 
  arXiv preprint: arxiv:1712.05743, 
  with Guy Bresler
• Optimal Single Sample Tests for Structured versus Unstructured Network Data. (2018)
  COLT 2018.
  arXiv preprint : arxiv:1802.06186 
  with Guy Bresler

Neural Networks:

• The staircase property: How hierarchical structure can guide deep learning. (2021)
  NeurIPS 2021, to appear
  with Emmanuel Abbe, Enric Boix-Adsera, Matthew Brennan and Guy Bresler
• A Law of Robustness for Two-Layers Neural Networks. (2020)
  COLT 2021 
  with Sébastien Bubeck and Yuanzhi Li
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth. (2020)
  NeurIPS 2020 
  with Guy Bresler.
• A Corrective View of Neural Networks: Representation, Memorization and Learning. (2020)
  COLT 2020
  arXiv preprint : arxiv:2002.00274
  with Guy Bresler.

Stochastic Optimization:

• Making Last Iterate of Stochastic Gradient Descent Information Theoretically Optimal. (2021)
  SIAM Journal on Optimization (2021) , COLT 2019 (extended abstract)
  with Praneeth Netrapalli and Prateek Jain
• SGD without Replacement: Sharper Rates for General Smooth Convex Functions. (2019)
  ICML 2019
  with Praneeth Netrapalli and Prateek Jain

Quantum Computing (from a different lifetime!):

•  Continuous limit of discrete quantum walks. (2015)
  Physical Review A, arxiv:1501.06950
  with Todd A. Brun