150 citations · 296 across the 5 of their papers we have counts for
5 papers
Fast-rate and optimistic-rate error bounds for L1-regularized regression
Rina Foygel, Nathan Srebro
We consider the prediction error of linear regression with L1 regularization when the number of covariates p is large relative to the sample size n. When the model is k-sparse and…
On the Universality of Online Mirror Descent
Nathan Srebro, Karthik Sridharan, Ambuj Tewari
We show that for a general class of convex online learning problems, Mirror Descent can always achieve a (nearly) optimal regret guarantee.
Better Mini-Batch Algorithms via Accelerated Gradient Methods
Andrew Cotter, Ohad Shamir, Nathan Srebro +1
Mini-batch algorithms have been proposed as a way to speed-up stochastic convex optimization problems. We study how such algorithms can be improved using accelerated gradient metho…
Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
Rina Foygel, Ruslan Salakhutdinov, Ohad Shamir +1
We provide rigorous guarantees on learning with the weighted trace-norm under arbitrary sampling distributions. We show that the standard weighted trace-norm might fail when the sa…
Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
Rina Foygel, Nathan Srebro
We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace…