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

AI summary

Overview

Research area: Global black-box optimization of Lipschitz-continuous functions with unknown Lipschitz constants, sitting at the intersection of derivative-free optimization, bandit-style regret analysis, and high-dimensional dimensionality reduction.

Technical level: Intermediate to Advanced. The paper is a theory-first algorithmic contribution: it is readable with a background in optimization or machine learning, but the core arguments rely on Lipschitz upper bounds, no-regret analysis, and Johnson-Lindenstrauss style random projection guarantees.

Scope (one sentence): The paper introduces ECPv2, a refinement of the Every Call is Precious (ECP) algorithm that makes Lipschitz-based global optimization scalable to high dimensions and long evaluation budgets by adding an adaptive lower bound, a reduced-memory comparison set, and a fixed random projection, while preserving ECP's no-regret guarantee and optimal finite-time regret bound.

What This Paper Is About

Many real-world optimization problems give you only a black-box function that is expensive to evaluate, with no gradients available, and the function varies at a bounded but unknown rate (an unknown Lipschitz constant). The prior ECP algorithm addressed this by evaluating a candidate point only when it is still consistent with being the global maximizer, which made every evaluation informative but also made each iteration cost grow linearly with both the number of past evaluations and the problem dimension, and caused overly conservative early rejections. ECPv2 keeps ECP's conservative acceptance logic while removing these practical bottlenecks, aiming to match or beat state-of-the-art optimizers at a substantially lower wall-clock cost.

Key Contributions

1. An adaptive lower bound ε_t^⊘ = (max_i f(x_i) − min_j f(x_j)) / diam(X), derived from the ECP acceptance rule, which prevents the acceptance region from becoming vacuously empty and reduces unnecessary early rejections. It costs only O(1) per iteration because the running maximum and minimum are tracked incrementally.

2. A Worst-m memory mechanism that restricts the acceptance comparison to the m previously evaluated points with the lowest objective values, instead of all t points. Setting m ≥ t recovers the original ECP condition; smaller m reduces both computational and memory cost.

