| 2020 | Open Problem: Information Complexity of VC Learning. | Thomas Steinke, Lydia Zakynthinou |
| 2020 | Reasoning About Generalization via Conditional Mutual Information. | Thomas Steinke, Lydia Zakynthinou |
| 2020 | Improper Learning for Non-Stochastic Control. | Max Simchowitz, Karan Singh, Elad Hazan |
| 2020 | Logistic Regression Regret: What's the Catch? | Gil I. Shamir |
| 2020 | A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere. | Marco Schmalhofer |
| 2020 | How Good is SGD with Random Shuffling? | Itay Safran, Ohad Shamir |
| 2020 | Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits. | Chlo Rouyer, Yevgeny Seldin |
| 2020 | List Decodable Subspace Recovery. | Prasad Raghavendra, Morris Yau |
| 2020 | Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning. | Guannan Qu, Adam Wierman |
| 2020 | Covariance-adapting algorithm for semi-bandits with application to sparse outcomes. | Pierre Perrault, Michal Valko, Vianney Perchet |
| 2020 | Fast Rates for Online Prediction with Abstention. | Gergely Neu, Nikita Zhivotovskiy |
| 2020 | Efficient and robust algorithms for adversarial linear contextual bandits. | Gergely Neu, Julia Olkhovskaya |
| 2020 | Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning. | Mikito Nanashima |
| 2020 | On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration. | Wenlong Mou, Chris Junchi Li, Martin J. Wainwright, Peter L. Bartlett, Michael I. Jordan |
| 2020 | Parallels Between Phase Transitions and Circuit Complexity? | Ankur Moitra, Elchanan Mossel, Colin Sandon |
| 2020 | Information Theoretic Optimal Learning of Gaussian Graphical Models. | Sidhant Misra, Marc Vuffray, Andrey Y. Lokhov |
| 2020 | Lipschitz and Comparator-Norm Adaptivity in Online Learning. | Zakaria Mhammedi, Wouter M. Koolen |
| 2020 | Tight Lower Bounds for Combinatorial Multi-Armed Bandits. | Nadav Merlis, Shie Mannor |
| 2020 | Open Problem: Average-Case Hardness of Hypergraphic Planted Clique Detection. | Yuetian Luo, Anru R. Zhang |
| 2020 | Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation. | Allen Liu, Ankur Moitra |
| 2020 | Near-Optimal Algorithms for Minimax Optimization. | Tianyi Lin, Chi Jin, Michael I. Jordan |
| 2020 | Learning Over-Parametrized Two-Layer Neural Networks beyond NTK. | Yuanzhi Li, Tengyu Ma, Hongyang R. Zhang |
| 2020 | Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model. | Yingyu Liang, Hui Yuan |
| 2020 | On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels. | Tengyuan Liang, Alexander Rakhlin, Xiyu Zhai |
| 2020 | Costly Zero Order Oracles. | Renato Paes Leme, Jon Schneider |