Papers
Testing Noise Assumptions of Learning Algorithms
Surbhi Goel, Adam Klivans, Konstantinos Stavropoulos et al.
Information-Theoretic Thresholds for Bipartite Latent-Space Graphs Under Noisy Observations
Andreas Göbel, Marcus Pappik, Leon Schiller
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
Andreas Göbel, Janosch Ruff, Leon Schiller
Sample-Efficient Omniprediction for Proper Losses
Isaac Gibbs, Ryan J. Tibshirani
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani et al.
Universality of high-dimensional scaling limits of stochastic gradient descent (extended abstract)
Reza Gheissari, Aukosh Jagannath
Fixed-Parameter Tractability of Private Synthetic Data Generation
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath et al.
Nearly Linear-Time User-Level DP-SCO with Optimal Rates
Badih Ghazi, Ravi Kumar, Daogao Liu et al.
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach
Learning Ising Models from Evolutions (Extended Abstract)
Jason Gaitonde, Ankur Moitra, Elchanan Mossel
Toward Simultaneously Optimal Regret in U-Calibration
Rafael Frongillo, Haipeng Luo, Nishant A. Mehta et al.
Space-Efficient Language Generation in the Limit
Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov et al.
Optimal Reconstruction from Linear Queries
Yuval Filmus, Shay Moran, Elizaveta Nesterova
Defensive Generation
Gabriele Farina, Juan Carlos Perdomo
Tight Sample Complexity Bounds for Entropic Best Policy Identification
Amer Essakine, Claire Vernade
The Sample Complexity of Multiclass and Sparse Contextual Bandits
Liad Erez, Fan Chen, Alon Cohen et al.
Leveraging Similarities in Multi-Armed Bandits
Khaled Eldowa, Thibaud Rahier, Augustin Cablant et al.
Theoretical Compression Bounds for Wide Multilayer Perceptrons
Houssam El Cheairi, David Gamarnik, Rahul Mazumder
The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network
Abhigyan Dutta, Itay Safran, Paul Valiant
Relatively Smart: A New Approach for Instance-Optimal Learning
Shaddin Dughmi, Alireza F. Pour
Online Realizable Regression and Applications for ReLU Networks
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
Daniil Dmitriev, Zhihan Huang, Yuting Wei
Rate-optimal community detection near the KS threshold via node-robust algorithms
Jingqiu Ding, Yiding Hua, Kasper Lindberg et al.
Minimax optimal differentially private synthetic data for smooth queries
Rundong Ding, Yiyun He, Yizhe Zhu