Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity

Probability inequalities for sums of bounded random variables

W. Hoeffding · 1963

Earlier work this paper cites.

The method of stochastic approximation for the determination of the least eigenvalue of a symmetrical matrix

T.P. Krasulina · 1969

Earlier work this paper cites.

Simplified neuron model as a principal component analyzer

E. Oja · 1982

Earlier work this paper cites.

Estimating the largest eigenvalue by the power and lanczos algorithms with a random start

J. Kuczynski and H. Wozniakowski · 1992

Earlier work this paper cites.

Convex optimization

S. Boyd and L. Vandenberghe · 2004

Earlier work this paper cites.

Sampling from large matrices: An approach through geometric functional analysis

M. Rudelson and R. Vershynin · 2007

Earlier work this paper cites.

Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

N. Halko, P. Martinsson, and J. Tropp · 2011

Earlier work this paper cites.

Stochastic optimization for PCA and PLS

R. Arora, A. Cotter, K. Livescu, and N. Srebro · 2012

Cited alongside, same era.

Matrix computations

G. H Golub and C. Van Loan · 2012

Cited alongside, same era.

Matrix analysis

R. Horn and C. Johnson · 2012

Cited alongside, same era.

Stochastic optimization of PCA with capped MSG

R. Arora, A. Cotter, and N. Srebro · 2013

Cited alongside, same era.

The fast convergence of incremental PCA

A. Balsubramani, S. Dasgupta, and Y. Freund · 2013

Cited alongside, same era.

Accelerating stochastic gradient descent using predictive variance reduction

R. Johnson and T. Zhang · 2013

Cited alongside, same era.

Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization

The noisy power method: A meta algorithm with applications

M. Hardt and E. Price · 2014

Later among the works it cites.

Stochastic proximal gradient descent with acceleration techniques

A. Nitanda · 2014

Later among the works it cites.

Sketching as a tool for numerical linear algebra

D. Woodruff · 2014

Later among the works it cites.

A lower bound for the optimization of finite sums

A. Agarwal and L. Bottou · 2015

Closest in time.

Global convergence of stochastic gradient descent for some nonconvex matrix problems

C. De Sa, K. Olukotun, and C. Ré · 2015

Closest in time.

A stochastic PCA and SVD algorithm with an exponential convergence rate

O. Shamir · 2015

Closest in time.