Partage de technologie

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Résumé

L'optimisation stochastique est un composant essentiel de l'apprentissage automatique et se trouve à la base de l'algorithme de descente de gradient stochastique (SGD), une méthode largement utilisée depuis sa première proposition il y a plus de 60 ans. Au cours des huit dernières années, nous avons assisté à un nouveau développement passionnant : les techniques de réduction de la variance pour les méthodes d’optimisation stochastique. Ces méthodes de réduction de la variance (méthodes VR) fonctionnent bien dans des scénarios qui permettent plusieurs itérations des données d'entraînement, montrant une convergence plus rapide que SGD, à la fois en théorie et en pratique. Cette augmentation de la vitesse met en évidence l’intérêt croissant pour les méthodes VR et l’accumulation rapide des résultats de recherche dans ce domaine. Cet article passe en revue les principes clés et les avancées majeures des méthodes VR pour l’optimisation d’ensembles de données limités, dans le but d’informer les lecteurs non experts. Nous nous concentrons principalement sur les environnements d'optimisation convexes et fournissons une référence aux lecteurs intéressés par les extensions à la minimisation des fonctions non convexes.

Mots clés Apprentissage automatique ; optimisation ;

1. Introduction

Dans le domaine de la recherche sur l’apprentissage automatique, une question fondamentale et importante est de savoir comment adapter le modèle à un vaste ensemble de données. Par exemple, on peut considérer le cas typique d’un modèle des moindres carrés linéaires :

$$X^{\ast }\in \arg \underset{X\in {\mathbb{R}}^d}{\min }\frac{1}{n}\sum _{je=1}^n({un}_{je}^{T}X-b_{je}{)}^2$$

Dans ce modèle nous avons $d$ paramètres, qui sont représentés par des vecteurs$X\in {\mathbb{R}}^d$ donné.En attendant, nous avons sous la main$n$ points de données, y compris les vecteurs de caractéristiques${un}_{je}\in {\mathbb{R}}^d$ et valeur cible$b_{je}\in \mathbb{R}$ .Le processus d'adaptation du modèle consiste à ajuster ces paramètres afin que la sortie prévue du modèle${un}_{je}^{T}X$ en moyenne aussi proche que possible de la valeur cible$b_{je}$。

Plus largement, nous pourrions utiliser une fonction de perte $F_{je}(X)$ Pour mesurer les prédictions du modèle et les$je$ À quel point les points de données sont proches :

$$X^{\ast }\in \arg \underset{X\in {\mathbb{R}}^d}{\min }F(X):=\frac{1}{n}\sum _{je=1}^n{F}_{je}(X)$$

fonction de perte $F_{je}(X)$ S'il est plus grand, cela indique que les prédictions du modèle s'écartent considérablement des données ;$F_{je}(X)$ Égal à zéro, le modèle s’adapte parfaitement aux points de données.fonction$F(X)$ Reflète la perte moyenne du modèle sur l'ensemble des données.

Les problèmes comme la forme (2) ci-dessus s'appliquent non seulement aux problèmes des moindres carrés linéaires, mais également à de nombreux autres modèles étudiés en apprentissage automatique. Par exemple, dans un modèle de régression logistique, nous résolvons :

$$X^{\ast }\in \arg \underset{X\in {\mathbb{R}}^d}{\min }\frac{1}{n}\sum _{je=1}^n\log (1+{ettttt}^{-b_{je}{un}_{je}^{T}X})+\frac{\lambda }{2}\Vert X{\Vert }_2^2$$

Ici, nous avons affaire à bi ∈ { − 1 , + 1 } b_i dans {-1, +1}bje​∈{−1,+1} Pour un problème de classification binaire, la prédiction est basée sur${un}_{je}^{T}X$ symboles.Un terme de régularisation est également introduit dans la formule$\frac{\lambda }{2}\Vert X{\Vert }_2^2$ pour éviter de surajuster les données, où$\Vert X{\Vert }_2^2$ exprimer$X$ Le carré de la norme euclidienne de .

Dans la plupart des modèles d'apprentissage supervisé, le processus de formation peut être exprimé sous la forme (2), comprenant les moindres carrés régularisés L1, la machine à vecteurs de support (SVM), l'analyse en composantes principales, les champs aléatoires conditionnels et les réseaux de neurones profonds, etc.

Un défi clé dans les instances de problèmes modernes est le nombre de points de données $n$ Probablement extrêmement grand. Nous traitons souvent d’ensembles de données qui dépassent largement la limite du téraoctet et peuvent provenir de sources aussi diverses qu’Internet, les satellites, les capteurs à distance, les marchés financiers et les expériences scientifiques. Pour traiter des ensembles de données aussi volumineux, une approche courante consiste à utiliser l’algorithme de descente de gradient stochastique (SGD), qui utilise uniquement un petit nombre de points de données sélectionnés au hasard à chaque itération. En outre, il y a eu récemment une forte augmentation de l'intérêt pour les méthodes de gradient stochastique de réduction de la variance (VR), qui ont des taux de convergence plus rapides que les méthodes de gradient stochastique traditionnelles.

Figure 1. Sur le problème de régression logistique basé sur l'ensemble de données champignon [7], la descente de gradient (GD), la descente de gradient accélérée (AGD, GD accélérée dans [50]), la descente de gradient stochastique (SGD) et la méthode ADAM [30] ont été par rapport aux méthodes de réduction de la variance (VR) SAG et SVRG, où n = 8 124, d = 112.

1.1. Méthodes de descente de gradient et de gradient stochastique

La descente de gradient (GD) est un algorithme classique utilisé pour résoudre le problème ci-dessus (2), et sa formule de mise à jour itérative est la suivante :
$$X_{k+1}=X_k-\gamma \frac{1}{n}\sum _{je=1}^n\nabla F_{je}(X_k)$$

ici,$\gamma$ est une valeur de pas fixe supérieure à zéro.Lors de chaque itération de l'algorithme GD, chaque point de données doit être$je$ Calculer le dégradé$\nabla F_{je}(X_k)$, ce qui signifie que GD nécessite tous $n$ effectuer un parcours complet des points de données.Lorsque la taille de l'ensemble de données$n$ Lorsqu’il devient très important, le coût de chaque itération de l’algorithme GD devient très élevé, limitant ainsi son application.

Comme alternative, nous pouvons considérer la méthode de descente de gradient stochastique (SGD), qui a été proposée pour la première fois par Robbins et Monro, et sa formule de mise à jour itérative est la suivante :
$$X_{k+1}=X_k-\gamma \nabla F_{{je}_k}(X_k)$$

L'algorithme SGD fonctionne en utilisant uniquement le gradient d'un point de données sélectionné au hasard à chaque itération. $\nabla F_{{je}_k}(X_k)$ pour réduire le coût de chaque itération. Dans la figure 1, nous pouvons voir que SGD réalise des progrès plus significatifs que GD (y compris les méthodes GD accélérées) dans les premières étapes du processus d'optimisation.Le graphique montre la progression de l'optimisation en termes d'époques, qui sont définies comme le calcul de tous$n$ Le nombre de gradients pour les échantillons d’entraînement. L'algorithme GD effectue une itération à chaque tour, tandis que l'algorithme SGD effectue une itération à chaque tour.$n$ itérations.Nous utilisons les tours comme base pour comparer SGD et GD, car sous l'hypothèse$n$ Dans les très grands cas, le coût principal des deux méthodes est concentré dans le gradient$\nabla F_{je}(X_k)$ calcul.

1.2. Problème d'écart

