1 citations · 1 across the 12 of their papers we have counts for
12 papers
Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing
Eric Shen, Tony Wu, Mahbod Majid +1
We study the task of learning the structure of a -sparse Gaussian graphical model on variables from a single trajectory of Glauber dynamics. Beyond algorithmic consideration…
The Power of Test-Time Training for Approximate Sampling
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Efficiently sampling from a complex probability distribution is a fundamental problem which has become increasingly pertinent in recent years with the rise of generative AI, as sop…
Learning Under Graphical Models
Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra +1
In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the unif…
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…
Subliminal Effects in Your Data: A General Mechanism via Log-Linearity
Ishaq Aden-Ali, Noah Golowich, Allen Liu +3
Training modern large language models (LLMs) has become a veritable smorgasbord of algorithms and datasets designed to elicit particular behaviors, making it critical to develop te…
Improved Pseudorandom Codes from Permuted Puzzles
Miranda Christ, Noah Golowich, Sam Gunn +2
Watermarks are an essential tool for identifying AI-generated content. Recently, Christ and Gunn (CRYPTO '24) introduced pseudorandom error-correcting codes (PRCs), which are equiv…
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…
Overcomplete Tensor Decomposition via Koszul-Young Flattenings
Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
Motivated by connections between algebraic complexity lower bounds and tensor decompositions, we investigate Koszul-Young flattenings, which are the main ingredient in recent lower…
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…
The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation
Noah Golowich, Ankur Moitra
In this paper, we study the offline RL problem with linear function approximation. Our main structural assumption is that the MDP has low inherent Bellman error, which stipulates t…
Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions
Noah Golowich, Ankur Moitra
One of the most natural approaches to reinforcement learning (RL) with function approximation is value iteration, which inductively generates approximations to the optimal value fu…
Edit Distance Robust Watermarks via Indexing Pseudorandom Codes
Noah Golowich, Ankur Moitra
Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which…