Online‑Lernalgorithmen für fast‑konvex Funktionen Budgetbeschränkungen

Ein neues arXiv‑Paper präsentiert einen innovativen Ansatz für Online‑Lernen unter langfristigen Budgetbeschränkungen im adversarialen Setting. Bei jedem Schritt wählt der Lernende aus einem konvexen Entscheidungsraum eine Aktion, danach offenbart der Adversär eine Kostenfunktion \(f_t\) und eine Ressourcennutzungsfunktion \(g_t\). Beide Funktionen gehören zur Klasse der \(\alpha\)-approx‑konvexen Funktionen – eine weitreichende Verallgemeinerung der klassischen Konvexität, die zahlreiche bekannte Probleme wie DR‑submodulare Maximierung, Online‑Vertex‑Cover und Regularized Phase Retrieval umfasst.

Das Ziel ist es, einen Online‑Algorithmus zu entwickeln, der die kumulativen Kosten über eine Zeitspanne von Länge \(T\) minimiert und gleichzeitig das langfristige Budget \(B_T\) nahezu einhält. Der Beitrag des Papers ist die Einführung eines effizienten First‑Order‑Online‑Algorithmus, der ein \(O(\sqrt{T})\) \(\alpha\)-Regret gegenüber dem optimalen festen Benchmark garantiert. Gleichzeitig wird der Ressourcenverbrauch auf \(O(B_T \log T)+\tilde{O}(\sqrt{T})\) begrenzt – sowohl im Full‑Information‑ als auch im Bandit‑Feedback‑Modell.

Im Bandit‑Feedback‑Setting liefert die Methode eine effiziente Lösung für das Problem „Adversarial Bandits with Knapsacks“ und verbessert die bisherigen Garantien signifikant. Darüber hinaus werden passende Lower Bounds bewiesen, die die Tightness der Resultate unterstreichen. Abschließend wird die Klasse der \(\alpha\)-approx‑konvexen Funktionen charakterisiert, wodurch die Anwendbarkeit der Ergebnisse auf eine breite Palette von Optimierungsproblemen demonstriert wird.