提出可证明最优性的剪枝方法，提升噪声环境下优化效率。
Certificate-Guided Pruning for Stochastic Lipschitz Optimization
- 用置信调整的Lipschitz包络维护潜在最优点集，实现显式最优性证明。
- 在近似最优维度α下，点集体积以ε^(-(2+α))速率收缩，样本复杂度可控。
- 支持高维优化与自适应学习，实验验证优于主流基线并提供停止依据。
我们研究在噪声评估下的Lipschitz函数黑箱优化。现有自适应离散化方法虽隐式避开次优区域，但无法提供最优性证书或可测量的进展保证。本文提出【证书引导剪枝（CGP）】，通过置信调整的Lipschitz包络维持一个显式的潜在最优点集 $A_t$。任何不在 $A_t$ 中的点均以高概率被证为次优。在边际条件下，近似最优维度为 $α$ 时，我们证明 $ ext{Vol}(A_t)$ 以可控速率收缩，样本复杂度为 $ ilde{O}(\varepsilon^{-(2+eta)})$。我们开发了三种扩展：CGP-Adaptive 在 $O( ext{log} hinspace T)$ 开销内在线学习 $L$；CGP-TR 通过信任区域实现 $d > 50$ 的可扩展性，并引入局部证书；CGP-Hybrid 在检测到局部光滑性时切换至高斯过程精修。在12个基准测试（$d \\[2, 100]$）上的实验表明，CGP变体在性能上匹配或超越强基线，同时通过证书体积提供合理终止条件。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。