research
∙
08/28/2023
Rate-Optimal Policy Optimization for Linear Markov Decision Processes
We study regret minimization in online episodic linear Markov Decision P...
share
research
∙
03/02/2023
Tight Risk Bounds for Gradient Descent on Separable Data
We study the generalization properties of unregularized gradient methods...
research
∙
02/27/2023
Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime
We consider online learning problems in the realizable setting, where th...
research
∙
02/17/2023
SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance
We study Stochastic Gradient Descent with AdaGrad stepsizes: a popular a...
research
∙
01/30/2023
Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation
We study reinforcement learning with linear function approximation and a...
research
∙
10/24/2022
Private Online Prediction from Experts: Separations and Faster Rates
Online prediction from experts is a fundamental problem in machine learn...
research
∙
07/28/2022
Regret Minimization and Convergence to Equilibria in General-sum Markov Games
An abundance of recent impossibility results establish that regret minim...
research
∙
07/17/2022
Uniform Stability for First-Order Empirical Risk Minimization
We consider the problem of designing uniformly stable first-order optimi...
research
∙
06/07/2022
Better Best of Both Worlds Bounds for Bandits with Switching Costs
We study best-of-both-worlds algorithms for bandits with switching cost,...
research
∙
06/03/2022
Rate-Optimal Online Convex Optimization in Adaptive Linear Control
We consider the problem of controlling an unknown linear dynamical syste...
research
∙
03/02/2022
Efficient Online Linear Control with Stochastic Convex Costs and Unknown Dynamics
We consider the problem of controlling an unknown linear dynamical syste...
research
∙
02/27/2022
Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond
An influential line of recent work has focused on the generalization pro...
research
∙
02/27/2022
Benign Underfitting of Stochastic Gradient Descent
We study to what extent may stochastic gradient descent (SGD) be underst...
research
∙
07/20/2021
Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
We study the online learning with feedback graphs framework introduced b...
research
∙
06/29/2021
Never Go Full Batch (in Stochastic Convex Optimization)
We study the generalization performance of full-batch optimization algor...
research
∙
06/29/2021
Optimal Rates for Random Order Online Optimization
We study online convex optimization in the random order model, recently ...
research
∙
06/22/2021
Asynchronous Stochastic Optimization Robust to Arbitrary Delays
We consider stochastic optimization with delayed gradients where, at eac...
research
∙
06/04/2021
Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions
We study the stochastic Multi-Armed Bandit (MAB) problem with random del...
research
∙
03/02/2021
Private Stochastic Convex Optimization: Optimal Rates in ℓ_1 Geometry
Stochastic convex optimization over an ℓ_1-bounded domain is ubiquitous ...
research
∙
02/25/2021
Online Policy Gradient for Model Free Learning of Linear Quadratic Regulators with √(T) Regret
We consider the task of learning to control a linear dynamical system un...
research
∙
02/24/2021
Multiplicative Reweighting for Robust Neural Network Optimization
Deep neural networks are widespread due to their powerful performance. Y...
research
∙
02/07/2021
Lazy OCO: Online Convex Optimization on a Switching Budget
We study a variant of online convex optimization where the player is per...
research
∙
02/03/2021
The Instability of Accelerated Gradient Descent
We study the algorithmic stability of Nesterov's accelerated gradient me...
research
∙
02/01/2021
SGD Generalizes Better Than GD (And Regularization Doesn't Help)
We give a new separation result between the generalization performance o...
research
∙
01/31/2021
Online Markov Decision Processes with Aggregate Bandit Feedback
We study a novel variant of online finite-horizon Markov Decision Proces...
research
∙
10/27/2020
Adversarial Dueling Bandits
We introduce the problem of regret minimization in Adversarial Dueling B...
research
∙
10/26/2020
Stochastic Optimization with Laggard Data Pipelines
State-of-the-art optimization is steadily shifting towards massively par...
research
∙
08/11/2020
Holdout SGD: Byzantine Tolerant Federated Learning
This work presents a new distributed Byzantine tolerant federated learni...
research
∙
07/01/2020
Bandit Linear Control
We consider the problem of controlling a known linear dynamical system u...
research
∙
05/10/2020
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
We study differentially private (DP) algorithms for stochastic convex op...
research
∙
03/13/2020
Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study
The notion of implicit bias, or implicit regularization, has been sugges...
research
∙
02/26/2020
Disentangling Adaptive Gradient Methods from Learning Rates
We investigate several confounding factors in the evaluation of optimiza...
research
∙
02/24/2020
Prediction with Corrupted Expert Advice
We revisit the fundamental problem of prediction with expert advice, in ...
research
∙
02/20/2020
Second Order Optimization Made Practical
Optimization in machine learning, both theoretical and applied, is prese...
research
∙
02/19/2020
Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently
We consider the problem of learning in Linear Quadratic Control systems ...
research
∙
06/08/2019
Robust Bi-Tempered Logistic Loss Based on Bregman Divergences
We introduce a temperature into the exponential function and replace the...
research
∙
04/23/2019
Semi-Cyclic Stochastic Gradient Descent
We consider convex SGD updates with a block-cyclic structure, i.e. where...
research
∙
02/22/2019
Better Algorithms for Stochastic Bandits with Adversarial Corruptions
We study the stochastic multi-armed bandits problem in the presence of a...
research
∙
02/17/2019
Learning Linear-Quadratic Regulators Efficiently with only √(T) Regret
We present the first computationally-efficient algorithm with O(√(T)) r...
research
∙
01/30/2019
Memory-Efficient Adaptive Optimization for Large-Scale Learning
Adaptive gradient-based optimizers such as AdaGrad and Adam are among th...
research
∙
06/19/2018
Online Linear Quadratic Control
We study the problem of controlling linear time-invariant systems with k...
research
∙
02/26/2018
Shampoo: Preconditioned Stochastic Tensor Optimization
Preconditioned gradient methods are among the most general and powerful ...
research
∙
06/20/2017
A Unified Approach to Adaptive Regularization in Online and Stochastic Optimization
We describe a framework for deriving and analyzing online optimization a...
research
∙
05/23/2016
Online Learning with Feedback Graphs Without the Graphs
We study an online learning framework introduced by Mannor and Shamir (2...
research
∙
06/18/2012