This page is no longer being updated and is missing newer publications
Nati Srebro - Online Publications and Other Material
In (rough) reverse chronological order:
- On Symmetric and Asymmetric LSHs for Inner Product Search
Behnam Neyshabur and Nathan Srebro
arXiv:1410.5518
- On Distributed Stochastic Optimization and Learning
Ohad Shamir and Nathan Srebro
52nd Annual Allerton Conference on Communication, Control, and Computing, October 2014
[PDF]
- Stochastic gradient descent and the randomized Kaczmarz algorithm
Deanna Needell, Nathan Srebro, Rachel Ward
Advances in Neural Information Processing Systems (NIPS) 27, December 2014
arXiv:1310.5715
- Clustering, Hamming Embedding, Generalized LSH and the Max Norm
Behnam Neyshabur, Yury Makarychev and Nathan Srebro
25th International Conference on Algorithmic Learning Theory (ALT), October 2014
arXiv:1405.3167
- Active collaborative permutation learning
Jialei Wang, Nathan Srebro, James Evans
20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2014
[PDF]
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
Ohad Shamir, Nathan Srebro, Tong Zhang
31st International Conference on Machine Learning (ICML), June 2014
arXiv:1312.7853
- Stochastic Optimization of PCA with Capped MSG
Raman Arora, Andy Cotter and Nathan Srebro
Advances in Neural Information Processing Systems (NIPS) 26, December 2013
arXiv:1307.1674
- Auditing: Active Learning with Outcome-Dependent Query Costs
Sivan Sabato, Anand Sarwate, Nathan Srebro
Advances in Neural Information Processing Systems (NIPS) 26, December 2013
arXiv:1306.2347
- The Power of Asymmetry in Binary Hashing
Behnam Neyshabur, Payman Yadollahpour, Yury Makarychev, Ruslan Salakhutdinov and Nathan Srebro
Advances in Neural Information Processing Systems (NIPS) 26, December 2013
arXiv:1311.7662
- Mini-batch primal and dual methods for SVMs
Martin Takac, Avleen Bijral, Peter Richtarik and Nathan Srebro
30th International Conference on Machine Learning (ICML), June 2013
arXiv:1303.2314
- Learning optimally sparse support vector machines
Andy Cotter, Shai Shalev-Shwartz and Nathan Srebro
30th International Conference on Machine Learning (ICML), June 2013
- Learning Sparse Low-Threshold Linear Classifiers
Sivan Sabato, Shai Shalev-Shwartz, Nathan Srebro, Daniel Hsu and Tong Zhang
arXiv:1212.3276
- PRISMA: PRoximal Iterative SMoothing Algorithm
Francesco Orabona, Andreas Argyriou and Nathan Srebro
arXiv:1206.2372, (June 2012)
- Sparse Prediction with the k-Support Norm
Andreas Argyriou, Rina Foygel and Nathan Srebro
Advances in Neural Information Processing Systems (NIPS) 25, December 2012
arXiv:1204.5043, (March 2012, June 2012)
- Matrix Reconstruction with the Local Max Norm
Rina Foygel, Nathan Srebro and Ruslan Salakhutdinov
Advances in Neural Information Processing Systems (NIPS) 25, December 2012
- Clustering using Max-norm Constrained Optimization
Ali Jalali
and Nathan Srebro
29th International Conference on Machine Learning (ICML), June 2012
arXiv:1202.5598
- The Kernelized Stochastic Batch Perceptron
Andrew Cotter,
Shai Shalev-Shwartz
and Nathan Srebro
29th International Conference on Machine Learning (ICML), June 2012
arXiv:1204.0566
- Minimizing The Misclassification Error Rate Using a Surrogate Convex Loss
Shai Ben-David,
David Loker,
Karthik Sridharan
and Nathan Srebro
29th International Conference on Machine Learning (ICML), June 2012
arXiv:1206.6442
- Approximate Inference by Intersecting Semidefinite Bound and
Local Polytope Jian Peng, Tamir Hazan, Nathan Srebro and Jinbo Xu
15th
International Conference on Artificial Intelligence and
Statistics (AISTATS), April 2012
[PDF]
- On the Universality of Online Mirror Descent
Nathan Srebro, Karthik Sridharan and Ambuj Tewari
Advances in Neural Information Processing Systems (NIPS) 24, December 2011
arXiv:1107.4080, July 2011
- Beating SGD: Learning SVMs in Sublinear Time
Elad Hazan, Tomer Koren and Nathan Srebro
Advances in Neural Information Processing Systems (NIPS) 24, December 2011
[PDF, full version]
- Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
Rina Foygel, Ruslan Salakhutdinov, Ohad Shamir and Nathan Srebro
Advances in Neural Information Processing Systems (NIPS) 24, December 2011
arXiv:1106.4251, June 2011
- Better Mini-Batch Algorithms via Accelerated Gradient Methods
Andrew Cotter, Ohad Shamir, Nathan Srebro and Karthik Sridharan
Advances in Neural Information Processing Systems (NIPS) 24, December 2011
arXiv:1106.4574, June 2011
- Explicit Approximations of the Gaussian Kernel
Andrew Cotter, Joseph Keshet and Nathan Srebro
arXiv:1109.4603, September 2011
- Fast-rate and optimistic-rate error bounds for L1-regularized regression
Rina Foygel and Nathan Srebro
arXiv:1108.0373, August 2011
- A GPU-Tailored Approach for Training Kernelized SVMs
Andrew Cotter, Joseph Keshet and Nathan Srebro
17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, August 2011.
[PDF]
- An Iterated Graph Laplacian Approach for Ranking on Manifolds
Xueyuan Zhou, Mikhail Beklin and Nathan Srebro
17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, August 2011.
[PDF]
- Semi-supervised Learning with Density Based Distances
Avleen Bijral, Nathan Ratliff and Nathan Srebro
27th Conference on Uncertainty in Artificial Intelligence (UAI 2011), July 2011.
[PDF]
- Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
Rina Foygel and Nathan Srebro
24nd Annual Conference on Learning Theory (COLT), July 2011.
[arXiv]
- Error Analysis of Laplacian Eigenmaps for Semi-supervised Learning
Xueyuan Zhou and Nathan Srebro
14th International Conference on Artificial Intelligence and Statistics (AISTSTS), April 2011.
[PDF]
- Smoothness, Low-Noise and Fast Rates
Nathan Srebro, Karthik Sridharan and Ambuj Tewari
Advances in Neural Information Processing Systems (NIPS) 23, December 2010
Extended version: arXiv:1009.3896v1
[PDF]
- Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
Ruslan Salakhutdinov and Nathan Srebro
Advances in Neural Information Processing Systems (NIPS) 23, December 2010
[PDF]
Previous version: arXiv:1002.2780v1
- Practical Large-Scale Optimization for Max-Norm Regularization
Jason Lee, Ben Recht, Ruslan Salakhutdinov, Nathan Srebro, and Joel A. Tropp
Advances in Neural Information Processing Systems (NIPS) 23, December 2010
[PDF]
- Tight Sample Complexity of Large-Margin Learning
Sivan Sabato, Nathan Srebro, Naftali Tishby
Advances in Neural Information Processing Systems (NIPS) 23, December 2010
[PDF (includes appendix with full proofs)]
Extended version:
Distribution-Dependent Sample Complexity of Large Margin Learning
Journal of Machine Learning Research (JMLR), 14:2119-2149
- Learnability, Stability and Uniform Convergence
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan
Journal of Machine Learning Research, 11:2635-2670, October 2010
[PDF]
- Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints
Shai Shalev-Shwartz, Nathan Srebro and Tong Zhang
SIAM Journal on Optimization, 20(6):2807--2832, 2010. DOI 10.1137/090759574
[PDF]
- Stochastic Optimization for Machine Learning
Nathan Srebro and Ambuj Tewari
Tutorial presented at the 27th International Conference on Machine Learning (ICML), June 2010.
[Tutorial Slides]
- On the Interaction between Norm and Dimensionality: Multiple Regimes in Learning
Percy Liang and Nathan Srebro
27th International Conference on Machine Learning (ICML), June 2010.
[PDF]
- Reducing Label Complexity by Learning from Bags
Sivan Sabato, Nathan Srebro, Naftali Tishby
13th International Conference on Artificial Intelligence and Statistics (AISTATS), May 2010.
[Conference proceedings PDF]
- Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data
Boaz Nadler, Nathan Srebro, Xueyuan Zhou
Advances in Neural Information Processing Systems (NIPS) 22, 2010 (December 2009 conference)
[PDF]
- Learnability and Stability in the General Learning Setting
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan
22nd Annual Conference on Learning Theory (COLT), June 2009.
[Conference proceedings PDF]
- Stochastic Convex Optimization
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan
22nd Annual Conference on Learning Theory (COLT), June 2009.
[Conference proceedings PDF]
- Fast Rates for Regularized Objectives
Karthik Sridharan, Shai Shalev-Shwartz, Nathan Srebro
Advances in Neural Information Processing Systems (NIPS) 21, 2009 (December 2008 conference)
[PDF]
- A theory of learning with similarity functions
Maria-Florina Balcan, Avrim Blum, Nathan Srebro
Machine Learning 72(1-2):89--112, August 2008.
[Journal Paper]
- Iterative Loss Minimization with l1-Norm Constraint and Guarantees on Sparsity
Shai Shalev-Shwartz, Nathan Srebro
July, 2008.
[Report]
- Low l1-Norm and Guarantees on Sparsifiability
Shai Shalev-Shwartz, Nathan Srebro
Sparse Optimization and Variable Selection, Workshop, ICML/COLT/UAI, July, 2008.
[Extended Abstract],[Report],[Shai's Slides]
- Similarity-Based Theoretical Foundations for Sparse Parzen Windows Prediction
Maria-Florina Balcan, Avrim Blum, Nathan Srebro
Sparse Optimization and Variable Selection, Workshop, ICML/COLT/UAI, July, 2008.
[Extended Abstract],[Poster]
- SVM Optimization: Inverse Dependence on Training Set Size
Shai Shalev-Shwartz, Nathan Srebro
25th International Conference on Machine Learning (ICML), July 2008. Best Paper Award
[Corrected Conference Proceedings],[Errata],[Talk Slides]
[Online Discussion]
- Improved Guarantees for Learning via Similarity Functions
Maria-Florina Balcan, Avrim Blum, Nathan Srebro
21st Annual Conference on Learning Theory (COLT), July 2008.
[Conference proceedings PDF]
- Complexity of Inference in Graphical Models
Venkat Chandrasekaran, Nathan Srebro, Prahladh Harsha
24th Conference on Uncertainty in Artificial Intelligence (UAI), July 2008.
[Conference proceedings PDF]
- Uncovering Shared Structures in Multiclass Classification
Yonatan Amit, Michael Fink, Nathan Srebro, Shimon Ullman
24th International Conference on Machine Learning (ICML), June 2007.
[Conference Proceedings PDF]
- Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro
24th International Conference on Machine Learning (ICML), June 2007.
([Conference Proceedings PDF]---please prefer the journal versoin below)
Extended version:
Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, Andrew Cotter
Mathematical Programming, Series B, 127(1):3-30, 2011
[Journal Version PDF]
- How Good is a Kernel When Used as a Similarity Measure?
Nathan Srebro
20th Annual Conference on Learning Theory (COLT), June 2007.
[Conference proceedings PDF]
- l1 Regularization in Infinite Dimensional Feature Spaces
Saharon Rosset, Grzegorz Swirszcz, Nathan Srebro, Ji Zhu
20th Annual Conference on Learning Theory (COLT), June 2007.
[Conference proceedings PDF]
- Are there local maxima in the infinite sample likelihood of Gaussian mixture estimation?
Nathan Srebro
Open problem presented at the 20th Annual Conference on Learning Theory (COLT), June 2007.
[Conference proceedings PDF]
- Improved Prediction of HIV Resistance In-Vitro by
Biochemically-Driven Models
Hani Neuvirth, Michal Rosen-Zvi, Nathan Srebro, Ehud Aharoni, Maurizio Zazzi and Naftali Tishby
Neural Information Processing Systems (NIPS) 2006 Workshop on New Problems and Methods in Computational Biology, December 2006
[Extended Abstract]
- An Investigation of Computational and Informational Limits in
Gaussian Mixture Clustering
Nathan Srebro, Gregory Shakhnarovich and Sam Roweis
23rd International Conference on Machine Learning (ICML), August 2006.
(preliminary version appeared as UTML-TR-2006-002, February 2006)
[Conference Proceedings PDF]
Further information
- Learning Bounds for Support Vector Machines with Learned Kernels
Nathan Srebro, Shai Ben-David
19th Annual Conference on Learning Theory (COLT), June 2006.
(preliminary version appeared as UTML-TR-2006-001, January 2006)
[Conference proceedings PDF]
Further information
- When is Clustering Hard?
Nathan Srebro, Gregory Shakhnarovich and Sam Roweis
PASCAL Workshop on Statistics and Optimization of Clustering Workshop, July 2005
[Abstract PDF], [Slides PDF]
Further information
- Fast Maximum Margin Matrix Factorization for Collaborative Prediction
Jason Rennie and Nathan Srebro
22nd International Conference on Machine Learning (ICML), August 2005.
[Conference proceedings PDF],
[Jason's Slides PDF]
More MMMF information, papers and code
- Loss Functions for Preference Levels: Regression with Discrete Ordered Labels
Jason Rennie and Nathan Srebro
IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, July 2005.
[Proceedings PDF],
[Slides PDF].
- Adaptive Gaussian Kernel SVMs
Nathan Srebro and Sam Roweis
Snowbird Learning Workshop 2007
[Abstract]
- Time-Varying Topic Models using Dependent Dirichlet Processes
Nathan Srebro and Sam Roweis
UTML-TR-2005-003, March 2005
[Tech Report PDF]
- Rank, Trace-Norm and Max-Norm
Nathan Srebro and Adi Shraibman
18th Annual Conference on Learning Theory (COLT), June 2005.
[Conference proceedings PDF],
[Slides in PDF]
- Maximum Margin Matrix Factorization
Nathan Srebro, Jason Rennie and Tommi Jaakkola
Advances in Neural Information Processing Systems (NIPS) 17, 2005 (December 2004 conference)
[PDF],
[Slides in PDF],
[Poster in PDF]
See also Chapter Five of my PhD Thesis
More MMMF information, papers and code
- Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices
Nathan Srebro, Noga Alon and Tommi Jaakkola
Advances in Neural Information Processing Systems (NIPS) 17, 2005 (December 2004 conference)
[PDF],
[Poster in PDF]
See also Section 6.1 of my PhD Thesis
- Learning with Matrix Factorizations
Nathan Srebro
PhD Thesis, Massachusetts Institute of Technology, August 2004.
[PDF], [Defense slides PDF]
- Pairs of short duplications in mammalian genomes
Elizabeth E. Thomas, Nathan Srebro, Jonathan Sebat, Nicholas Navin, John Healy, Bud Mishra, and Michael Wigler
Proceedings of the National Academy of Science 101(28):10349-54, July 2004
[PDF],
[pubmed],
[Open access on PNAS],
[Open access on PubMed Central]
- Linear Dependent Dimensionality Reduction
Nathan Srebro and Tommi Jaakkola
Advances in Neural Information Processing Systems (NIPS) 16, 2004 (December 2003 conference)
[PDF],
[Poster in PDF]
See also Section 3.4 and Chapter 4 of my PhD Thesis
- Weighted Low-Rank Approximations
Nathan Srebro and Tommi Jaakkola
20th International Conference on Machine Learning (ICML), August 2003
[Conference proceedings PDF],
[Slides of conference presentation PDF]
See also Section 3.2 of my PhD Thesis
- How Much Of A Hypertree Can Be Captured By Windmills?
Percy Liang and Nathan Srebro, 2003
[PDF]
More on Hypertrees
- A Dynamic Data Structure for Checking Hyperacyclicity
Percy Liang and Nathan Srebro, 2003
[PDF]
More on Hypertrees
- K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data
Ziv Bar-Joseph, Erik Demaine, David Gifford, Angèle Hamel, Tommi Jaakkola and Nathan Srebro
2nd Workshop on Algorithms in Bioinformatics (WABI), LNCS 2452, pp 506-520, 2002
[Conference proceedings PDF]
[Slides of conference presentation PDF]
Eextended version:
Bioinformatics 19(9):1070-1078, 2003.
[PDF]
- Sparse Matrix Factorization for Analyzing Gene Expression Patterns
Nathan Srebro and Tommi Jaakkola
Neural Information Processing Systems (NIPS) 2001 Workshop on Machine Learning Techniques for Bioinformatics, December 2001
[Abstract] [Slides]
- Maximum Likelihood Bounded Tree-Width Markov Networks
Nathan Srebro
17th Conference on Uncertainty in Artificial Intelligence (UAI), August 2001.
Best student paper award
[Conference proceedings PDF],
[Presentation slides PDF],
[Poster PDF]
Extended version:
Artificial Intelligence 143(1):123-138, January 2003
[PDF]
See also my Master's Thesis
More on Hypertrees
- Learning Markov Networks: Maximum Bounded Tree-Width Graphs
David Karger and Nathan Srebro
12th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2001
[Conference proceedings PDF]
See also my Master's Thesis
More on Hypertrees
- Maximum Likelihood Markov Networks: An Algorithmic Approach
Nathan Srebro
MSc Thesis, Massachusetts Institute of Technology, October 2000.
[PDF]
More on Hypertrees
- Locating Disease Genes by Genetic Diversity
Nathan Srebro and Eric Lander
Mathematics and Molecular Biology VI: Understanding Structure, January 1999
Nati Srebro
Last modified: Tue Dec 02 16:40:27 Central Standard Time 2014