Improved Iteration Complexity in Black-Box Optimization Problems under Higher Order Smoothness Function Condition

This paper is devoted to the study (common in many applications) of the black-box optimization problem, where the black-box represents a gradient-free oracle f̃ = f(x) + ξ providing the objective function value with some stochastic noise. Assuming that the objective function is μ-strongly convex, and also not just L-smooth, but has a higher order of smoothness (β ≥ 2) we provide a novel optimization method: Zero-Order Accelerated Batched Stochastic Gradient Descent, whose theoretical analysis closes the question regarding the iteration complexity, achieving optimal estimates. Moreover, we provide a thorough analysis of the maximum noise level, and show under which condition the maximum noise level will take into account information about batch size B as well as information about the smoothness order of the function β.