# Certificate-Guided Pruning for Stochastic Lipschitz Optimization

arXiv: https://arxiv.org/abs/2601.20231 · HTML: https://mlsanity.com/paper/2601.20231/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 43 references that are in the map.
- First posted on arXiv 28 Jan 2026.

## Builds on (most cited first, 14 of 14)

- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [HEBO Pushing The Limits of Sample-Efficient Hyperparameter Optimisation](https://mlsanity.com/paper/2012.03826/) (2020)
- [Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces](https://mlsanity.com/paper/2307.00618/) (2023)
- [Detecting Proxy Gaming in RL and LLM Alignment via Evaluator Stress Tests](https://mlsanity.com/paper/2507.05619/) (2025)
- [Beyond Variance: Knowledge-Aware LLM Compression via Fisher-Aligned Subspace Diagnostics](https://mlsanity.com/paper/2601.07197/) (2026)
- [What Fundamental Structure in Reward Functions Enables Efficient Sparse-Reward Learning?](https://mlsanity.com/paper/2509.03790/) (2025)

## Abstract (arXiv)

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 At of potentially optimal points via confidence-adjusted Lipschitz envelopes. Any point outside At is certifiably suboptimal with high probability, and under a margin condition with near-optimality dimension α, we prove Vol(At) 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 ∈ [2, 100]) show CGP variants match or exceed strong baselines while providing principled stopping criteria via certificate volume.