1.9k citations · 6.5k across the 132 of their papers we have counts for
3 papers · 1 filter
Tight Sample Complexity of Large-Margin Learning
Sivan Sabato, Nathan Srebro, Naftali Tishby
We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L_2 regularization: We introduce the γ-adapted-dimension, whic…
Optimistic Rates for Learning with a Smooth Loss
Nathan Srebro, Karthik Sridharan, Ambuj Tewari
We establish an excess risk bound of O(H R_n^2 + R_n \sqrt{H L*}) for empirical risk minimization with an H-smooth loss function and a hypothesis class with Rademacher complexity R…
Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
Ruslan Salakhutdinov, Nathan Srebro
We show that matrix completion with trace-norm regularization can be significantly hurt when entries of the matrix are sampled non-uniformly. We introduce a weighted version of the…