536 citations · 4.4k across the 97 of their papers we have counts for
10 papers · 1 filter
A Variant of Azuma's Inequality for Martingales with Subgaussian Tails
Ohad Shamir
We provide a variant of Azuma's concentration inequality for martingales, in which the standard boundedness requirement is replaced by the milder requirement of a subgaussian tail.
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
Alexander Rakhlin, Ohad Shamir, Karthik Sridharan
Stochastic gradient descent (SGD) is a simple and popular method to solve stochastic optimization problems which arise in machine learning. For strongly convex problems, its conver…
Adaptively Learning the Crowd Kernel
Omer Tamuz, Ce Liu, Serge Belongie +2
We introduce an algorithm that, given n objects, learns a similarity matrix over all n^2 pairs, from crowdsourced data alone. The algorithm samples responses to adaptively chosen t…
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…
Using More Data to Speed-up Training Time
Shai Shalev-Shwartz, Ohad Shamir, Eran Tromer
In many recent applications, data is plentiful. By now, we have a rather clear understanding of how more data can be used to improve the accuracy of learning algorithms. Recently,…