Laboratoire de Mathématiques Raphaël Salem

UMR 6085 CNRS - Université de Rouen Normandie

L'optimisation de fonctions convexes lisses dans un cadre stochastique, où seules des estimations bruitées des gradients et des Hessiennes sont disponibles, est un problème classique en statistique computationnelle. Si les méthodes de premier ordre possèdent un faible coût par itération, leur convergence peut s'avérer lente pour les problèmes mal conditionnés. Les méthodes de Newton stochastiques exploitent l'information du second ordre pour corriger la courbure locale, mais le coût par itération en $\mathcal{O}(d^3)$ pour inverser la Hessienne (où $d$ est la dimension du problème) est élevé en grande dimension. Ce travail présente un algorithme de Newton stochastique en ligne par mini-lots, nommé mSNA (masked Stochastic Newton Algorithm). Cette méthode emploie une stratégie de masquage aléatoire sélectionnant un sous-ensemble de colonnes de la Hessienne à chaque itération, ce qui réduit le coût de calcul par étape. Cette approche permet à l'algorithme d'atteindre un coût de calcul total pour une passe unique sur $N$ points de données de $\mathcal{O}(Nd)$, un ordre de grandeur comparable aux méthodes de premier ordre tout en conservant les propriétés de convergence du second ordre. Nous établissons la convergence presque sûre et l'efficacité asymptotique de l'estimateur résultant sans recourir au moyennage des itérés, améliorant ainsi les résultats théoriques des travaux précédents.