Srebro, Nathan

122 publications

COLT 2025 A Theory of Learning with Autoregressive Chain of Thought Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, Nathan Srebro

NeurIPS 2025 Learning Single Index Models via Harmonic Decomposition Nirmit Joshi, Hugo Koubbi, Theodor Misiakiewicz, Nathan Srebro

ICML 2025 PENCIL: Long Thoughts with Short Memory Chenxiao Yang, Nathan Srebro, David Mcallester, Zhiyuan Li

ICLRW 2025 PENCIL: Long Thoughts with Short Memory Chenxiao Yang, Nathan Srebro, David McAllester, Zhiyuan Li

COLT 2025 Quantifying Overfitting Along the Regularization Path for Two-Part-Code MDL in Supervised Classification Xiaohan Zhu, Nathan Srebro

NeurIPS 2025 Temperature Is All You Need for Generalization in Langevin Dynamics and Other Markov Processes Itamar Harel, Yonathan Wolanowsky, Gal Vardi, Nathan Srebro, Daniel Soudry

ICML 2025 Weak-to-Strong Generalization Even in Random Feature Networks, Provably Marko Medvedev, Kaifeng Lyu, Dingli Yu, Sanjeev Arora, Zhiyuan Li, Nathan Srebro

ICLR 2024 An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression Lijia Zhou, James B Simon, Gal Vardi, Nathan Srebro

COLT 2024 Depth Separation in Norm-Bounded Infinite-Width Neural Networks Suzanna Parkinson, Greg Ongie, Rebecca Willett, Ohad Shamir, Nathan Srebro

ICML 2024 How Uniform Random Weights Induce Non-Uniform Bias: Typical Interpolating Neural Networks Generalize with Narrow Teachers Gon Buzaglo, Itamar Harel, Mor Shpigel Nacson, Alon Brutzkus, Nathan Srebro, Daniel Soudry

COLT 2024 Metalearning with Very Few Samples per Task Maryam Aliakbarpour, Konstantina Bairaktari, Gavin Brown, Adam Smith, Nathan Srebro, Jonathan Ullman

ICLR 2024 Noisy Interpolation Learning with Shallow Univariate ReLU Networks Nirmit Joshi, Gal Vardi, Nathan Srebro

NeurIPS 2024 On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries Nirmit Joshi, Theodor Misiakiewicz, Nathan Srebro

NeurIPS 2024 Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality Marko Medvedev, Gal Vardi, Nathan Srebro

NeurIPS 2024 Provable Tempered Overfitting of Minimal Nets and Typical Nets Itamar Harel, William M. Hoza, Gal Vardi, Itay Evron, Nathan Srebro, Daniel Soudry

ICMLW 2024 Provable Tempered Overfitting of Minimal Nets and Typical Nets Itamar Harel, William M. Hoza, Gal Vardi, Itay Evron, Nathan Srebro, Daniel Soudry

COLT 2024 The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication Kumar Kshitij Patel, Margalit Glasgow, Ali Zindari, Lingxiao Wang, Sebastian U Stich, Ziheng Cheng, Nirmit Joshi, Nathan Srebro

NeurIPS 2024 The Price of Implicit Bias in Adversarially Robust Generalization Nikolaos Tsilivis, Natalie S. Frank, Nathan Srebro, Julia Kempe

COLT 2023 Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization Spencer Frei, Gal Vardi, Peter Bartlett, Nathan Srebro

ICML 2023 Continual Learning in Linear Classification on Separable Data Itay Evron, Edward Moroshko, Gon Buzaglo, Maroun Khriesh, Badea Marjieh, Nathan Srebro, Daniel Soudry

ICML 2023 Federated Online and Bandit Convex Optimization Kumar Kshitij Patel, Lingxiao Wang, Aadirupa Saha, Nathan Srebro

ICLR 2023 Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data Spencer Frei, Gal Vardi, Peter Bartlett, Nathan Srebro, Wei Hu

ICMLW 2023 On the Still Unreasonable Effectiveness of Federated Averaging for Heterogeneous Distributed Learning Kumar Kshitij Patel, Margalit Glasgow, Lingxiao Wang, Nirmit Joshi, Nathan Srebro

COLT 2023 Shortest Program Interpolation Learning Naren Sarayu Manoj, Nathan Srebro

