Sham M. Kakade

is this you? claim profile

∙ 0 followers
Microsoft ∙ University of Pennsylvania ∙ University of Washington

Washington Research Foundation Data Science Chair at University of Washington, Associate Professor in Department of Statistics at University of Washington, Associate Professor in Department of Computer Science at University of Washington, Senior Data Science Fellow, eScience Institute, Adjunct Professor in Department of Electrical Engineering at University of Washington

Featured Co-authors

Michael I. Jordan
196 publications
Ruslan Salakhutdinov
141 publications
Yi Zhang
120 publications
Anima Anandkumar
105 publications
Tong Zhang
99 publications
Le Song
85 publications
Quanquan Gu
77 publications
Daniel Hsu
61 publications
Jason D. Lee
60 publications
Prateek Jain
59 publications
Ohad Shamir
58 publications

Benign Overfitting of Constant-Stepsize SGD for Linear Regression

There is an increasing realization that algorithmic inductive biases are...
03/23/2021 ∙ by Difan Zou, et al. ∙ 9 ∙ share

read it
An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap

A fundamental question in the theory of reinforcement learning is: suppo...
03/23/2021 ∙ by Yuanhao Wang, et al. ∙ 0 ∙ share

read it
Bilinear Classes: A Structural Framework for Provable Generalization in RL

This work introduces Bilinear Classes, a new structural framework, which...
03/19/2021 ∙ by Simon S. Du, et al. ∙ 52 ∙ share

read it
Instabilities of Offline RL with Pre-Trained Neural Representation

In offline reinforcement learning (RL), we seek to utilize offline data ...
03/08/2021 ∙ by Ruosong Wang, et al. ∙ 15 ∙ share

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

Offline reinforcement learning seeks to utilize offline (observational) ...
10/22/2020 ∙ by Ruosong Wang, et al. ∙ 0 ∙ share

read it
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...
07/15/2020 ∙ by Kaiqing Zhang, et al. ∙ 27 ∙ share

read it
Sample-Efficient Reinforcement Learning of Undercomplete POMDPs

Partial observability is a common challenge in many reinforcement learni...
06/22/2020 ∙ by Chi Jin, et al. ∙ 9 ∙ share

read it
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...
05/01/2020 ∙ by Ruosong Wang, et al. ∙ 7 ∙ share

read it
Few-Shot Learning via Learning the Representation, Provably

This paper studies few-shot learning via representation learning, where ...
02/21/2020 ∙ by Simon S. Du, et al. ∙ 46 ∙ share

read it
Robust Aggregation for Federated Learning

We present a robust aggregation approach to make federated learning robu...
12/31/2019 ∙ by Krishna Pillutla, et al. ∙ 22 ∙ share

read it
Optimal Estimation of Change in a Population of Parameters

Paired estimation of change in parameters of interest over a population ...
11/28/2019 ∙ by Ramya Korlakai Vinayak, et al. ∙ 15 ∙ share

read it
The Nonstochastic Control Problem

We consider the problem of controlling an unknown linear dynamical syste...
11/27/2019 ∙ by Elad Hazan, et al. ∙ 15 ∙ share

read it
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?

Modern deep learning methods provide an effective means to learn good re...
10/07/2019 ∙ by Simon S. Du, et al. ∙ 15 ∙ share

read it
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes

Policy gradient methods are among the most effective methods in challeng...
08/01/2019 ∙ by Alekh Agarwal, et al. ∙ 3 ∙ share

read it
Calibration, Entropy Rates, and Memory in Language Models

Building accurate language models that capture meaningful long-term depe...
06/11/2019 ∙ by Mark Braverman, et al. ∙ 1 ∙ share

read it
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...
04/29/2019 ∙ by Rong Ge, et al. ∙ 12 ∙ share

read it
Online Control with Adversarial Disturbances

We study the control of a linear dynamical system with adversarial distu...
02/23/2019 ∙ by Naman Agarwal, et al. ∙ 8 ∙ share

read it
Stochastic Gradient Descent Escapes Saddle Points Efficiently

This paper considers the perturbed stochastic gradient descent algorithm...
02/13/2019 ∙ by Chi Jin, et al. ∙ 20 ∙ share

read it
Maximum Likelihood Estimation for Learning Populations of Parameters

Consider a setting with N independent individuals, each with an unknown ...
02/12/2019 ∙ by Ramya Korlakai Vinayak, et al. ∙ 4 ∙ share

read it
A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm

In this note, we derive concentration inequalities for random vectors wi...
02/11/2019 ∙ by Chi Jin, et al. ∙ 16 ∙ share

read it
A Smoother Way to Train Structured Prediction Models

We present a framework to train a structured prediction model by perform...
02/08/2019 ∙ by Krishna Pillutla, et al. ∙ 0 ∙ share

read it
Provably Efficient Maximum Entropy Exploration

