Descent Direction Stochastic Approximation Algorithm with Adaptive Step Sizes (Journal of Computational Mathematics, 2018)
A stochastic approximation (SA) algorithm with new adaptive step sizes for solvingunconstrained minimization problems in noisy environment is proposed. New adaptivestep size scheme uses ordered statistics of fixed number of previous noisy function valuesas a criterion for accepting good and rejecting bad steps. The scheme allows the algorithmto move in bigger steps and avoid steps proportional to $1/k$ when it is expected thatlarger steps will improve the performance. An algorithm with the new adaptive scheme isdefined for a general descent direction. The almost sure convergence is established. Theperformance of new algorithm is tested on a set of standard test problems and comparedwith relevant algorithms. Numerical results support theoretical expectations and verifyefficiency of the algorithm regardless of chosen search direction and noise level. Numericalresults on problems arising in machine learning are also presented. Linear regressionproblem is considered using real data set. The results suggest that the proposed algorithmshows promise.
Keywords: Unconstrained optimization; Stochastic optimization; Stochastic approximation; Noisy function; Adaptive step size; Descent direction; Linear regression model.