In this paper we present the greedy step averaging(GSA) method, a parameter-free stochastic optimization algorithm for a variety of machine learning problems. As a gradient-based optimization method, GSA makes use of the information from the minimizer of a single sample's loss function, and takes average strategy to calculate reasonable learning rate sequence. While most existing gradient-based algorithms introduce an increasing number of hyper parameters or try to make a trade-off between computational cost and convergence rate, GSA avoids the manual tuning of learning rate and brings in no more hyper parameters or extra cost. We perform exhaustive numerical experiments for logistic and softmax regression to compare our method with the other state of the art ones on 16 datasets. Results show that GSA is robust on various scenarios.
A typical SAG computes the full gradients at the beginning of iteration, in each following step it chooses a sample's gradient randomly to refresh the full gradients. The update scheme reads @math where the @math denotes the randomly chosen index, and . Like FG method, SAG incorporates a gradient with respect to each training sample, but like SGD, in each iteration it only computes the gradient with respect to a single training example and the cost of the iteration is independent of @math . In @cite_20 , the authors show that the SAG iterations have a linear convergence rate. However SAG have at least 2 drawbacks. First it involves the evaluation of full gradient.Even though it calls for full gradient only once, it is hard to implement in some scenarios. Maybe this difficulty can be resolved by arbitrarily choose the initial gradients for each sample(e.g. zero vectors), but the second weakness makes it completely infeasible in certain scenarios: SAG has an extremely large memory cost @math because it has to store previous gradient for each sample. There is no free lunch. These are prices we have to pay for linear convergence.
@cite_20
2105875671
We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard algorithms, both in terms of optimizing the training error and reducing the test error quickly.