Suppose an agent is in a (possibly unknown) Markov decision process (MDP...
12/06/2018 ∙ by Elad Hazan, et al. ∙ 2 ∙ share

read it
Coupled Recurrent Models for Polyphonic Music Composition

This work describes a novel recurrent model for music composition, which...
11/20/2018 ∙ by John Thickstun, et al. ∙ 10 ∙ share

read it
On the insufficiency of existing momentum schemes for Stochastic Optimization

Momentum based stochastic gradient methods such as heavy ball (HB) and N...
03/15/2018 ∙ by Rahul Kidambi, et al. ∙ 0 ∙ share

read it
Global Convergence of Policy Gradient Methods for Linearized Control Problems

Direct policy gradient methods for reinforcement learning and continuous...
01/15/2018 ∙ by Maryam Fazel, et al. ∙ 0 ∙ share

read it
Invariances and Data Augmentation for Supervised Music Transcription

This paper explores a variety of models for frame-based music transcript...
11/13/2017 ∙ by John Thickstun, et al. ∙ 0 ∙ share

read it
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...
10/25/2017 ∙ by Prateek Jain, et al. ∙ 0 ∙ share

read it
Accelerating Stochastic Gradient Descent

There is widespread sentiment that it is not possible to effectively uti...
04/26/2017 ∙ by Prateek Jain, et al. ∙ 0 ∙ share

read it
How to Escape Saddle Points Efficiently

This paper shows that a perturbed form of gradient descent converges to ...
03/02/2017 ∙ by Chi Jin, et al. ∙ 0 ∙ share

read it
Parallelizing Stochastic Approximation Through Mini-Batching and Tail-Averaging

This work characterizes the benefits of averaging techniques widely used...
10/12/2016 ∙ by Prateek Jain, et al. ∙ 0 ∙ share

read it
Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent

Matrix completion, where we wish to recover a low rank matrix by observi...
05/26/2016 ∙ by Chi Jin, et al. ∙ 0 ∙ share

read it
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis

This paper considers the problem of canonical-correlation analysis (CCA)...
04/13/2016 ∙ by Rong Ge, et al. ∙ 0 ∙ share

read it
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm

This work provides improved guarantees for streaming principle component...
02/22/2016 ∙ by Prateek Jain, et al. ∙ 0 ∙ share

read it
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

We develop a family of accelerated stochastic algorithms that minimize s...
06/24/2015 ∙ by Roy Frostig, et al. ∙ 0 ∙ share

read it
Competing with the Empirical Risk Minimizer in a Single Pass

In many estimation problems, e.g. linear and logistic regression, we wis...
12/20/2014 ∙ by Roy Frostig, et al. ∙ 0 ∙ share

read it
Least Squares Revisited: Scalable Approaches for Multi-class Prediction

This work provides simple algorithms for multi-class (and multi-label) p...
10/07/2013 ∙ by Alekh Agarwal, et al. ∙ 0 ∙ share

read it
A Tensor Approach to Learning Mixed Membership Community Models

Community detection is the task of detecting hidden communities from obs...
02/12/2013 ∙ by Anima Anandkumar, et al. ∙ 0 ∙ share

read it
Analysis of a randomized approximation scheme for matrix multiplication

This note gives a simple analysis of a randomized approximation scheme f...
11/23/2012 ∙ by Daniel Hsu, et al. ∙ 0 ∙ share

read it
Tensor decompositions for learning latent variable models

This work considers a computationally and statistically efficient parame...
10/29/2012 ∙ by Anima Anandkumar, et al. ∙ 0 ∙ share

read it
Learning Topic Models and Latent Bayesian Networks Under Expansion Constraints

Unsupervised estimation of latent variable models is a fundamental probl...
09/24/2012 ∙ by Daniel Hsu, et al. ∙ 0 ∙ share

read it
Planning in POMDPs Using Multiplicity Automata

Planning and learning in Partially Observable MDPs (POMDPs) are among th...
07/04/2012 ∙ by Eyal Even-Dar, et al. ∙ 0 ∙ share

read it
Learning mixtures of spherical Gaussians: moment methods and spectral decompositions

This work provides a computationally efficient and statistically consist...
06/25/2012 ∙ by Daniel Hsu, et al. ∙ 0 ∙ share

read it
A Spectral Algorithm for Latent Dirichlet Allocation

The problem of topic modeling can be seen as a generalization of the clu...
04/30/2012 ∙ by Dean P. Foster, et al. ∙ 0 ∙ share

read it
A Method of Moments for Mixture Models and Hidden Markov Models

Mixture models are a fundamental tool in applied statistics and machine ...
03/03/2012 ∙ by Daniel Hsu, et al. ∙ 0 ∙ share

read it
Towards minimax policies for online linear optimization with bandit feedback

We address the online linear optimization problem with bandit feedback. ...
02/14/2012 ∙ by Sébastien Bubeck, et al. ∙ 0 ∙ share

read it
Spectral Methods for Learning Multivariate Latent Tree Structure

This work considers the problem of learning the structure of multivariat...
07/07/2011 ∙ by Kamalika Chaudhuri, et al. ∙ 0 ∙ share

read it
Random design analysis of ridge regression

This work gives a simultaneous analysis of both the ordinary least squar...
06/13/2011 ∙ by Daniel Hsu, et al. ∙ 0 ∙ share

read it
A Risk Comparison of Ordinary Least Squares vs Ridge Regression

We compare the risk of ridge regression to a simple variant of ordinary ...
05/04/2011 ∙ by Paramveer S. Dhillon, et al. ∙ 0 ∙ share

read it
Dimension-free tail inequalities for sums of random matrices

We derive exponential tail inequalities for sums of random matrices with...
04/09/2011 ∙ by Daniel Hsu, et al. ∙ 0 ∙ share

read it
Robust Matrix Decomposition with Outliers

Suppose a given observation matrix can be decomposed as the sum of a low...
11/05/2010 ∙ by Daniel Hsu, et al. ∙ 0 ∙ share

read it