Empirische Risikominimierung für stochastische konvexe Optimierung: Risikoschranken vom Typ $O(1/n)$ und $O(1/n^2)$

Obwohl es zahlreiche Theorien zur empirischen Risikominimierung (ERM) für überwachtes Lernen gibt, sind die aktuellen theoretischen Erkenntnisse zur ERM für das verwandte Problem der stochastischen konvexen Optimierung (SCO) begrenzt. In dieser Arbeit stärken wir den Bereich der ERM für SCO, indem wir Glättungs- und starke Konvexitätsbedingungen ausnutzen, um die Risikoschranken zu verbessern. Zunächst etablieren wir eine Risikoschranke von $\widetilde{O}(d/n + \sqrt{F_/n})$, wenn die zufällige Funktion nichtnegativ, konvex und glatt ist und die erwartete Funktion Lipschitz-stetig ist. Hierbei bezeichnet $d$ die Dimensionalität des Problems, $n$ die Anzahl der Stichproben und $F_$ das minimale Risiko. Somit erhalten wir bei kleinem $F_*$ eine Risikoschranke von $\widetilde{O}(d/n)$, was analog zur $\widetilde{O}(1/n)$-optimistischen Rate der ERM für überwachtes Lernen ist.Zweitens zeigen wir, dass wenn die Zielfunktion auch $λ$-stark konvex ist, eine Risikoschranke von $\widetilde{O}(d/n + κF_/n)$ gilt, wobei $κ$ die Konditionszahl ist. Wir verbessern diese Schranke auf $O(1/[λn^2] + κF_/n)$, wenn $n=\widetildeΩ(κd)$ gilt. Als Ergebnis erhalten wir unter der Bedingung, dass $n$ groß und $F_*$ klein ist, eine Risikoschranke von $O(κ/n^2)$. Dies ist nach unserem Wissen die erste Risikoschranke vom Typ $O(1/n^2)$ für ERM.Drittens betonen wir, dass obige Ergebnisse in einem einheitlichen Rahmen hergeleitet wurden, der es uns ermöglicht, neue Risikoschranken unter schwächeren Bedingungen abzuleiten. Zum Beispiel können wir darauf verzichten, dass die zufällige Funktion konvex ist oder dass die erwartete Funktion Lipschitz-stetig ist.Schließlich demonstrieren wir, dass um eine Risikoschranke von $O(1/[λn^2] + κF_*/n)$ für überwachtes Lernen zu erreichen, das Anforderungsniveau an $n$ von $\widetildeΩ(κd)$ durch $Ω(κ^2)$ ersetzt werden kann. Dieses Ergebnis ist dimensionsunabhängig.