Słownik AI
Kompletny słownik sztucznej inteligencji
SVRG (Stochastic Variance Reduced Gradient)
Algorithme d'optimisation qui combine des calculs de gradient complets périodiques avec des mises à jour stochastiques pour réduire la variance. SVRG maintient une référence du gradient complet pour corriger les estimations de gradient stochastiques.
SAGA
Méthode de réduction de variance qui utilise une table de gradients historiques pour chaque point de données et effectue des corrections à chaque itération. SAGA combine les avantages de SAG et de SVRG avec une convergence linéaire garantie pour les problèmes convexes.
SAG (Stochastic Average Gradient)
Algorithme d'optimisation qui maintient en mémoire les gradients précédents pour chaque point de données et les met à jour de manière incrémentale. SAG réduit la variance en utilisant la moyenne des gradients historiques comme estimation de référence.
Mini-batch
Sous-ensemble de taille intermédiaire du jeu de données complet utilisé pour calculer des estimations de gradient à chaque itération. Les mini-batches réduisent la variance par rapport au SGD pur tout en étant plus efficaces que les gradients complets.
Control variates
Technique statistique utilisée pour réduire la variance des estimateurs en introduisant une variable de contrôle corrélée. Dans l'optimisation stochastique, les control variates corrigent les estimations de gradient en utilisant une référence de faible variance.
Gradient snapshot
Calcul complet du gradient stocké périodiquement dans les algorithmes de réduction de variance comme SVRG. Le snapshot sert de référence pour corriger les estimations de gradient stochastiques entre les mises à jour complètes.
Linear convergence
Taux de convergence où l'erreur décroît exponentiellement avec le nombre d'itérations pour les problèmes convexes forts. Les méthodes de réduction de variance comme SVRG et SAGA atteignent une convergence linéaire sous certaines conditions.
Gradient variance
Mesure de la variabilité des estimations de gradient stochastiques due à l'échantillonnage aléatoire des données. La réduction de cette variance est l'objectif principal des techniques SVRG et SAGA pour améliorer la convergence.
Memory complexity
Espace mémoire requis par l'algorithme pour stocker les informations nécessaires aux calculs. SAG et SAGA nécessitent O(n) mémoire pour stocker les gradients historiques, tandis que SVRG ne nécessite que O(1) mémoire supplémentaire.
Strong convexity
Propriété d'une fonction où sa courbure est bornée inférieurement par une constante positive. La convexité forte est une condition clé garantissant la convergence linéaire des méthodes de réduction de variance.
Proximal operator
Opération mathématique généralisant la projection sur un ensemble convexe pour inclure des termes de régularisation. Les méthodes de réduction de variance peuvent être combinées avec des opérateurs proximaux pour traiter des problèmes non-différentiables.
Stochastic gradient estimator
Estimateur non-biaisé du gradient vrai calculé sur un sous-ensemble aléatoire des données. Les techniques de réduction de variance modifient cet estimateur pour réduire sa variance tout en conservant son biais nul.
Variance bound
Limite supérieure théorique sur la variance des estimations de gradient garantie par les algorithmes de réduction de variance. Cette borne est souvent liée au conditionnement du problème et à la distance à l'optimum.
SARAH (StochAstic Recursive gAdient algoritHm)
Algorithme de réduction de variance utilisant une approche récursive pour mettre à jour l'estimateur de gradient à chaque itération. SARAH combine des idées de SVRG et de méthodes de gradient accéléré avec une convergence garantie.