Rates of Convergence of Semi-Stochastic Approximation Procedures for Solving Stochastic Optimization Problems
Kurt Marti, Erich Fuchs · Optimization · 1986
A semi-stochastic approximation procedure is considered for the minimization of a convex mean value function F(x) = Ef(x,ω) subject to xεD. Here Dis a closed convex subset of Rr f=f(x,ω) is a random function on Rr P D denotes the projection of Rronto Dand ρ n >0 is a step size. Furthermored n denotes either a stochastic search direction, e.g. a negative stochastic(quasi-) gradient, of Fat X n or if available a (deterministic) descent direction for Fat X n . Having already sufficient conditions for the almost sure convergence of semi-stochastic approximation procedures to an optimal solution x *of the basic minimization problem minimize problem minimize F(x) s.t. xεDthe problem is now to find estimates for the speed of convergence of this hydride procedure In the case of a fixed rate of stochastic, deterministic steps taken in (1), we find the asymptotic representation Where is the mean square error of the pure stochastic and semi-stochastic approximation procedure and(X n) respectively. MoreoversQ 1,Q 2are coefficients with O< Q 1<1Q 1< Q 2and given by known formulas involving the parameters of the algorithms If the stochastic steps are taken at a decreasing rate in (1), then the speed of convergence can be increased from, in the pure stochastic case, to the order of b=O(n -λ) with 1< λ 2 in the semi-stochastic case.