On the Almost Sure Convergence of the Stochastic Three Points Algorithm

The stochastic three points (STP) algorithm is a derivative-free optimization technique designed for unconstrained optimization problems in ℝd. In this paper, we analyze this algorithm for three classes of functions: smooth functions that may lack convexity, smooth convex functions, and smooth functions that are strongly convex. Our work provides the first almost sure convergence results of the STP algorithm, alongside some convergence results in expectation. For the class of smooth functions, we establish that the best gradient iterate of the STP algorithm converges almost surely to zero at a rate of o(1/T^frac12-ε) for any ε∈ (0,frac12), where T is the number of iterations. Furthermore, within the same class of functions, we establish both almost sure convergence and convergence in expectation of the final gradient iterate towards zero. For the class of smooth convex functions, we establish that f(θT) converges to infθ ∈ ℝd f(θ) almost surely at a rate of o(1/T1-ε) for any ε∈ (0,1), and in expectation at a rate of O(fracdT) where d is the dimension of the space. Finally, for the class of smooth functions that are strongly convex, we establish that when step sizes are obtained by approximating the directional derivatives of the function, f(θT) converges to infθ ∈ ℝd f(θ) in expectation at a rate of O((1-fracμ2π dL)T), and almost surely at a rate of o((1-sfracμ2π dL)T) for any s∈ (0,1), where μ and L are the strong convexity and smoothness parameters of the function.