Certificate-Guided Pruning for Stochastic Lipschitz Optimization
This addresses the need for measurable progress guarantees in stochastic Lipschitz optimization, offering a novel method with extensions for scalability and adaptive learning, though it is incremental in improving upon existing adaptive discretization methods.
The paper tackles the problem of black-box optimization of Lipschitz functions under noisy evaluations by introducing Certificate-Guided Pruning (CGP), which provides explicit certificates of optimality and achieves a sample complexity of \(\tilde{O}(\varepsilon^{-(2+\alpha)})\) under a margin condition.
We study black-box optimization of Lipschitz functions under noisy evaluations. Existing adaptive discretization methods implicitly avoid suboptimal regions but do not provide explicit certificates of optimality or measurable progress guarantees. We introduce \textbf{Certificate-Guided Pruning (CGP)}, which maintains an explicit \emph{active set} $A_t$ of potentially optimal points via confidence-adjusted Lipschitz envelopes. Any point outside $A_t$ is certifiably suboptimal with high probability, and under a margin condition with near-optimality dimension $α$, we prove $\Vol(A_t)$ shrinks at a controlled rate yielding sample complexity $\tildeO(\varepsilon^{-(2+α)})$. We develop three extensions: CGP-Adaptive learns $L$ online with $O(\log T)$ overhead; CGP-TR scales to $d > 50$ via trust regions with local certificates; and CGP-Hybrid switches to GP refinement when local smoothness is detected. Experiments on 12 benchmarks ($d \in [2, 100]$) show CGP variants match or exceed strong baselines while providing principled stopping criteria via certificate volume.