Dual‑Guided Loss: Skalierbares Lernen für Entscheidungsoptimierung

In vielen praktischen Situationen werden Entscheidungen unter Unsicherheit getroffen, indem Vorhersagen in Optimierungsprobleme eingespeist werden. Das „Predict‑then‑Optimize“-Paradigma hat die Entwicklung von decision‑focused learning (DFL) vorangetrieben, bei dem Modelle so trainiert werden, dass sie die Art und Weise berücksichtigen, wie der Optimierer die Vorhersagen nutzt. Trotz des vielversprechenden Ansatzes ist die Skalierbarkeit ein Problem: aktuelle Methoden verlangen häufige und kostenintensive Aufrufe eines Optimierers, oft eines kombinatorischen, oder setzen auf aufgaben­spezifische Surrogates.

Die vorgestellte Arbeit nutzt Dualvariablen aus dem nachgelagerten Optimierungsproblem, um das Lernen zu steuern, und führt die Dual‑Guided Loss (DGL) ein. DGL ist ein einfaches, skalierbares Ziel, das die Entscheidungsausrichtung bewahrt, aber die Abhängigkeit vom Solver deutlich reduziert. Der Ansatz ist speziell für kombinatorische Auswahlprobleme mit One‑of‑Many‑Beschränkungen wie Matching, Knapsack und kürzeste Pfade konzipiert.

Der Kern des Vorgehens besteht darin, die Optimierung von den Gradientenupdates zu entkoppeln: Das Optimierungsproblem wird nur periodisch gelöst; zwischen den Aufrufen werden auf dual‑angepasste Ziele mit einfachen differenzierbaren Surrogatverlusten trainiert. Wenn die Aktualisierungen seltener werden, nähert sich die Trainingskosten dem Standard‑Supervised‑Learning, während die starke Entscheidungsausrichtung erhalten bleibt.

Die Autoren zeigen theoretisch, dass DGL asymptotisch abnehmende Entscheidungsregret liefert, analysieren die Laufzeitkomplexität und demonstrieren in zwei Problemklassen, dass DGL den aktuellen DFL‑Standards gleichkommt oder ihn übertrifft – und das bei deutlich weniger Solver‑Aufrufen und wesentlich kürzerer Trainingszeit.