Optimisation stochastique

L'optimisation stochastique minimise une fonction objectif en utilisant des estimations bruitées de son gradient ou de sa valeur, mettant à jour les paramètres à partir de sous-ensembles aléatoires de données ou de perturbations aléatoires plutôt qu'à partir de la fonction objectif complète et exacte.

Definition

L'optimisation stochastique est une famille de méthodes itératives qui mettent à jour les estimations des paramètres en utilisant des estimations aléatoires et non biaisées d'une fonction objectif ou de son gradient, permettant l'optimisation lorsque la fonction objectif complète est trop coûteuse à évaluer ou n'est observée qu'avec du bruit.

Scope

Ce sujet aborde l'approximation stochastique dans la tradition de Robbins-Monro, la descente de gradient stochastique et ses variantes par mini-lots (mini-batch) et avec momentum, les schémas de taille de pas (taux d'apprentissage) qui contrôlent la convergence, le compromis entre le bruit et le coût computationnel, et les garanties de convergence. Son rôle dans l'ajustement de modèles statistiques et d'apprentissage automatique à grande échelle est souligné.

Core questions

• Comment des estimations de gradient bruitées peuvent-elles mener à la convergence vers un optimum ?
• Quels schémas de taille de pas garantissent la convergence dans le cadre de Robbins-Monro ?
• Comment l'utilisation de mini-lots (mini-batching) arbitre-t-elle entre le bruit et le coût computationnel par étape ?
• Pourquoi l'optimisation stochastique est-elle essentielle pour les très grands ensembles de données ?

Key concepts

• Approximation stochastique
• Gradient par mini-lot
• Schéma de taux d'apprentissage
• Estimation de gradient non biaisée
• Décroissance de la taille de pas
• Convergence presque sûre

Key theories

Approximation stochastique

Le schéma de Robbins-Monro trouve la racine d'une fonction inconnue à partir de mesures bruitées en effectuant de petits pas dont les tailles diminuent à un rythme prescrit, convergeant presque sûrement sous certaines conditions sur la séquence des tailles de pas.

Méthodes de gradient stochastique

Le remplacement du gradient complet par une estimation non biaisée issue d'un sous-ensemble de données aléatoire produit des mises à jour peu coûteuses dont la trajectoire moyenne descend la fonction objectif, avec des schémas de taux d'apprentissage équilibrant la vitesse de convergence et la variance du bruit.

Clinical relevance

Les méthodes de gradient stochastique permettent d'ajuster des modèles à des ensembles de données trop volumineux pour être traités en une seule fois, et elles constituent la stratégie d'optimisation dominante pour l'entraînement des réseaux neuronaux et la régression à grande échelle, où le calcul du gradient complet à chaque étape serait prohibitif.

History

Robbins et Monro ont introduit l'approximation stochastique en 1951 pour trouver des racines à partir d'observations bruitées, et Kiefer et Wolfowitz l'ont adaptée à l'optimisation peu après ; l'explosion de l'apprentissage automatique à grande échelle a ravivé ces idées sous la forme de la descente de gradient stochastique et de ses nombreuses variantes modernes.

Key figures

• Herbert Robbins
• Sutton Monro
• Harold Kushner
• Jack Kiefer

Seminal works

• robbins1951
• kushner2003

Frequently asked questions

Pourquoi utiliser des gradients bruités plutôt que le gradient exact ?

Le calcul du gradient exact sur des millions de points de données est coûteux. Un gradient estimé à partir d'un petit lot aléatoire est beaucoup moins cher et, bien que bruité, il pointe toujours vers le bas en moyenne, de sorte que de nombreuses étapes bruitées et peu coûteuses peuvent être plus efficaces que quelques étapes exactes.

Pourquoi la taille de pas diminue-t-elle généralement avec le temps ?

La diminution de la taille de pas amortit le bruit du gradient à mesure que les itérations approchent de l'optimum, ce qui est requis par les conditions de Robbins-Monro pour la convergence. Une taille de pas qui reste trop grande fait osciller l'estimation autour de la solution.