# A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control

arXiv: https://arxiv.org/abs/2006.10820 · HTML: https://mlsanity.com/paper/2006.10820/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2020.

## Built on by (most cited first, 14 of 14)

- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Second-Order Fine-Tuning without Pain for LLMs:A Hessian Informed Zeroth-Order Optimizer](https://mlsanity.com/paper/2402.15173/) (2024)
- [FZOO: Fast Zeroth-Order Optimizer for Fine-Tuning Large Language Models towards Adam-Scale Speed](https://mlsanity.com/paper/2506.09034/) (2025)
- [Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions](https://mlsanity.com/paper/2202.13046/) (2022)
- [Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamics](https://mlsanity.com/paper/2503.07324/) (2025)
- [Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent](https://mlsanity.com/paper/2107.12416/) (2021)
- [Policy Evaluation in Distributional LQR](https://mlsanity.com/paper/2303.13657/) (2023)
- [No-regret learning for repeated non-cooperative games with lossy bandits](https://mlsanity.com/paper/2205.06968/) (2022)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)
- [Risk-averse learning with delayed feedback](https://mlsanity.com/paper/2409.16866/) (2024)
- [BOND: License to Train with Black-Box Functions](https://mlsanity.com/paper/2510.25074/) (2025)
- [GLUE: Gradient-free Learning to Unify Experts](https://mlsanity.com/paper/2512.22467/) (2025)
- [Guiding the Recommender: Information-Aware Auto-Bidding for Content Promotion](https://mlsanity.com/paper/2601.20422/) (2026)
- [Greedy dynamical meta-learning](https://mlsanity.com/paper/2607.23925/) (2026)

## Abstract (arXiv)

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.