
-
Benign Overfitting of Constant-Stepsize SGD for Linear Regression
There is an increasing realization that algorithmic inductive biases are...
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...
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 Pre-Trained 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
-
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...
read it
-
Sample-Efficient 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
-
Few-Shot Learning via Learning the Representation, Provably
This paper studies few-shot 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 long-term 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 frame-based 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 Mini-Batching and Tail-Averaging
This work characterizes the benefits of averaging techniques widely used...
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...
read it
-
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
This paper considers the problem of canonical-correlation analysis (CCA)...
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...
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...
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 Multi-class Prediction
This work provides simple algorithms for multi-class (and multi-label) 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
-
Dimension-free 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