Sham M. Kakade

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...

0 Dylan J. Foster, et al. ∙

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...

1 Jingfeng Wu, et al. ∙

research

∙ 02/28/2023

Learning Hidden Markov Models Using Conditional Samples

This paper is concerned with the computational complexity of learning th...

0 Sham M. Kakade, et al. ∙

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...

0 Abhishek Gupta, et al. ∙

research

∙ 10/09/2022

The Role of Coverage in Online Reinforcement Learning

Coverage conditions – which assert that the data logging distribution ad...

0 Tengyang Xie, et al. ∙

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...

4 Jingfeng Wu, et al. ∙

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 ...

4 Difan Zou, et al. ∙

research

∙ 12/27/2021

The Statistical Complexity of Interactive Decision Making

A fundamental challenge in interactive learning and decision making, ran...

13 Dylan J. Foster, et al. ∙

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...

5 Jingfeng Wu, et al. ∙

research

∙ 08/10/2021

The Benefits of Implicit Regularization from SGD in Least Squares Problems

Stochastic gradient descent (SGD) exhibits strong algorithmic regulariza...

0 Difan Zou, et al. ∙

research

∙ 07/14/2021

Going Beyond Linear RL: Sample Efficient Neural Function Approximation

Deep Reinforcement Learning (RL) powered by neural net approximation of ...

4 Baihe Huang, et al. ∙

research

∙ 07/09/2021

Optimal Gradient-based Algorithms for Non-concave Bandit Optimization

Bandit problems with linear or concave reward have been extensively stud...

10 Baihe Huang, et al. ∙

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...

5 Kaixuan Huang, et al. ∙

research

∙ 03/23/2021

Benign Overfitting of Constant-Stepsize SGD for Linear Regression

There is an increasing realization that algorithmic inductive biases are...

9 Difan Zou, et al. ∙

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...

0 Yuanhao Wang, et al. ∙

research

∙ 03/19/2021

Bilinear Classes: A Structural Framework for Provable Generalization in RL

This work introduces Bilinear Classes, a new structural framework, which...

52 Simon S. Du, et al. ∙

research

∙ 03/08/2021

Instabilities of Offline RL with Pre-Trained Neural Representation

In offline reinforcement learning (RL), we seek to utilize offline data ...

15 Ruosong Wang, et al. ∙

research

∙ 10/22/2020

What are the Statistical Limits of Offline RL with Linear Function Approximation?

Offline reinforcement learning seeks to utilize offline (observational) ...

0 Ruosong Wang, et al. ∙

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...

27 Kaiqing Zhang, et al. ∙

research

∙ 06/22/2020

Sample-Efficient Reinforcement Learning of Undercomplete POMDPs

Partial observability is a common challenge in many reinforcement learni...

9 Chi Jin, et al. ∙

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...

7 Ruosong Wang, et al. ∙

research

∙ 02/21/2020

Few-Shot Learning via Learning the Representation, Provably

This paper studies few-shot learning via representation learning, where ...

46 Simon S. Du, et al. ∙

research

∙ 12/31/2019

Robust Aggregation for Federated Learning

We present a robust aggregation approach to make federated learning robu...

22 Krishna Pillutla, et al. ∙

research

∙ 11/28/2019

Optimal Estimation of Change in a Population of Parameters

Paired estimation of change in parameters of interest over a population ...

15 Ramya Korlakai Vinayak, et al. ∙

research

∙ 11/27/2019

The Nonstochastic Control Problem

We consider the problem of controlling an unknown linear dynamical syste...

15 Elad Hazan, et al. ∙

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...

15 Simon S. Du, et al. ∙

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...

3 Alekh Agarwal, et al. ∙

research

∙ 06/11/2019

Calibration, Entropy Rates, and Memory in Language Models

Building accurate language models that capture meaningful long-term depe...

1 Mark Braverman, et al. ∙

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...

12 Rong Ge, et al. ∙

research

∙ 02/23/2019

Online Control with Adversarial Disturbances

We study the control of a linear dynamical system with adversarial distu...

8 Naman Agarwal, et al. ∙

research

∙ 02/13/2019

Stochastic Gradient Descent Escapes Saddle Points Efficiently

This paper considers the perturbed stochastic gradient descent algorithm...

20 Chi Jin, et al. ∙

research

∙ 02/12/2019

Maximum Likelihood Estimation for Learning Populations of Parameters

Consider a setting with N independent individuals, each with an unknown ...

4 Ramya Korlakai Vinayak, et al. ∙

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...

16 Chi Jin, et al. ∙

research

∙ 02/08/2019

A Smoother Way to Train Structured Prediction Models

We present a framework to train a structured prediction model by perform...

0 Krishna Pillutla, et al. ∙

research

∙ 12/06/2018

Provably Efficient Maximum Entropy Exploration

Suppose an agent is in a (possibly unknown) Markov decision process (MDP...

2 Elad Hazan, et al. ∙

research

∙ 11/20/2018

Coupled Recurrent Models for Polyphonic Music Composition

This work describes a novel recurrent model for music composition, which...

10 John Thickstun, et al. ∙

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...

0 Rahul Kidambi, et al. ∙

research

∙ 01/15/2018

Global Convergence of Policy Gradient Methods for Linearized Control Problems

Direct policy gradient methods for reinforcement learning and continuous...

0 Maryam Fazel, et al. ∙

research

∙ 11/13/2017

Invariances and Data Augmentation for Supervised Music Transcription

This paper explores a variety of models for frame-based music transcript...

0 John Thickstun, et al. ∙

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...

0 Prateek Jain, et al. ∙

research

∙ 04/26/2017

Accelerating Stochastic Gradient Descent

There is widespread sentiment that it is not possible to effectively uti...

0 Prateek Jain, et al. ∙

research

∙ 03/02/2017

How to Escape Saddle Points Efficiently

This paper shows that a perturbed form of gradient descent converges to ...

0 Chi Jin, et al. ∙

research

∙ 10/12/2016

Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging

This work characterizes the benefits of averaging techniques widely used...

0 Prateek Jain, et al. ∙

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...

0 Chi Jin, et al. ∙

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)...

0 Rong Ge, et al. ∙

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...

0 Prateek Jain, et al. ∙

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...

0 Roy Frostig, et al. ∙

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...

0 Roy Frostig, et al. ∙

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...

0 Alekh Agarwal, et al. ∙

research

∙ 02/12/2013

A Tensor Approach to Learning Mixed Membership Community Models

Community detection is the task of detecting hidden communities from obs...

0 Anima Anandkumar, et al. ∙

Sham M. Kakade

Featured Co-authors