1.9k citations · 6.5k across the 132 of their papers we have counts for
7 papers · 1 filter
Communication Efficient Distributed Optimization using an Approximate Newton-type Method
Ohad Shamir, Nathan Srebro, Tong Zhang
We present a novel Newton-type method for distributed optimization, which is particularly well suited for stochastic optimization and learning problems. For quadratic objectives, t…
The Power of Asymmetry in Binary Hashing
Behnam Neyshabur, Payman Yadollahpour, Yury Makarychev +2
When approximating binary similarity using the hamming distance between short binary hashes, we show that even if the similarity is symmetric, we can have shorter and more accurate…
Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
Deanna Needell, Nathan Srebro, Rachel Ward
We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic depende…
Stochastic Optimization of PCA with Capped MSG
Raman Arora, Andrew Cotter, Nathan Srebro
We study PCA as a stochastic optimization problem and propose a novel stochastic approximation algorithm which we refer to as "Matrix Stochastic Gradient" (MSG), as well as a pract…
Auditing: Active Learning with Outcome-Dependent Query Costs
Sivan Sabato, Anand D. Sarwate, Nathan Srebro
We propose a learning setting in which unlabeled data is free, and the cost of a label depends on its value, which is not known in advance. We study binary classification in an ext…
Mini-Batch Primal and Dual Methods for SVMs
Martin Takáč, Avleen Bijral, Peter Richtárik +1
We address the issue of using mini-batches in stochastic optimization of SVMs. We show that the same quantity, the spectral norm of the data, controls the parallelization speedup o…