Sham M. Kakade

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ramya Korlakai Vinayak, et al. ∙

research

∙ 11/27/2019

The Nonstochastic Control Problem

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

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

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

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

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

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

Naman Agarwal, et al. ∙

research

∙ 02/13/2019

Stochastic Gradient Descent Escapes Saddle Points Efficiently

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

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

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

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

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

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

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

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

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

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

Prateek Jain, et al. ∙

research

∙ 04/26/2017

Accelerating Stochastic Gradient Descent

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

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

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

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

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

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

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

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

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

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

Anima Anandkumar, et al. ∙

research

∙ 11/23/2012

Analysis of a randomized approximation scheme for matrix multiplication

This note gives a simple analysis of a randomized approximation scheme f...

Daniel Hsu, et al. ∙

research

∙ 10/29/2012

Tensor decompositions for learning latent variable models

This work considers a computationally and statistically efficient parame...

Anima Anandkumar, et al. ∙

research

∙ 09/24/2012

Learning Topic Models and Latent Bayesian Networks Under Expansion Constraints

Unsupervised estimation of latent variable models is a fundamental probl...

Daniel Hsu, et al. ∙

research

∙ 07/04/2012

Planning in POMDPs Using Multiplicity Automata

Planning and learning in Partially Observable MDPs (POMDPs) are among th...

Eyal Even-Dar, et al. ∙

research

∙ 06/25/2012

Learning mixtures of spherical Gaussians: moment methods and spectral decompositions

This work provides a computationally efficient and statistically consist...

Daniel Hsu, et al. ∙

Sham M. Kakade

Featured Co-authors