ICMLW 2023 When Is Agnostic Reinforcement Learning Statistically Tractable? Gene Li, Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, Nathan Srebro

AISTATS 2022 Transductive Robust Learning Guarantees Omar Montasser, Steve Hanneke, Nathan Srebro

NeurIPSW 2022 Distributed Online and Bandit Convex Optimization Kumar Kshitij Patel, Aadirupa Saha, Lingxiao Wang, Nathan Srebro

COLT 2022 How Catastrophic Can Catastrophic Forgetting Be in Linear Regression? Itay Evron, Edward Moroshko, Rachel Ward, Nathan Srebro, Daniel Soudry

ICML 2022 Implicit Bias of the Step Size in Linear Diagonal Neural Networks Mor Shpigel Nacson, Kavya Ravichandran, Nathan Srebro, Daniel Soudry

IJCAI 2022 The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication (Extended Abstract) Blake E. Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro

AISTATS 2021 Does Invariant Risk Minimization Capture Invariance? Pritish Kamath, Akilesh Tangella, Danica Sutherland, Nathan Srebro

AISTATS 2021 Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent Suriya Gunasekar, Blake Woodworth, Nathan Srebro

NeurIPS 2021 A Stochastic Newton Algorithm for Distributed Convex Optimization Brian Bullins, Kshitij Patel, Ohad Shamir, Nathan Srebro, Blake E Woodworth

COLT 2021 Adversarially Robust Learning with Unknown Perturbation Sets Omar Montasser, Steve Hanneke, Nathan Srebro

NeurIPS 2021 An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning Blake E Woodworth, Nathan Srebro

ICML 2021 Dropout: Explicit Forms and Capacity Control Raman Arora, Peter Bartlett, Poorya Mianjy, Nathan Srebro

NeurIPSW 2021 Exponential Family Model-Based Reinforcement Learning via Score Matching Gene Li, Junbo Li, Nathan Srebro, Zhaoran Wang, Zhuoran Yang

ICML 2021 Fast Margin Maximization via Dual Acceleration Ziwei Ji, Nathan Srebro, Matus Telgarsky

ICML 2021 On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E Woodworth, Nathan Srebro, Amir Globerson, Daniel Soudry

NeurIPS 2021 On the Power of Differentiable Learning Versus PAC and SQ Learning Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, Nathan Srebro

ICML 2021 Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels Eran Malach, Pritish Kamath, Emmanuel Abbe, Nathan Srebro

NeurIPS 2021 Representation Costs of Linear Neural Networks: Analysis and Design Zhen Dai, Mina Karzand, Nathan Srebro

COLT 2021 The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication Blake E Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro

NeurIPS 2021 Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting Frederic Koehler, Lijia Zhou, Danica J. Sutherland, Nathan Srebro

ICLR 2020 A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case Greg Ongie, Rebecca Willett, Daniel Soudry, Nathan Srebro

ALT 2020 A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates Yossi Arjevani, Ohad Shamir, Nathan Srebro

COLT 2020 Approximate Is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity Pritish Kamath, Omar Montasser, Nathan Srebro

ICLR 2020 Dropout: Explicit Forms and Capacity Control Raman Arora, Peter Bartlett, Poorya Mianjy, Nathan Srebro

ICML 2020 Efficiently Learning Adversarially Robust Halfspaces with Noise Omar Montasser, Surbhi Goel, Ilias Diakonikolas, Nathan Srebro

ICML 2020 Fair Learning with Private Demographic Data Hussein Mozannar, Mesrob Ohannessian, Nathan Srebro

AISTATS 2020 Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis Ryan Rogers, Aaron Roth, Adam Smith, Nathan Srebro, Om Thakkar, Blake Woodworth

ICML 2020 Is Local SGD Better than Minibatch SGD? Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, Nathan Srebro

COLT 2020 Kernel and Rich Regimes in Overparametrized Models Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, Nathan Srebro

AISTATS 2019 Convergence of Gradient Descent on Separable Data Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, Daniel Soudry

COLT 2019 How Do Infinite Width Bounded Norm Networks Look in Function Space? Pedro Savarese, Itay Evron, Daniel Soudry, Nathan Srebro

ICML 2019 Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, Daniel Soudry

COLT 2019 Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory Blake Woodworth, Nathan Srebro

