Ohad Shamir

I am a post-doctoral researcher at Microsoft Research New England. Previous to that, I was a Ph.D. student at the Machine Learning Lab in the Hebrew University, advised by Prof. Naftali Tishby.
My work focuses on machine learning, with emphasis on novel algorithms which combine practical applicability and theoretical insight.

NEWS: I'll be joining the Weizmann Institute (CS and Applied Math Department) as a faculty member in 2013.

Publications

Journal Papers

• Optimal Distributed Online Prediction Using Mini-Batches
  Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir and Lin Xiao
  Journal of Machine Learning Research, 13(Jan):165-202, 2012

• Online Learning with Noise
  Nicolò Cesa-Bianchi, Shai Shalev-Shwartz and Ohad Shamir
  IEEE Transactions on Information Theory, 57(12):7907-7931, 2011

• Learning Kernel Based Halfspaces with the 0-1 Loss
  Shai Shalev-Shwartz, Ohad Shamir and Karthik Sridharan
  SIAM Journal on Computing, 40(6):1623-1646, 2011

• Efficient Learning with Partially Observed Attributes
  Nicolò Cesa-Bianchi, Shai Shalev-Shwartz and Ohad Shamir
  Journal of Machine Learning Research, 12(Oct):2857-2878, 2011

• Learnability, Stability and Uniform Convergence
  Shai Shalev Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan
  Journal of Machine Learning Research, 11(Oct):2635-2670, 2010

• Stability and Model Selection in k-means Clustering
  Ohad Shamir and Naftali Tishby
  Machine Learning, 80(2):213-243, 2010

• Learning to Classify with Missing and Corrupted Features
  Ofer Dekel, Ohad Shamir and Lin Xiao
  Machine Learning, 81(2):149-178, 2010

• Learning and Generalization with the Information Bottleneck
  Ohad Shamir, Sivan Sabato and Naftali Tishby
  Theoretical Computer Science, 411(29-30):2696-2711, 2010

Conference Papers

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
  Alexander Rakhlin, Ohad Shamir and Karthik Sridharan
  29th International Conference on Machine Learning (ICML 2012)

• Decoupling Exploration and Exploitation in Multi-Armed Bandits
  Orly Avner, Shie Mannor and Ohad Shamir
  29th International Conference on Machine Learning (ICML 2012)
  • Also presented at the 10th European Workshop on Reinforcement Learning (EWRL 2012)

• Unified Algorithms for Online Learning and Competitive Analysis
  Niv Buchbinder, Shahar Chen, Joseph (Seffi) Naor and Ohad Shamir
  25th Annual Conference on Learning Theory (COLT 2012)

• Using More Data to Speed-up Training Time
  Shai Shalev-Shwartz, Ohad Shamir and Eran Tromer
  15th International Conference on Artificial Intelligence and Statistics (AISTATS 2012)

• There's a Hole in My Data Space: Piecewise Predictors for Heterogeneous Learning Problems
  Ofer Dekel and Ohad Shamir
  15th International Conference on Artificial Intelligence and Statistics (AISTATS 2012)

• Learning from Weak Teachers
  Ruth Urner, Shai Ben-David and Ohad Shamir
  15th International Conference on Artificial Intelligence and Statistics (AISTATS 2012)

• Efficient Online Learning via Randomized Rounding
  Nicolò Cesa-Bianchi and Ohad Shamir
  25th Annual Conference on Neural Information Processing Systems (NIPS 2011)
  Note: this version fixes a few small (but important) typos in the conference proceedings, such as the definition of L

• From Bandits to Experts: On the Value of Side-Observations
  Shie Mannor and Ohad Shamir
  25th Annual Conference on Neural Information Processing Systems (NIPS 2011)

• Better Mini-Batch Algorithms via Accelerated Gradient Methods
  Andrew Cotter, Ohad Shamir, Nathan Srebro and Karthik Sridharan
  25th Annual Conference on Neural Information Processing Systems (NIPS 2011)
  • Supplementary material

• Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
  Sham Kakade, Adam Tauman Kalai, Varun Kanade, Ohad Shamir
  25th Annual Conference on Neural Information Processing Systems (NIPS 2011)
  • Supplementary material

• Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
  Rina Foygel, Ruslan Salakhutdinov, Ohad Shamir and Nathan Srebro
  25th Annual Conference on Neural Information Processing Systems (NIPS 2011)
  • Supplementary material

• Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing
  Ohad Shamir and Shai Shalev-Shwartz
  24th Annual Conference on Learning Theory (COLT 2011)

• Optimal Distributed Online Prediction
  Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir and Lin Xiao
  28th International Conference on Machine Learning (ICML 2011)
  
  • Also presented at the Learning on Cores, Clusters and Clouds Workshop, NIPS 2010
  • The paper is largely based on work presented in more detail here and here.

• Large-Scale Convex Minimization with a Low-Rank Constraint
  Alon Gonen, Shai Shalev-Shwartz and Ohad Shamir
  28th International Conference on Machine Learning (ICML 2011)
  • Full version

