We propose dynamic sampled stochastic approximation (SA) methods for stochastic optimization with a heavy-tailed distribution (with finite 2nd moment). The objective is the sum of a smooth convex function with a convex regularizer. Typically, it is assumed an oracle with an upper bound @math on its variance (OUBV). Differently, we assume an oracle with . This rarely addressed setup is more aggressive but realistic, where the variance may not be bounded. Our methods achieve optimal iteration complexity and (near) optimal oracle complexity. For the smooth convex class, we use an accelerated SA method a la FISTA which achieves, given tolerance @math , the optimal iteration complexity of @math with a near-optimal oracle complexity of @math . This improves upon Ghadimi and Lan [, 156:59-99, 2016] where it is assumed an OUBV. For the strongly convex class, our method achieves optimal iteration complexity of @math and optimal oracle complexity of @math . This improves upon [, 134:127-155, 2012] where it is assumed an OUBV. In terms of variance, our bounds are local: they depend on variances @math at solutions @math and the per unit distance multiplicative variance @math . For the smooth convex class, there exist policies such that our bounds resemble those obtained if it was assumed an OUBV with @math . For the strongly convex class such property is obtained exactly if the condition number is estimated or in the limit for better conditioned problems or for larger initial batch sizes. In any case, if it is assumed an OUBV, our bounds are thus much sharper since typically @math .
The initial version of the SG method uses with stepsizes satisfying @math and @math , typically @math . A fundamental improvement in respect to estimation error was Polyak-Ruppert's scheme @cite_37 @cite_47 @cite_45 @cite_34 , where @math are used with a subsequent of the iterates with weights @math (this is sometimes called ). , such scheme obtains optimal iteration and oracle complexities of @math for the smooth convex class and of @math for smooth strongly convex class. These are also the size of the final ergodic average, a measure of the additional implicitly required in iterate averaging schemes. Such methods, hence, are efficient in terms of oracle complexity. Iterate averaging was then extensively explored (see e.g. @cite_48 @cite_5 @cite_50 @cite_24 @cite_43 @cite_55 @cite_23 ). The important work @cite_43 exploits the robustness of iterate averaging in SA methods and shows that such schemes can outperform the SAA approach on relevant convex problems. On the strongly convex class, @cite_21 gives a detailed non-asymptotic robust analysis of Polyak-Ruppert averaging scheme. See also @cite_14 @cite_25 @cite_52 for improvements.
@cite_37 @cite_14 @cite_48 @cite_55 @cite_21 @cite_52 @cite_24 @cite_43 @cite_45 @cite_50 @cite_23 @cite_5 @cite_47 @cite_34 @cite_25
2950132609 2500690480 1791038712 2951196414
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 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 propose the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method's iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from O(1 k^ 1 2 ) to O(1 k) in general, and when the sum is strongly-convex the convergence rate is improved from the sub-linear O(1 k) to a linear convergence rate of the form O(p^k) for p 1. Further, in many cases the convergence rate of the new method is also faster than black-box deterministic gradient methods, in terms of the number of gradient evaluations. Numerical experiments indicate that the new algorithm often dramatically outperforms existing SG and deterministic gradient methods, and that the performance may be further improved through the use of non-uniform sampling strategies. Stochastic gradient descent (SGD) is a simple and popular method to solve stochastic optimization problems which arise in machine learning. For strongly convex problems, its convergence rate was known to be O( (T) T), by running SGD for T iterations and returning the average point. However, recent results showed that using a different algorithm, one can get an optimal O(1 T) rate. This might lead one to believe that standard SGD is suboptimal, and maybe should even be replaced as a method of choice. In this paper, we investigate the optimality of SGD in a stochastic setting. We show that for smooth problems, the algorithm attains the optimal O(1 T) rate. However, for non-smooth problems, the convergence rate with averaging might really be ( (T) T), and this is not just an artifact of the analysis. On the flip side, we show that a simple modification of the averaging step suffices to recover the O(1 T) rate, and no other change of the algorithm is necessary. We also present experimental results which support our findings, and point out open problems.