13 citations · 29 across the 27 of their papers we have counts for
30 papers
Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference
Noah Golowich, Fan Chen, Dhruv Rohatgi +4
Inference-time methods that aggregate and prune multiple samples have emerged as a powerful paradigm for steering large language models, yet we lack any principled understanding of…
Steering diffusion models with quadratic rewards: a fine-grained analysis
Ankur Moitra, Andrej Risteski, Dhruv Rohatgi
Inference-time algorithms are an emerging paradigm in which pre-trained models are used as subroutines to solve downstream tasks. Such algorithms have been proposed for tasks rangi…
To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning
Yuda Song, Dhruv Rohatgi, Aarti Singh +1
Partial observability is a notorious challenge in reinforcement learning (RL), due to the need to learn complex, history-dependent policies. Recent empirical successes have used pr…
Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
Dhruv Rohatgi, Abhishek Shetty, Donya Saless +4
Test-time algorithms that combine the generative power of language models with process verifiers that assess the quality of partial generations offer a promising lever for elicitin…
Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration
Dylan J. Foster, Zakaria Mhammedi, Dhruv Rohatgi
Language model alignment (or, reinforcement learning) techniques that leverage active exploration -- deliberately encouraging the model to produce diverse, informative responses --…
Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
Dhruv Rohatgi, Adam Block, Audrey Huang +2
Next-token prediction with the logarithmic loss is a cornerstone of autoregressive sequence modeling, but, in practice, suffers from error amplification, where errors in the model…
Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
Dhruv Rohatgi, Dylan J. Foster
Algorithms for reinforcement learning (RL) in large state spaces crucially rely on supervised learning subroutines to estimate objects such as value functions or transition probabi…
Self-Improvement in Language Models: The Sharpening Mechanism
Audrey Huang, Adam Block, Dylan J. Foster +5
Recent work in language modeling has raised the possibility of self-improvement, where a language models evaluates and refines its own generations to achieve higher performance wit…
Towards characterizing the value of edge embeddings in Graph Neural Networks
Dhruv Rohatgi, Tanya Marwah, Zachary Chase Lipton +3
Graph neural networks (GNNs) are the dominant approach to solving machine learning problems defined over graphs. Despite much theoretical and empirical work in recent years, our un…
Online Control in Population Dynamics
Noah Golowich, Elad Hazan, Zhou Lu +2
The study of population dynamics originated with early sociological works but has since extended into many fields, including biology, epidemiology, evolutionary game theory, and ec…
On Learning Parities with Dependent Noise
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
In this expository note we show that the learning parities with noise (LPN) assumption is robust to weak dependencies in the noise distribution of small batches of samples. This pr…
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Supervised learning is often computationally easy in practice. But to what extent does this mean that other modes of learning, such as reinforcement learning (RL), ought to be comp…
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
It is well-known that the statistical performance of Lasso can suffer significantly when the covariates of interest have strong correlations. In particular, the prediction error of…
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
The key assumption underlying linear Markov Decision Processes (MDPs) is that the learner has access to a known feature map that maps state-action pairs to -dimensiona…
Provable benefits of score matching
Chirag Pabbaraju, Dhruv Rohatgi, Anish Sevekari +3
Score matching is an alternative to maximum likelihood (ML) for estimating a probability distribution parametrized up to a constant of proportionality. By fitting the ''score'' of…
Feature Adaptation for Sparse Linear Regression
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression is a central problem in high-dimensional statistics. We study the correlated random design setting, where the covariates are drawn from a multivariate Gaus…
Learning in Observable POMDPs, without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Much of reinforcement learning theory is built on top of oracles that are computationally hard to implement. Specifically for learning near-optimal policies in Partially Observable…
Provably Auditing Ordinary Least Squares in Low Dimensions
Ankur Moitra, Dhruv Rohatgi
Measuring the stability of conclusions derived from Ordinary Least Squares linear regression is critically important, but most metrics either only measure local stability (i.e. aga…
Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs
Jonathan A. Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression with ill-conditioned Gaussian random designs is widely believed to exhibit a statistical/computational gap, but there is surprisingly little formal evidenc…
Planning in Observable POMDPs in Quasipolynomial Time
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Partially Observable Markov Decision Processes (POMDPs) are a natural and general model in reinforcement learning that take into account the agent's uncertainty about its current s…
Robust Generalized Method of Moments: A Finite Sample Viewpoint
Dhruv Rohatgi, Vasilis Syrgkanis
For many inference problems in statistics and econometrics, the unknown parameter is identified by a set of moment conditions. A generic method of solving moment conditions is the…
On the Power of Preconditioning in Sparse Linear Regression
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression is a fundamental problem in high-dimensional statistics, but strikingly little is known about how to efficiently solve it without restrictive conditions on…
Truncated Linear Regression in High Dimensions
Constantinos Daskalakis, Dhruv Rohatgi, Manolis Zampetakis
As in standard linear regression, in truncated linear regression, we are given access to observations whose dependent variable equals $y_i= A_i^{\rm T} \cdot x^* + η…
Constant-Expansion Suffices for Compressed Sensing with Generative Priors
Constantinos Daskalakis, Dhruv Rohatgi, Manolis Zampetakis
Generative neural networks have been empirically found very promising in providing effective structural priors for compressed sensing, since they can be trained to span low-dimensi…