• Adaptively Learning the Crowd Kernel
  Serge Belongie, Adam Kalai, Ce Liu, Ohad Shamir and Omer Tamuz
  28th International Conference on Machine Learning (ICML 2011)

• Quantity Makes Quality: Learning with Partial Views
  Nicolò Cesa-Bianchi, Shai Shalev-Shwartz and Ohad Shamir
  Twenty-Fifth Conference on Artificial Intelligence (AAAI 2011)
  
  • Nectar Track Paper

• Spectral Clustering on a Budget
  Ohad Shamir and Naftali Tishby
  Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS 2011)
  
  • Full version

• Learning from Noisy Data under Distributional Assumptions
  Nicolò Cesa-Bianchi, Shai Shalev-Shwartz and Ohad Shamir
  Robust Statistical Learning Workshop (NIPS 2010)
  
  • Full version

• Learning Kernel-Based Halfspaces with the Zero-One Loss (best paper award)
  Shai Shalev-Shwartz, Ohad Shamir and Karthik Sridharan
  23rd Annual Conference on Learning Theory (COLT 2010)
  
  • Full version
  • A somewhat less technical version presented at the best paper track of (IJCAI 2011)

• Online Learning of Noisy Data with Kernels
  Nicolò Cesa-Bianchi, Shai Shalev-Shwartz and Ohad Shamir
  23rd Annual Conference on Learning Theory (COLT 2010)
  
  • Full version

• Efficient Learning with Partially Observed Attributes
  Nicolò Cesa-Bianchi, Shai Shalev-Shwartz and Ohad Shamir
  27th International Conference on Machine Learning (ICML 2010)
  
  • Full version

• Multiclass-Multilabel Classification with More Labels than Examples
  Ofer Dekel and Ohad Shamir
  13th International Conference on Artificial Intelligence and Statistics (AISTATS 2010)
  

• Learning Exponential Families in High Dimensions: Strong Convexity and Sparsity
  Sham Kakade, Ohad Shamir, Karthik Sridharan and Ambuj Tewari
  13th International Conference on Artificial Intelligence and Statistics (AISTATS 2010)
  
  • Supplementary material

• Vox Populi: Collecting High-Quality Labels from a Crowd
  Ofer Dekel and Ohad Shamir
  22nd Annual Conference on Learning Theory (COLT 2009)
  

• Learnability and Stability in the General Learning Setting
  Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan
  22nd Annual Conference on Learning Theory (COLT 2009)
  

• Stochastic Convex Optimization
  Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan
  22nd Annual Conference on Learning Theory (COLT 2009)
  

• Good Learners for Evil Teachers
  Ofer Dekel and Ohad Shamir
  26th International Conference on Machine Learning (ICML 2009)
  

• On the Reliability of Clustering Stability in the Large Sample Regime
  Ohad Shamir and Naftali Tishby
  22nd Annual Conference on Neural Information Processing Systems (NIPS 2008)
  
  • Supplementary material

• Learning and Generalization with the Information Bottleneck
  Ohad Shamir, Sivan Sabato and Naftali Tishby
  19th International Conference on Algorithmic Learning Theory (ALT 2008)
  
  • Full version

• Model Selection and Stability in k-means Clustering
  Ohad Shamir and Naftali Tishby
  21st Annual Conference on Learning Theory (COLT 2008)
  

• Learning to Classify with Missing and Corrupted Features
  Ofer Dekel and Ohad Shamir
  25th International Conference on Machine Learning (ICML 2008)

• Cluster Stability for Finite Samples
  Ohad Shamir and Naftali Tishby
  21st Annual Conference on Neural Information Processing Systems (NIPS 2007)
  
  • Supplementary material

Other Publications and Misc.

• Is Averaging Needed for Strongly Convex Stochastic Gradient Descent?
  Ohad Shamir
  Open problem presented in the 25th Annual Conference on Learning Theory (COLT 2012)

• Some Impossibility Results for Budgeted Learning
  Nicolò Cesa-Bianchi, Shai Shalev-Shwartz and Ohad Shamir
  Budgeted Learning Workshop, in conjunction with ICML 2010
  

• A Variant of Azuma's Inequality for Martingales with Subgaussian Tails
  Ohad Shamir
  A small note on how to apply a concentration inequality for martingales which are only bounded in high probability

• Agnostically Learning Halfspaces with Margin Errors
  Shai Shalev-Shwartz, Ohad Shamir and Karthik Sridharan
  TTI-C Technical Report, June 2009
  Note: this technical report is largely superseded by our COLT 2010 paper, Learning Kernel-Based Halfspaces with the Zero-One Loss

• The Complexity of Improperly Learning Large Margin Halfspaces
  Shai Shalev-Shwartz, Ohad Shamir and Karthik Sridharan
  Open problem presented in the 22nd Annual Conference on Learning Theory (COLT 2009)

Teaching

• TA in Introduction to Information Theory, 2008-2009
• TA In Introduction to Machine Learning, 2009-2010

Hobbies