
When does gradient descent with logistic loss find interpolating twolayer networks?
We study the training of finitewidth twolayer smoothed ReLU networks f...
read it

Optimal Mean Estimation without a Variance
We study the problem of heavytailed mean estimation in settings where t...
read it

Failures of modeldependent generalization bounds for leastnorm interpolation
We consider bounds on the generalization performance of the leastnorm l...
read it

Optimal Robust Linear Regression in Nearly Linear Time
We study the problem of highdimensional robust linear regression where ...
read it

On Linear Stochastic Approximation: Finegrained PolyakRuppert and NonAsymptotic Concentration
We undertake a precise study of the asymptotic and nonasymptotic proper...
read it

On Thompson Sampling with Langevin Algorithms
Thompson sampling is a methodology for multiarmed bandit problems that ...
read it

SelfDistillation Amplifies Regularization in Hilbert Space
Knowledge distillation introduced in the deep learning context is a meth...
read it

Oracle lower bounds for stochastic gradient sampling algorithms
We consider the problem of sampling from a strongly logconcave density ...
read it

Sampling for Bayesian Mixture Models: MCMC with PolynomialTime Mixing
We study the problem of sampling from the power posterior distribution i...
read it

Hebbian Synaptic Modifications in Spiking Neurons that Learn
In this paper, we derive a new model of synaptic plasticity, based on re...
read it

Learning Nearoptimal Convex Combinations of Basis Models with Generalization Guarantees
The problem of learning an optimal convex combination of basis models ha...
read it

An Efficient Sampling Algorithm for Nonsmooth Composite Potentials
We consider the problem of sampling from a density of the form p(x) ∝(f...
read it

HighOrder Langevin Diffusion Yields an Accelerated MCMC Algorithm
We propose a Markov chain Monte Carlo (MCMC) algorithm based on thirdor...
read it

Bayesian Robustness: A Nonasymptotic Viewpoint
We study the problem of robustly estimating the posterior distribution f...
read it

Improved Bounds for Discretization of Langevin Diffusions: NearOptimal Rates without Convexity
We present an improved analysis of the EulerMaruyama discretization of ...
read it

Quantitative W_1 Convergence of LangevinLike Stochastic Processes with NonConvex Potential StateDependent Noise
We prove quantitative convergence rates at which discrete Langevinlike ...
read it

Benign Overfitting in Linear Regression
The phenomenon of benign overfitting is one of the key mysteries uncover...
read it

Langevin Monte Carlo without Smoothness
Langevin Monte Carlo (LMC) is an iterative algorithm used to generate sa...
read it

OSOM: A Simultaneously Optimal Algorithm for MultiArmed and Linear Contextual Bandits
We consider the stochastic linear (multiarmed) contextual bandit proble...
read it

Testing Markov Chains without Hitting
We study the problem of identity testing of markov chains. In this setti...
read it

Fast Mean Estimation with SubGaussian Rates
We propose an estimator for the mean of a random vector in R^d that can ...
read it

Quantitative Central Limit Theorems for Discrete Stochastic Processes
In this paper, we establish a generalization of the classical Central Li...
read it

LargeScale Markov Decision Problems via the Linear Programming Dual
We consider the problem of controlling a fully specified Markov decision...
read it

DerivativeFree Methods for Policy Optimization: Guarantees for Linear Quadratic Systems
We study derivativefree methods for policy optimization over the class ...
read it

GenOja: A Simple and Efficient Algorithm for Streaming Generalized Eigenvector Computation
In this paper, we study the problems of principal Generalized Eigenvecto...
read it

A simple parameterfree and adaptive approach to optimization under a minimal local smoothness assumption
We study the problem of optimizing a function under a budgeted number of...
read it

Best of many worlds: Robust model selection for online supervised learning
We introduce algorithms for online, fullinformation prediction that are...
read it

Sharp Convergence Rates for Langevin Dynamics in the Nonconvex Setting
We study the problem of sampling from a distribution where the negative ...
read it

Representing smooth functions as compositions of nearidentity functions with implications for deep network optimization
We show that any smooth biLipschitz h can be represented exactly as a c...
read it

Online learning with kernel losses
We present a generalization of the adversarial linear bandits framework,...
read it

Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks
We analyze algorithms for approximating a function f(x) = Φ x mapping ^d...
read it

On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
We provide convergence guarantees in Wasserstein distance for a variety ...
read it

Alternating minimization for dictionary learning with random initialization
We present theoretical guarantees for an alternating minimization algori...
read it

Acceleration and Averaging in Stochastic Mirror Descent Dynamics
We formulate and study a general family of (continuoustime) stochastic ...
read it

Underdamped Langevin MCMC: A nonasymptotic analysis
We study the underdamped Langevin diffusion when the log of the target d...
read it

Recovery Guarantees for Onehiddenlayer Neural Networks
In this paper, we consider regression problems with onehiddenlayer neu...
read it

RL^2: Fast Reinforcement Learning via Slow Reinforcement Learning
Deep reinforcement learning (deep RL) has been successful in learning so...
read it

HitandRun for Sampling and Planning in NonConvex Spaces
We propose the HitandRun algorithm for planning and sampling problems ...
read it

FLAG n' FLARE: Fast LinearlyCoupled Adaptive Gradient Methods
We consider first order gradient methods for effectively optimizing a co...
read it

Linear Programming for LargeScale Markov Decision Problems
We consider the problem of controlling a Markov decision process (MDP) w...
read it

Bounding Embeddings of VC Classes into Maximum Classes
One of the earliest conjectures in computational learning theorythe Sam...
read it

Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions
We study the problem of learning Markov decision processes with finite s...
read it

Oracle inequalities for computationally adaptive model selection
We analyze general model selection procedures using penalized empirical ...
read it

Randomized Smoothing for Stochastic Optimization
We analyze convergence rates of stochastic optimization procedures for n...
read it

Informationtheoretic lower bounds on the oracle complexity of stochastic convex optimization
Relative to the large literature on upper bounds on complexity of convex...
read it

Marginadaptive model selection in statistical learning
A classical condition for fast learning rates is the margin condition, f...
read it