Command Palette
Search for a command to run...
Empirische Risikominimierung für stochastische konvexe Optimierung: Risikoschranken vom Typ O(1/n) und O(1/n2)
Empirische Risikominimierung für stochastische konvexe Optimierung: Risikoschranken vom Typ O(1/n) und O(1/n2)
Lijun Zhang; Tianbao Yang; Rong Jin
Zusammenfassung
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 O(d/n+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 O(d/n), was analog zur 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 O(d/n+κF/n) gilt, wobei κ die Konditionszahl ist. Wir verbessern diese Schranke auf O(1/[λn2]+κF/n), wenn n=Ω(κd) gilt. Als Ergebnis erhalten wir unter der Bedingung, dass n groß und F∗ klein ist, eine Risikoschranke von O(κ/n2). Dies ist nach unserem Wissen die erste Risikoschranke vom Typ O(1/n2) 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/[λn2]+κF∗/n) für überwachtes Lernen zu erreichen, das Anforderungsniveau an n von Ω(κd) durch Ω(κ2) ersetzt werden kann. Dieses Ergebnis ist dimensionsunabhängig.