Optimal Step Sizes in Semi-Stochastic Approximation Procedures. II
K. Marti, E. Plöchinger · Optimization · 1990
Based on the recurrence relations for the optimal error bounds obtained in the first part, here the corresponding recursions for the optimal step sizes are derived first. As a consequence, several basic properties of the optimal step sizes are found. The recurrence relations for the optimal step sizes involve certain functional parameters which can be estimated for practical applications. The main part is then devoted to the derivation of the convergence rates of the optimally controlled stochastic and semistochastic approximation procedure. As a basic result we find that the well-known unsatisfactory convergence behavior of standard stochastic approximation methods can be improved up to a linear convergence rate in optimally controlled semi-stochastic approximation procedures. Finally, the initial behavior of the optimally controlled process is compared with the initial behavior of the uncontrolled procedure.