b'Noah Golowich'

research

∙ 09/21/2023

Smooth Nash Equilibria: Algorithms and Complexity

A fundamental shortcoming of the concept of Nash equilibrium is its comp...

0 Constantinos Daskalakis, et al. ∙

research

∙ 09/18/2023

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles

The key assumption underlying linear Markov Decision Processes (MDPs) is...

0 Noah Golowich, 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

∙ 03/22/2023

Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games

We consider the problem of decentralized multi-agent reinforcement learn...

0 Dylan J. Foster, et al. ∙

research

∙ 01/19/2023

Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient

A foundational problem in reinforcement learning and interactive decisio...

0 Dylan J. Foster, 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

∙ 10/18/2022

STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games

Min-max optimization problems involving nonconvex-nonconcave objectives ...

0 Constantinos Daskalakis, et al. ∙

research

∙ 06/07/2022

Learning in Observable POMDPs, without Computationally Intractable Oracles

Much of reinforcement learning theory is built on top of oracles that ar...

0 Noah Golowich, et al. ∙

research

∙ 04/08/2022

The Complexity of Markov Equilibrium in Stochastic Games

We show that computing approximate stationary Markov coarse correlated e...

0 Constantinos Daskalakis, 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

∙ 01/12/2022

Planning in Observable POMDPs in Quasipolynomial Time

Partially Observable Markov Decision Processes (POMDPs) are a natural an...

0 Noah Golowich, et al. ∙

research

∙ 11/24/2021

Differentially Private Nonparametric Regression Under a Growth Condition

Given a real-valued hypothesis class ℋ, we investigate under what condit...

0 Noah Golowich, et al. ∙

research

∙ 11/17/2021

Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games

We study fast rates of convergence in the setting of nonparametric onlin...

0 Constantinos Daskalakis, et al. ∙

research

∙ 11/11/2021

Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games

Recently, Daskalakis, Fishelson, and Golowich (DFG) (NeurIPS`21) showed ...

0 Ioannis Anagnostides, et al. ∙

research

∙ 10/25/2021

Can Q-Learning be Improved with Advice?

Despite rapid progress in theoretical reinforcement learning (RL) over t...

0 Noah Golowich, et al. ∙

research

∙ 08/16/2021

Near-Optimal No-Regret Learning in General Games

We show that Optimistic Hedge – a common variant of multiplicative-weigh...

0 Constantinos Daskalakis, et al. ∙

research

∙ 06/25/2021

Littlestone Classes are Privately Online Learnable

We consider the problem of online classification under a privacy constra...

0 Noah Golowich, et al. ∙

research

∙ 02/11/2021

On Deep Learning with Label Differential Privacy

In many machine learning applications, the training data can contain hig...

0 Badih Ghazi, et al. ∙

research

∙ 01/11/2021

Independent Policy Gradient Methods for Competitive Reinforcement Learning

We obtain global, non-asymptotic convergence guarantees for independent ...

0 Constantinos Daskalakis, et al. ∙

research

∙ 12/07/2020

Sample-efficient proper PAC learning with approximate differential privacy

In this paper we prove that the sample complexity of properly learning a...

0 Badih Ghazi, et al. ∙

research

∙ 10/26/2020

Tight last-iterate convergence rates for no-regret learning in multi-player games

We study the question of obtaining last-iterate convergence rates for no...

0 Noah Golowich, et al. ∙

research

∙ 07/07/2020

Near-tight closure bounds for Littlestone and threshold dimensions

We study closure properties for the Littlestone and threshold dimensions...

0 Badih Ghazi, et al. ∙

research

∙ 02/05/2020

Pure Differentially Private Summation from Anonymous Messages

The shuffled (aka anonymous) model has recently generated significant in...

0 Badih Ghazi, et al. ∙

research

∙ 01/31/2020

Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems

In this paper we study the smooth convex-concave saddle point problem. S...

0 Noah Golowich, et al. ∙

research

∙ 09/01/2019

Round Complexity of Common Randomness Generation: The Amortized Setting

We study the effect of rounds of interaction on the common randomness ge...

0 Noah Golowich, et al. ∙

research

∙ 08/29/2019

Private Heavy Hitters and Range Queries in the Shuffled Model

An exciting new development in differential privacy is the shuffled mode...

0 Badih Ghazi, et al. ∙

research

∙ 10/04/2018

A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks

We analyze speed of convergence to global optimum for gradient descent t...

8 Sanjeev Arora, et al. ∙

research

∙ 08/27/2018

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

We study the role of interaction in the Common Randomness Generation (CR...

0 Mitali Bafna, 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. ∙

Noah Golowich

Featured Co-authors