ICML 2019 Semi-Cyclic Stochastic Gradient Descent Hubert Eichner, Tomer Koren, Brendan Mcmahan, Nathan Srebro, Kunal Talwar

JMLR 2019 Stochastic Canonical Correlation Analysis Chao Gao, Dan Garber, Nathan Srebro, Jialei Wang, Weiran Wang

AISTATS 2019 Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate Mor Shpigel Nacson, Nathan Srebro, Daniel Soudry

ALT 2019 Stochastic Nonconvex Optimization with Large Minibatches Weiran Wang, Nathan Srebro

COLT 2019 The Complexity of Making the Gradient Small in Stochastic Convex Optimization Dylan J. Foster, Ayush Sekhari, Ohad Shamir, Nathan Srebro, Karthik Sridharan, Blake Woodworth

ICLR 2019 The Role of Over-Parametrization in Generalization of Neural Networks Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, Nathan Srebro

ICML 2019 Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, Seungil You

COLT 2019 VC Classes Are Adversarially Robustly Learnable, but Only Improperly Omar Montasser, Steve Hanneke, Nathan Srebro

ICLR 2018 A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks Behnam Neyshabur, Srinadh Bhojanapalli, Nathan Srebro

ICML 2018 Characterizing Implicit Bias in Terms of Optimization Geometry Suriya Gunasekar, Jason Lee, Daniel Soudry, Nathan Srebro

ALT 2018 Efficient Coordinate-Wise Leading Eigenvector Computation Jialei Wang, Weiran Wang, Dan Garber, Nathan Srebro

ICLR 2018 The Implicit Bias of Gradient Descent on Separable Data Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Nathan Srebro

JMLR 2018 The Implicit Bias of Gradient Descent on Separable Data Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, Nathan Srebro

ICML 2017 Communication-Efficient Algorithms for Distributed Stochastic Principal Component Analysis Dan Garber, Ohad Shamir, Nathan Srebro

ICML 2017 Efficient Distributed Learning with Sparsity Jialei Wang, Mladen Kolar, Nathan Srebro, Tong Zhang

COLT 2017 Learning Non-Discriminatory Predictors Blake Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, Nathan Srebro

COLT 2017 Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox Jialei Wang, Weiran Wang, Nathan Srebro

ICLR 2016 Data-Dependent Path Normalization in Neural Networks Behnam Neyshabur, Ryota Tomioka, Ruslan Salakhutdinov, Nathan Srebro

AISTATS 2016 Distributed Multi-Task Learning Jialei Wang, Mladen Kolar, Nathan Srebro

AISTATS 2016 Fast and Scalable Structural SVM with Slack Rescaling Heejin Choi, Ofer Meshi, Nathan Srebro

AISTATS 2015 Efficient Training of Structured SVMs via Soft Constraints Ofer Meshi, Nathan Srebro, Tamir Hazan

ICLR 2015 In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning Behnam Neyshabur, Ryota Tomioka, Nathan Srebro

JMLR 2015 Learning Sparse Low-Threshold Linear Classifiers Sivan Sabato, Shai Shalev-Shwartz, Nathan Srebro, Daniel Hsu, Tong Zhang

COLT 2015 Norm-Based Capacity Control in Neural Networks Behnam Neyshabur, Ryota Tomioka, Nathan Srebro

ICML 2015 On Symmetric and Asymmetric LSHs for Inner Product Search Behnam Neyshabur, Nathan Srebro

ALT 2014 Clustering, Hamming Embedding, Generalized LSH and the Max Norm Behnam Neyshabur, Yury Makarychev, Nathan Srebro

JMLR 2013 Distribution-Dependent Sample Complexity of Large Margin Learning Sivan Sabato, Nathan Srebro, Naftali Tishby

AISTATS 2012 Approximate Inference by Intersecting Semidefinite Bound and Local Polytope Jian Peng, Tamir Hazan, Nathan Srebro, Jinbo Xu

ICML 2012 Clustering Using Max-Norm Constrained Optimization Ali Jalali, Nathan Srebro

NeurIPS 2012 Matrix Reconstruction with the Local Max Norm Rina Foygel, Nathan Srebro, Ruslan Salakhutdinov

ICML 2012 Minimizing the Misclassification Error Rate Using a Surrogate Convex Loss Shai Ben-David, David Loker, Nathan Srebro, Karthik Sridharan

