Papers
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
Online Convex Optimization with Sublinear Noisy Probes
Simone Di Gregorio, Anupam Gupta, Stefano Leonardi et al.
A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance
Ilias Diakonikolas, Jingyi Gao, Giannis Iakovidis et al.
Linear Regression under Missing or Corrupted Coordinates
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane et al.
High-Dimensional Gaussian Mean Estimation under Realizable Contamination
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas
Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
Michał Dereziński, Xiaoyu Dong
The matrix-vector complexity of Ax=b
Michał Dereziński, Ethan N Epperly, Raphael A Meyer
Stochastic Safe Action Model Learning
Zihao Deng, Brendan Juba