Variance-Reduced Stochastic PCA and SVD with Exponential Convergence (VR-PCA)

Variance-Reduced Stochastic PCA and SVD with Exponential Convergence (VR-PCA) is an epoch-based stochastic spectral optimization algorithm introduced and analyzed by Ohad Shamir (2015) for computing the leading eigenvector(s) of an empirical covariance matrix A = (1/n) sum_{i=1}^n x_i x_i^T from a data matrix X = (x_1, ..., x_n) in R^{d x n}. In each outer epoch s, VR-PCA computes the exact full-pass anchor vector u_tilde = A w_tilde_{s-1} = (1/n) sum_{i=1}^n x_i (x_i^T w_tilde_{s-1}) and performs m inner stochastic updates w_t' = w_{t-1} + eta*(x_{i_t}(x_{i_t}^T w_{t-1} - x_{i_t}^T w_tilde_{s-1}) + u_tilde) = (I + eta*A)w_{t-1} + eta*(x_{i_t} x_{i_t}^T - A)(w_{t-1} - w_tilde_{s-1}), w_t = w_t' / ||w_t'||_2 with a fixed step size eta, driving the stochastic gradient variance ||w_{t-1} - w_tilde_{s-1}||_2^2 to zero across epochs and achieving linear/exponential convergence in O(d_s (n + (r/lambda)^2) log(1/epsilon)) total runtime.