HyperAIHyperAI

Command Palette

Search for a command to run...

Empirische Risikominimierung für stochastische konvexe Optimierung: Risikoschranken vom Typ O(1/n)O(1/n)O(1/n) und O(1/n2)O(1/n^2)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)\widetilde{O}(d/n + \sqrt{F_/n})O(d/n+F/n), wenn die zufällige Funktion nichtnegativ, konvex und glatt ist und die erwartete Funktion Lipschitz-stetig ist. Hierbei bezeichnet ddd die Dimensionalität des Problems, nnn die Anzahl der Stichproben und F_ das minimale Risiko. Somit erhalten wir bei kleinem FF_*F eine Risikoschranke von O~(d/n)\widetilde{O}(d/n)O(d/n), was analog zur O~(1/n)\widetilde{O}(1/n)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)\widetilde{O}(d/n + κF_/n)O(d/n+κF/n) gilt, wobei κκκ die Konditionszahl ist. Wir verbessern diese Schranke auf O(1/[λn2]+κF/n)O(1/[λn^2] + κF_/n)O(1/[λn2]+κF/n), wenn n=Ω~(κd)n=\widetildeΩ(κd)n=Ω(κd) gilt. Als Ergebnis erhalten wir unter der Bedingung, dass nnn groß und FF_*F klein ist, eine Risikoschranke von O(κ/n2)O(κ/n^2)O(κ/n2). Dies ist nach unserem Wissen die erste Risikoschranke vom Typ O(1/n2)O(1/n^2)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)O(1/[λn^2] + κF_*/n)O(1/[λn2]+κF/n) für überwachtes Lernen zu erreichen, das Anforderungsniveau an nnn von Ω~(κd)\widetildeΩ(κd)Ω(κd) durch Ω(κ2)Ω(κ^2)Ω(κ2) ersetzt werden kann. Dieses Ergebnis ist dimensionsunabhängig.


KI mit KI entwickeln

Von der Idee bis zum Launch – beschleunigen Sie Ihre KI-Entwicklung mit kostenlosem KI-Co-Coding, sofort einsatzbereiter Umgebung und bestem GPU-Preis.

KI-gestütztes kollaboratives Programmieren
Sofort einsatzbereite GPUs
Die besten Preise

HyperAI Newsletters

Abonnieren Sie unsere neuesten Updates
Wir werden die neuesten Updates der Woche in Ihren Posteingang liefern um neun Uhr jeden Montagmorgen
Unterstützt von MailChimp