Considérons l'indexation aléatoire ${je}_k$ de la collecte { 1 , … , n } {1, points, n}{1,…,n} Dans le cas d'une sélection aléatoire uniforme, cela signifie que pour tous$je$,choisir ${je}_k=je$ La probabilite$P[{je}_k=je]$ égal$\frac{1}{n}$ . dans ce cas,$\nabla F_{{je}_k}(X_k)$ comme$\nabla F(X_k)$ L’estimateur de est sans biais car, par la définition de l’espérance, nous avons :
$$E[\nabla F_{{je}_k}(X_k)|X_k]=\frac{1}{n}\sum _{je=1}^n\nabla F_{je}(X_k)=\nabla F(X_k)(6)$$

Bien que la méthode SGD (Stochastic Gradient Descent) ne garantisse pas le fonctionnement à chaque itération $F$ La valeur de diminuera, mais en moyenne elle se déplacera vers le gradient complet négatif, qui représente la direction vers le bas.

Cependant, disposer d’un estimateur de gradient sans biais n’est pas suffisant pour garantir la convergence des itérations SGD. Pour illustrer ce point, la figure 2 (à gauche) montre la trajectoire itérative de SGD lors de l'application d'une fonction de régression logistique utilisant un pas constant sur l'ensemble de données à quatre catégories fourni par LIBSVM [7].Les ellipses concentriques sur la figure représentent les contours de la fonction, c'est-à-dire la valeur de la fonction$F(X)=c$ point correspondant$X$ rassembler,$c$ est une constante spécifique dans l'ensemble des nombres réels.différentes valeurs constantes$c$ Correspond à différentes ellipses.

La trajectoire itérative de SGD ne converge pas vers la solution optimale (indiquée par un astérisque vert sur la figure), mais forme un nuage de points autour de la solution optimale. En revanche, nous montrons sur la figure 2 la trajectoire itérative d'une méthode de réduction de la variance (VR), gradient moyen stochastique (SAG), utilisant la même taille de pas constante, que nous introduirons plus tard. La raison pour laquelle SGD ne parvient pas à converger dans cet exemple est que le gradient stochastique lui-même ne converge pas vers zéro et que, par conséquent, la méthode SGD à pas constant (5) ne s'arrête jamais.Cela contraste fortement avec les méthodes de descente de gradient (GD), qui s'arrêtent naturellement dès que$X_k$ Approches$X^{\ast }$,pente $\nabla F(X_k)$ tendra vers zéro.

Figure 2. Graphiques d'ensemble de niveaux pour la régression logistique bidimensionnelle utilisant les méthodes itératives SGD (à gauche) et SAG (à droite) à pas fixe. L'astérisque vert indique xdélier.

1.3. Méthode classique de réduction de la variance

traitement en raison de $\nabla F_{je}(X_k)$ Il existe plusieurs techniques classiques pour résoudre les problèmes de non-convergence causés par la variance des valeurs.Par exemple, Robbins et Monro [64] utilisent une série de pas décroissants${\gamma }_k$ pour résoudre le problème de variance, en garantissant que le produit${\gamma }_k\nabla F_{{je}_k}(X_k)$ peut converger vers zéro. Cependant, ajuster cette séquence d’étapes décroissantes pour éviter d’arrêter l’algorithme trop tôt ou trop tard est un problème difficile.

Une autre technique classique pour réduire la variance consiste à utiliser plusieurs $\nabla F_{je}(X_k)$ moyenne de pour obtenir le dégradé complet$\nabla F(X)$ une estimation plus précise. Cette approche est appelée minibatch et est particulièrement utile lorsque plusieurs gradients peuvent être évalués en parallèle. Cela donne une itération de la forme :
$$X_{k+1}=X_k-\gamma \frac{1}{|B_k|}\sum _{je\in B_k}\nabla F_{je}(X_k)(7)$$
dans$B_k$ est un ensemble d'index aléatoires,$|B_k|$ exprimer$B_k$ la taille de.si$B_k$ En échantillonnant uniformément avec remplacement, alors la variance de cette estimation de gradient est liée à la "taille du lot"$|B_k|$ est inversement proportionnel, la variance peut donc être réduite en augmentant la taille du lot.

Cependant, le coût de telles itérations est proportionnel à la taille du lot, donc cette forme de réduction de la variance se fait au prix d’un coût de calcul accru.

Une autre stratégie courante pour réduire la variance et améliorer les performances empiriques de SGD consiste à ajouter « élan », un terme supplémentaire basé sur la direction utilisée dans les étapes précédentes. En particulier, la forme du SGD avec élan est la suivante :
$$X_{k+1}=X_k-\gamma m_k(9)$$
où le paramètre d'impulsion$\beta$ Situé dans la plage (0, 1).Si l'élan initial$m_0=0$, et développez en (8) $m_k$ Pour les mises à jour, nous obtenons$m_k$ est la moyenne pondérée des gradients précédents :
$$m_k=\sum _{t=0}^k{\beta }^{k-t}\nabla F_{{je}_t}(X_t)(10)$$
donc,$m_k$ est la somme pondérée des gradients stochastiques.parce que${\sum }_{t=0}^k{\beta }^{k-t}=\frac{1-{\beta }^{k+1}}{1-\beta }$, nous pouvons convertir $\frac{1-\beta }{1-{\beta }^k}{m}_k$ Considéré comme une moyenne pondérée de gradients stochastiques.Si nous comparons cela avec l'expression du dégradé complet$\nabla F(X_k)=\frac{1}{n}{\sum }_{je=1}^n\nabla F_{je}(X_k)$ Pour comparer, nous pouvons$\frac{1-\beta }{1-{\beta }^k}{m}_k$(ainsi que $m_k$ ) est interprété comme une estimation du gradient complet. Même si cette somme pondérée réduit la variance, elle soulève également des questions clés.Puisque la somme pondérée (10) donne plus de poids aux gradients récemment échantillonnés, elle ne convergera pas vers le gradient complet.$\nabla F(X_k)$ , cette dernière est une moyenne simple. La première méthode de réduction de la variance que nous verrons dans la section II-A résout ce problème en utilisant une moyenne simple au lieu de toute moyenne pondérée.

1.4. Méthodes modernes de réduction de la variance

Contrairement aux méthodes classiques, elles utilisent directement un ou plusieurs $\nabla F_{je}(X_k)$ comme$\nabla F(X_k)$ À titre d'approximation, les méthodes modernes de réduction de la variance (VR) emploient une stratégie différente.Ces méthodes utilisent$\nabla F_{je}(X_k)$ pour mettre à jour l'estimation du gradient$g_k$, dont le but est de faire $g_k$ approchant$\nabla F(X_k)$ .Plus précisément, nous espérons$g_k$ capable de satisfaire$g_k\approx \nabla F(X_k)$ . Sur la base de ces estimations de gradient, nous effectuons ensuite une étape de gradient approximative de la forme :
$$X_{k+1}=X_k-\gamma g_k(11)$$
ici$\gamma >0$ est le paramètre de taille de pas.

Pour garantir qu'une taille de pas constante est utilisée $\gamma$ Lorsque l'itération (11) peut converger, nous devons nous assurer que l'estimation du gradient$g_k$ La variance tend vers zéro. Mathématiquement, cela peut s'exprimer comme suit :
$$E\left[\Vert g_k-\nabla F(X_k){\Vert }^2\right]\to 0\text{comme}k\to \infty (12)$$
attentes ici$E$ est basé sur l'algorithme jusqu'au$k$ Toutes les variables aléatoires sont calculées pour les itérations. La propriété (12) garantit que la méthode VR peut être arrêtée lorsque la solution optimale est atteinte. Nous considérons cette propriété comme une caractéristique distinctive de l’approche VR et c’est pourquoi nous l’appelons une propriété VR. Il est à noter que l’expression variance « réduite » peut être trompeuse, car en fait la variance tend vers zéro. La propriété (12) est un facteur clé qui permet aux méthodes VR d'atteindre une convergence plus rapide en théorie (sous des hypothèses appropriées) et en pratique (comme le montre la figure 1).

