Certificate-Guided Pruning for Stochastic Lipschitz Optimization

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 **Certificate-Guided Pruning (CGP)**, which maintains an explicit *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 $\alpha$, we prove Vol$(A_t)$ shrinks at a controlled rate yielding sample complexity $Õ(\varepsilon^{-(2+\alpha)})$. 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 the computable gap proxy $\varepsilon_t$.

Scientists and engineers often need to find the best setting for something, like the ideal configuration of a neural network or the best design in a physical simulation. The catch is that each test can be very expensive, costing hours of computing or real money, so every trial has to count. Existing search methods quietly steer away from bad options, but they cannot tell you which options are provably hopeless, how much of the search space is still worth exploring, or when it is finally safe to stop. We built a method called Certificate Guided Pruning (CGP) that keeps an explicit, shrinking list of the settings that could still be the best, and rules out the rest with high confidence. As testing proceeds, this list provably shrinks at a controlled rate, giving a clear, trustworthy signal of progress and a principled point to stop. We also added versions that learn the problem's difficulty as they go, scale up to problems with a hundred adjustable knobs, and borrow smarter techniques when the landscape is smooth. Across twelve benchmark problems, our approach matched or beat strong competitors while saving up to roughly 33 to 59 percent of the testing budget, which means less wasted computation, lower energy use, and more reliable decisions in safety critical settings like robotics.