Abstract
Recent years have seen advances in optimizing large
scale statistical estimation problems. In statistical
learning settings iterative optimization algorithms
have been shown to enjoy geometric convergence.
While powerful, such results only hold for the original dataset, and may face computational challenges
when the sample size is large. In this paper, we study
sketched iterative algorithms, in particular sketchedPGD (projected gradient descent) and sketchedSVRG (stochastic variance reduced gradient) for
structured generalized linear model, and illustrate
that these methods continue to have geometric convergence to the statistical error under suitable assumptions. Moreover, the sketching dimension is
allowed to be even smaller than the ambient dimension, thus can lead to significant speed-ups. The
sketched iterative algorithms introduced provide an
additional dimension to study the trade-offs between
statistical accuracy and time