Cluster Stability for Finite Samples. - Ohad Shamir; Naftali Tishby (NIPS, 2007)

Model Selection and Stability in k-means Clustering. - Ohad Shamir; Naftali Tishby (COLT, 2008)

Learning to classify with missing and corrupted features. - Ofer Dekel; Ohad Shamir (ICML, 2008)

On the Reliability of Clustering Stability in the Large Sample Regime. - Ohad Shamir; Naftali Tishby (NIPS, 2008)

Vox Populi: Collecting High-Quality Labels from a Crowd. - Ofer Dekel; Ohad Shamir (COLT, 2009)

The Complexity of Improperly Learning Large Margin Halfspaces. - Shai Shalev-Shwartz; Ohad Shamir; Karthik Sridharan (COLT, 2009)

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

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

Good learners for evil teachers. - Ofer Dekel; Ohad Shamir (ICML, 2009)

Learning Exponential Families in High-Dimensions: Strong Convexity and Sparsity - Sham M. Kakade; Ohad Shamir; Karthik Sridharan; Ambuj Tewari (CoRR, 2009)

Online Learning of Noisy Data with Kernels. - Nicolò Cesa-Bianchi; Shai Shalev-Shwartz; Ohad Shamir (COLT, 2010)

Learning Kernel-Based Halfspaces with the Zero-One Loss. - Shai Shalev-Shwartz; Ohad Shamir; Karthik Sridharan (COLT, 2010)

Robust Distributed Online Prediction - Ofer Dekel; Ran Gilad-Bachrach; Ohad Shamir; Lin Xiao (CoRR, 2010)

Multiclass-Multilabel Classification with More Classes than Examples. - Ofer Dekel; Ohad Shamir (AISTATS, 2010)

Learning Exponential Families in High-Dimensions: Strong Convexity and Sparsity. - Sham M. Kakade; Ohad Shamir; Karthik Sindharan; Ambuj Tewari (AISTATS, 2010)

Learnability, Stability and Uniform Convergence. - Shai Shalev-Shwartz; Ohad Shamir; Nathan Srebro; Karthik Sridharan (J. Mach. Learn. Res., 2010)

Learning to classify with missing and corrupted features. - Ofer Dekel; Ohad Shamir; Lin Xiao (Mach. Learn., 2010)

Stability and model selection in k-means clustering. - Ohad Shamir; Naftali Tishby (Mach. Learn., 2010)

Learning and generalization with the information bottleneck. - Ohad Shamir; Sivan Sabato; Naftali Tishby (Theor. Comput. Sci., 2010)

On stability in statistical machine learning (עם תקציר בעברית ושער נוסף: על יציבות בלמידה חישובית סטטיסטית.). - Ohad Shamir (2010)

Quantity Makes Quality: Learning with Partial Views. - Nicolò Cesa-Bianchi; Shai Shalev-Shwartz; Ohad Shamir (AAAI, 2011)

Optimal Distributed Online Prediction. - Ofer Dekel; Ran Gilad-Bachrach; Ohad Shamir; Lin Xiao (ICML, 2011)

Large-Scale Convex Minimization with a Low-Rank Constraint. - Shai Shalev-Shwartz; Alon Gonen; Ohad Shamir (ICML, 2011)

Adaptively Learning the Crowd Kernel. - Omer Tamuz; Ce Liu 001; Serge J. Belongie; Ohad Shamir; Adam Kalai (ICML, 2011)

Learning Linear and Kernel Predictors with the 0-1 Loss Function. - Shai Shalev-Shwartz; Ohad Shamir; Karthik Sridharan (IJCAI, 2011)

Efficient Online Learning via Randomized Rounding. - Nicolò Cesa-Bianchi; Ohad Shamir (NIPS, 2011)

Better Mini-Batch Algorithms via Accelerated Gradient Methods. - Andrew Cotter; Ohad Shamir; Nati Srebro; Karthik Sridharan (NIPS, 2011)

Learning with the weighted trace-norm under arbitrary sampling distributions. - Rina Foygel; Ruslan Salakhutdinov; Ohad Shamir; Nati Srebro (NIPS, 2011)

Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression. - Sham M. Kakade; Adam Kalai; Varun Kanade; Ohad Shamir (NIPS, 2011)

