Technisches Resümee: Skalierbare Batch-Bayessche Optimierung mittels Subraum-Akquisitionsfunktionen

Problemstellung

Die Bayessche Optimierung (BO) ist ein leistungsfähiger Rahmen zur Lösung teurer, Black-Box-Optimierungsprobleme. Während die Standard-BO sequenziell arbeitet und jeweils einen Stichprobenpunkt auswählt, ist dieser Ansatz ineffizient, wenn parallele Rechenressourcen zur Verfügung stehen. Um Parallelität nutzen zu können, sind Batch-Bayessche Optimierungsalgorithmen erforderlich, um mehrere Stichproben gleichzeitig zu evaluieren.

Bestehende Batch-Ansätze stehen jedoch vor erheblichen Skalierungsproblemen, wenn die Batch-Größe ($q$) steigt:

• Multi-Punkt-Expected Improvement (qEI): Obwohl theoretisch fundiert, erhöht die Optimierung von qEI den Suchraum auf eine Dimension von $d \times q$ (wobei $d$ die Problemdimension ist). Wenn $q$ wächst, steigen die Rechenkosten für die Auswertung der multivariaten kumulativen Verteilungsfunktion sowie die Schwierigkeit der Optimierung der Akquisitionsfunktion exponentiell an, was qEI und seine Varianten (z. B. FqEI, qLogEI) für große Batch-Größen (typischerweise $q > 10$) unpraktikabel macht.
• Heuristische Ansätze (z. B. Kriging Believer, Constant Liar, Local Penalization): Diese Methoden verlassen sich oft auf "falsche" Punkte oder künstliche Straffunktionen, um Batch-Effekte zu simulieren. Wenn die Batch-Größe zunimmt, verschlechtert die Akkumulation dieser künstlichen Punkte die Genauigkeit des Gauß-Prozess-Modells (GP), was die Suchrichtung fehlleiten und die Optimierungseffizienz verringern kann.
• Multi-Objective- und Multi-Modell-Ansätze: Methoden, die mehrere Ersatzmodelle trainieren oder Multi-Objective-Optimierungsprobleme lösen, verursachen oft hohe Rechenkosten, die mit großen Batch-Größen nicht gut skalieren.

Die zentrale Herausforderung, die in dieser Arbeit adressiert wird, ist das Design einer Batch-Akquisitionsstrategie, die für großskalige Batch-Evaluierungen rechentechnisch handhabbar bleibt und nicht unter dem Fluch der Dimensionalität oder Modellverschlechterung leidet.

Methodik

Die Autoren schlagen einen neuartigen Ansatz namens Subspace Acquisition Functions vor, der bestehende Akquisitionsfunktionen (speziell Expected Improvement, aber auch adaptierbar auf PI und UCB) erweitert, um innerhalb zufällig ausgewählter, achsenparalleler Subräume zu operieren.

Kernkonzept: Subspace Expected Improvement (SSEI)

Anstatt $q$ Punkte gleichzeitig im vollen $d$-dimensionalen Designraum zu suchen, nutzt die Methode:

1. Auswahl von Subräumen: Es werden zufällig eine Menge achsenparalleler Subräume ausgewählt. Ein $k$-dimensionaler achsenparalleler Subraum wird definiert, indem $k$ Koordinaten aus den ursprünglichen $d$ Dimensionen gewählt werden, während die verbleibenden $d-k$ Koordinaten auf die Werte der aktuellen besten Lösung ($x_{min}$) fixiert werden.
2. Lokale Optimierung: Für jeden ausgewählten Subraum wird die Standard-Akquisitionsfunktion (z. B. EI) nur über die $k$ aktiven Variablen optimiert. Die nicht ausgewählten Variablen bleiben bei $x_{min}$ fixiert.
3. Generierung des Batches: Ein Abfragepunkt wird aus jedem einzigartigen Subraum ausgewählt. Wenn die erforderliche Batch-Größe $q$ die Anzahl der verfügbaren Subräume ($N = 2^d - 1$) übersteigt, verwendet die Methode die Subspace Multi-Point Expected Improvement (SSqEI), welche mehrere Punkte innerhalb eines einzelnen Subraums optimiert.

Computational Framework

Der vorgeschlagene Algorithmus (Algorithmus 1) arbeitet wie folgt:

• Initialisierung: Generiere initiale Stichproben und trainiere ein GP-Modell.
• Subraum-Auswahl: Ziehe zufällig eine ganze Zahl $k \in [1, d]$ und dann eine zufällige Kombination von $k$ Koordinaten, um einen Subraum zu bilden. Dies vermeidet die Rechenkosten der Enumeration aller möglichen Subräume.
• Akquisitions-Optimierung:
  • Wenn $q \le N$: Wähle $q$ distinkte Subräume aus und optimiere die Standard-SSEI in jedem, um einen Punkt pro Subraum zu finden.
  • Wenn $q > N$: Verteile die $q$ Punkte auf die verfügbaren $N$ Subräume (indem mehrere Punkte pro Subraum mittels SSqEI optimiert werden).
• Evaluierung: Evaluiere den resultierenden Batch der $q$ Punkte parallel.
• Update: Aktualisiere das GP-Modell mit den neuen Beobachtungen und wiederhole den Vorgang.

Die Dimensionalität des Optimierungsproblems für die Akquisitionsfunktion wird von $d \times q$ auf etwa $k \times 1$ (oder $k \times q_i$ für SSqEI) reduziert, wobei der erwartete Wert $E[k] \approx d/2$ ist. Dies reduziert die Komplexität der Akquisitions-Optimierung erheblich.

