
Benign Overfitting of ConstantStepsize SGD for Linear Regression
There is an increasing realization that algorithmic inductive biases are...
read it

An Exponential Lower Bound for LinearlyRealizable MDPs with Constant Suboptimality Gap
A fundamental question in the theory of reinforcement learning is: suppo...
read it

Bilinear Classes: A Structural Framework for Provable Generalization in RL
This work introduces Bilinear Classes, a new structural framework, which...
read it

Instabilities of Offline RL with PreTrained Neural Representation
In offline reinforcement learning (RL), we seek to utilize offline data ...
read it

What are the Statistical Limits of Offline RL with Linear Function Approximation?
Offline reinforcement learning seeks to utilize offline (observational) ...
read it

ModelBased MultiAgent RL in ZeroSum Markov Games with NearOptimal Sample Complexity
Modelbased reinforcement learning (RL), which finds an optimal policy u...
read it

SampleEfficient Reinforcement Learning of Undercomplete POMDPs
Partial observability is a common challenge in many reinforcement learni...
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...
read it

FewShot Learning via Learning the Representation, Provably
This paper studies fewshot learning via representation learning, where ...
read it

Robust Aggregation for Federated Learning
We present a robust aggregation approach to make federated learning robu...
read it

Optimal Estimation of Change in a Population of Parameters
Paired estimation of change in parameters of interest over a population ...
read it

The Nonstochastic Control Problem
We consider the problem of controlling an unknown linear dynamical syste...
read it

Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
Modern deep learning methods provide an effective means to learn good re...
read it

Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
Policy gradient methods are among the most effective methods in challeng...
read it

Calibration, Entropy Rates, and Memory in Language Models
Building accurate language models that capture meaningful longterm depe...
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...
read it

Online Control with Adversarial Disturbances
We study the control of a linear dynamical system with adversarial distu...
read it

Stochastic Gradient Descent Escapes Saddle Points Efficiently
This paper considers the perturbed stochastic gradient descent algorithm...
read it

Maximum Likelihood Estimation for Learning Populations of Parameters
Consider a setting with N independent individuals, each with an unknown ...
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...
read it

A Smoother Way to Train Structured Prediction Models
We present a framework to train a structured prediction model by perform...
read it

Provably Efficient Maximum Entropy Exploration
Suppose an agent is in a (possibly unknown) Markov decision process (MDP...
read it

Coupled Recurrent Models for Polyphonic Music Composition
This work describes a novel recurrent model for music composition, which...
read it

On the insufficiency of existing momentum schemes for Stochastic Optimization
Momentum based stochastic gradient methods such as heavy ball (HB) and N...
read it

Global Convergence of Policy Gradient Methods for Linearized Control Problems
Direct policy gradient methods for reinforcement learning and continuous...
read it

Invariances and Data Augmentation for Supervised Music Transcription
This paper explores a variety of models for framebased music transcript...
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...
read it

Accelerating Stochastic Gradient Descent
There is widespread sentiment that it is not possible to effectively uti...
read it

How to Escape Saddle Points Efficiently
This paper shows that a perturbed form of gradient descent converges to ...
read it

Parallelizing Stochastic Approximation Through MiniBatching and TailAveraging
This work characterizes the benefits of averaging techniques widely used...
read it

Provable Efficient Online Matrix Completion via Nonconvex Stochastic Gradient Descent
Matrix completion, where we wish to recover a low rank matrix by observi...
read it

Efficient Algorithms for Largescale Generalized Eigenvector Computation and Canonical Correlation Analysis
This paper considers the problem of canonicalcorrelation analysis (CCA)...
read it

Streaming PCA: Matching Matrix Bernstein and NearOptimal Finite Sample Guarantees for Oja's Algorithm
This work provides improved guarantees for streaming principle component...
read it

Unregularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
We develop a family of accelerated stochastic algorithms that minimize s...
read it

Competing with the Empirical Risk Minimizer in a Single Pass
In many estimation problems, e.g. linear and logistic regression, we wis...
read it

Least Squares Revisited: Scalable Approaches for Multiclass Prediction
This work provides simple algorithms for multiclass (and multilabel) p...
read it

A Tensor Approach to Learning Mixed Membership Community Models
Community detection is the task of detecting hidden communities from obs...
read it

Analysis of a randomized approximation scheme for matrix multiplication
This note gives a simple analysis of a randomized approximation scheme f...
read it

Tensor decompositions for learning latent variable models
This work considers a computationally and statistically efficient parame...
read it

Learning Topic Models and Latent Bayesian Networks Under Expansion Constraints
Unsupervised estimation of latent variable models is a fundamental probl...
read it

Planning in POMDPs Using Multiplicity Automata
Planning and learning in Partially Observable MDPs (POMDPs) are among th...
read it

Learning mixtures of spherical Gaussians: moment methods and spectral decompositions
This work provides a computationally efficient and statistically consist...
read it

A Spectral Algorithm for Latent Dirichlet Allocation
The problem of topic modeling can be seen as a generalization of the clu...
read it

A Method of Moments for Mixture Models and Hidden Markov Models
Mixture models are a fundamental tool in applied statistics and machine ...
read it

Towards minimax policies for online linear optimization with bandit feedback
We address the online linear optimization problem with bandit feedback. ...
read it

Spectral Methods for Learning Multivariate Latent Tree Structure
This work considers the problem of learning the structure of multivariat...
read it

Random design analysis of ridge regression
This work gives a simultaneous analysis of both the ordinary least squar...
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 ...
read it

Dimensionfree tail inequalities for sums of random matrices
We derive exponential tail inequalities for sums of random matrices with...
read it

Robust Matrix Decomposition with Outliers
Suppose a given observation matrix can be decomposed as the sum of a low...
read it
Sham M. Kakade
is this you? claim profile
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