ECPv2: Fast, Efficient, and Scalable Global Optimization of Lipschitz Functions
This provides a faster and more efficient solution for high-dimensional, non-convex optimization problems, though it appears incremental as it builds on the existing ECP framework.
The paper tackles the problem of global optimization of Lipschitz-continuous functions with unknown Lipschitz constants by proposing ECPv2, which addresses computational cost and conservative behavior in prior methods. The result shows that ECPv2 matches or outperforms state-of-the-art optimizers across benchmarks while significantly reducing wall-clock time.
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 to avoid vacuous acceptance regions, (ii) a Worst-m memory mechanism that restricts comparisons to a fixed-size subset of past evaluations, and (iii) a fixed random projection to accelerate distance computations in high dimensions. We theoretically show that ECPv2 retains ECP's no-regret guarantees with optimal finite-time bounds and expands the acceptance region with high probability. We further empirically validate these findings through extensive experiments and ablation studies. Using principled hyperparameter settings, we evaluate ECPv2 across a wide range of high-dimensional, non-convex optimization problems. Across benchmarks, ECPv2 consistently matches or outperforms state-of-the-art optimizers, while significantly reducing wall-clock time.