A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control
This addresses a practical bottleneck in online optimization where data is not available a priori, offering a more efficient alternative for applications like simulation-based control.
The paper tackles the inefficiency of two-point feedback in zeroth-order optimization for black-box learning and control by proposing a one-point residual feedback scheme that queries the function value once per iteration, achieving query complexity matching two-point schemes for deterministic Lipschitz functions and the same convergence rate for stochastic bandit problems.
Zeroth-order optimization (ZO) algorithms have been recently used to solve black-box or simulation-based learning and control problems, where the gradient of the objective function cannot be easily computed but can be approximated using the objective function values. Many existing ZO algorithms adopt two-point feedback schemes due to their fast convergence rate compared to one-point feedback schemes. However, two-point schemes require two evaluations of the objective function at each iteration, which can be impractical in applications where the data are not all available a priori, e.g., in online optimization. In this paper, we propose a novel one-point feedback scheme that queries the function value once at each iteration and estimates the gradient using the residual between two consecutive points. When optimizing a deterministic Lipschitz function, we show that the query complexity of ZO with the proposed one-point residual feedback matches that of ZO with the existing two-point schemes. Moreover, the query complexity of the proposed algorithm can be improved when the objective function has Lipschitz gradient. Then, for stochastic bandit optimization problems where only noisy objective function values are given, we show that ZO with one-point residual feedback achieves the same convergence rate as that of two-point scheme with uncontrollable data samples. We demonstrate the effectiveness of the proposed one-point residual feedback via extensive numerical experiments.