1.5. Premier exemple de méthode de réduction de variance : SGD²

Une méthode d'amélioration simple peut permettre à la formule récursive SGD (5) d'atteindre une convergence sans réduire la taille du pas, c'est-à-dire traduire chaque gradient. La méthode spécifique consiste à soustraire. $\nabla F_{je}(X^{\ast })$, cette méthode est définie comme suit :
$$X_{k+1}=X_k-\gamma (\nabla F_{{je}_k}(X_k)-\nabla F_{{je}_k}(X^{\ast }))(13)$$
Cette méthode est appelée SGD² [22].Même si nous ne pouvons généralement pas savoir avec certitude chaque$\nabla F_{je}(X^{\ast })$ , mais SGD², à titre d'exemple, peut bien illustrer les caractéristiques de base de la méthode de réduction de la variance.De plus, de nombreuses méthodes de réduction de la variance peuvent être considérées comme une forme approximative de la méthode SGD² ; ces méthodes ne s'appuient pas sur les méthodes connues ;$\nabla F_{je}(X^{\ast })$, mais utilisez plutôt une méthode qui peut se rapprocher $\nabla F_{je}(X^{\ast })$ valeur estimée.

Il convient de noter que SGD² utilise une estimation impartiale du gradient complet.parce que$\nabla F(X^{\ast })=0$,F:
$$E[\nabla F_{{je}_k}(X_k)-\nabla F_{{je}_k}(X^{\ast })]=\nabla F(X_k)-\nabla F(X^{\ast })=\nabla F(X_k)$$
De plus, lorsque SGD² atteint la solution optimale, il s'arrêtera naturellement car pour tout$je$,avoir:
$$(\nabla F_{je}(X)-\nabla F_{je}(X^{\ast })){|}_{X=X^{\ast }}=0$$

Après une observation plus approfondie, avec $X_k$ près$X^{\ast }$(pour les consécutifs $\nabla F_{je}$), SGD² satisfait la propriété de réduction de variance (12) car :
$$\begin{gathered} E\left[\Vert g_k-\nabla F(X_k){\Vert }^2\right]= \\ E\left[\Vert \nabla F_{{je}_k}(X_k)-\nabla F_{{je}_k}(X^{\ast })-\nabla F(X_k){\Vert }^2\right]\le E\left[\Vert \nabla F_{{je}_k}(X_k)-\nabla F_{{je}_k}(X^{\ast }){\Vert }^2\right] \end{gathered}$$
Ici nous utilisons le lemme 2, soit$X=\nabla F_{{je}_k}(X_k)-\nabla F_{{je}_k}(X^{\ast })$, et a profité de $E[\nabla F_{{je}_k}(X_k)-\nabla F_{{je}_k}(X^{\ast })]=\nabla F(X_k)$ nature. Cette propriété indique que SGD² a une vitesse de convergence plus rapide que les méthodes SGD traditionnelles, que nous avons détaillées dans l'annexe B.

1.6. Convergence rapide de la méthode de réduction de la variance

Dans cette section, nous présenterons deux hypothèses standard utilisées pour analyser la méthode de réduction de la variance (VR) et discuterons de l'effet d'accélération qui peut être obtenu sous ces hypothèses par rapport à la méthode SGD traditionnelle. Premièrement, nous supposons que le gradient a une continuité Lipschitzienne, ce qui signifie que le taux de changement du gradient est fini.

Hypothèse 1 (continuité Lipschitzienne)

Nous supposons que la fonction $F$est différentiable et est $L$- lisse, pour tous $X$ et$et$ et quelqu'un$0<L<\infty$,Les conditions suivantes :
$$\Vert \nabla F(X)-\nabla F(et)\Vert \le L\Vert X-et\Vert (14)$$
Cela signifie que chaque$Fje:{\mathbb{R}}^d\to \mathbb{R}$ est différentiable,$L_{je}$- lisse, nous définissons $L_{\text{max}}$ pour max ⁡ { L 1 , . . . , L n } max{L_1, . . . , L_n}max{L1​,...,Ln​}。

Bien que cela soit généralement considéré comme une hypothèse faible, dans les chapitres suivants, nous discuterons des méthodes VR adaptées aux problèmes non fluides. Pour une fonction univariée deux fois différentiable,$L$-La douceur peut être intuitivement comprise comme : cela équivaut à supposer que la dérivée seconde est $L$ limite supérieure, c'est-à-dire$|F^{\prime \prime }(X)|\le L$ pour tous$X\in {\mathbb{R}}^d$ .Pour les fonctions deux fois différentiables de plusieurs variables, cela équivaut à supposer une matrice hessienne${\nabla }^{2}F(X)$ La valeur singulière de$L$ limite supérieure.

Hypothèse 2 (forte convexité)

La deuxième hypothèse que nous considérons est que la fonction (f) est $\mu$-Fortement convexe, ce qui signifie que pendant un certain temps $\mu >0$,fonction $X\mapsto F(X)-\frac{\mu }{2}\Vert X{\Vert }^2$ C'est convexe.De plus, pour chaque$je=1,...,n$，$Fje:{\mathbb{R}}^d\to \mathbb{R}$ C'est convexe.

