Dhruv Rohatgi

Hi! I'm a fourth-year PhD student in EECS at MIT. My research lies at the intersection of theoretical computer science, statistics, and machine learning: I seek to understand the structural assumptions that enable computationally efficient learning, particularly in the context of interactive learning and decision-making.

I'm very fortunate to be advised by Ankur Moitra. I also spent two wonderful summers at Microsoft Research New England—under the supervision of Vasilis Syrgkanis in Summer 2021, and Dylan Foster in Summer 2024. I am grateful to have been supported by an NDSEG Fellowship and an MIT Akamai Presidential Fellowship in the past.

To reach me: [first initial][last name]@mit.edu

Publications

1. Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration
   with Dylan J. Foster and Zakaria Mhammedi
   
   COLT 2025 ♦ 38th Annual Conference on Learning Theory (to appear).
   [arXiv:2503.07453]
2. Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
   with Adam Block, Audrey Huang, Akshay Krishnamurthy, and Dylan J. Foster
   
   COLT 2025 ♦ 38th Annual Conference on Learning Theory (to appear).
   [arXiv:2502.12465]
3. Necessary and Sufficient Oracles: Towards a Computational Taxonomy for Reinforcement Learning
   with Dylan J. Foster
   COLT 2025 ♦ 38th Annual Conference on Learning Theory (to appear).
   [arXiv:2502.08632]
4. Towards Characterizing the Value of Edge Embeddings in Graph Neural Networks
   with Tanya Marwah, Zachary Chase Lipton, Jianfeng Lu, Ankur Moitra, and Andrej Risteski
   
   Preliminary version selected for Oral Presentation at M3L Workshop (NeurIPS 2024)
   ICML 2025 ♦ 42nd International Conference on Machine Learning (to appear).
   [arXiv:2410.09867]
5. Self-Improvement in Language Models: The Sharpening Mechanism
   with Audrey Huang, Adam Block, Dylan J. Foster, Cyril Zhang, Max Simchowitz, Jordan T. Ash, and Akshay Krishnamurthy
   
   ICLR 2025 (Oral Presentation) ♦ 13th International Conference on Learning Representations (to appear).
   [arXiv:2412.01951]
6. Online Control in Population Dynamics
   with Noah Golowich, Elad Hazan, Zhou Lu, and Jennifer Sun
   
   NeurIPS 2024 ♦ 38th Conference on Neural Information Processing Systems.
   [arXiv:2406.01799] [Conference]
7. Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
   with Ankur Moitra and Noah Golowich
   
   FOCS 2024 ♦ 65th Annual Symposium on Foundations of Computer Science (to appear).
   [arXiv:2404.03774]
8. Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
   with Jonathan Kelner, Frederic Koehler, and Raghu Meka
   
   COLT 2024 ♦ 37th Annual Conference on Learning Theory.
   [arXiv:2402.15409] [Conference]
9. Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
   with Ankur Moitra and Noah Golowich
   
   STOC 2024 ♦ 56th Annual ACM Symposium on Theory of Computing.
   [arXiv:2309.09457] [Conference]
10. Provable Benefits of Score Matching
    with Chirag Pabbaraju, Anish Sevekari, Holden Lee, Ankur Moitra, and Andrej Risteski
    
    NeurIPS 2023 (Spotlight Presentation) ♦ 37th Conference on Neural Information Processing Systems.
    [arXiv:2306.01993] [Conference]
11. Feature Adaptation for Sparse Linear Regression
    with Jonathan Kelner, Frederic Koehler, and Raghu Meka
    
    NeurIPS 2023 (Spotlight Presentation) ♦ 37th Conference on Neural Information Processing Systems.
    [arXiv:2305.16892] [Conference]
12. Learning in Observable POMDPs, without Computationally Intractable Oracles
    with Ankur Moitra and Noah Golowich
    
    NeurIPS 2022 ♦ 36th Conference on Neural Information Processing Systems.
    [arXiv:2206.03446] [Conference]
13. Provably Auditing Ordinary Least Squares in Low Dimensions
    with Ankur Moitra
    
    ICLR 2023 ♦ 11th International Conference on Learning Representations.
    [arXiv:2205.14284] [Conference]
14. Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs
    with Jonathan Kelner, Frederic Koehler, and Raghu Meka
    
    NeurIPS 2022 ♦ 36th Conference on Neural Information Processing Systems.
    [arXiv:2203.02824] [Conference]
15. Planning in Observable POMDPs in Quasipolynomial Time
    with Ankur Moitra and Noah Golowich
    
    STOC 2023 ♦ 55th Annual ACM Symposium on Theory of Computing.
    [arXiv:2201.04735] [Conference]
16. Robust Generalized Method of Moments: A Finite Sample Viewpoint
    with Vasilis Syrgkanis
    
    Preliminary version selected for Oral Presentation at MLECON Workshop (NeurIPS 2021)
    NeurIPS 2022 ♦ 36th Conference on Neural Information Processing Systems.
    [arXiv:2110.03070] [Conference]
17. On the Power of Preconditioning in Sparse Linear Regression
    with Jonathan Kelner, Frederic Koehler, and Raghu Meka
    
    FOCS 2021 ♦ 62nd Annual IEEE Symposium on Foundations of Computer Science.
    [arXiv:2106.09207] [Conference]
18. Truncated Linear Regression in High Dimensions
    with Costis Daskalakis and Manolis Zampetakis
    NeurIPS 2020 ♦ 34th Conference on Neural Information Processing Systems.
    [arXiv:2007.14539] [Conference]
19. Constant-Expansion Suffices for Compressed Sensing with Generative Priors
    with Costis Daskalakis and Manolis Zampetakis
    NeurIPS 2020 (Spotlight Presentation) ♦ 34th Conference on Neural Information Processing Systems.
    [arXiv:2006.04237] [Conference]
20. Regarding Two Conjectures on Clique and Biclique Partitions
    with John C. Urschel and Jake Wellens
    E-JC ♦ The Electronic Journal of Combinatorics, 2021.
    [arXiv:2005.02529] [Journal]
21. Near-Optimal Bounds for Online Caching with Machine-Learned Advice
    SODA 2020 ♦ 31st ACM-SIAM Symposium on Discrete Algorithms.
    [arXiv:1910.12172] [Conference]
22. Conditional Hardness for Approximate Earth Mover Distance
    APPROX 2019 ♦ 22nd Intl. Conference on Approximation Algorithms for Combinatorial Optimization Problems.
    [arXiv:1909.11068] [Conference]
23. Off-diagonal Ordered Ramsey Numbers of Matchings
    E-JC ♦ The Electronic Journal of Combinatorics, 2019.
    [arXiv:1808.04025] [Journal]

Technical Reports

1. On Learning Parities with Dependent Noise
   with Ankur Moitra and Noah Golowich
   
   [arXiv:2404.11325]

Website design adapted from Frederic Koehler and Manolis Zampetakis.