| 2021 | Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes. | Dongruo Zhou, Quanquan Gu, Csaba Szepesvri |
| 2021 | A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network. | Mo Zhou, Rong Ge, Chi Jin |
| 2021 | Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov Noise. | Chicheng Zhang, Yinan Li |
| 2021 | Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon. | Zihan Zhang, Xiangyang Ji, Simon S. Du |
| 2021 | Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation. | Andrea Zanette, Ching-An Cheng, Alekh Agarwal |
| 2021 | Open Problem: Can Single-Shuffle SGD be Better than Reshuffling SGD and GD? | Chulhee Yun, Suvrit Sra, Ali Jadbabaie |
| 2021 | Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap. | Haike Xu, Tengyu Ma, Simon S. Du |
| 2021 | The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication. | Blake E. Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro |
| 2021 | On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function. | Gellrt Weisz, Philip Amortila, Barnabs Janzer, Yasin Abbasi-Yadkori, Nan Jiang, Csaba Szepesvri |
| 2021 | Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games. | Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng Luo |
| 2021 | Non-stationary Reinforcement Learning without Prior Knowledge: an Optimal Black-box Approach. | Chen-Yu Wei, Haipeng Luo |
| 2021 | Implicit Regularization in ReLU Networks with the Square Loss. | Gal Vardi, Ohad Shamir |
| 2021 | Size and Depth Separation in Approximating Benign Functions with Neural Networks. | Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir |
| 2021 | Open Problem: Tight Online Confidence Intervals for RKHS Elements. | Sattar Vakili, Jonathan Scarlett, Tara Javidi |
| 2021 | A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation. | Adrien Vacher, Boris Muzellec, Alessandro Rudi, Francis R. Bach, Franois-Xavier Vialard |
| 2021 | Machine Unlearning via Algorithmic Stability. | Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi, Raman Arora |
| 2021 | On Empirical Bayes Variational Autoencoder: An Excess Risk Bound. | Rong Tang, Yun Yang |
| 2021 | Efficient Bandit Convex Optimization: Beyond Linear Losses. | Arun Sai Suggala, Pradeep Ravikumar, Praneeth Netrapalli |
| 2021 | Johnson-Lindenstrauss Transforms with Best Confidence. | Maciej Skorski |
| 2021 | Lazy OCO: Online Convex Optimization on a Switching Budget. | Uri Sherman, Tomer Koren |
| 2021 | Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball. | Othmane Sebbouh, Robert M. Gower, Aaron Defazio |
| 2021 | The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks. | Itay Safran, Gilad Yehudai, Ohad Shamir |
| 2021 | Average-Case Communication Complexity of Statistical Problems. | Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu |
| 2021 | Exponential Weights Algorithms for Selective Learning. | Mingda Qiao, Gregory Valiant |
| 2021 | Exponential savings in agnostic active learning through abstention. | Nikita Puchkin, Nikita Zhivotovskiy |