Minimisation du Risque Empirique pour l'Optimisation Convexe Stochastique : Bornes de Risque de Type $O(1/n)$ et $O(1/n^2)$

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 $\widetilde{O}(d/n + \sqrt{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 $\widetilde{O}(d/n)$, analogue au taux optimiste $\widetilde{O}(1/n)$ de l'ERM pour l'apprentissage supervisé. Deuxièmement, si la fonction objectif est également $\lambda$-fortement convexe, nous prouvons une borne de risque $\widetilde{O}(d/n + κF_/n)$ où $κ$ est le nombre de conditionnement, et nous améliorons cette borne à $O(1/[λn^2] + κF_/n)$ lorsque $n=\widetildeΩ(κd)$. Par conséquent, sous la condition que $n$ soit grand et que $F_$ soit petit, nous obtenons une borne de risque $O(κ/n^2)$, qui constitue selon nos connaissances la première borne de risque de type $O(1/n^2)$ 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/[λn^2] + κF_*/n)$ pour l'apprentissage supervisé, la condition $\widetildeΩ(κd)$ sur $n$ peut être remplacée par $Ω(κ^2)$, ce qui est indépendant de la dimensionnalité.