C’est une hypothèse forte.Dans le problème des moindres carrés, chaque (fi$ est convexe, mais la fonction globale (f) n'est que dans la matrice de conception$UN:=[{un}_1,...,{un}_n]$ Il n'est fortement convexe que s'il a un rang de ligne complet. Le problème de régression logistique régularisée L2 satisfait cette hypothèse en raison de l’existence du terme de régularisation, où$\mu \ge \lambda$。

Une classe importante de problèmes qui satisfont à ces hypothèses sont les problèmes d’optimisation de la forme :
$$X^{\ast }\in \arg \underset{X\in {\mathbb{R}}^d}{\min }F(X)=\frac{1}{n}\sum _{je=1}^n{\ell }_{je}({un}_{je}^{T}X)+\frac{\lambda }{2}\Vert X{\Vert }^2(15)$$
où chaque fonction "perte"${\ell }_{je}:\mathbb{R}\to \mathbb{R}$ est deux fois différentiable, et sa dérivée seconde${\ell }_{je}^{\prime \prime }$ est limité à 0 et à une certaine limite supérieure$M$ entre. Cela inclut une variété de fonctions de perte avec régularisation L2 dans l'apprentissage automatique, telles que les moindres carrés, la régression logistique, la régression probit, la régression robuste de Huber, etc.Dans ce cas, pour tous$je$,Nous avons $L_{je}\le M\Vert {un}_{je}{\Vert }^2+\lambda$ et$\mu \ge \lambda$。

Sous ces hypothèses, le taux de convergence de la méthode de descente de gradient (GD) est déterminé par le numéro de condition $\kappa :=L/\mu$ Décider. Le numéro de condition est toujours supérieur ou égal à 1, et lorsqu'il est significativement supérieur à 1, les contours de la fonction deviennent très elliptiques, faisant osciller les itérations de la méthode GD.Au contraire, quand$\kappa$ Lorsqu’il est proche de 1, la méthode GD converge plus rapidement.

Selon les hypothèses 1 et 2, la méthode VR converge à un rythme linéaire.On dit que la valeur de la fonction d'une méthode aléatoire ({f(x_k)}) est donnée par$0<\rho \le 1$ Le taux de convergence linéaire (sous attente), s'il existe une constante$C>0$ Fait du:
$$E[F(X_k)]-F(X^{\ast })\le (1-\rho {)}^{k}C=O(\exp (-k\rho ))\forall k(16)$$
Cela contraste avec les méthodes SGD classiques qui reposent uniquement sur des estimations non biaisées du gradient à chaque itération, qui n'obtiennent des taux sous-linéaires que sous ces hypothèses :
$$E[F(X_k)]-F(X^{\ast })\le O(1/k)$$
Le minimum qui satisfait cette inégalité$k$ C'est ce qu'on appelle la complexité itérative de l'algorithme. Voici la complexité itérative et le coût d'une itération pour les variantes de base des méthodes GD, SGD et VR :

La durée totale d’exécution d’un algorithme est déterminée par le produit de la complexité de l’itération et de la durée d’exécution de l’itération.utilisé ici${\kappa }_{\text{max}}:={\max }_{je}{L}_{je}/\mu$ .Avis${\kappa }_{\text{max}}\ge \kappa$Par conséquent, la complexité itérative de GD est inférieure à celle de la méthode VR.

Cependant, comme le coût par itération de GD est celui de la méthode VR $n$ fois, la méthode VR est supérieure en termes de durée totale d’exécution.

L’avantage des méthodes SGD classiques est que leur temps d’exécution et leur taux de convergence ne dépendent pas de $n$, mais il a une tolérance $ϵ$ La dépendance de est bien pire, ce qui explique les mauvaises performances du SGD lorsque la tolérance est faible.

En annexe B, nous fournissons une preuve simple montrant que la méthode SGD² a la même complexité itérative que la méthode VR.

2. Méthode de base de réduction de la variance

Le développement des méthodes de réduction de la variance (VR) a traversé plusieurs étapes et le premier lot de méthodes a abouti à des taux de convergence considérablement améliorés. Le début de cette série de méthodes est l’algorithme SAG. Par la suite, l'algorithme de montée stochastique à double coordonnée (SDCA), l'algorithme MISO, l'algorithme de gradient de réduction de variance stochastique (SVRG/S2GD) et l'algorithme SAGA (qui signifie SAG « amélioré ») sont apparus l'un après l'autre.

Dans ce chapitre, nous examinons de plus près ces méthodes VR pionnières. Au chapitre 4, nous explorerons certaines méthodes plus récentes qui présentent des caractéristiques supérieures par rapport à ces méthodes de base dans des scénarios d'application spécifiques.

2.1. Méthode du gradient moyen stochastique (SAG)

Notre exploration de la première méthode de réduction de la variance (VR) commence par l'imitation de la structure du gradient complet.Depuis le gradient complet$\nabla F(X)$ est tout$\nabla F_{je}(X)$ une simple moyenne des gradients, puis notre estimation du gradient complet$g_k$ Il devrait également s'agir de la moyenne de ces estimations de gradient. Cette idée a donné naissance à notre première méthode VR : la méthode du gradient moyen stochastique (SAG).

La méthode SAG [37], [65] est une version randomisée de la première méthode du gradient incrémental agrégé (IAG) [4]. L'idée centrale de SAG est que pour chaque point de données$je$ maintenir une estimation$v_{je}\approx \nabla F_{je}(X_k)$ .Ensuite, utilisez-les$v_{je}$ La moyenne des valeurs est utilisée comme estimation du gradient complet, soit :
$${\bar{g}}_k=\frac{1}{n}\sum _{j=1}^n{v}_{je\; plaisante}\approx \frac{1}{n}\sum _{j=1}^n\nabla F_j(X_k)=\nabla F(X_k)(18)$$

Dans chaque itération de SAG, à partir de l'ensemble { 1 , … , n } {1, points, n}{1,…,n} Extraire un index de${je}_k$, puis mis à jour selon les règles suivantes $v_{je\; plaisante}$：
$$v_{je\; plaisante}^{k+1}=\{\begin{array}{ll}\nabla F_{{je}_k}(X_k),& \text{si}j={je}_k\\ v_{je\; plaisante}^k,& \text{si}j\ne {je}_k\end{array}(19)$$
Parmi eux, chacun$v_{0je}$ Peut être initialisé à zéro ou$\nabla F_{je}(X_0)$ valeur approximative.Avec la solution$X^{\ast }$ approximation, chacun$v_{je}$ convergera progressivement vers$\nabla F_{je}(X^{\ast })$, satisfaisant ainsi la propriété VR (12).

Afin de mettre en œuvre efficacement SAG, nous devons prêter attention au calcul ${\bar{g}}_k$ pour éviter de recommencer la somme à zéro à chaque fois$n$ vecteur, parce que c'est$n$ Le coût est élevé quand il est important.Heureusement, puisque chaque itération n'a qu'un seul$v_{je}$ Les conditions changeront et nous n'aurons pas à recalculer la totalité de la somme à chaque fois.Plus précisément, supposons qu'en itérant$k$ Index extrait de${je}_k$, ensuite il y a:
$${\bar{g}}_k=\frac{1}{n}\sum _{\begin{array}{c}j=1\\ j\ne {je}_k\end{array}}^n{v}_{je\; plaisante}+\frac{1}{n}{v}_{{je}_k}^k={\bar{g}}_{k-1}-\frac{1}{n}{v}_{{je}_k}^{k-1}+\frac{1}{n}{v}_{{je}_k}^k(20)$$

Puisqu'en plus de $v_{{je}_k}$ tout sauf$v_{je\; plaisante}$ Les valeurs restent toutes les mêmes, on stocke simplement chacune$j$ Un vecteur correspondant à$v_j$ . L'algorithme 1 montre l'implémentation spécifique de la méthode SAG.

SAG est la première méthode stochastique à atteindre une convergence linéaire, et sa complexité itérative est $O(({\kappa }_{\text{max}}+n)\log (1/ϵ))$, en utilisant la taille du pas $\gamma =O(1/L_{\text{max}})$ . Cette convergence linéaire peut être observée sur la figure 1.Il convient de noter qu'en raison de$L_{\text{max}}$-Fonction fluide pour tout $L^{\prime }\ge L_{\text{max}}$ Aussi$L^{\prime }$- Les méthodes SAG douces atteignent des taux de convergence linéaires pour des pas suffisamment petits, contrairement aux méthodes SGD classiques, qui n'atteignent des taux sublinéaires qu'avec des séquences de pas décroissants difficiles à ajuster en pratique.

À l’époque, la convergence linéaire de SAG constituait une avancée significative car elle ne calculait qu’un seul gradient stochastique (en traitant un seul point de données) à chaque itération. Cependant, la preuve de convergence fournie par Schmidt et al. [65] est très complexe et repose sur des étapes vérifiées par ordinateur. L’une des principales raisons pour lesquelles SAG est difficile à analyser est que$g_k$ est une estimation biaisée du gradient.

Ensuite, nous introduisons la méthode SAGA, une variante de SAG qui exploite le concept de covariables pour créer une variante impartiale de la méthode SAG qui a des performances similaires mais est plus facile à analyser.

---

Algorithme 1 : méthode SAG

1. Paramètres : taille du pas $\gamma >0$
2. initialisation :$X_0$，$v_{je}=0\in {\mathbb{R}}^d$ pour$je=1,\dots ,n$
3. droite $k=1,\dots ,T-1$ mettre en œuvre:
   une. Sélection aléatoire ik ∈ { 1 , … , n } i_k dans {1, ldots, n}jek​∈{1,…,n}
   b. Calculer${\bar{g}}_k={\bar{g}}_{k-1}-\frac{1}{n}{v}_{{je}_k}^{k-1}$
   c. Mise à jour$v_{{je}_k}^k=\nabla F_{{je}_k}(X_k)$
   d. Mettre à jour l'estimation du gradient${\bar{g}}_k={\bar{g}}_k+\frac{1}{n}{v}_{{je}_k}^k$
   e. Mise à jour$X_{k+1}=X_k-\gamma {\bar{g}}_k$
4. Sortir:$X_T$

2.2.Méthode SAGA

Une estimation de gradient impartiale de base réduite $\nabla F_{{je}_k}(X_k)$ L'approche de la variance repose sur l'utilisation de ce que l'on appelle des covariables ou variables de contrôle.pour$je=1,\dots ,n$,installation $v_{je}\in {\mathbb{R}}^d$ est un vecteur.En utilisant ces vecteurs, nous pouvons convertir le dégradé complet$\nabla F(X)$ Réécrit comme suit :
$$\nabla F(X)=\frac{1}{n}\sum _{je=1}^n(\nabla F_{je}(X)-v_{je}+v_{je})=\frac{1}{n}\sum _{je=1}^n\nabla F_{je}(X)-v_{je}+\frac{1}{n}\sum _{j=1}^n{v}_j$$
$$:=\frac{1}{n}\sum _{je=1}^n\nabla F_{je}(X,v)(21)$$
qui définit$\nabla F_{je}(X,v):=\nabla F_{je}(X)-v_{je}+\frac{1}{n}{\sum }_{j=1}^n{v}_j$ .Maintenant, nous pouvons échantillonner au hasard un$\nabla F_{je}(X,v)$ pour construire le dégradé complet$\nabla F(X)$ Une estimation impartiale de i ∈ { 1 , … , n } i dans {1, ldots, n}je∈{1,…,n}, vous pouvez appliquer la méthode SGD et utiliser l'estimation du gradient :
$$g_k=\nabla F_{{je}_k}(X_k,v)=\nabla F_{{je}_k}(X_k)-v_{{je}_k}+\frac{1}{n}\sum _{j=1}^n{v}_j(22)$$

pour observation $v_{je}$ La différence entre les paires de sélection$g_k$ influencer, nous pouvons$g_k=\nabla F_{{je}_k}(X_k,v)$ Substitut et utilisation$E_{je}\sim \frac{1}{n}[v_{je}]=\frac{1}{n}{\sum }_{j=1}^n{v}_j$ Pour calculer l’espérance, on obtient :
$$E\left[\Vert \nabla F_{je}(X_k)-v_{je}+E_{je}\sim \frac{1}{n}[v_{je}-\nabla F_{je}(X_k)]{\Vert }^2\right]\le E\left[\Vert \nabla F_{je}(X_k)-v_{je}{\Vert }^2\right](23)$$
Le lemme 2 est utilisé ici, où$X=\nabla F_{je}(X_k)-v_{je}$ .Cette borne (23) montre que si$v_{je}$ avec$k$ L'augmentation est proche de$\nabla F_{je}(X_k)$ , nous pouvons obtenir des attributs VR (12).C'est pourquoi nous appelons$v_{je}$ sont des covariables, et nous pouvons les sélectionner pour réduire la variance.

Par exemple, cette approche est également mise en œuvre par la méthode SGD² (13), où $v_{je}=\nabla F_{je}(X^{\ast })$ .Cependant, cela n’est pas couramment utilisé dans la pratique car nous ne savons généralement pas$\nabla F_{je}(X^{\ast })$ .Une option plus pratique est$v_{je}$ comme nous le savons${\bar{X}}_{je}\in {\mathbb{R}}^d$ dégradé à proximité$\nabla F_{je}({\bar{X}}_{je})$ . SAGA pour chaque fonction$F_{je}$ utiliser un point de référence${\bar{X}}_{je}\in {\mathbb{R}}^d$, et utilisez des covariables $v_{je}=\nabla F_{je}({\bar{X}}_{je})$, dont chacun ${\bar{X}}_{je}$ sera notre dernière évaluation$F_{je}$ indiquer. En utilisant ces covariables, nous pouvons construire une estimation de gradient, suivant (22), donnant :
$$g_k=\nabla F_{{je}_k}(X_k)-\nabla F_{{je}_k}({\bar{X}}_{{je}_k})+\frac{1}{n}\sum _{j=1}^n\nabla F_j({\bar{X}}_j)(24)$$

Pour implémenter SAGA, nous pouvons stocker des dégradés $\nabla F_{je}({\bar{X}}_{je})$ au lieu de$n$ point de référence${\bar{X}}_{je}$ .C'est-à-dire supposons$v_j=\nabla F_j({\bar{X}}_j)$ pour j ∈ { 1 , … , n } j dans {1, ldots, n}j∈{1,…,n}, à chaque itération, nous mettons à jour un gradient stochastique comme SAG $v_j$。

Algorithme 2 SAGA

1. Paramètres : taille du pas $\gamma >0$
2. initialisation :$X_0$，$v_{je}=0\in {\mathbb{R}}^d$ pour$je=1,\dots ,n$
3. conduire $k=1,\dots ,T-1$ itérations :
   une. Sélection aléatoire ik ∈ { 1 , … , n } i_k dans {1, ldots, n}jek​∈{1,…,n}
   b. Enregistrer l'ancienne valeur$v_{\text{vieux}}=v_{{je}_k}$
   c. Mise à jour$v_{{je}_k}=\nabla F_{{je}_k}(X_k)$
   d. Mise à jour$X_{k+1}=X_k-\gamma (v_{{je}_k}-v_{\text{vieux}}+{\bar{g}}_k)$
   e. Mettre à jour l'estimation du gradient${\bar{g}}_k={\bar{g}}_{k-1}+\frac{1}{n}(v_{{je}_k}-v_{\text{vieux}})$
4. Sortir:$X_T$

La méthode SAGA a la même complexité itérative que SAG $O(({\kappa }_{\text{max}}+n)\log (1/ϵ))$, en utilisant la taille du pas $\gamma =O(1/L_{\text{max}})$ , mais la preuve est beaucoup plus simple.Cependant, comme SAG, la méthode SAGA nécessite un stockage$n$ vecteurs auxiliaires$v_{je}\in {\mathbb{R}}^d$ pour$je=1,\dots ,n$, ce qui signifie la nécessité $O(nd)$ d'espace de stockage.quand$d$ et$n$ Lorsque les deux sont importants, cela peut ne pas être réalisable. Dans la section suivante, nous détaillons comment réduire ce besoin de mémoire pour les modèles courants tels que les modèles linéaires régularisés.

quand il est capable de $n$ Lorsque deux vecteurs auxiliaires sont stockés en mémoire, SAG et SAGA ont tendance à se comporter de manière similaire. Si ce besoin en mémoire est trop élevé, la méthode SVRG, que nous reviendrons dans la section suivante, est une bonne alternative. La méthode SVRG atteint le même taux de convergence et est souvent presque aussi rapide en pratique, mais ne nécessite que$O(d)$ de mémoire, pour des questions générales.

2.3.Méthode SVRG

Avant l'émergence de la méthode SAGA, certains premiers travaux ont introduit pour la première fois des covariables pour résoudre le problème de mémoire élevée requis par la méthode SAG.Ces études s'appuient sur un point de référence fixe$\bar{X}\in {\mathbb{R}}^d$ covariables, nous avons calculé le gradient complet à ce stade$\nabla F(\bar{X})$ .en stockant des points de référence$\bar{X}$ et le dégradé complet correspondant$\nabla F(\bar{X})$, nous pouvons le faire sans stocker chacun $\nabla F_j(\bar{X})$ Au cas où, utilisez${\bar{X}}_j=\bar{X}$ à tous$j$ pour mettre en œuvre la mise à jour (24).Plus précisément, au lieu de stocker ces vecteurs, nous utilisons les points de référence stockés à chaque itération$\bar{X}$ calculer$\nabla F_{{je}_k}(\bar{X})$ . Cette méthode a été initialement proposée par différents auteurs sous des noms différents, mais a ensuite été unifiée sous le nom de méthode SVRG, suivant la nomenclature de [28] et [84].

Nous formalisons la méthode SVRG dans l'algorithme 3.

En utilisant (23), nous pouvons dériver l’estimation du gradient $g_k$ La variance de est bornée :
$$E\left[\Vert g_k-\nabla F(X_k){\Vert }^2\right]\le E\left[\Vert \nabla F_{je}(X_k)-\nabla F_{je}(\bar{X}){\Vert }^2\right]\le L_{\text{max}}^2\Vert X_k-\bar{X}{\Vert }^2$$
où la deuxième inégalité utilise chacun$F_{je}$ de$L_{je}$-Douceur.

Il convient de noter que le point de référence $\bar{X}$ Plus on se rapproche du point actuel$X_k$, plus la variance de l'estimation du gradient est petite.

Pour que la méthode SVRG soit efficace, nous devons mettre à jour fréquemment les points de référence $\bar{X}$ (nécessitant ainsi le calcul de la pente complète) est mis en balance avec l'avantage d'une variance réduite.Pour cette raison, nous chacun$t$ Mettez à jour le point de référence une fois à chaque itération pour le rapprocher de$X_k$ (Voir ligne 11 de l'algorithme II-C).Autrement dit, la méthode SVRG contient deux boucles : une boucle externe$m$, où le gradient de référence est calculé $\nabla F({\bar{X}}_{m-1})$(ligne 4), et une boucle interne dans laquelle le point de référence est fixe et l'itération interne est mise à jour sur la base de l'étape de gradient stochastique (22). $X_k$(Ligne 10).

Contrairement à SAG et SAGA, SVRG ne nécessite que $O(d)$ de mémoire. Les inconvénients de SVRG incluent : 1) Nous avons un paramètre supplémentaire$t$, c'est-à-dire la longueur de la boucle intérieure, doit être ajustée ; 2) Deux gradients doivent être calculés pour chaque itération, et le gradient complet doit être calculé à chaque fois que le point de référence est modifié.

Johnson et Zhang [28] ont montré que SVRG a une complexité itérative $O(({\kappa }_{\text{max}}+n)\log (1/ϵ))$ , similaire à SAG et SAGA.C'est le nombre de boucles dans l'hypothèse$t$ de la collecte { 1 , … , m } {1, points, m}{1,…,m} Obtenu sous la condition d'un échantillonnage uniforme, où$L_{\text{max}}$，$\mu$, taille de pas $\gamma$ et$t$ Certaines dépendances doivent être satisfaites entre eux.En pratique, en utilisant$\gamma =O(1/L_{\text{max}})$ et longueur de la boucle intérieure$t=n$, SVRG a tendance à bien fonctionner, ce qui correspond exactement au paramètre que nous avons utilisé dans la figure 1.

Il existe désormais de nombreuses variantes de la méthode SVRG originale.Par exemple, certaines variantes utilisent$t$ distribution alternative [32], certaines variantes permettent la forme$O(1/L_{\text{max}})$ La taille du pas [27], [33], [35].Il existe également quelques variantes utilisant$\nabla F(\bar{X})$ approximation des mini-lots pour réduire le coût de ces évaluations de gradient complet et augmenter la taille des mini-lots pour préserver les propriétés VR.Il existe également quelques variantes où les mises à jour sont répétées dans la boucle interne selon [54]$g_k$：
[ g_k = nombre f_{i_k}(x_k) - nombre f_{i_k}(x_{k-1}) + g_{k-1} quad (25) ]
Cela fournit une approximation plus locale. L'utilisation de cette variante de mise à jour continue (25) présente des avantages uniques dans la minimisation des fonctions non convexes, comme nous le discutons brièvement dans la section IV.Notez enfin que SVRG peut profiter de$\nabla F({\bar{X}}_m)$ valeur pour aider à décider quand terminer l’algorithme.

Algorithme 3 Méthode SVRG

1. Paramètres : taille du pas $\gamma >0$
2. Initialiser le point de référence ${\bar{X}}_0=X_0\in {\mathbb{R}}^d$
3. Réaliser une circulation externe $m=1,2,\dots$：
   a. Calculer et stocker$\nabla F({\bar{X}}_{m-1})$
   b.$X_0={\bar{X}}_{m-1}$
   c. Sélectionnez le nombre d'itérations de la boucle interne$t$
   d. Effectuer la circulation interne$k=0,1,\dots ,t-1$：
   i. Sélection aléatoire ik ∈ { 1 , … , n } i_k dans {1, ldots, n}jek​∈{1,…,n}
   ii. Calcul$g_k=\nabla F_{{je}_k}(X_k)-\nabla F_{{je}_k}({\bar{X}}_{m-1})+\nabla F({\bar{X}}_{m-1})$
   iii. Mise à jour$X_{k+1}=X_k-\gamma g_k$
   e. Mettre à jour le point de référence${\bar{X}}_m=X_t$

2.4. SDCA et ses variantes

Un inconvénient des méthodes SAG et SVRG est que leur taille de pas repose sur des valeurs inconnues qui peuvent être inconnues dans certains problèmes. $L_{\text{max}}$ . Avant SVRG, la méthode SDCA [70], l’une des premières méthodes VR, a étendu la recherche sur les méthodes de descente de coordonnées aux problèmes à somme finie. L'idée derrière le SDCA et ses variantes est que les coordonnées du gradient fournissent une estimation naturelle du gradient réduisant la variance.Plus précisément, supposons j ∈ { 1 , … , d } j dans {1, ldots, d}j∈{1,…,d}, et définir ${\nabla }_{j}F(X):=\left(\frac{\partial F(X)}{\partial X_j}\right){ettttt}_j$ est le ième de (f(x))$j$ dérivées dans des directions de coordonnées, où${ettttt}_j\in {\mathbb{R}}^d$ C'est le premier$j$ vecteur unitaire.Une propriété clé des dérivées de coordonnées est que${\nabla }_{j}F(X^{\ast })=0$, parce que nous savons $\nabla F(X^{\ast })=0$ .La dérivée de ceci avec chaque point de données$\nabla F_j$ différent, ce dernier est$X^{\ast }$ peut ne pas être nul. Nous avons donc :
$$\Vert \nabla F(X)-{\nabla }_{j}F(X){\Vert }^2\to 0\text{quand}X\to X^{\ast }(26)$$
Cela signifie que la dérivée de coordonnées satisfait la propriété de réduction de la variance (12).De plus, nous pouvons utiliser${\nabla }_{j}F(X)$ construire$\nabla F(X)$ une estimation impartiale de.Par exemple, supposons$j$ est de la collection { 1 , … , d } {1, points, d}{1,…,d} Un index sélectionné de manière uniforme et aléatoire dans .Par conséquent, pour tout i ∈ { 1 , … , d } i dans {1, ldots, d}je∈{1,…,d},Nous avons $P[j=je]=\frac{1}{d}$ . donc,$d\times {\nabla }_{j}F(X)$ Oui$\nabla F(X)$ Une estimation impartiale de parce que :
$$E\left[d{\nabla }_{j}F(X)\right]=d\sum _{je=1}^{d}P[j=je]\frac{\partial F(X)}{\partial X_{je}}{ettttt}_{je}=\sum _{je=1}^d\frac{\partial F(X)}{\partial X_{je}}{ettttt}_{je}=\nabla F(X)$$

donc,${\nabla }_{j}F(X)$ Possède toutes les propriétés idéales auxquelles nous nous attendons pour l'estimation VR de gradients complets, sans avoir besoin d'utiliser des covariables. L’un des inconvénients de l’utilisation de ce gradient de coordonnées est qu’il est coûteux en calcul pour notre problème de somme (2).C'est parce que le calcul${\nabla }_{j}F(X)$ Besoin de parcourir l'intégralité de l'ensemble de données car${\nabla }_{j}F(X)=\frac{1}{n}{\sum }_{je=1}^n{\nabla }_j{F}_{je}(X)$ . Par conséquent, l’utilisation de dérivées de coordonnées semble incompatible avec la structure de notre problème de somme. Cependant, nous pouvons souvent réécrire le problème original (2) dans une formulation dite duale, où les dérivées coordonnées peuvent exploiter la structure inhérente.

Par exemple, la formule duale du modèle linéaire régularisé L2 (15) est :
$$v^{\ast }\in \arg \underset{v\in {\mathbb{R}}^n}{\max }\frac{1}{n}\sum _{je=1}^n-{\ell }_{je}^{\ast }(-v_{je})-\frac{\lambda }{2}{\Vert \frac{1}{\lambda }\sum _{je=1}^n{v}_{je}{un}_{je}\Vert }^2(27)$$
dans${\ell }_{je}^{\ast }(v)$ Oui${\ell }_{je}$ conjugué convexe.Nous pouvons utiliser la cartographie$X=\frac{1}{\lambda }{\sum }_{je=1}^n{v}_{je}{un}_{je}$ pour restaurer le problème d'origine (15)$X$ variable.résoudra$v^{\ast }$ En remplaçant par le côté droit de la cartographie ci-dessus, nous pouvons obtenir la solution de (15)$X^{\ast }$。

Notez que ce double problème a $n$ variables réelles$v_{je}\in \mathbb{R}$ , correspondant à un pour chaque échantillon d'apprentissage.De plus, chaque fonction de double perte${\ell }_{je}^{\ast }$ seulement$v_{je}$ La fonction. Autrement dit, le premier terme de la fonction de perte est séparable de manière coordonnée. Cette séparabilité en coordonnées, couplée à la forme simple du deuxième terme, permet de mettre en œuvre efficacement la méthode de remontée de coordonnées.En effet, Shalev-Shwartz et Zhang ont montré que l'ascension coordonnée sur ce problème présente une complexité itérative similaire à celle de SAG, SAGA et SVRG.$O(({\kappa }_{\text{max}}+n)\log (1/ϵ))$。

Le coût d'itération et la structure de l'algorithme sont également très similaires : sommation par suivi ${\sum }_{je=1}^n{v}_{je}{un}_{je}$ Pour gérer le deuxième terme de (27), chaque itération d'ascension à double coordonnée n'a besoin de considérer qu'un seul échantillon d'apprentissage, et le coût de chaque itération est le même que$n$ Rien à faire.De plus, nous pouvons utiliser une recherche de ligne 1D pour calculer efficacement la taille du pas afin de maximiser$v_{je}$ Double objectif de la fonction.Cela signifie que même sans$L_{\text{max}}$ En connaissant les quantités pertinentes, il est également possible d'obtenir des temps d'exécution rapides dans le pire des cas pour les méthodes VR.

3. Questions pratiques liées à la réduction de la variance

Afin de mettre en œuvre la méthode de base de réduction de la variance (VR) et d’obtenir des performances raisonnables, plusieurs problèmes de mise en œuvre doivent être résolus. Dans cette section, nous abordons plusieurs questions non abordées ci-dessus.

3.1.Taille du pas de réglage SAG/SAGA/SVRG

Dans le domaine des algorithmes d'optimisation, en particulier dans les méthodes de réduction de variation telles que le gradient moyen stochastique (SAG), l'algorithme de gradient moyen stochastique (SAGA) et le gradient stochastique (SVRG), le réglage de la taille du pas est une question clé.Bien que pour la méthode d'ascension stochastique à double coordonnée (SDCA), nous puissions utiliser le double objectif pour déterminer la taille du pas, la base théorique des méthodes variables originales de SAG, SAGA et SVRG est que la taille du pas doit être$\gamma =O\left(\frac{1}{L_{\text{max}}}\right)$ formulaire.Cependant, dans les applications pratiques, nous ne savons souvent pas$L_{\text{max}}$ La valeur exacte de et l'utilisation d'autres tailles de pas peuvent donner de meilleures performances.

Une stratégie classique pour définir la taille du pas dans la méthode de descente de gradient complet (full-GD) est la recherche de ligne Armijo.point actuel donné$X_k$ et direction de recherche$g_k$, recherche de ligne Armijo dans ${\gamma }_k$ s'effectue sur la ligne définie comme γ k ∈ { γ : xk + γ gk } gamma_k dans {gamma : x_k + gamma g_k}γk​∈{γ:Xk​+γgk​}, et la fonction doit être suffisamment réduite, c'est-à-dire :
$$F(X_k+{\gamma }_k{g}_k)<F(X_k)-c{\gamma }_k\Vert \nabla F(X_k){\Vert }^2$$
Cependant, cette approche nécessite plusieurs étapes candidates${\gamma }_k$ Calcul$F(X_k+{\gamma }_k{g}_k)$, qui évalue $F(X)$ Coût prohibitif lorsqu'il s'agit de parcourir l'intégralité de l'ensemble de données.

Afin de résoudre ce problème, une méthode de variation aléatoire peut être utilisée pour trouver ceux qui remplissent les conditions suivantes ${\gamma }_k$：
$$F_{je}(X_k+{\gamma }_k{g}_k)<F_{je}(X_k)-c{\gamma }_k\Vert \nabla F_{je}(X_k){\Vert }^2$$
Cette approche fonctionne généralement bien dans la pratique, surtout lorsque$\Vert \nabla F_{je}(X_k)\Vert$ pas proche de zéro, bien qu’il n’existe actuellement aucune théorie pour soutenir cette approche.

De plus, Mairal a proposé une « technique Bottou » pour régler la taille du pas dans la pratique. Cette méthode effectue une recherche binaire en prenant une petite partie de l'ensemble de données (par exemple 5 %) pour essayer de trouver la taille de pas optimale en un seul passage dans cet échantillon. Semblable à la recherche linéaire Armijo, cette méthode fonctionne souvent bien dans la pratique, mais là encore, elle manque de fondement théorique.

Veuillez noter que le contenu ci-dessus est une reformulation du texte original, utilisant le format Markdown pour représenter des formules et des variables mathématiques.

Cependant, la méthode SDCA présente également certains inconvénients.Premièrement, cela nécessite de calculer le conjugué convexe${\ell }_{je}^{\ast }$ plutôt qu'un simple dégradé. Nous n’avons pas d’équivalent différentiel automatique pour les conjugués convexes, ce qui peut donc augmenter les efforts de mise en œuvre. Des travaux récents ont proposé des méthodes SDCA « doubles » qui ne nécessitent pas de conjugaison et utilisent plutôt directement des gradients. Cependant, dans ces méthodes, il n'est plus possible de suivre la double cible pour définir la taille du pas.Deuxièmement, même si la SDCA requiert uniquement$O(n+d)$ mémoire pour résoudre le problème (15), mais pour cette catégorie de problèmes, SAG/SAGA n'a besoin que$O(n+d)$ de mémoire (voir section 3).Une variante de SDCA adaptée à des problèmes plus généraux avec SAG/SAGA$O(nd)$ mémoire parce que$v_{je}$ devenir avoir$d$ vecteur d'éléments. Un dernier inconvénient subtil de la SDCA est qu’elle suppose implicitement une forte constante de convexité.$\mu$ égal$\lambda$ .pour$\mu$ plus que le$\lambda$ problème, la méthode VR originale surpasse généralement considérablement la SDCA.

3.2. Détermination des conditions de résiliation

Dans le domaine de l’optimisation des algorithmes, nous nous appuyons souvent sur des résultats théoriques de complexité itérative pour prédire le nombre d’itérations requis pour qu’un algorithme atteigne une précision spécifique. Cependant, ces limites théoriques reposent souvent sur des constantes que nous ne pouvons pas prédire, et dans les applications pratiques, l'algorithme peut souvent atteindre la précision attendue en moins d'itérations. Par conséquent, nous devons définir certains critères de test pour déterminer quand l’algorithme doit être terminé.

Dans la méthode traditionnelle de descente à gradient complet (full-GD), nous utilisons généralement la norme du gradient $\Vert \nabla F(X_k)\Vert$ Ou une autre quantité liée à cela pour décider quand arrêter l'itération.Pour la méthode SVRG on peut adopter le même critère mais utiliser$\Vert \nabla F({\bar{X}}_m)\Vert$ comme base de jugement.Pour la méthode SAG/SAGA, bien que nous ne calculions pas explicitement le gradient complet, la quantité $ g_{bar{k}} $ se rapprochera progressivement$\nabla F(X_k)$, on utilise donc $\Vert g_{\bar{k}}\Vert$ car une condition d'arrêt est une heuristique raisonnable.

Dans la méthode SDCA, avec quelques travaux d'enregistrement supplémentaires, nous pouvons suivre le gradient du double objectif sans ajouter de coût asymptotique supplémentaire.En outre, une approche plus systématique consisterait à suivre le double écart, même si cela augmenterait le$O(n)$ coût, mais il est capable de fournir des conditions de résiliation avec des preuves à double écart. De plus, basée sur la condition d’optimalité des cibles fortement convexes, la méthode MISO adopte une méthode fondée sur des principes basés sur une borne inférieure quadratique [41].

Les formules et variables mathématiques suivantes sont exprimées au format Markdown :

• Norme de gradient :$\Vert \nabla F(X_k)\Vert$
• Norme de gradient dans la méthode SVRG :$\Vert \nabla F({\bar{X}}_m)\Vert$
• La quantité de gradient d'approximation dans la méthode SAG/SAGA : $ g_{bar{k}} $
• Augmentation du coût par itération :$O(n)$
• Méthode MISO
• borne inférieure quadratique

Veuillez noter que le contenu ci-dessus est une reformulation du texte original, utilisant le format Markdown pour représenter des formules et des variables mathématiques.

3.3. Réduire les besoins en mémoire

Bien que l'algorithme SVRG (Stochastic Variational Reduction of Gradient) élimine les besoins en mémoire des méthodes de réduction de variation antérieures, dans les applications pratiques, les algorithmes SAG (Stochastic Average Gradient Descent) et SAGA (Stochastic Average Gradient Descent with Gradient Accumulation) sont utilisés dans de nombreux problèmes. . ont tendance à nécessiter moins d’itérations que l’algorithme SVRG.Cela a déclenché une réflexion : existe-t-il certains problèmes qui permettent à SAG/SAGA de$O(nd)$ Les exigences en matière de mémoire sont implémentées ci-dessous. Cette section explore une classe de modèles linéaires pour lesquels les besoins en mémoire peuvent être considérablement réduits.

Considérons un modèle linéaire où chaque fonction $F_{je}(X)$ Cela peut être exprimé comme${\xi }_{je}({\mathbf{un}}_{je}^{\top }X)$ .droite$X$ La dérivée donne la forme du gradient :
$$\nabla F_{je}(X)={\xi }^{\prime }({\mathbf{un}}_{je}^{\top }X){\mathbf{un}}_{je}$$
ici,${\xi }^{\prime }$ exprimer$\xi$ la dérivée de.En supposant que nous ayons un accès direct aux vecteurs propres${\mathbf{un}}_{je}$, alors pour implémenter la méthode SAG/SAGA, il suffit de stocker le scalaire $\xi ({\mathbf{un}}_{je}^{\top }X)$ .De cette façon, les besoins en mémoire varient de$O(nd)$ réduit à$O(n)$ . L'algorithme SVRG peut également profiter de cette structure de gradients : en stockant cette$n$ scalaire, nous pouvons réduire le nombre d'évaluations de gradient requises par itération "interne" SVRG à 1 pour cette classe de problèmes.

Il existe d'autres types de problèmes, tels que les modèles graphiques probabilistes, qui offrent également la possibilité de réduire les besoins en mémoire [66]. Grâce à une structure de données spécifique et à l'optimisation de l'algorithme, les ressources mémoire requises par l'algorithme au moment de l'exécution peuvent être encore réduites.

Les formules et variables mathématiques suivantes sont exprimées au format Markdown :

• Fonction du modèle linéaire :$F_{je}(X)={\xi }_{je}({\mathbf{un}}_{je}^{\top }X)$
• Expression du dégradé :$\nabla F_{je}(X)={\xi }^{\prime }({\mathbf{un}}_{je}^{\top }X){\mathbf{un}}_{je}$
• Vecteur de caractéristiques :${\mathbf{un}}_{je}$
• Les besoins en mémoire vont de $O(nd)$ Réduire à$O(n)$。

3.4. Traitement des dégradés clairsemés

Dans certains problèmes, le gradient $\nabla F_{je}(X)$ Peut contenir un grand nombre de valeurs nulles, comme un modèle linéaire avec des fonctionnalités clairsemées.Dans ce cas, l'algorithme traditionnel de descente de gradient stochastique (SGD) peut être mis en œuvre efficacement, avec une complexité de calcul linéaire dans le nombre d'éléments non nuls dans le gradient, qui est généralement beaucoup plus petit que la dimension du problème.$d$ . Cependant, dans les méthodes standards de réduction variationnelle (VR), cet avantage n’est pas exploité. Heureusement, il existe deux manières connues d’améliorer cela.

La première amélioration a été proposée par Schmidt et al., qui tire parti de la simplicité du processus de mise à jour et implémente une variante de calcul « à la volée » telle que le coût de chaque itération est proportionnel au nombre d'itérations non nulles. éléments.En prenant SAG comme exemple (mais cette approche fonctionne pour toutes les variantes), cela se fait en ne stockant pas le vecteur complet après chaque itération$v_{je}$, mais ne calcule que ceux correspondant aux éléments non nuls $v_{je{k}_j}$, en mettant à jour chaque variable depuis la dernière fois que cet élément était différent de zéro $v_{je{k}_j}$。

La deuxième méthode d'amélioration a été proposée par Leblond et al. pour SAGA, qui met à jour la formule. $X_{k+1}=X_k-\gamma (\nabla F_{je}(X_k)-\nabla F_{je}({\bar{X}}_{je})+{\bar{g}}_k)$ Un caractère aléatoire supplémentaire est introduit. ici,$\nabla F_{je}(X_k)$ et$\nabla F_{je}({\bar{X}}_{je})$ est clairsemé, et${\bar{g}}_k$ est dense.Dans cette méthode, le terme dense$({\bar{g}}_k{)}_j$ Chaque composant de est remplacé par$m_j({\bar{g}}_k{)}_j$,dans $m\in {\mathbb{R}}^d$ est un vecteur clairsemé aléatoire dont l'ensemble de supports est contenu dans$\nabla F_{je}(X_k)$ , et devrait être un vecteur constant avec tous les éléments égaux à 1. De cette façon, le processus de mise à jour reste impartial (bien que désormais clairsemé) et la variance accrue n'affecte pas le taux de convergence de l'algorithme. Plus de détails sont fournis par Leblond et al.

Les formules et variables mathématiques suivantes sont exprimées au format Markdown :

• pente:$\nabla F_{je}(X)$
• Mise à jour SGD :$X_{k+1}=X_k-\gamma (\nabla F_{je}(X_k)-\nabla F_{je}({\bar{X}}_{je})+{\bar{g}}_k)$
• Dégradé clairsemé :$\nabla F_{je}(X_k)$ et$\nabla F_{je}({\bar{X}}_{je})$
• Dégradé dense :${\bar{g}}_k$
• Vecteurs clairsemés aléatoires :$m$
• Attend un vecteur constant : un vecteur dont tous les éléments sont égaux à 1.