# Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 59 references that are in the map.
- First posted on arXiv 6 Feb 2025.

## Builds on (most cited first, 17 of 17)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization](https://mlsanity.com/paper/2109.09831/) (2021)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [InstructZero: Efficient Instruction Optimization for Black-Box Large Language Models](https://mlsanity.com/paper/2306.03082/) (2023)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Global optimization of Lipschitz functions](https://mlsanity.com/paper/1703.02628/) (2017)
- [Use Your INSTINCT: INSTruction optimization for LLMs usIng Neural bandits Coupled with Transformers](https://mlsanity.com/paper/2310.02905/) (2023)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [cmaes: A Simple yet Practical Python Library for CMA-ES](https://mlsanity.com/paper/2402.01373/) (2024)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Global Continuous Optimization with Error Bound and Fast Convergence](https://mlsanity.com/paper/1607.04817/) (2016)
- [Stochastic Q-learning for Large Discrete Action Spaces](https://mlsanity.com/paper/2405.10310/) (2024)
- [LIPO+: Frugal Global Optimization for Lipschitz Functions](https://mlsanity.com/paper/2406.19723/) (2024)
- [A ranking approach to global optimization](https://mlsanity.com/paper/1603.04381/) (2016)

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

- [Verification and Validation of Physics-Informed Surrogate Component Models for Dynamic Power-System Simulation](https://mlsanity.com/paper/2603.17836/) (2026)
- [Label-Efficient School Detection from Aerial Imagery via Weakly Supervised Pretraining and Fine-Tuning](https://mlsanity.com/paper/2605.03968/) (2026)
- [Signal from Space: Detecting Schools and Towers to Bridge the Digital Divide](https://mlsanity.com/paper/2607.02724/) (2026)

## Abstract (arXiv)

Optimizing expensive, non-convex, black-box Lipschitz continuous functions presents significant challenges, particularly when the Lipschitz constant of the underlying function is unknown. Such problems often demand numerous function evaluations to approximate the global optimum, which can be prohibitive in terms of time, energy, or resources. In this work, we introduce Every Call is Precious (ECP), a novel global optimization algorithm that minimizes unpromising evaluations by strategically focusing on potentially optimal regions. Unlike previous approaches, ECP eliminates the need to estimate the Lipschitz constant, thereby avoiding additional function evaluations. ECP guarantees no-regret performance for infinite evaluation budgets and achieves minimax-optimal regret bounds within finite budgets. Extensive ablation studies validate the algorithm's robustness, while empirical evaluations show that ECP outperforms 10 benchmark algorithms including Lipschitz, Bayesian, bandits, and evolutionary methods across 30 multi-dimensional non-convex synthetic and real-world optimization problems, which positions ECP as a competitive approach for global optimization.