Dhruv Rohatgi

CoRR, 2024

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning.

[BibT_eX]

[DOI]

CoRR, 2024

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Planning and Learning in Partially Observable Systems via Filter Stability.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Provable benefits of score matching.

[BibT_eX]

[DOI]

Chirag Pabbaraju

Anish Prasad Sevekari

Holden Lee

Andrej Risteski

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Feature Adaptation for Sparse Linear Regression.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Provably Auditing Ordinary Least Squares in Low Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

2022

Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs.

[BibT_eX]

[DOI]

CoRR, 2022

Planning in Observable POMDPs in Quasipolynomial Time.

[BibT_eX]

[DOI]

CoRR, 2022

Robust Generalized Method of Moments: A Finite Sample Viewpoint.

[BibT_eX]

[DOI]

Vasilis Syrgkanis

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Learning in Observable POMDPs, without Computationally Intractable Oracles.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

Regarding Two Conjectures on Clique and Biclique Partitions.

[BibT_eX]

[DOI]

John C. Urschel

Jake Wellens

Electron. J. Comb., 2021

On the Power of Preconditioning in Sparse Linear Regression.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Near-Optimal Bounds for Online Caching with Machine Learned Advice.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Constant-Expansion Suffices for Compressed Sensing with Generative Priors.

[BibT_eX]

[DOI]

Constantinos Daskalakis

Emmanouil Zampetakis

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Truncated Linear Regression in High Dimensions.

[BibT_eX]

[DOI]

Constantinos Daskalakis

Emmanouil Zampetakis

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019

Off-Diagonal Ordered Ramsey Numbers of Matchings.

[BibT_eX]

[DOI]

Electron. J. Comb., 2019

Conditional Hardness of Earth Mover Distance.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Sliding window order statistics in sublinear space.

[BibT_eX]

[DOI]