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.
The idea behind Momentum and Gradient Averaging is to utilize previous gradient information to determine a better descent direction to accelerate convergence. However, rather than averaging the gradients, the previous iterative points @math can also be taken into account. Some authors use the basic SG iteration but take an average over @math values to give a new algorithm. With a suitable choice of step-sizes, this gives the same asymptotic efficiency as Newton-like second-order SG methods and also leads to increased robustness of the convergence rate to the exact sequence of step sizes @cite_3 . The update scheme reads @math @math The Iterate Averaging method uses all the previous iterative points and take its average as the next searching point. It has been proved that under certain assumptions of appropriate step-size, this method enjoys a second-order convergence rate @cite_3 . Even for a fixed step-size strategy, it can also show a great robustness to avoid oscillations. But unfortunately, it is extremely sensible to the initial points: a bad starting point can not only hinder the convergence rate but also cause divergence. Besides, it also requires an extra @math memory cost as Momentum.
@cite_3
2086161653
A new recursive algorithm of stochastic approximation type with the averaging of trajectories is investigated. Convergence with probability one is proved for a variety of classical optimization and identification problems. It is also demonstrated for these problems that the proposed algorithm achieves the highest possible rate of convergence.