Papers
1,396 papers found
SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics
Emmanuel Abbe, Enric Boix Adserà, Theodor Misiakiewicz
Sharp analysis of EM for learning mixtures of pairwise differences
Abhishek Dhawan, Cheng Mao, Ashwin Pananjady
Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes
Zihan Zhang, Qiaomin Xie
Sharp thresholds in inference of planted subgraphs
Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn et al.
Shortest Program Interpolation Learning
Naren Sarayu Manoj, Nathan Srebro
Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints
Ankit Pensia, Amir Reza Asadi, Varun Jog et al.
Sparse PCA Beyond Covariance Thresholding
Gleb Novikov
Sparsity-aware generalization theory for deep neural networks
Ramchandran Muthukumar, Jeremias Sulam
SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians
Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas et al.
Statistical and Computational Limits for Tensor-on-Tensor Association Detection
Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo et al.
Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression
Gabriel Arpino, Ramji Venkataramanan
STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games
Constantinos Daskalakis, Noah Golowich, Stratis Skoulakis et al.
Tackling Combinatorial Distribution Shift: A Matrix Completion Perspective
Max Simchowitz, Abhishek Gupta, Kaiqing Zhang
Testing of Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh et al.
The $k$-Cap Process on Geometric Random Graphs
Mirabel E. Reid, Santosh S. Vempala
The Aggregation–Heterogeneity Trade-off in Federated Learning
Xuyang Zhao, Huiyuan Wang, Wei Lin
The Complexity of Markov Equilibrium in Stochastic Games
Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang
The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
Alexandros Hollender, Emmanouil Zampetakis
The Expressive Power of Tuning Only the Normalization Layers
Angeliki Giannou, Shashank Rajput, Dimitris Papailiopoulos
The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks
Yuan Cao, Difan Zou, Yuanzhi Li et al.
The One-Inclusion Graph Algorithm is not Always Optimal
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty et al.
The Sample Complexity of Approximate Rejection Sampling With Applications to Smoothed Online Learning
Adam Block, Yury Polyanskiy
Ticketed Learning–Unlearning Schemes
Badih Ghazi, Pritish Kamath, Ravi Kumar et al.
Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures
Wai Ming Tai, Bryon Aragam