research
∙
07/25/2023
Settling the Sample Complexity of Online Reinforcement Learning
A central issue lying at the heart of online reinforcement learning (RL)...
share
research
∙
07/07/2023
Teaching Arithmetic to Small Transformers
Large language models like GPT-4 exhibit emergent capabilities across ge...
research
∙
07/05/2023
Scaling In-Context Demonstrations with Structured Attention
The recent surge of large language models (LLMs) highlights their abilit...
research
∙
06/21/2023
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms
In stochastic zeroth-order optimization, a problem of practical relevanc...
research
∙
05/30/2023
Solving Robust MDPs through No-Regret Dynamics
Reinforcement Learning is a powerful framework for training agents to na...
research
∙
05/29/2023
How to Query Human Feedback Efficiently in RL?
Reinforcement Learning with Human Feedback (RLHF) is a paradigm in which...
research
∙
05/28/2023
Reward Collapse in Aligning Large Language Models
The extraordinary capabilities of large language models (LLMs) such as C...
research
∙
05/27/2023
Fine-Tuning Language Models with Just Forward Passes
Fine-tuning language models (LMs) has yielded success on diverse downstr...
research
∙
05/24/2023
Provable Offline Reinforcement Learning with Human Feedback
In this paper, we investigate the problem of offline reinforcement learn...
research
∙
05/19/2023
Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability
Recent research has observed that in machine learning optimization, grad...
research
∙
05/18/2023
Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models
We focus on the task of learning a single index model σ(w^⋆· x) with res...
research
∙
05/17/2023
Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning
This paper studies tabular reinforcement learning (RL) in the hybrid set...
research
∙
05/11/2023
Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks
One of the central questions in the theory of deep learning is to unders...
research
∙
05/08/2023
Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning
Policy optimization methods with function approximation are widely used ...
research
∙
03/03/2023
Can We Find Nash Equilibria at a Linear Rate in Markov Games?
We study decentralized learning in two-player zero-sum discounted Markov...
research
∙
02/22/2023
Provably Efficient Reinforcement Learning via Surprise Bound
Value function approximation is important in modern reinforcement learni...
research
∙
02/09/2023
Efficient displacement convex optimization with particle gradient descent
Particle gradient descent, which uses particles to represent a probabili...
research
∙
02/05/2023
Refined Value-Based Offline RL under Realizability and Partial Coverage
In offline reinforcement learning (RL) we have no opportunity to explore...
research
∙
01/30/2023
Looped Transformers as Programmable Computers
We present a framework for using transformer networks as universal compu...
research
∙
01/27/2023
Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing
It is believed that Gradient Descent (GD) induces an implicit bias towar...
research
∙
10/13/2022
From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent
Stochastic Gradient Descent (SGD) has been the method of choice for lear...
research
∙
09/30/2022
Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability
Traditional analyses of gradient descent show that when the largest eige...
research
∙
07/12/2022
PAC Reinforcement Learning for Predictive State Representations
In this paper we study online Reinforcement Learning (RL) in partially o...
research
∙
06/30/2022
Neural Networks can Learn Representations with Gradient Descent
Significant theoretical work has established that in specific regimes, n...
research
∙
06/24/2022
Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings
We study reinforcement learning with function approximation for large-sc...
research
∙
06/24/2022
Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems
We study Reinforcement Learning for partially observable dynamical syste...
research
∙
06/08/2022
Identifying good directions to escape the NTK regime and efficiently learn low-degree plus sparse polynomials
A recent goal in the theory of deep learning is to identify how neural n...
research
∙
06/03/2022
Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Games
We study decentralized policy learning in Markov games where we control ...
research
∙
05/18/2022
On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias
We study the dynamics and implicit bias of gradient flow (GF) on univari...
research
∙
03/29/2022
Nearly Minimax Algorithms for Linear Bandits with Shared Representation
We give novel algorithms for multi-task and lifelong linear bandits with...
research
∙
02/09/2022
Offline Reinforcement Learning with Realizability and Single-policy Concentrability
Sample-efficiency guarantees for offline reinforcement learning (RL) oft...
research
∙
12/04/2021
Optimization-Based Separations for Neural Networks
Depth separation results propose a possible theoretical explanation for ...
research
∙
10/18/2021
Provable Hierarchy-Based Meta-Reinforcement Learning
Hierarchical reinforcement learning (HRL) has seen widespread interest a...
research
∙
10/15/2021
Provable Regret Bounds for Deep Online Learning and Control
The use of deep neural networks has been highly successful in reinforcem...
research
∙
07/30/2021
Towards General Function Approximation in Zero-Sum Markov Games
This paper considers two-player zero-sum finite-horizon Markov games wit...
research
∙
07/14/2021
Going Beyond Linear RL: Sample Efficient Neural Function Approximation
Deep Reinforcement Learning (RL) powered by neural net approximation of ...
research
∙
07/09/2021
Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
Bandit problems with linear or concave reward have been extensively stud...
research
∙
07/06/2021
A Short Note on the Relationship of Information Gain and Eluder Dimension
Eluder dimension and information gain are two widely used methods of com...
research
∙
05/24/2021
Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
Policy optimization, which learns the policy of interest by maximizing t...
research
∙
05/05/2021
How Fine-Tuning Allows for Effective Meta-Learning
Representation learning has been widely studied in the context of meta-l...
research
∙
03/19/2021
Bilinear Classes: A Structural Framework for Provable Generalization in RL
This work introduces Bilinear Classes, a new structural framework, which...
research
∙
02/23/2021
MUSBO: Model-based Uncertainty Regularized and Sample Efficient Batch Optimization for Deployment Constrained Reinforcement Learning
In many contemporary applications such as healthcare, finance, robotics,...
research
∙
02/22/2021
A Theory of Label Propagation for Subpopulation Shift
One of the central problems in machine learning is domain adaptation. Un...
research
∙
02/17/2021
Provably Efficient Policy Gradient Methods for Two-Player Zero-Sum Markov Games
Policy gradient methods are widely used in solving two-player zero-sum g...
research
∙
10/22/2020
Beyond Lazy Training for Over-parameterized Tensor Decomposition
Over-parametrization is an important technique in training neural networ...
research
∙
10/12/2020
How Important is the Train-Validation Split in Meta-Learning?
Meta-learning aims to perform fast adaptation on a new task through lear...
research
∙
09/22/2020
Sanity-Checking Pruning Methods: Random Tickets can Win the Jackpot
Network pruning is a method for reducing test-time computational resourc...
research
∙
09/21/2020
Generalized Leverage Score Sampling for Neural Networks
Leverage score sampling is a powerful technique that originates from the...
research
∙
08/03/2020
Predicting What You Already Know Helps: Provable Self-Supervised Learning
Self-supervised representation learning solves auxiliary prediction task...
research
∙
07/13/2020