From Bandits to Experts: On the Value of Side-Observations. - Shie Mannor; Ohad Shamir (NIPS, 2011)

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization - Ohad Shamir (CoRR, 2011)

A Variant of Azuma's Inequality for Martingales with Subgaussian Tails - Ohad Shamir (CoRR, 2011)

Efficient Learning with Partially Observed Attributes. - Nicolò Cesa-Bianchi; Shai Shalev-Shwartz; Ohad Shamir (J. Mach. Learn. Res., 2011)

Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing. - Ohad Shamir; Shai Shalev-Shwartz (COLT, 2011)

Spectral Clustering on a Budget. - Ohad Shamir; Naftali Tishby (AISTATS, 2011)

Learning Kernel-Based Halfspaces with the 0-1 Loss. - Shai Shalev-Shwartz; Ohad Shamir; Karthik Sridharan (SIAM J. Comput., 2011)

Online Learning of Noisy Data. - Nicolò Cesa-Bianchi; Shai Shalev-Shwartz; Ohad Shamir (IEEE Trans. Inf. Theory, 2011)

Decoupling Exploration and Exploitation in Multi-Armed Bandits. - Orly Avner; Shie Mannor; Ohad Shamir (ICML, 2012)

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization. - Alexander Rakhlin; Ohad Shamir; Karthik Sridharan (ICML, 2012)

Relax and Randomize : From Value to Algorithms. - Alexander Rakhlin; Ohad Shamir; Karthik Sridharan (NIPS, 2012)

Relax and Localize: From Value to Algorithms - Alexander Rakhlin; Ohad Shamir; Karthik Sridharan (CoRR, 2012)

Optimal Distributed Online Prediction Using Mini-Batches. - Ofer Dekel; Ran Gilad-Bachrach; Ohad Shamir; Lin Xiao (J. Mach. Learn. Res., 2012)

There's a Hole in My Data Space: Piecewise Predictors for Heterogeneous Learning Problems. - Ofer Dekel; Ohad Shamir (AISTATS, 2012)

Using More Data to Speed-up Training Time. - Shai Shalev-Shwartz; Ohad Shamir; Eran Tromer (AISTATS, 2012)

Open Problem: Is Averaging Needed for Strongly Convex Stochastic Gradient Descent? - Ohad Shamir (COLT, 2012)

Learning from Weak Teachers. - Ruth Urner; Shai Ben-David; Ohad Shamir (AISTATS, 2012)

Localization and Adaptation in Online Learning. - Alexander Rakhlin; Ohad Shamir; Karthik Sridharan (AISTATS, 2013)

Efficient Transductive Online Learning via Randomized Rounding. - Nicolò Cesa-Bianchi; Ohad Shamir (Empirical Inference, 2013)

Online Learning for Time Series Prediction. - Oren Anava; Elad Hazan; Shie Mannor; Ohad Shamir (COLT, 2013)

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization. - Ohad Shamir (COLT, 2013)

Probabilistic Label Trees for Efficient Large Scale Image Classification. - Baoyuan Liu; Fereshteh Sadeghi; Marshall F. Tappen; Ohad Shamir; Ce Liu 001 (CVPR, 2013)

Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes. - Ohad Shamir; Tong Zhang 001 (ICML (1), 2013)

Online Learning with Switching Costs and Other Adaptive Adversaries. - Nicolò Cesa-Bianchi; Ofer Dekel; Ohad Shamir (NIPS, 2013)

Accurate Profiling of Microbial Communities from Massively Parallel Sequencing Using Convex Optimization. - Or Zuk; Amnon Amir; Amit Zeisel; Ohad Shamir; Noam Shental (SPIRE, 2013)

A Provably Efficient Algorithm for Training Deep Networks - Roi Livni; Shai Shalev-Shwartz; Ohad Shamir (CoRR, 2013)

Distributed stochastic optimization and learning. - Ohad Shamir; Nathan Srebro (Allerton, 2014)

On-demand, Spot, or Both: Dynamic Resource Allocation for Executing Batch Jobs in the Cloud. - Ishai Menache; Ohad Shamir; Navendu Jain (ICAC, 2014)

Communication-Efficient Distributed Optimization using an Approximate Newton-type Method. - Ohad Shamir; Nathan Srebro; Tong Zhang 001 (ICML, 2014)

