Noah Golowich

IACR Cryptol. ePrint Arch., 2024

Improved bounds for calibration via stronger sign preservation games.

[BibT_eX]

[DOI]

Yuval Dagan

CoRR, 2024

A Lower Bound on Swap Regret in Extensive-Form Games.

[BibT_eX]

[DOI]

CoRR, 2024

Online Control in Population Dynamics.

[BibT_eX]

[DOI]

CoRR, 2024

On Learning Parities with Dependent Noise.

[BibT_eX]

[DOI]

CoRR, 2024

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces.

[BibT_eX]

[DOI]

Yuval Dagan

Maxwell Fishelson

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation.

[BibT_eX]

RLJ, 2024

Smooth Nash Equilibria: Algorithms and Complexity.

[BibT_eX]

[DOI]

Nika Haghtalab

Abhishek Shetty

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Is Efficient PAC Learning Possible with an Oracle That Responds "Yes" or "No"?

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Near-Optimal Learning and Planning in Separated Latent MDPs.

[BibT_eX]

[DOI]

Fan Chen

Alexander Rakhlin

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spaces.

[BibT_eX]

[DOI]

Yuval Dagan

Maxwell Fishelson

CoRR, 2023

Planning and Learning in Partially Observable Systems via Filter Stability.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Model-Free Reinforcement Learning with the Decision-Estimation Coefficient.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games.

[BibT_eX]

[DOI]

Dylan J. Foster

Sham M. Kakade

Proceedings of the International Conference on Machine Learning, 2023

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

[BibT_eX]

[DOI]

Dylan J. Foster

Yanjun Han

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

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

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

The Complexity of Markov Equilibrium in Stochastic Games.

[BibT_eX]

[DOI]

Kaiqing Zhang

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

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

[BibT_eX]

[DOI]

Stratis Skoulakis

Emmanouil Zampetakis

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

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

[BibT_eX]

[DOI]

CoRR, 2022

Planning in Observable POMDPs in Quasipolynomial Time.

[BibT_eX]

[DOI]

CoRR, 2022

Fast rates for nonparametric online learning: from realizability to learning in games.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games.

[BibT_eX]

[DOI]

Ioannis Anagnostides

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Learning in Observable POMDPs, without Computationally Intractable Oracles.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Can Q-learning be Improved with Advice?

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Smoothed Online Learning is as Easy as Statistical Learning.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Sample-efficient proper PAC learning with approximate differential privacy.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Littlestone Classes are Privately Online Learnable.

[BibT_eX]

[DOI]

Roi Livni

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Deep Learning with Label Differential Privacy.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Near-Optimal No-Regret Learning in General Games.

[BibT_eX]

[DOI]

Maxwell Fishelson

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - EUROCRYPT 2021, 2021

Differentially Private Nonparametric Regression Under a Growth Condition.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Near-tight closure b ounds for the Littlestone and threshold dimensions.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2021

2020

Near-tight closure bounds for Littlestone and threshold dimensions.

[BibT_eX]

[DOI]

CoRR, 2020

Round Complexity of Common Randomness Generation: The Amortized Setting.

[BibT_eX]

[DOI]

Madhu Sudan

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

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

[BibT_eX]

[DOI]

Sarath Pattathil

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Independent Policy Gradient Methods for Competitive Reinforcement Learning.

[BibT_eX]

[DOI]

Dylan J. Foster

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Pure Differentially Private Summation from Anonymous Messages.

[BibT_eX]

[DOI]

Proceedings of the 1st Conference on Information-Theoretic Cryptography, 2020

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

[BibT_eX]

[DOI]

Sarath Pattathil

Asuman E. Ozdaglar

Proceedings of the Conference on Learning Theory, 2020

2019

On the Power of Multiple Anonymous Messages.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2019

Private Heavy Hitters and Range Queries in the Shuffled Model.

[BibT_eX]

[DOI]

CoRR, 2019

A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the 7th International Conference on Learning Representations, 2019

2018

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Theory of Deep Learning IIb: Optimization Properties of SGD.

[BibT_eX]

[DOI]

CoRR, 2018

Coloring Chains for Compression with Uncertain Priors.

[BibT_eX]

[DOI]

Electron. J. Comb., 2018

Deep Learning for Multi-Facility Location Mechanism Design.

[BibT_eX]

[DOI]

Harikrishna Narasimhan

David C. Parkes

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Size-Independent Sample Complexity of Neural Networks.

[BibT_eX]

[DOI]

Alexander Rakhlin

Ohad Shamir

Proceedings of the Conference On Learning Theory, 2018

2016

The m-degenerate chromatic number of a digraph.

[BibT_eX]

[DOI]

Discret. Math., 2016

2015

Acyclic Subgraphs of Planar Digraphs.

[BibT_eX]

[DOI]

David Rolnick

Electron. J. Comb., 2015

2014

Resolving a Conjecture on Degree of Regularity of Linear Homogeneous Equations.

[BibT_eX]

[DOI]