text: Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence in expectation to the solution within a specified tolerance. This generalized framework applies to problems such as sparse signal recovery in compressed sensing, low-rank matrix recovery, and covariance matrix estimation, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments which align with the theoretical analysis and demonstrate these improvements in several different settings.
  @cite_22: We consider the minimization of a convex objective function defined on a Hilbert space, which is only available through unbiased estimates of its gradients. This problem includes standard machine learning algorithms such as kernel logistic regression and least-squares regression, and is commonly referred to as a stochastic approximation problem in the operations research community. We provide a non-asymptotic analysis of the convergence of two well-known algorithms, stochastic gradient descent (a.k.a. Robbins-Monro algorithm) as well as a simple modification where iterates are averaged (a.k.a. Polyak-Ruppert averaging). Our analysis suggests that a learning rate proportional to the inverse of the number of iterations, while leading to the optimal convergence rate in the strongly convex case, is not robust to the lack of strong convexity or the setting of the proportionality constant. This situation is remedied when using slower decays together with averaging, robustly leading to the optimal rate of convergence. We illustrate our theoretical results with simulations on synthetic and standard datasets.
  @cite_15: The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of in the context of reconstructing bandlimited functions from nonuniform sampling.
  @cite_8: 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 @math (where @math is a bound on the smoothness and @math on the strong convexity) to a linear dependence on @math . Furthermore, we show how reweighting the sampling distribution (i.e. importance sampling) is necessary in order to further improve convergence, and obtain a linear dependence in the average smoothness, dominating previous results. We also discuss importance sampling for SGD more broadly and show how it can improve convergence also in other scenarios. Our results are based on a connection we make between SGD and the randomized Kaczmarz algorithm, which allows us to transfer ideas between the separate bodies of literature studying each of the two methods. In particular, we recast the randomized Kaczmarz algorithm as an instance of SGD, and apply our results to prove its exponential convergence, but to the solution of a weighted least squares problem rather than the original least squares problem. We then present a modified Kaczmarz algorithm with partially biased sampling which does converge to the original least squares solution with the same exponential convergence rate.
  @cite_1: 
  @cite_39: In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an ( )-accurate solution with probability at least (1- ) in at most (O((n ) (1 )) ) iterations, where (n ) is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341–362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing ( ) from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving first true iteration complexity bounds. For strongly convex functions the method converges linearly. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale ( _1 )-regularized least squares problems with a billion variables.
  @cite_40: In this paper we propose new methods for solving huge-scale optimization problems. For problems of this size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply an optimization technique based on random partial update of decision variables. For these methods, we prove the global estimates for the rate of convergence. Surprisingly enough, for certain classes of objective functions, our results are better than the standard worst-case bounds for deterministic algorithms. We present constrained and unconstrained versions of the method, and its accelerated variant. Our numerical test confirms a high efficiency of this technique on problems of very big size.
  @cite_31: This comprehensive book offers 504 main pages divided into 17 chapters. In addition, five very useful and clearly written appendices are provided, covering multivariate analysis, basic tests in statistics, probability theory and convergence, random number generators and Markov processes. Some of the topics covered in the book include: stochastic approximation in nonlinear search and optimization; evolutionary computations; reinforcement learning via temporal differences; mathematical model selection; and computer-simulation-based optimizations. Over 250 exercises are provided in the book, though only a small number of them have solutions included in the volume. A separate solution manual is available, as is a very informative webpage. The book may serve as either a reference for researchers and practitioners in many fields or as an excellent graduate level textbook.
  @cite_16: 
summary: Methods for stochastic convex optimization have been developed in a very related but somewhat independent large body of work. We discuss only a few here which motivated our work, and refer the reader to e.g. @cite_31 @cite_1 for a more complete survey. Stochastic Gradient Descent (SGD) aims to minimize a convex objective function using unbiased stochastic gradient estimates, typically of the form @math where @math is chosen stochastically. For the optimization ) with no constraint, this can be summarized concisely by the update rule @math for some step size @math . For smooth objective functions @math , classical results demonstrate a @math convergence rate with respect to the objective difference @math . In the strongly convex case, Bach and Moulines @cite_22 improve this convergence to a linear rate, depending on the average squared condition number of the system. Recently, Needell et. al. draw on connections to the Kaczmarz method (see @cite_16 @cite_15 and references therein), and improve this to a linear dependence on the uniform condition number @cite_8 . Another line of work is the Stochastic Coordinate Descent (SCD) beginning with the work of @cite_40 . Extension to minimization of composite functions in ) is described in @cite_39 .