On the Computational Efficiency of Training Neural Networks. - Roi Livni; Shai Shalev-Shwartz; Ohad Shamir (NIPS, 2014)

Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation. - Ohad Shamir (NIPS, 2014)

Attribute Efficient Linear Regression with Data-Dependent Sampling. - Doron Kukliansky; Ohad Shamir (CoRR, 2014)

A Stochastic PCA Algorithm with an Exponential Convergence Rate. - Ohad Shamir (CoRR, 2014)

Matrix completion with the trace norm: learning, bounding, and transducing. - Ohad Shamir; Shai Shalev-Shwartz (J. Mach. Learn. Res., 2014)

Graph Approximation and Clustering on a Budget. - Ethan Fetaya; Ohad Shamir; Shimon Ullman (AISTATS, 2015)

On the Complexity of Learning with Kernels. - Nicolò Cesa-Bianchi; Yishay Mansour; Ohad Shamir (COLT, 2015)

On the Complexity of Bandit Linear Optimization. - Ohad Shamir (COLT, 2015)

Attribute Efficient Linear Regression with Distribution-Dependent Sampling. - Doron Kukliansky; Ohad Shamir (ICML, 2015)

A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate. - Ohad Shamir (ICML, 2015)

Communication Complexity of Distributed Convex Learning and Optimization. - Yossi Arjevani; Ohad Shamir (NIPS, 2015)

On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems. - Yossi Arjevani; Shai Shalev-Shwartz; Ohad Shamir (CoRR, 2015)

The sample complexity of learning linear predictors with the squared loss. - Ohad Shamir (J. Mach. Learn. Res., 2015)

The Power of Depth for Feedforward Neural Networks. - Ronen Eldan; Ohad Shamir (COLT, 2016)

On the Iteration Complexity of Oblivious First-Order Optimization Algorithms. - Yossi Arjevani; Ohad Shamir (ICML, 2016)

Multi-Player Bandits - a Musical Chairs Approach. - Jonathan Rosenski; Ohad Shamir; Liran Szlak (ICML, 2016)

On the Quality of the Initial Basin in Overspecified Neural Networks. - Itay Safran; Ohad Shamir (ICML, 2016)

Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity. - Ohad Shamir (ICML, 2016)

Convergence of Stochastic Gradient Descent for PCA. - Ohad Shamir (ICML, 2016)

Dimension-Free Iteration Complexity of Finite Sum Optimization Problems. - Yossi Arjevani; Ohad Shamir (NIPS, 2016)

Without-Replacement Sampling for Stochastic Gradient Methods. - Ohad Shamir (NIPS, 2016)

Depth Separation in ReLU Networks for Approximating Smooth Non-Linear Functions. - Itay Safran; Ohad Shamir (CoRR, 2016)

Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization. - Ohad Shamir (CoRR, 2016)

On Lower and Upper Bounds in Smooth and Strongly Convex Optimization. - Yossi Arjevani; Shai Shalev-Shwartz; Ohad Shamir (J. Mach. Learn. Res., 2016)

Unified Algorithms for Online Learning and Competitive Analysis. - Niv Buchbinder; Shahar Chen; Joseph Naor; Ohad Shamir (Math. Oper. Res., 2016)

Preface: Conference on Learning Theory (COLT), 2017. - Satyen Kale; Ohad Shamir (COLT, 2017)

Oracle Complexity of Second-Order Methods for Finite-Sum Problems. - Yossi Arjevani; Ohad Shamir (ICML, 2017)

Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis. - Dan Garber; Ohad Shamir; Nathan Srebro (ICML, 2017)

Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks. - Itay Safran; Ohad Shamir (ICML, 2017)

Failures of Gradient-Based Deep Learning. - Shai Shalev-Shwartz; Ohad Shamir; Shaked Shammah (ICML, 2017)

Online Learning with Local Permutations and Delayed Feedback. - Ohad Shamir; Liran Szlak (ICML, 2017)

Failures of Deep Learning. - Shai Shalev-Shwartz; Ohad Shamir; Shaked Shammah (CoRR, 2017)

Weight Sharing is Crucial to Succesful Optimization. - Shai Shalev-Shwartz; Ohad Shamir; Shaked Shammah (CoRR, 2017)

