Before revision:  In this case, linear convergence rate of the expected function error is also proved , along with a worst-case \mathcal{O (\log(\varepsilon^{-1})) complexity bound} .  Numerical experiments, including comparisons with state-of-the art first- and second-order stochastic optimization methods, show the efficiency of our approach.
After revision:  In this case, linear convergence rate of the expected function error is also proved , along with a worst-case \mathcal{O (\log(\varepsilon^{-1})) complexity bound} . A key issue is a two-step sampling at each iteration, which allows us to control the error present in the line-search procedure. Stationarity of limit points is proved in the almost-sure sense, while almost-sure convergence of the sequence of approximations to the solution holds with the additional hypothesis that the functions are strongly convex. Numerical experiments, including comparisons with state-of-the art first- and second-order stochastic optimization methods, show the efficiency of our approach.