The Black-Box Optimization Problem: Zero-Order Accelerated Stochastic Method via Kernel Approximation

Understand

In this paper, we study the standard formulation of an optimization problem when the computation of gradient is not available.

• Such a problem can be classified as a "black box" optimization problem, since the oracle returns only the value of the objective function at the requested point, possibly with some stochastic noise.
• Assuming convex, and higher-order of smoothness of the objective function, this paper provides a zero-order accelerated stochastic gradient descent (ZO-AccSGD) method for solving this problem, which exploits the higher-order of smoothness information via kernel approximation.
• As theoretical results, we show that the ZO-AccSGD algorithm proposed in this paper improves the convergence results of state-of-the-art (SOTA) algorithms, namely the estimate of iteration complexity.