An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback. - Ohad Shamir (J. Mach. Learn. Res., 2017)

Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback. - Noga Alon; Nicolò Cesa-Bianchi; Claudio Gentile; Shie Mannor; Yishay Mansour; Ohad Shamir (SIAM J. Comput., 2017)

Bandit Regret Scaling with the Effective Loss Range. - Nicolò Cesa-Bianchi; Ohad Shamir (ALT, 2018)

Detecting Correlations with Little Memory and Communication. - Yuval Dagan; Ohad Shamir (COLT, 2018)

Size-Independent Sample Complexity of Neural Networks. - Noah Golowich; Alexander Rakhlin; Ohad Shamir (COLT, 2018)

Spurious Local Minima are Common in Two-Layer ReLU Neural Networks. - Itay Safran; Ohad Shamir (ICML, 2018)

Global Non-convex Optimization with Discretized Diffusions. - Murat A. Erdogdu; Lester Mackey; Ohad Shamir (NeurIPS, 2018)

Are ResNets Provably Better than Linear Predictors? - Ohad Shamir (NeurIPS, 2018)

Distribution-Specific Hardness of Learning Neural Networks. - Ohad Shamir (J. Mach. Learn. Res., 2018)

Space lower bounds for linear prediction in the streaming model. - Yuval Dagan; Gil Kur; Ohad Shamir (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 E. Woodworth (COLT, 2019)

Depth Separations in Neural Networks: What is Actually Being Separated? - Itay Safran; Ronen Eldan; Ohad Shamir (COLT, 2019)

Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks. - Ohad Shamir (COLT, 2019)

On the Power and Limitations of Random Features for Understanding Neural Networks. - Gilad Yehudai; Ohad Shamir (NeurIPS, 2019)

Space lower bounds for linear prediction. - Yuval Dagan; Gil Kur; Ohad Shamir (CoRR, 2019)

Oracle complexity of second-order methods for smooth convex optimization. - Yossi Arjevani; Ohad Shamir; Ron Shiff (Math. Program., 2019)

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

How Good is SGD with Random Shuffling? - Itay Safran; Ohad Shamir (COLT, 2020)

Learning a Single Neuron with Gradient Methods. - Gilad Yehudai; Ohad Shamir (COLT, 2020)

The Complexity of Finding Stationary Points with Stochastic Gradient Descent. - Yoel Drori; Ohad Shamir (ICML, 2020)

Proving the Lottery Ticket Hypothesis: Pruning is All You Need. - Eran Malach; Gilad Yehudai; Shai Shalev-Shwartz; Ohad Shamir (ICML, 2020)

Is Local SGD Better than Minibatch SGD? - Blake E. Woodworth; Kumar Kshitij Patel; Sebastian U. Stich; Zhen Dai; Brian Bullins; H. Brendan McMahan; Ohad Shamir; Nathan Srebro (ICML, 2020)

Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions? - Ohad Shamir (CoRR, 2020)

High-Order Oracle Complexity of Smooth and Strongly Convex Optimization. - Guy Kornowski; Ohad Shamir (CoRR, 2020)

Neural Networks with Small Weights and Depth-Separation Barriers. - Gal Vardi; Ohad Shamir (Electron. Colloquium Comput. Complex., 2020)

The Connection Between Approximation, Depth Separation and Learnability in Neural Networks. - Eran Malach; Gilad Yehudai; Shai Shalev-Shwartz; Ohad Shamir (COLT, 2021)

The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks. - Itay Safran; Gilad Yehudai; Ohad Shamir (COLT, 2021)

Size and Depth Separation in Approximating Benign Functions with Neural Networks. - Gal Vardi; Daniel Reichman 001; Toniann Pitassi; Ohad Shamir (COLT, 2021)

Implicit Regularization in ReLU Networks with the Square Loss. - Gal Vardi; Ohad Shamir (COLT, 2021)

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

A Stochastic Newton Algorithm for Distributed Convex Optimization. - Brian Bullins; Kumar Kshitij Patel; Ohad Shamir; Nathan Srebro; Blake E. Woodworth (NeurIPS, 2021)

Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems. - Itay Safran; Ohad Shamir (NeurIPS, 2021)

Learning a Single Neuron with Bias Using Gradient Descent. - Gal Vardi; Gilad Yehudai; Ohad Shamir (NeurIPS, 2021)

Size and Depth Separation in Approximating Natural Functions with Neural Networks. - Gal Vardi; Daniel Reichman 001; Toniann Pitassi; Ohad Shamir (CoRR, 2021)

Convergence Results For Q-Learning With Experience Replay. - Liran Szlak; Ohad Shamir (CoRR, 2021)

Replay For Safety. - Liran Szlak; Ohad Shamir (CoRR, 2021)

Gradient Methods Never Overfit On Separable Data. - Ohad Shamir (J. Mach. Learn. Res., 2021)

Width is Less Important than Depth in ReLU Neural Networks. - Gal Vardi; Gilad Yehudai; Ohad Shamir (COLT, 2022)

On the Optimal Memorization Power of ReLU Neural Networks. - Gal Vardi; Gilad Yehudai; Ohad Shamir (ICLR, 2022)

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

Elephant in the Room: Non-Smooth Non-Convex Optimization. - Ohad Shamir (ISAIM, 2022)

Reconstructing Training Data From Trained Neural Networks. - Niv Haim; Gal Vardi; Gilad Yehudai; Ohad Shamir; Michal Irani (NeurIPS, 2022)

The Sample Complexity of One-Hidden-Layer Neural Networks. - Gal Vardi; Ohad Shamir; Nati Srebro (NeurIPS, 2022)

On Margin Maximization in Linear and ReLU Networks. - Gal Vardi; Ohad Shamir; Nati Srebro (NeurIPS, 2022)

Gradient Methods Provably Converge to Non-Robust Networks. - Gal Vardi; Gilad Yehudai; Ohad Shamir (NeurIPS, 2022)

On the Complexity of Finding Small Subgradients in Nonsmooth Optimization. - Guy Kornowski; Ohad Shamir (CoRR, 2022)

Oracle Complexity in Nonsmooth Nonconvex Optimization. - Guy Kornowski; Ohad Shamir (J. Mach. Learn. Res., 2022)

Implicit Regularization Towards Rank Minimization in ReLU Networks. - Nadav Timor; Gal Vardi; Ohad Shamir (ALT, 2023)

Deterministic Nonsmooth Nonconvex Optimization. - Michael I. Jordan; Guy Kornowski; Tianyi Lin; Ohad Shamir; Manolis Zampetakis (COLT, 2023)

Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance. - Nikita Kornilov; Ohad Shamir; Aleksandr V. Lobanov; Darina Dvinskikh; Alexander V. Gasnikov; Innokentiy Shibaev; Eduard Gorbunov; Samuel Horváth (NeurIPS, 2023)

From Tempered to Benign Overfitting in ReLU Neural Networks. - Guy Kornowski; Gilad Yehudai; Ohad Shamir (NeurIPS, 2023)

Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks. - Roey Magen; Ohad Shamir (NeurIPS, 2023)

The Implicit Bias of Benign Overfitting. - Ohad Shamir (J. Mach. Learn. Res., 2023)

Open Problem: Anytime Convergence Rate of Gradient Descent. - Guy Kornowski; Ohad Shamir (COLT, 2024)

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

Generalization in Kernel Regression Under Realistic Assumptions. - Daniel Barzilai; Ohad Shamir (ICML, 2024)

On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization. - Guy Kornowski; Swati Padmanabhan; Ohad Shamir (CoRR, 2024)

Simple Relative Deviation Bounds for Covariance and Gram Matrices. - Daniel Barzilai; Ohad Shamir (CoRR, 2024)

An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization. - Guy Kornowski; Ohad Shamir (J. Mach. Learn. Res., 2024)

Logarithmic Width Suffices for Robust Memorization. - Amitsour Egosi; Gilad Yehudai; Ohad Shamir (COLT, 2025)

The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria. - Guy Kornowski; Ohad Shamir (COLT, 2025)

Are Convex Optimization Curves Convex? - Guy Barzilai; Ohad Shamir; Moslem Zamani (Trans. Mach. Learn. Res., 2025)

Hardness of Learning Fixed Parities with Neural Networks. - Itamar Shoshani; Ohad Shamir (CoRR, 2025)

Overfitting Regimes of Nadaraya-Watson Interpolators. - Daniel Barzilai; Guy Kornowski; Ohad Shamir (CoRR, 2025)

When Models Don't Collapse: On the Consistency of Iterative MLE. - Daniel Barzilai; Ohad Shamir (CoRR, 2025)