Neues Verfahren: Zertifikatsgesteuerte Pruning-Strategie für Lipschitz-Optimierung

In einer kürzlich veröffentlichten Studie auf arXiv wird ein innovatives Verfahren zur Black‑Box‑Optimierung von Lipschitz‑Funktionen unter verrauschten Messungen vorgestellt. Das neue Konzept, genannt Certificate‑Guided Pruning (CGP), bietet im Gegensatz zu bisherigen adaptiven Diskretisierungsmethoden nicht nur eine implizite Vermeidung suboptimaler Regionen, sondern liefert explizite Zertifikate der Optimalität und messbare Fortschrittsgarantien.

CGP hält eine aktive Menge At potenziell optimaler Punkte aufrecht, die durch mit Unsicherheit korrigierte Lipschitz‑Umhüllungen bestimmt wird. Jeder Punkt außerhalb dieser Menge ist mit hoher Wahrscheinlichkeit eindeutig suboptimal. Unter einer Margin‑Bedingung und einer nahe‑optimalen Dimension α lässt sich zeigen, dass das Volumen von At mit einer kontrollierten Rate schrumpft, was zu einer Stichprobenkomplexität von etwa Õ(ε-(2+α)) führt.

Die Autoren erweitern CGP um drei Varianten: CGP‑Adaptive erlernt die Lipschitz‑Konstante L online mit nur O(log T) Overhead; CGP‑TR skaliert das Verfahren auf Dimensionen über 50 durch Trust‑Regions und lokale Zertifikate; CGP‑Hybrid wechselt zu einer GP‑Verfeinerung, sobald lokales Glattheitsverhalten erkannt wird. In Experimenten an 12 Benchmarks mit Dimensionen zwischen 2 und 100 übertrifft oder erreicht jede CGP‑Variante starke Baselines und bietet gleichzeitig ein prinzipielles Stoppkriterium über die Zertifikatsvolumen.