3. A fixed random projection P: R^d → R^{d'} applied inside the acceptance criterion, with d' = 8 log(βn)/(δ² − δ³) for a controlled distortion δ ∈ [0, 1). This reduces the cost of distance computations from O(d) to O(log(n)) in the relevant regime, where n is the maximum number of evaluations. For δ = 0 the projection reduces to the identity, recovering ECP.

4. Theoretical guarantees plus an empirical validation plan: the paper proves that the ECPv2 acceptance region strictly contains the ECP acceptance region with high probability, that no-regret is retained with optimal finite-time bounds, and reports extensive experiments and ablation studies across high-dimensional, non-convex problems.

Main Findings

• The adaptive lower bound prevents empty acceptance regions. Lemma 1 shows that if any point x ∈ X can satisfy the ECP acceptance condition, then ε_t must satisfy ε_t ≥ ε_t^⊘ = (f_max_t − f_min_t)/diam(X). This gives a principled re-initialization that avoids long rejection loops without sacrificing convergence or optimality.

• Each mechanism only enlarges the acceptance region. Lemma 2 shows A_ECP(ε_t, t) ⊆ A_t(ε_t, t) for the lower-bound version; Lemma 3 shows A_t(ε_t, t) ⊆ A_t(ε_t, t, m) for any m ≥ 1 under the Worst-m rule; Lemma 5 shows the projected-space region contains the unprojected region with probability at least 1 − 1/β².

• Combined, ECPv2 accepts everything ECP accepts, with high probability. Corollary 1 states that for any m ≤ n, A_ECP(ε_t, t) ⊆ A_ECPv2(ε_t, t, m, P) with probability at least 1 − 1/β², so no potential maximizer is erroneously discarded.

• Distance preservation is controlled. Lemma 4 establishes that for d' ≥ 8 log(βn)/(δ² − δ³), with probability at least 1 − 1/β², the inequalities (1 − δ)‖x_i − x_j‖² ≤ ‖x'_i − x'_j‖² ≤ (1 + δ)‖x_i − x_j‖² hold simultaneously for all pairs in the set of n vectors.

• Computational complexity drops substantially. Table 1 reports memory O((m + d) log(β n)) and runtime Ω(n (m + d) log(β n)) for ECPv2, versus memory O(nd) and runtime Ω(n² d) for ECP and for AdaLIPO and AdaLIPO+.

• The regret guarantee is preserved. ECPv2 retains the regret bound O_{1 − 1/β² − 1/ξ}(c* · (ln(1/ξ))^{1/d} · k · n^{−1/d}), where c* = diam(X) · log_{τ_{n,d}}(k/ε_1)^{1/d}, matching the ECP bound of O_{1 − 1/ξ}(c* · (ln(1/ξ))^{1/d} · k · n^{−1/d}) up to the added 1/β² failure probability.

• The bound is optimal up to constants. The minimax lower bound from Bull (2011) is Ω(rad(X) · k · n^{−1/d}), which frames the n^{−1/d} scaling as the fundamental limit for Lipschitz functions.

• Empirical claims are stated at a high level. The abstract and contributions state that across benchmarks ECPv2 consistently matches or outperforms state-of-the-art optimizers while significantly reducing wall-clock time, and that the authors derive principled hyperparameter settings. Specific benchmark names, dataset sizes, and numerical results are not reported in the available portion of the paper.

Methodology in Plain English

The starting point is the ECP algorithm's acceptance rule: a new candidate point x is evaluated only if its best-case value under a Lipschitz assumption — computed as the minimum over past evaluations of f(X_i) + ε_t · ‖x − X_i‖ — is at least the best value seen so far. The researchers keep this rule but change three things about how it is computed and when it applies.

First, they compute a data-driven floor for the parameter ε_t. Rather than letting ε_t grow only by geometric multiplication (ε_t ← τ_{n,d} · ε_t) whenever rejections exceed a threshold C > 1, they reset ε_t at each step to max(τ_{n,d} · ε_{t−1}, ε_t^⊘), where ε_t^⊘ is the spread between the best and worst observed function values divided by the domain diameter. This guarantees the acceptance test is never trivially unsatisfiable.

Second, instead of comparing the candidate against every point evaluated so far, they compare it against only the m points with the lowest observed function values. Intuitively, low-value points still exert useful rejection pressure on bad regions, while high-value points tend to over-constrain exploration. The mechanism is inspired by a stochastic maximization trick from earlier work (Fourati et al. 2024).

Third, they project the points into a lower-dimensional space using a fixed random Gaussian projection matrix — a scaled Gaussian matrix when δ > 0, an identity matrix when δ = 0 — and perform the distance computations there, using a rescaled parameter ε̃_t = max{ε_t, ε_t^⊘}/√(1 − δ). The projection dimension is chosen so that Johnson-Lindenstrauss style guarantees hold for all point pairs simultaneously.

The theoretical work then proceeds by proving each modification enlarges (never shrinks) the acceptance region, chaining the three inclusion lemmas into Corollary 1, and verifying that the regret bound retains the n^{−1/d} rate with matching constants.

Why This Matters

Impact on research. ECPv2 shows that a conservative, geometry-based acceptance rule — which previously carried a prohibitive Ω(n² d) cost per run — can be made asymptotically cheaper while keeping the same regret rate. It connects Lipschitz global optimization to Johnson-Lindenstrauss dimensionality reduction and to reduced-memory comparison tricks, offering a template for accelerating other confidence-bound-based optimizers such as AdaLIPO and AdaLIPO+ that share the same O(n² d) scaling.

Real-world applications: The paper explicitly cites the following domains as motivation.

• Robotics, where each evaluation can be a physical or simulated trial.
• Hyperparameter tuning for machine learning models, where each evaluation means a full training run.
• Query optimization for black-box large language models, where each query costs tokens, latency, or money.
• Any setting where evaluations carry substantial computational, temporal, energetic, or monetary cost and gradients are unavailable.

Industry relevance. The core selling point is wall-clock time and memory reduction at equal optimization quality, which directly translates into lower compute bills for expensive tuning loops. The paper releases code at https://github.com/fouratifares/ECP, lowering the barrier to adoption, and the hyperparameters m, δ, and β give practitioners explicit levers to trade conservatism for speed.

Future Directions

• Deriving principled hyperparameter settings in full. The paper states that principled settings are derived and used, but the available content does not report the specific recommended values of m, δ, β, ε_1, τ_{n,d}, and C, nor the sensitivity analysis that would let practitioners choose them without tuning.

• Characterizing the practical cost of the enlargement. Corollary 1 guarantees the ECPv2 region contains the ECP region, but the paper's own analysis notes the enlargement is "controlled" rather than quantified in practice. How much extra exploration the relaxed region induces in realistic high-dimensional problems remains to be measured.

• Extending the acceleration techniques beyond ECP. The Worst-m trick and the projection-based acceptance test are stated to be motivated by a general stochastic maximization idea, raising the question of whether the same combination can be transplanted onto AdaLIPO, AdaLIPO+, or other Lipschitz and Bayesian optimizers with similar per-iteration costs.

• Interaction of projection distortion with stopping behavior. The failure probability 1/β² enters both the distance-preservation guarantee and the final regret bound. The trade-off between choosing a large β (better guarantees, larger d') and practical runtime is a natural open design question, along with how the projection interacts with the geometric growth schedule τ_{n,d} over long horizons.

Target Audience

This paper is most valuable to researchers and graduate students working on derivative-free, black-box, or Lipschitz global optimization, and to theoretically inclined machine learning researchers interested in no-regret analysis and dimensionality reduction for optimization. It also serves practitioners who run expensive hyperparameter tuning, simulation-based optimization, or black-box large language model query optimization at scale, provided they are comfortable reading regret bounds and complexity tables to decide whether to adopt the algorithm. Readers looking for a purely empirical benchmark comparison will need the full paper, since the specific benchmarks and numerical results are not contained in the available content.

Authors’ 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 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.