Alexander Rakhlin

research

∙ 07/08/2023

Efficient Model-Free Exploration in Low-Rank MDPs

A major challenge in reinforcement learning is to develop practical, sam...

0 Zakaria Mhammedi, et al. ∙

research

∙ 06/02/2023

Convex and Non-Convex Optimization under Generalized Smoothness

Classical analysis of convex and non-convex optimization methods often r...

0 Haochuan Li, et al. ∙

research

∙ 05/29/2023

On the Variance, Admissibility, and Stability of Empirical Risk Minimization

It is well known that Empirical Risk Minimization (ERM) with squared los...

3 Gil Kur, et al. ∙

research

∙ 05/01/2023

On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring

A central problem in the theory of multi-agent reinforcement learning (M...

3 Dylan J. Foster, et al. ∙

research

∙ 04/27/2023

Convergence of Adam Under Relaxed Assumptions

In this paper, we provide a rigorous proof of convergence of the Adaptiv...

1 Haochuan Li, et al. ∙

research

∙ 04/12/2023

Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL

We study the design of sample-efficient algorithms for reinforcement lea...

1 Zakaria Mhammedi, et al. ∙

research

∙ 03/06/2023

Lower Bounds for γ-Regret via the Decision-Estimation Coefficient

In this note, we give a new lower bound for the γ-regret in bandit probl...

0 Margalit Glasgow, et al. ∙

research

∙ 02/10/2023

Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making

Smoothed online learning has emerged as a popular framework to mitigate ...

2 Adam Block, et al. ∙

research

∙ 11/25/2022

A Note on Model-Free Reinforcement Learning with the Decision-Estimation Coefficient

We consider the problem of interactive decision making, encompassing str...

9 Dylan J. Foster, et al. ∙

research

∙ 06/27/2022

On the Complexity of Adversarial Decision Making

A central problem in online learning and decision making – from bandits ...

8 Dylan J. Foster, et al. ∙

research

∙ 05/04/2022

Rate of convergence of the smoothed empirical Wasserstein distance

Consider an empirical measure ℙ_n induced by n iid samples from a d-dime...

0 Adam Block, et al. ∙

research

∙ 02/15/2022

Damped Online Newton Step for Portfolio Selection

We revisit the classic online portfolio selection problem, where at each...

5 Zakaria Mhammedi, et al. ∙

research

∙ 02/09/2022

Smoothed Online Learning is as Easy as Statistical Learning

Much of modern learning theory has been split between two regimes: the c...

0 Adam Block, et al. ∙

research

∙ 12/27/2021

The Statistical Complexity of Interactive Decision Making

A fundamental challenge in interactive learning and decision making, ran...

13 Dylan J. Foster, et al. ∙

research

∙ 12/03/2021

On Submodular Contextual Bandits

We consider the problem of contextual bandits where actions are subsets ...

5 Dean P. Foster, et al. ∙

research

∙ 06/08/2021

Intrinsic Dimension Estimation

It has long been thought that high-dimensional data encountered in many ...

12 Adam Block, et al. ∙

research

∙ 03/16/2021

Deep learning: a statistical viewpoint

The remarkable practical success of deep learning has revealed some majo...

13 Peter L. Bartlett, et al. ∙

research

∙ 02/24/2021

On the Minimal Error of Empirical Risk Minimization

We study the minimal error of the Empirical Risk Minimization (ERM) proc...

7 Gil Kur, et al. ∙

research

∙ 02/15/2021

Top-k eXtreme Contextual Bandits with Arm Hierarchy

Motivated by modern applications, such as online advertisement and recom...

4 Rajat Sen, et al. ∙

research

∙ 10/08/2020

Learning the Linear Quadratic Regulator from Nonlinear Observations

We introduce a new problem setting for continuous control called the LQR...

4 Zakaria Mhammedi, et al. ∙

research

∙ 10/07/2020

Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

In the classical multi-armed bandit problem, instance-dependent algorith...

10 Dylan J. Foster, et al. ∙

research

∙ 06/19/2020

Fast Mixing of Multi-Scale Langevin Dynamics under the Manifold Hypothesis

Recently, the task of image generation has attracted much attention. In ...

6 Adam Block, et al. ∙

research

∙ 06/19/2020

Fast Mixing of Multi-Scale Langevin Dynamics underthe Manifold Hypothesis

Recently, the task of image generation has attracted much attention. In ...

1 Adam Block, et al. ∙

research

∙ 06/07/2020

On Suboptimality of Least Squares with Application to Estimation of Convex Bodies

We develop a technique for establishing lower bounds on the sample compl...

0 Gil Kur, et al. ∙

research

∙ 04/30/2020

Learning nonlinear dynamical systems from a single trajectory

We introduce algorithms for learning nonlinear dynamical systems of the ...

8 Dylan J. Foster, et al. ∙

research

∙ 02/12/2020

Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles

A fundamental challenge in contextual bandits is to develop flexible, ge...

9 Dylan J. Foster, et al. ∙

research

∙ 01/31/2020

Generative Modeling with Denoising Auto-Encoders and Langevin Sampling

We study convergence of a generative modeling method that first estimate...

1 Adam Block, et al. ∙

research

∙ 11/15/2019

ℓ_∞ Vector Contraction for Rademacher Complexity

We show that the Rademacher complexity of any R^K-valued function class ...

15 Dylan J. Foster, et al. ∙

research

∙ 08/27/2019

On the Risk of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels

We study the risk of minimum-norm interpolants of data in a Reproducing ...

6 Tengyuan Liang, et al. ∙

research

∙ 05/05/2019

Breast Tumor Cellularity Assessment using Deep Neural Networks

Breast cancer is one of the main causes of death worldwide. Histopatholo...

7 Alexander Rakhlin, et al. ∙

research

∙ 12/28/2018

Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon

We show that minimum-norm interpolation in the Reproducing Kernel Hilber...

16 Alexander Rakhlin, et al. ∙

research

∙ 08/01/2018

Just Interpolate: Kernel "Ridgeless" Regression Can Generalize

In the absence of explicit regularization, Kernel "Ridgeless" Regression...

0 Tengyuan Liang, et al. ∙

research

∙ 06/25/2018

Does data interpolation contradict statistical optimality?

We show that learning methods interpolating the training data can achiev...

4 Mikhail Belkin, et al. ∙

research

∙ 04/21/2018

Angiodysplasia Detection and Localization Using Deep Convolutional Neural Networks

Accurate detection and localization for angiodysplasia lesions is an imp...

0 Alexey Shvets, et al. ∙

research

∙ 03/20/2018

Online Learning: Sufficient Statistics and the Burkholder Method

We uncover a fairly general principle in online learning: If regret can ...

0 Dylan J. Foster, et al. ∙

research

∙ 03/03/2018

Automatic Instrument Segmentation in Robot-Assisted Surgery Using Deep Learning

Semantic segmentation of robotic instruments is an important problem for...

0 Alexey Shvets, et al. ∙

research

∙ 02/02/2018

Deep Convolutional Neural Networks for Breast Cancer Histology Image Analysis

Breast cancer is one of the main causes of cancer death worldwide. Early...

0 Alexander Rakhlin, et al. ∙

research

∙ 01/07/2018

Theory of Deep Learning IIb: Optimization Properties of SGD

In Theory IIb we characterize with a mix of theory and experiments the o...

0 Chiyuan Zhang, et al. ∙

research

∙ 12/18/2017

Size-Independent Sample Complexity of Neural Networks

We study the sample complexity of learning neural networks, by providing...

0 Noah Golowich, et al. ∙

research

∙ 12/13/2017

Pediatric Bone Age Assessment Using Deep Convolutional Neural Networks

Skeletal bone age assessment is a common clinical practice to diagnose e...

0 Vladimir Iglovikov, et al. ∙

research

∙ 11/05/2017

Fisher-Rao Metric, Geometry, and Complexity of Neural Networks

We study the relationship between geometry and capacity measures for dee...

0 Tengyuan Liang, et al. ∙

research

∙ 09/12/2017

Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information

We study the misclassification error for community detection in general ...

0 T. Tony Cai, et al. ∙

research

∙ 04/13/2017

ZigZag: A new approach to adaptive online learning

We develop a novel family of algorithms for the online learning setting ...

0 Dylan J. Foster, et al. ∙

research

∙ 02/13/2017

Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis

Stochastic Gradient Langevin Dynamics (SGLD) is a popular variant of Sto...

0 Maxim Raginsky, et al. ∙

research

∙ 08/31/2016

A Tutorial on Online Supervised Learning with Applications to Node Classification in Social Networks

We revisit the elegant observation of T. Cover '65 which, perhaps, is no...

0 Alexander Rakhlin, et al. ∙

research

∙ 03/22/2016

Inference via Message Passing on Partially Labeled Stochastic Block Models

We study the community detection and recovery problem in partially-label...

0 T. Tony Cai, et al. ∙

research

∙ 02/06/2016

BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits

We present efficient algorithms for the problem of contextual bandits wi...

0 Alexander Rakhlin, et al. ∙

research

∙ 10/13/2015

On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities

We study an equivalence of (i) deterministic pathwise statements appeari...

0 Alexander Rakhlin, et al. ∙

research

∙ 08/21/2015

Adaptive Online Learning

We propose a general framework for studying adaptive regret bounds in th...

0 Dylan J. Foster, et al. ∙

research

∙ 03/04/2015

Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints

We study online prediction where regret of the algorithm is measured aga...

0 Alexander Rakhlin, et al. ∙

Alexander Rakhlin

Featured Co-authors