ECPv2: Fast, Efficient, and Scalable Global Optimization of Lipschitz Functions

Abstract

We propose ECPv2, a scalable and theoretically grounded algorithm for global optimization of Lipschitz continuous functions with unknown Lipschitz constants. Building on the Every Call is Precious (ECP) framework, which ensures that each accepted function evaluation is potentially informative, ECPv2 addresses key limitations of ECP, including high computational cost and overly conservative early behavior. ECPv2 introduces three innovations: (i) an adaptive lower bound that prevents vacuous acceptance regions, (ii) a memory mechanism that restricts comparisons to a fixed-size subset of past evaluations, and (iii) a fixed random projection that accelerates distance computations in high dimensions. We theoretically show that ECPv2 retains ECP’s regret guarantees and expands the acceptance region with high probability. Extensive experiments and ablation studies empirically validate these findings. Using principled hyperparameter settings, we evaluate ECPv2 across a wide range of nonconvex optimization problems and find that it consistently matches or outperforms leading optimizers while significantly reducing wall clock time.