COLT 2012 Preface Shie Mannor, Nathan Srebro, Robert C. Williamson

NeurIPS 2012 Sparse Prediction with the $k$-Support Norm Andreas Argyriou, Rina Foygel, Nathan Srebro

ICML 2012 The Kernelized Stochastic Batch Perceptron Andrew Cotter, Shai Shalev-Shwartz, Nathan Srebro

COLT 2011 Concentration-Based Guarantees for Low-Rank Matrix Reconstruction Rina Foygel, Nathan Srebro

AISTATS 2011 Error Analysis of Laplacian Eigenmaps for Semi-Supervised Learning Xueyuan Zhou, Nathan Srebro

UAI 2011 Semi-Supervised Learning with Density Based Distances Avleen Singh Bijral, Nathan D. Ratliff, Nathan Srebro

NeurIPS 2010 Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm Nathan Srebro, Ruslan Salakhutdinov

JMLR 2010 Learnability, Stability and Uniform Convergence Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan

NeurIPS 2010 Practical Large-Scale Optimization for Max-Norm Regularization Jason Lee, Ben Recht, Nathan Srebro, Joel Tropp, Ruslan Salakhutdinov

AISTATS 2010 Reducing Label Complexity by Learning from Bags Sivan Sabato, Nathan Srebro, Naftali Tishby

NeurIPS 2010 Smoothness, Low Noise and Fast Rates Nathan Srebro, Karthik Sridharan, Ambuj Tewari

NeurIPS 2010 Tight Sample Complexity of Large-Margin Learning Sivan Sabato, Nathan Srebro, Naftali Tishby

COLT 2009 Learnability and Stability in the General Learning Setting Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan

NeurIPS 2009 Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data Boaz Nadler, Nathan Srebro, Xueyuan Zhou

COLT 2009 Stochastic Convex Optimization Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan

MLJ 2008 A Theory of Learning with Similarity Functions Maria-Florina Balcan, Avrim Blum, Nathan Srebro

UAI 2008 Complexity of Inference in Graphical Models Venkat Chandrasekaran, Nathan Srebro, Prahladh Harsha

NeurIPS 2008 Fast Rates for Regularized Objectives Karthik Sridharan, Shai Shalev-shwartz, Nathan Srebro

COLT 2008 Improved Guarantees for Learning via Similarity Functions Maria-Florina Balcan, Avrim Blum, Nathan Srebro

ICML 2008 SVM Optimization: Inverse Dependence on Training Set Size Shai Shalev-Shwartz, Nathan Srebro

COLT 2007 Are There Local Maxima in the Infinite-Sample Likelihood of Gaussian Mixture Estimation? Nathan Srebro

COLT 2007 How Good Is a Kernel When Used as a Similarity Measure? Nathan Srebro

COLT 2007 L1 Regularization in Infinite Dimensional Feature Spaces Saharon Rosset, Grzegorz Swirszcz, Nathan Srebro, Ji Zhu

ICML 2007 Pegasos: Primal Estimated Sub-GrAdient SOlver for SVM Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro

ICML 2007 Uncovering Shared Structures in Multiclass Classification Yonatan Amit, Michael Fink, Nathan Srebro, Shimon Ullman

ICML 2006 An Investigation of Computational and Informational Limits in Gaussian Mixture Clustering Nathan Srebro, Gregory Shakhnarovich, Sam T. Roweis

COLT 2006 Learning Bounds for Support Vector Machines with Learned Kernels Nathan Srebro, Shai Ben-David

ICML 2005 Fast Maximum Margin Matrix Factorization for Collaborative Prediction Jason D. M. Rennie, Nathan Srebro

COLT 2005 Rank, Trace-Norm and Max-Norm Nathan Srebro, Adi Shraibman

NeurIPS 2004 Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices Nathan Srebro, Noga Alon, Tommi S. Jaakkola

NeurIPS 2004 Maximum-Margin Matrix Factorization Nathan Srebro, Jason Rennie, Tommi S. Jaakkola

NeurIPS 2003 Linear Dependent Dimensionality Reduction Nathan Srebro, Tommi S. Jaakkola

ICML 2003 Weighted Low-Rank Approximations Nathan Srebro, Tommi S. Jaakkola

UAI 2001 Maximum Likelihood Bounded Tree-Width Markov Networks Nathan Srebro