Papers
Depth Separations in Neural Networks: What is Actually Being Separated?
Itay Safran, Ronen Eldan, Ohad Shamir
The All-or-Nothing Phenomenon in Sparse Linear Regression
Galen Reeves, Jiaming Xu, Ilias Zadik
Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon
Alexander Rakhlin, Xiyu Zhai
A Theory of Selective Prediction
Mingda Qiao, Gregory Valiant
Affine Invariant Covariance Estimation for Heavy-Tailed Distributions
Dmitrii M. Ostrovskii, Alessandro Rudi
VC Classes are Adversarially Robustly Learnable, but Only Improperly
Omar Montasser, Steve Hanneke, Nathan Srebro
Lipschitz Adaptivity with Multiple Learning Rates in Online Learning
Zakaria Mhammedi, Wouter M Koolen, Tim Van Erven
Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
Nadav Merlis, Shie Mannor
Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit
Song Mei, Theodor Misiakiewicz, Andrea Montanari
Uniform concentration and symmetrization for weak interactions
Andreas Maurer, Massimiliano Pontil
Planting trees in graphs, and finding them back
Laurent Massoulié, Ludovic Stephan, Don Towsley
Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance
Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis Bach et al.
Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
Oren Mangoubi, Nisheeth K Vishnoi
Combinatorial Algorithms for Optimal Design
Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat et al.
Sharp Theoretical Analysis for Nonparametric Testing under Random Projection
Meimei Liu, Zuofeng Shang, Guang Cheng
Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
Yingkai Li, Yining Wang, Yuan Zhou
On Mean Estimation for General Norms with Statistical Queries
Jerry Li, Aleksandar Nikolov, Ilya Razenshteyn et al.
Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
Yin Tat Lee, Zhao Song, Qiuyi Zhang
An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
Tor Lattimore, Csaba Szepesvári
Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression
Jeongyeol Kwon, Wei Qian, Constantine Caramanis et al.
Distribution-Dependent Analysis of Gibbs-ERM Principle
Ilja Kuzborskij, Nicolò Cesa-Bianchi, Csaba Szepesvári
Contextual bandits with continuous actions: Smoothing, zooming, and adapting
Akshay Krishnamurthy, John Langford, Aleksandrs Slivkins et al.
Bandit Principal Component Analysis
Wojciech Kotłowski, Gergely Neu