research
∙
03/22/2023
Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games
We consider the problem of decentralized multi-agent reinforcement learn...
share
research
∙
03/03/2023
Learning High-Dimensional Single-Neuron ReLU Networks with Finite Samples
This paper considers the problem of learning a single ReLU neuron with s...
research
∙
02/28/2023
Learning Hidden Markov Models Using Conditional Samples
This paper is concerned with the computational complexity of learning th...
research
∙
10/18/2022
Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity
Reinforcement learning provides an automated framework for learning beha...
research
∙
10/09/2022
The Role of Coverage in Online Reinforcement Learning
Coverage conditions – which assert that the data logging distribution ad...
research
∙
08/03/2022
The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shift
We study linear regression under covariate shift, where the marginal dis...
research
∙
03/07/2022
Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime
Stochastic gradient descent (SGD) has achieved great success due to its ...
research
∙
12/27/2021
The Statistical Complexity of Interactive Decision Making
A fundamental challenge in interactive learning and decision making, ran...
research
∙
10/12/2021
Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
Stochastic gradient descent (SGD) has been demonstrated to generalize we...
research
∙
08/10/2021
The Benefits of Implicit Regularization from SGD in Least Squares Problems
Stochastic gradient descent (SGD) exhibits strong algorithmic regulariza...
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
∙
03/23/2021
Benign Overfitting of Constant-Stepsize SGD for Linear Regression
There is an increasing realization that algorithmic inductive biases are...
research
∙
03/23/2021
An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
A fundamental question in the theory of reinforcement learning is: suppo...
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
∙
03/08/2021
Instabilities of Offline RL with Pre-Trained Neural Representation
In offline reinforcement learning (RL), we seek to utilize offline data ...
research
∙
10/22/2020
What are the Statistical Limits of Offline RL with Linear Function Approximation?
Offline reinforcement learning seeks to utilize offline (observational) ...
research
∙
07/15/2020
Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
Model-based reinforcement learning (RL), which finds an optimal policy u...
research
∙
06/22/2020
Sample-Efficient Reinforcement Learning of Undercomplete POMDPs
Partial observability is a common challenge in many reinforcement learni...
research
∙
05/01/2020
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?
Learning to plan for long horizons is a central challenge in episodic re...
research
∙
02/21/2020
Few-Shot Learning via Learning the Representation, Provably
This paper studies few-shot learning via representation learning, where ...
research
∙
12/31/2019
Robust Aggregation for Federated Learning
We present a robust aggregation approach to make federated learning robu...
research
∙
11/28/2019
Optimal Estimation of Change in a Population of Parameters
Paired estimation of change in parameters of interest over a population ...
research
∙
11/27/2019
The Nonstochastic Control Problem
We consider the problem of controlling an unknown linear dynamical syste...
research
∙
10/07/2019
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
Modern deep learning methods provide an effective means to learn good re...
research
∙
08/01/2019
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
Policy gradient methods are among the most effective methods in challeng...
research
∙
06/11/2019
Calibration, Entropy Rates, and Memory in Language Models
Building accurate language models that capture meaningful long-term depe...
research
∙
04/29/2019
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure
There is a stark disparity between the step size schedules used in pract...
research
∙
02/23/2019
Online Control with Adversarial Disturbances
We study the control of a linear dynamical system with adversarial distu...
research
∙
02/13/2019
Stochastic Gradient Descent Escapes Saddle Points Efficiently
This paper considers the perturbed stochastic gradient descent algorithm...
research
∙
02/12/2019
Maximum Likelihood Estimation for Learning Populations of Parameters
Consider a setting with N independent individuals, each with an unknown ...
research
∙
02/11/2019
A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm
In this note, we derive concentration inequalities for random vectors wi...
research
∙
02/08/2019
A Smoother Way to Train Structured Prediction Models
We present a framework to train a structured prediction model by perform...
research
∙
12/06/2018
Provably Efficient Maximum Entropy Exploration
Suppose an agent is in a (possibly unknown) Markov decision process (MDP...
research
∙
11/20/2018
Coupled Recurrent Models for Polyphonic Music Composition
This work describes a novel recurrent model for music composition, which...
research
∙
03/15/2018
On the insufficiency of existing momentum schemes for Stochastic Optimization
Momentum based stochastic gradient methods such as heavy ball (HB) and N...
research
∙
01/15/2018
Global Convergence of Policy Gradient Methods for Linearized Control Problems
Direct policy gradient methods for reinforcement learning and continuous...
research
∙
11/13/2017
Invariances and Data Augmentation for Supervised Music Transcription
This paper explores a variety of models for frame-based music transcript...
research
∙
10/25/2017
A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
This work provides a simplified proof of the statistical minimax optimal...
research
∙
04/26/2017
Accelerating Stochastic Gradient Descent
There is widespread sentiment that it is not possible to effectively uti...
research
∙
03/02/2017
How to Escape Saddle Points Efficiently
This paper shows that a perturbed form of gradient descent converges to ...
research
∙
10/12/2016
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging
This work characterizes the benefits of averaging techniques widely used...
research
∙
05/26/2016
Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
Matrix completion, where we wish to recover a low rank matrix by observi...
research
∙
04/13/2016
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
This paper considers the problem of canonical-correlation analysis (CCA)...
research
∙
02/22/2016
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
This work provides improved guarantees for streaming principle component...
research
∙
06/24/2015
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
We develop a family of accelerated stochastic algorithms that minimize s...
research
∙
12/20/2014
Competing with the Empirical Risk Minimizer in a Single Pass
In many estimation problems, e.g. linear and logistic regression, we wis...
research
∙
10/07/2013
Least Squares Revisited: Scalable Approaches for Multi-class Prediction
This work provides simple algorithms for multi-class (and multi-label) p...
research
∙
02/12/2013