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.
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 .
@cite_22 @cite_15 @cite_8 @cite_1 @cite_39 @cite_40 @cite_31 @cite_16
2156779765 2048305372 2950132609 2117686388 2095984592 2064076655
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. We propose a novel stochastic gradient method---semi-stochastic coordinate descent (S2CD)---for the problem of minimizing a strongly convex function represented as the average of a large number of smooth convex functions: @math . Our method first performs a deterministic step (computation of the gradient of @math at the starting point), followed by a large number of stochastic steps. The process is repeated a few times, with the last stochastic iterate becoming the new starting point where the deterministic step is taken. The novelty of our method is in how the stochastic steps are performed. In each such step, we pick a random function @math and a random coordinate @math ---both using nonuniform distributions---and update a single coordinate of the decision vector only, based on the computation of the @math partial derivative of @math at two different points. Each random step of the method constitutes an unbiased estimate of the gradient of @math and moreover, the squared norm of the steps goes to zero in expectation, meaning that the stochastic estimate of the gradient progressively improves. The complexity of the method is the sum of two terms: @math evaluations of gradients @math and @math evaluations of partial derivatives @math , where @math is a novel condition number. Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., the problem @math minxEvfv(Ew[gw(x)]). In order to solve this stochastic composition problem, we propose a class of stochastic compositional gradient descent (SCGD) algorithms that can be viewed as stochastic versions of quasi-gradient method. SCGD update the solutions based on noisy sample gradients of @math fv,gw and use an auxiliary variable to track the unknown quantity @math Ewgw(x). We prove that the SCGD converge almost surely to an optimal solution for convex optimization problems, as long as such a solution exists. The convergence involves the interplay of two iterations with different time scales. For nonsmooth convex problems, the SCGD achieves a convergence rate of @math O(k-1 4) in the general case and @math O(k-2 3) in the strongly convex case, after taking k samples. For smooth convex problems, the SCGD can be accelerated to converge at a rate of @math O(k-2 7) in the general case and @math O(k-4 5) in the strongly convex case. For nonconvex problems, we prove that any limit point generated by SCGD is a stationary point, for which we also provide the convergence rate analysis. Indeed, the stochastic setting where one wants to optimize compositions of expected-value functions is very common in practice. The proposed SCGD methods find wide applications in learning, estimation, dynamic programming, etc. We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in @math iterations for smooth objectives, and stochastic gradient descent that converges in @math iterations for objectives that are sum of smooth functions. We provide the first improvement in this line of research. Our result is based on the variance reduction trick recently introduced to convex optimization, as well as a brand new analysis of variance reduction that is suitable for non-convex optimization. For objectives that are sum of smooth functions, our first-order minibatch stochastic method converges with an @math rate, and is faster than full gradient descent by @math . We demonstrate the effectiveness of our methods on empirical risk minimizations with non-convex loss functions and training neural nets. The stochastic composition optimization proposed recently by [2014] minimizes the objective with the compositional expectation form: @math It summarizes many important applications in machine learning, statistics, and finance. In this paper, we consider the finite-sum scenario for composition optimization: [ f (x) := 1 n i = 1 ^n F_i ( 1 m j = 1 ^m G_j (x) ). ] We propose two algorithms to solve this problem by combining the stochastic compositional gradient descent (SCGD) and the stochastic variance reduced gradient (SVRG) technique. A constant linear convergence rate is proved for strongly convex optimization, which substantially improves the sublinear rate @math of the best known algorithm. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . We consider stochastic strongly convex optimization with a complex inequality constraint. This complex inequality constraint may lead to computationally expensive projections in algorithmic iterations of the stochastic gradient descent (SGD) methods. To reduce the computation costs pertaining to the projections, we propose an Epoch-Projection Stochastic Gradient Descent (Epro-SGD) method. The proposed Epro-SGD method consists of a sequence of epochs; it applies SGD to an augmented objective function at each iteration within the epoch, and then performs a projection at the end of each epoch. Given a strongly convex optimization and for a total number of @math iterations, Epro-SGD requires only @math projections, and meanwhile attains an optimal convergence rate of @math , both in expectation and with a high probability. To exploit the structure of the optimization problem, we propose a proximal variant of Epro-SGD, namely Epro-ORDA, based on the optimal regularized dual averaging method. We apply the proposed methods on real-world applications; the empirical results demonstrate the effectiveness of our methods. We study the minimization of a convex function @math over the set of @math positive semi-definite matrices, but when the problem is recast as @math , with @math and @math . We study the performance of gradient descent on @math ---which we refer to as Factored Gradient Descent (FGD)---under standard assumptions on the original function @math . We provide a rule for selecting the step size and, with this choice, show that the local convergence rate of FGD mirrors that of standard gradient descent on the original @math : i.e., after @math steps, the error is @math for smooth @math , and exponentially small in @math when @math is (restricted) strongly convex. In addition, we provide a procedure to initialize FGD for (restricted) strongly convex objectives and when one only has access to @math via a first-order oracle; for several problem instances, such proper initialization leads to global convergence guarantees. FGD and similar procedures are widely used in practice for problems that can be posed as matrix factorization. To the best of our knowledge, this is the first paper to provide precise convergence rate guarantees for general convex functions under standard convex assumptions.