Command Palette
Search for a command to run...
Minimisation du Risque Empirique pour l'Optimisation Convexe Stochastique : Bornes de Risque de Type O(1/n) et O(1/n2)
Minimisation du Risque Empirique pour l'Optimisation Convexe Stochastique : Bornes de Risque de Type O(1/n) et O(1/n2)
Lijun Zhang; Tianbao Yang; Rong Jin
Résumé
Bien que de nombreuses théories d'optimisation du risque empirique (ERM) pour l'apprentissage supervisé existent, les compréhensions théoriques actuelles de l'ERM pour un problème connexe — l'optimisation convexe stochastique (SCO) — sont limitées. Dans ce travail, nous renforçons le domaine de l'ERM pour la SCO en exploitant les conditions de régularité et de forte convexité afin d'améliorer les bornes de risque. Premièrement, nous établissons une borne de risque O(d/n+F/n) lorsque la fonction aléatoire est non négative, convexe et régulière, et que la fonction attendue est lipschitzienne continue, où d est la dimensionnalité du problème, n est le nombre d'échantillons, et F_ est le risque minimal. Ainsi, lorsque F_ est petit, nous obtenons une borne de risque O(d/n), analogue au taux optimiste O(1/n) de l'ERM pour l'apprentissage supervisé. Deuxièmement, si la fonction objectif est également λ-fortement convexe, nous prouvons une borne de risque O(d/n+κF/n) où κ est le nombre de conditionnement, et nous améliorons cette borne à O(1/[λn2]+κF/n) lorsque n=Ω(κd). Par conséquent, sous la condition que n soit grand et que F_ soit petit, nous obtenons une borne de risque O(κ/n2), qui constitue selon nos connaissances la première borne de risque de type O(1/n2) pour l'ERM. Troisièmement, nous soulignons que ces résultats sont établis dans un cadre unifié, permettant ainsi de déduire de nouvelles bornes de risque sous des conditions plus faibles, par exemple sans nécessiter la convexité de la fonction aléatoire ni la continuité lipschitzienne de la fonction attendue. Enfin, nous montrons qu'en vue d'obtenir une borne de risque O(1/[λn2]+κF∗/n) pour l'apprentissage supervisé, la condition Ω(κd) sur n peut être remplacée par Ω(κ2), ce qui est indépendant de la dimensionnalité.