Fetching the paper…
Reading the bibliography…
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 dependence on the conditioning $(L/\mu)^2$ (where $L$ is a bound on the smoothness and $\mu$ on the strong convexity) to a linear dependence on $L/\mu$.
Angenäherte auflösung von systemen linearer gleichungen
S. Kaczmarz · 1937
Earlier work this paper cites.
A stochastic approximation method
H. Robbins and S. Monroe · 1951
Earlier work this paper cites.
Two algorithms related to the method of steepest descent
T. M. Whitney and R. K. Meany · 1967
Earlier work this paper cites.
Projection method for solving a singular system of linear equations and its applications
K. Tanabe · 1971
Earlier work this paper cites.
Computerized transverse axial scanning (tomography): Part 1. description of system
G. N Hounsfield · 1973
Earlier work this paper cites.
Block-iterative methods for consistent and inconsistent linear equations
T. Elfving · 1980
Earlier work this paper cites.
Iterative algorithms for large partitioned linear systems, with applications to image reconstruction
P. P. B. Eggermont, G. T. Herman, and A. Lent · 1981
Earlier work this paper cites.
Strong underrelaxation in Kaczmarz’s method for inconsistent systems
Y. Censor, P. P. B. Eggermont, and D. Gordon · 1983
Earlier work this paper cites.
The mathematics of computerized tomography , volume 32 of Classics in Applied Mathematics
F. Natterer · 1986
Earlier work this paper cites.
On the acceleration of Kaczmarz’s method for inconsistent linear systems
M. Hanke and W. Niethammer · 1990
Earlier work this paper cites.
New variants of the POCS method using affine subspaces of finite codimension, with applications to irregular sampling
C. Cenker, H. G. Feichtinger, M. Mayer, H. Steier, and T. Strohmer · 1992
Earlier work this paper cites.
Algebraic reconstruction techniques can be made computationally efficient
G.T. Herman and L.B. Meyer · 1993
Earlier work this paper cites.
A statistical study of on-line learning
N. Murata · 1998
Earlier work this paper cites.
Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems
C. Popa · 1998
Earlier work this paper cites.
Block-projections algorithms with blocks containing mutually orthogonal rows and columns
C. Popa · 1999
Earlier work this paper cites.
A fast Kaczmarz-Kovarik algorithm for consistent least-squares problems
C. Popa · 2001
Earlier work this paper cites.
Introductory Lectures on Convex Optimization
Y. Nesterov · 2004
Earlier work this paper cites.
A Kaczmarz-Kovarik algorithm for symmetric ill-conditioned matrices
C. Popa · 2004
Earlier work this paper cites.
The tradeoffs of large scale learning
O. Bousquet and L. Bottou · 2007
Cited alongside, same era.
Applied iterative methods
C. L. Byrne · 2008
Cited alongside, same era.
Svm optimization: inverse dependence on training set size
S. Shalev-Shwartz and N. Srebro · 2008
Cited alongside, same era.
An improved approximation algorithm for the column subset selection problem
C. Boutsidis, M. Mahoney, and P. Drineas · 2009
Cited alongside, same era.
Fundamentals of computerized tomography: image reconstruction from projections
G. T. Herman · 2009
Cited alongside, same era.
Robust stochastic approximation approach to stochastic programming
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro · 2009
Cited alongside, same era.
On Kaczmarzs projection iteration as a direct solver for linear least squares problems
C. Popa, T. Preclik, H. Köstler, and U. Rüde · 2012
Later among the works it cites.
Sparse Legendre expansions via ℓ 1 \ell_{1} -minimization
H. Rauhut and R. Ward · 2012
Later among the works it cites.
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
P. Richtárik and M. Takáč · 2012
Later among the works it cites.
O. Shamir and T. Zhang · 2012
Later among the works it cites.
Randomized extended Kaczmarz for solving least-squares
A. Zouzias and N. M. Freris · 2012
Later among the works it cites.
Revisiting the nyström method for improved large-scale machine learning
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A randomized Kaczmarz algorithm with exponential convergence
T. Strohmer and R. Vershynin · 2009
Cited alongside, same era.
Large-scale machine learning with stochastic gradient descent
L. Bottou · 2010
Cited alongside, same era.
Randomized Kaczmarz solver for noisy linear systems
D. Needell · 2010
Cited alongside, same era.
Smoothness, low noise and fast rates
N. Srebro, K. Sridharan, and A. Tewari · 2010
Cited alongside, same era.
Non-asymptotic analysis of stochastic approximation algorithms for machine learning
F. Bach and E. Moulines · 2011
Cited alongside, same era.
The tradeoffs of large-scale learning
L. Bottou and O. Bousquet · 2011
Cited alongside, same era.
A. Gittens and M. Mahoney · 2013
Closest in time.
Augmented ℓ 1 \ell_{1} and nuclear-norm models with a globally linearly convergent algorithm
M. Lai and W. Yin · 2013
Closest in time.
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
Y. T. Lee and A. Sidford · 2013
Closest in time.
Paved with good intentions: Analysis of a randomized block kaczmarz method
D. Needell and J. A. Tropp · 2013
Closest in time.
Two-subspace projection method for coherent overdetermined linear systems
D. Needell and R. Ward · 2013
Closest in time.
Improving cur matrix decomposition and the nystrom approximation via adaptive sampling
S. Wang and Z. Zhang · 2013
Closest in time.
Gradient methods for convex minimization: better rates under weaker conditions
H. Zhang and W. Yin · 2013
Closest in time.
Coherent matrix completion
Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, and Rachel Ward · 2014
Closest in time.
Stable and robust sampling strategies for compressive imaging
F. Krahmer and R. Ward · 2014
Closest in time.
An asynchronous parallel randomized kaczmarz algorithm
Ji Liu, Stephen J Wright, and Srikrishna Sridhar · 2014
Closest in time.
A statistical perspective on algorithmic leveraging
P. Ma, B. Yu, and M. Mahoney · 2014
Closest in time.
Stochastic optimization with importance sampling
P. Zhao and T. Zhang · 2014
Closest in time.