Zentrale Beiträge

1. Skalierbare Batch-Strategie: Das Paper führt eine Methode ein, um die Bayessche Optimierung auf große Batch-Größen zu erweitern, indem es die Batch-Auswahl in unabhängige oder niedrigdimensionale Subraum-Optimierungen entkoppelt und so die exponentielle Komplexität von qEI vermeidet.
2. Einfachheit und Allgemeingültigkeit: Der Ansatz benötigt keine zusätzlichen Hyperparameter und ist auf eine breite Palette von Akquisitionsfunktionen anwendbar (demonstriert für EI, PI und UCB). Er ist konzeptionell einfach: „Subräume ziehen, lokal optimieren, aggregieren.“
3. Robustheit gegenüber Dimensionalität: Durch die Beschränkung der Suche auf achsenparallele Subräume, die an der aktuellen besten Lösung verankert sind, balanciert die Methode natürlich zwischen Exploration (durch zufällige Subraum-Auswahl) und Exploitation (durch lokale Suche um $x_{min}$), was sie besonders effektiv in hochdimensionalen Räumen macht.

Experimentelle Ergebnisse

Die Autoren evaluierten die vorgeschlagene Methode (SSEI) gegen zehn State-of-the-Art Batch-Algorithmen (darunter qEI, qLogEI, FqEI, TuRBO, MSMR, MACE, PEI, EIMI, KB und Random Search) auf 60 synthetischen Benchmark-Problemen (GPMean, SumSquares, Rosenbrock, etc.) über Dimensionen $d \in \{2, 4, 8, 10, 20, 30\}$ und Batch-Größen $q \in \{1, 2, 4, 8, 16, 32, 64, 128\}$.

• Performance vs. Sequenzielle BO: Bei $q=1$ performt SSEI ähnlich wie die Standard-EI bei niedrigdimensionalen Problemen, schneidet jedoch bei hochdimensionalen Problemen ($d \ge 8$) signifikant besser ab. Die Autoren führen dies darauf zurück, dass die sequenzielle EI Schwierigkeiten hat, die Akquisitionsfunktion in hohen Dimensionen zu optimieren, während die lokale Subraum-Suche von SSEI bessere lokale Optima für die Akquisitionsfunktion findet.
• Skalierbarkeit mit Batch-Größe:
  • Kleine bis mittlere Batches ($q \le 32$): SSEI erreicht nahezu eine lineare Beschleunigung in Bezug auf die Wandzeit (Iterationen), während sie gemessen an den Funktionsauswertungen eine vergleichbare oder bessere Performance als andere Batch-Methoden beibehält.
  • Große Batches ($q = 128$): SSEI übertrifft alle verglichenen Batch-Algorithmen deutlich, einschließlich der qEI-Varianten, die bei dieser Skala versagen oder signifikant degradieren. Die vorgeschlagene Methode konvergiert schneller und findet bessere Endlösungen.
• Vergleich mit spezifischen Algorithmen:
  • vs. qEI/qLogEI/FqEI: SSEI ist überlegen, insbesondere wenn $d$ und $q$ steigen, da sie den Fluch der $d \times q$ Dimensionalität vermeidet.
  • vs. TuRBO: SSEI ist wettbewerbsfähig, übertrifft TuRBO oft bei niedrigen bis mittleren Dimensionen und gleicht es bei hohen Dimensionen.
  • vs. Penalty-basierte Methoden (PEI, EIMI, KB): SSEI übertrifft diese Methoden konsistent, die mit wachsender Batch-Größe unter Modellverschlechterung leiden.
• Generalisierbarkeit: Der Subraum-Ansatz wurde erfolgreich auf Probability of Improvement (SSPI) und Upper Confidence Bound (SSUCB) angewendet und zeigte ähnliche Leistungssteigerungen gegenüber ihren Multi-Punkt-Pendants (qPI, qUCB).

Bedeutung und Ansprüche

Das Paper behauptet, dass die vorgeschlagenen Subspace Acquisition Functions eine einfache, effiziente und skalierbare Lösung für die Batch-Bayessche Optimierung bieten. Die primäre Bedeutung liegt in der Ermöglichung der Nutzung von großskaligen parallelen Rechenressourcen (großes $q$) ohne die computationalen Engpässe oder die Genauigkeitsdegradierung, die mit bestehenden Methoden verbunden sind.

Die Autoren betonen:

• Die Methode mildert effektiv den Fluch der Dimensionalität bei der Optimierung der Akquisitionsfunktion ab.
• Sie bietet einen praktischen Trade-off zwischen globaler Exploration (via zufälliger Subraum-Auswahl) und lokaler Exploitation (via Fixierung nicht-ausgewählter Variablen).
• Sie ist eine „Plug-and-Play“-Erweiterung, die auf verschiedene Akquisitionsfunktionen angewendet werden kann und besonders wertvoll für teure Optimierungsprobleme ist, bei denen eine parallele Evaluierung machbar ist.

Die Arbeit kommt zu dem Schluss, dass die Auswahl von Abfragepunkten aus mehreren verschiedenen Subräumen eine vielversprechende Strategie für die großskalige Batch-Bayessche Optimierung ist, die signifikante Verbesserungen der Konvergenzgeschwindigkeit und der Lösungsqualität gegenüber aktuellen State-of-the-Art-Ansätzen bietet.