Sparse recovery by reduced variance stochastic approximation
  In this paper, we discuss application of iterative Stochastic Optimization
routines to the problem of sparse signal recovery from noisy observation. Using
Stochastic Mirror Descent algorithm as a building block, we develop a
multistage procedure for recovery of sparse solutions to Stochastic
Optimization problem under assumption of smoothness and quadratic minoration on
the expected objective. An interesting feature of the proposed algorithm is
linear convergence of the approximate solution during the preliminary phase of
the routine when the component of stochastic error in the gradient observation
which is due to bad initial approximation of the optimal solution is larger
than the "ideal" asymptotic error component owing to observation noise "at the
optimal solution." We also show how one can straightforwardly enhance
reliability of the corresponding solution by using Median-of-Means like
techniques.
  We illustrate the performance of the proposed algorithms in application to
classical problems of recovery of sparse and low rank signals in generalized
linear regression framework. We show, under rather weak assumption on the
regressor and noise distributions, how they lead to parameter estimates which
obey (up to factors which are logarithmic in problem dimension and confidence
level) the best known to us accuracy bounds.
