Compartilhamento de tecnologia

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

Resumo

A otimização estocástica é um componente vital do aprendizado de máquina e em seu núcleo está o algoritmo estocástico de descida gradiente (SGD), um método que tem sido amplamente utilizado desde que foi proposto pela primeira vez, há mais de 60 anos. Nos últimos oito anos, testemunhamos um novo desenvolvimento interessante: técnicas de redução de variância para métodos de otimização estocástica. Esses métodos de redução de variância (métodos VR) apresentam bom desempenho em cenários que permitem múltiplas iterações dos dados de treinamento, apresentando convergência mais rápida que o SGD, tanto na teoria quanto na prática. Este aumento na velocidade destaca o interesse crescente em métodos de RV e o rápido acúmulo de resultados de pesquisa nesta área. Este artigo revisa os princípios-chave e os principais avanços nos métodos de RV para otimização limitada de conjuntos de dados, com o objetivo de informar leitores não especialistas. Nós nos concentramos principalmente em ambientes de otimização convexa e fornecemos uma referência para leitores interessados ​​em extensões para minimização de funções não-convexas.

Palavras-chave | Otimização de aprendizado de máquina;

1. Introdução

No campo da pesquisa em aprendizado de máquina, uma questão básica e importante é como adaptar o modelo a um enorme conjunto de dados. Por exemplo, podemos considerar o caso típico de um modelo linear de mínimos quadrados:

$$x^{\ast }\in \arg \underset{x\in {\mathbb{R}}^e}{\mathrm{mínimo}}\frac{1}{e}\sum _{eu=1}^e(a_{eu}^{E}x-b_{eu}{)}^2$$

Neste modelo temos $e$ parâmetros, que são representados por vetores$x\in {\mathbb{R}}^e$ dado.Enquanto isso, temos em mãos$e$ pontos de dados, incluindo vetores de recursos$a_{eu}\in {\mathbb{R}}^e$ e valor alvo$b_{eu}\in \mathbb{R}$ .O processo de adaptação do modelo consiste em ajustar esses parâmetros para que a saída prevista do modelo$a_{eu}^{E}x$ em média, o mais próximo possível do valor-alvo$b_{eu}$。

De forma mais ampla, poderíamos usar uma função de perda $e_{eu}(x)$ Para medir as previsões do modelo e o$eu$ Quão próximos estão os pontos de dados:

$$x^{\ast }\in \arg \underset{x\in {\mathbb{R}}^e}{\mathrm{mínimo}}e(x):=\frac{1}{e}\sum _{eu=1}^e{e}_{eu}(x)$$

função de perda $e_{eu}(x)$ Se for maior, indica que as previsões do modelo se desviam muito dos dados;$e_{eu}(x)$ Igual a zero, o modelo se ajusta perfeitamente aos pontos de dados.função$e(x)$ Reflete a perda média do modelo em todo o conjunto de dados.

Problemas como a forma (2) acima se aplicam não apenas a problemas lineares de mínimos quadrados, mas também a muitos outros modelos estudados em aprendizado de máquina. Por exemplo, em um modelo de regressão logística resolvemos:

$$x^{\ast }\in \arg \underset{x\in {\mathbb{R}}^e}{\mathrm{mínimo}}\frac{1}{e}\sum _{eu=1}^e\mathrm{eisg}(1+e^{-b_{eu}{a}_{eu}^{E}x})+\frac{\lambda }{2}\Vert x{\Vert }_2^2$$

Aqui, estamos lidando com bi ∈ { − 1 , + 1 } b_i em {-1, +1}beu​∈{−1,+1} Para um problema de classificação binária, a previsão é baseada em$a_{eu}^{E}x$ símbolos.Um termo de regularização também é introduzido na fórmula$\frac{\lambda }{2}\Vert x{\Vert }_2^2$ para evitar overfitting dos dados, onde$\Vert x{\Vert }_2^2$ expressar$x$ O quadrado da norma euclidiana de.

Na maioria dos modelos de aprendizagem supervisionada, o processo de treinamento pode ser expresso como a forma (2), incluindo mínimos quadrados regularizados L1, máquina de vetores de suporte (SVM), análise de componentes principais, campos aleatórios condicionais e redes neurais profundas, etc.

Um desafio importante nas instâncias problemáticas modernas é o número de pontos de dados $e$ Provavelmente extremamente grande. Lidamos frequentemente com conjuntos de dados que vão muito além da faixa dos terabytes e podem vir de fontes tão diversas como a Internet, satélites, sensores remotos, mercados financeiros e experiências científicas. Para lidar com conjuntos de dados tão grandes, uma abordagem comum é usar o algoritmo de descida gradiente estocástica (SGD), que usa apenas um pequeno número de pontos de dados selecionados aleatoriamente em cada iteração. Além disso, tem havido um aumento acentuado recentemente no interesse em métodos de gradiente estocástico de redução de variância (VR), que apresentam taxas de convergência mais rápidas do que os métodos tradicionais de gradiente estocástico.

Figura 1. No problema de regressão logística baseado no conjunto de dados de cogumelo [7], descida gradiente (GD), descida gradiente acelerada (AGD, GD acelerada em [50]), descida gradiente estocástica (SGD) e método ADAM [30] foi em comparação com os métodos de redução de variância (VR) SAG e SVRG, onde n = 8.124, d = 112.

1.1. Métodos gradiente e gradiente estocástico descendente.

O gradiente descendente (GD) é um algoritmo clássico usado para resolver o problema acima (2), e sua fórmula de atualização iterativa é a seguinte:
$$x_{o+1}=x_o-\gamma \frac{1}{e}\sum _{eu=1}^e\nabla e_{eu}(x_o)$$

aqui,$\gamma$ é um valor de passo fixo maior que zero.Durante cada iteração do algoritmo GD, cada ponto de dados deve ser$eu$ Calcular gradiente$\nabla e_{eu}(x_o)$, o que significa que GD exige que todos $e$ realizar uma travessia completa dos pontos de dados.Quando o tamanho do conjunto de dados$e$ Quando se torna muito grande, o custo de cada iteração do algoritmo GD torna-se muito elevado, limitando assim a sua aplicação.

Como alternativa, podemos considerar o método estocástico de descida gradiente (SGD), que foi proposto pela primeira vez por Robbins e Monro, e sua fórmula de atualização iterativa é a seguinte:
$$x_{o+1}=x_o-\gamma \nabla e_{{eu}_o}(x_o)$$

O algoritmo SGD funciona usando apenas o gradiente de um ponto de dados selecionado aleatoriamente em cada iteração. $\nabla e_{{eu}_o}(x_o)$ para reduzir o custo de cada iteração. Na Figura 1, podemos ver que o SGD alcança um progresso mais significativo do que o GD (incluindo métodos acelerados de GD) nos estágios iniciais do processo de otimização.O gráfico mostra o progresso da otimização em termos de épocas, que são definidas como o cálculo de todos$e$ O número de gradientes para amostras de treinamento. O algoritmo GD realiza uma iteração em cada rodada, enquanto o algoritmo SGD realiza uma iteração em cada rodada$e$ iterações.Usamos rodadas como base para comparar SGD e GD, porque sob a suposição$e$ Em casos muito grandes, o principal custo de ambos os métodos está concentrado no gradiente$\nabla e_{eu}(x_o)$ Cálculo.

1.2. Problema de variância

Vamos considerar a indexação aleatória ${eu}_o$ da coleção { 1 , … , n } {1, pontos, n}{1,…,e} No caso de seleção aleatória uniforme, isso significa que para todos$eu$,escolher ${eu}_o=eu$ A probabilidade$P[{eu}_o=eu]$ igual$\frac{1}{e}$ . nesse caso,$\nabla e_{{eu}_o}(x_o)$ como$\nabla e(x_o)$ O estimador de é imparcial porque, pela definição de expectativa, temos:
$$E[\nabla e_{{eu}_o}(x_o)|x_o]=\frac{1}{e}\sum _{eu=1}^e\nabla e_{eu}(x_o)=\nabla e(x_o)(6)$$

Embora o método SGD (Stochastic Gradient Descent) não garanta a função em cada iteração $e$ O valor de diminuirá, mas em média move-se em direção ao gradiente total negativo, que representa a direção descendente.

No entanto, ter um estimador de gradiente imparcial não é suficiente para garantir a convergência das iterações do SGD. Para ilustrar este ponto, a Figura 2 (esquerda) mostra a trajetória iterativa do SGD ao aplicar uma função de regressão logística usando um tamanho de passo constante no conjunto de dados de quatro categorias fornecido pelo LIBSVM [7].As elipses concêntricas na figura representam os contornos da função, ou seja, o valor da função$e(x)=c$ ponto correspondente$x$ juntar,$c$ é uma constante específica no conjunto dos números reais.valores constantes diferentes$c$ Corresponde a diferentes elipses.

A trajetória iterativa do SGD não converge para a solução ótima (indicada por um asterisco verde na figura), mas forma uma nuvem de pontos em torno da solução ótima. Em contrapartida, mostramos na Figura 2 a trajetória iterativa de um método de redução de variância (VR), gradiente médio estocástico (SAG), utilizando o mesmo tamanho de passo constante, que apresentaremos posteriormente. A razão pela qual o SGD não consegue convergir neste exemplo é que o próprio gradiente estocástico não converge para zero e, portanto, o método SGD de passo constante (5) nunca para.Isto contrasta fortemente com os métodos de descida gradiente (GD), que naturalmente param quando$x_o$ Abordagens$x^{\ast }$,gradiente $\nabla e(x_o)$ tenderá a zero.

Figura 2. Gráficos de nível definido para regressão logística bidimensional usando métodos iterativos de passo fixo SGD (esquerda) e SAG (direita). Asterisco verde indica xdesatar.

1.3. Método clássico de redução de variância

processamento devido a $\nabla e_{eu}(x_o)$ Existem diversas técnicas clássicas para problemas de não convergência causados ​​pela variância de valores.Por exemplo, Robbins e Monro [64] usam uma série de etapas decrescentes${\gamma }_o$ para resolver o problema de variância, garantindo que o produto${\gamma }_o\nabla e_{{eu}_o}(x_o)$ pode convergir para zero. No entanto, ajustar esta sequência de passos decrescentes para evitar parar o algoritmo demasiado cedo ou demasiado tarde é um problema difícil.

Outra técnica clássica para reduzir a variância é usar múltiplos $\nabla e_{eu}(x_o)$ média de para obter o gradiente completo$\nabla e(x)$ uma estimativa mais precisa. Essa abordagem é chamada de minilote e é particularmente útil quando vários gradientes podem ser avaliados em paralelo. Isso resulta em uma iteração do formulário:
$$x_{o+1}=x_o-\gamma \frac{1}{|B_o|}\sum _{eu\in B_o}\nabla e_{eu}(x_o)(7)$$
em$B_o$ é um conjunto de índices aleatórios,$|B_o|$ expressar$B_o$ o tamanho de.se$B_o$ Amostrando uniformemente com substituição, então a variância desta estimativa de gradiente está relacionada ao "tamanho do lote"$|B_o|$ é inversamente proporcional, portanto a variação pode ser reduzida aumentando o tamanho do lote.

No entanto, o custo de tais iterações é proporcional ao tamanho do lote, portanto esta forma de redução da variância acarreta um aumento no custo computacional.

Outra estratégia comum para reduzir a variância e melhorar o desempenho empírico do SGD é adicionar “momentum”, um termo extra baseado na direção usada nas etapas anteriores. Em particular, a forma do SGD com momentum é a seguinte:
$$x_{o+1}=x_o-\gamma {eu}_o(9)$$
onde o parâmetro de momento$\beta$ Localizado no intervalo (0, 1).Se o impulso inicial${eu}_0=0$e expanda em (8) ${eu}_o$ Para atualizações, obtemos${eu}_o$ é a média ponderada dos gradientes anteriores:
$${eu}_o=\sum _{para=0}^o{\beta }^{o-para}\nabla e_{{eu}_{para}}(x_{para})(10)$$
portanto,${eu}_o$ é a soma ponderada dos gradientes estocásticos.porque${\sum }_{para=0}^o{\beta }^{o-para}=\frac{1-{\beta }^{o+1}}{1-\beta }$, podemos converter $\frac{1-\beta }{1-{\beta }^o}{eu}_o$ Considerado como uma média ponderada de gradientes estocásticos.Se compararmos isso com a expressão para o gradiente completo$\nabla e(x_o)=\frac{1}{e}{\sum }_{eu=1}^e\nabla e_{eu}(x_o)$ Para comparar, podemos$\frac{1-\beta }{1-{\beta }^o}{eu}_o$(assim como ${eu}_o$ ) é interpretado como uma estimativa do gradiente completo. Embora esta soma ponderada reduza a variância, também levanta questões importantes.Como a soma ponderada (10) dá mais peso aos gradientes amostrados recentemente, ela não convergirá para o gradiente completo$\nabla e(x_o)$ , esta última é uma média simples. O primeiro método de redução de variância que veremos na Seção II-A resolve esse problema usando uma média simples em vez de qualquer média ponderada.

1.4. Métodos modernos de redução de variância

Ao contrário dos métodos clássicos, eles usam diretamente um ou mais $\nabla e_{eu}(x_o)$ como$\nabla e(x_o)$ Como aproximação, os métodos modernos de redução de variância (VR) empregam uma estratégia diferente.Esses métodos usam$\nabla e_{eu}(x_o)$ para atualizar a estimativa do gradiente$g_o$, cujo objetivo é fazer $g_o$ abordagem$\nabla e(x_o)$ .Especificamente, esperamos$g_o$ capaz de satisfazer$g_o\approx \nabla e(x_o)$ . Com base nessas estimativas de gradiente, executamos então uma etapa de gradiente aproximada da forma:
$$x_{o+1}=x_o-\gamma g_o(11)$$
aqui$\gamma >0$ é o parâmetro de tamanho do passo.

Para garantir que um tamanho de passo constante seja usado $\gamma$ Quando a iteração (11) pode convergir, precisamos garantir que a estimativa do gradiente$g_o$ A variância tende a zero. Matematicamente, isso pode ser expresso como:
$$E\left[\Vert g_o-\nabla e(x_o){\Vert }^2\right]\to 0\text{como}o\to \infty (12)$$
expectativas aqui$E$ é baseado no algoritmo até o$o$ Todas as variáveis ​​aleatórias são calculadas para iterações. A propriedade (12) garante que o método VR pode ser interrompido quando a solução ótima for alcançada. Consideramos esta propriedade como uma característica marcante da abordagem de RV e, portanto, a chamamos de propriedade de RV. Vale ressaltar que a expressão variância “reduzida” pode ser enganosa, pois na verdade a variância tende a zero. A propriedade (12) é um fator chave que permite que os métodos de RV alcancem uma convergência mais rápida na teoria (sob suposições apropriadas) e na prática (conforme mostrado na Figura 1).

1.5 Primeiro exemplo de método de redução de variância: SGD².

Um método simples de melhoria pode fazer com que a fórmula recursiva SGD (5) alcance a convergência sem reduzir o tamanho do passo, ou seja, traduza cada gradiente. $\nabla e_{eu}(x^{\ast })$, este método é definido da seguinte forma:
$$x_{o+1}=x_o-\gamma (\nabla e_{{eu}_o}(x_o)-\nabla e_{{eu}_o}(x^{\ast }))(13)$$
Este método é denominado SGD² [22].Embora geralmente não possamos saber com certeza cada$\nabla e_{eu}(x^{\ast })$ , mas o SGD², por exemplo, pode ilustrar bem as características básicas do método de redução de variância.Além disso, muitos métodos de redução de variância podem ser vistos como uma forma aproximada do método SGD². Esses métodos não dependem do conhecido;$\nabla e_{eu}(x^{\ast })$, mas em vez disso use um método que possa aproximar $\nabla e_{eu}(x^{\ast })$ valor estimado.

Vale ressaltar que o SGD² utiliza uma estimativa imparcial do gradiente completo.porque$\nabla e(x^{\ast })=0$,F:
$$E[\nabla e_{{eu}_o}(x_o)-\nabla e_{{eu}_o}(x^{\ast })]=\nabla e(x_o)-\nabla e(x^{\ast })=\nabla e(x_o)$$
Além disso, quando o SGD² atingir a solução ótima, irá naturalmente parar porque para qualquer$eu$,ter:
$$(\nabla e_{eu}(x)-\nabla e_{eu}(x^{\ast })){|}_{x=x^{\ast }}=0$$

Após observação adicional, com $x_o$ aproximar$x^{\ast }$(para consecutivas $\nabla e_{eu}$), SGD² satisfaz a propriedade de redução de variância (12) porque:
$$\begin{gathered} E\left[\Vert g_o-\nabla e(x_o){\Vert }^2\right]= \\ E\left[\Vert \nabla e_{{eu}_o}(x_o)-\nabla e_{{eu}_o}(x^{\ast })-\nabla e(x_o){\Vert }^2\right]\le E\left[\Vert \nabla e_{{eu}_o}(x_o)-\nabla e_{{eu}_o}(x^{\ast }){\Vert }^2\right] \end{gathered}$$
Aqui usamos o Lema 2, vamos$X=\nabla e_{{eu}_o}(x_o)-\nabla e_{{eu}_o}(x^{\ast })$, e aproveitou $E[\nabla e_{{eu}_o}(x_o)-\nabla e_{{eu}_o}(x^{\ast })]=\nabla e(x_o)$ natureza. Esta propriedade indica que o SGD² possui velocidade de convergência mais rápida do que os métodos SGD tradicionais, que detalhamos no Apêndice B.

1.6. Método de convergência rápida de redução de variância

Nesta seção apresentaremos duas suposições padrão usadas para analisar o método de redução de variância (VR) e discutiremos o efeito de aceleração que pode ser alcançado sob essas suposições em comparação com o método SGD tradicional. Primeiro, assumimos que o gradiente tem continuidade de Lipschitz, o que significa que a taxa de variação do gradiente é finita.

Suposição 1 (continuidade de Lipschitz)

Assumimos que a função $e$é diferenciável e é $eu$- suave, para todos $x$ e$e$ e alguém$0<eu<\infty$,As seguintes condições:
$$\Vert \nabla e(x)-\nabla e(e)\Vert \le eu\Vert x-e\Vert (14)$$
Isto significa que cada$eeu:{\mathbb{R}}^e\to \mathbb{R}$ é diferenciável,${eu}_{eu}$- suave, nós definimos ${eu}_{\text{máx.}}$ para máx ⁡ { L 1 , . . . , L n } máx. {L_1, . . . , Eu_n}máx.{eu1​,...,eue​}。

Embora esta seja geralmente considerada uma suposição fraca, nos capítulos subsequentes discutiremos métodos de RV que são adequados para problemas não suaves. Para uma função univariada duas vezes diferenciável,$eu$-A suavidade pode ser intuitivamente entendida como: equivale a assumir que a segunda derivada é $eu$ limite superior, ou seja$|e^{\prime \prime }(x)|\le eu$ para todos$x\in {\mathbb{R}}^e$ .Para funções duas vezes diferenciáveis ​​de múltiplas variáveis, é equivalente a assumir uma matriz Hessiana${\nabla }^{2}e(x)$ O valor singular de$eu$ limite superior.

Suposição 2 (forte convexidade)

A segunda hipótese que consideramos é que a função (f) é $\mu$-Fortemente convexo, o que significa que para um certo $\mu >0$,função $x\mapsto e(x)-\frac{\mu }{2}\Vert x{\Vert }^2$ É convexo.Além disso, para cada$eu=1,...,e$，$eeu:{\mathbb{R}}^e\to \mathbb{R}$ É convexo.

Esta é uma suposição forte.No problema dos mínimos quadrados, cada (fi$ é convexo, mas a função geral (f) está apenas na matriz de projeto$A:=[a_1,...,a_e]$ É fortemente convexo apenas se tiver classificação de linha completa. O problema de regressão logística regularizada L2 satisfaz esta suposição devido à existência do termo de regularização, onde$\mu \ge \lambda$。

Uma importante classe de problemas que satisfazem essas suposições são os problemas de otimização da forma:
$$x^{\ast }\in \arg \underset{x\in {\mathbb{R}}^e}{\mathrm{mínimo}}e(x)=\frac{1}{e}\sum _{eu=1}^e{\ell }_{eu}(a_{eu}^{E}x)+\frac{\lambda }{2}\Vert x{\Vert }^2(15)$$
onde cada função de "perda"${\ell }_{eu}:\mathbb{R}\to \mathbb{R}$ é duas vezes diferenciável e sua segunda derivada${\ell }_{eu}^{\prime \prime }$ está restrito a 0 e algum limite superior$M$ entre. Isso inclui uma variedade de funções de perda com regularização L2 em aprendizado de máquina, como mínimos quadrados, regressão logística, regressão probit, regressão robusta de Huber, etc.Neste caso, para todos$eu$,Nós temos ${eu}_{eu}\le M\Vert a_{eu}{\Vert }^2+\lambda$ e$\mu \ge \lambda$。

Sob essas suposições, a taxa de convergência do método gradiente descendente (GD) é determinada pelo número de condição $\kappa :=eu/\mu$ Decidir. O número de condição é sempre maior ou igual a 1 e, quando é significativamente maior que 1, os contornos da função tornam-se muito elípticos, fazendo com que as iterações do método GD oscilem.Pelo contrário, quando$\kappa$ Quando está próximo de 1, o método GD converge mais rapidamente.

Nas Suposições 1 e 2, o método VR converge a uma taxa linear.Dizemos que o valor da função de um método aleatório ({f(x_k)}) é dado por$0<\rho \le 1$ A taxa de convergência linear (sob expectativa), se existir uma constante$C>0$ Faz:
$$E[e(x_o)]-e(x^{\ast })\le (1-\rho {)}^{o}C=O(\mathrm{experiência}(-o\rho ))\forall o(16)$$
Isto contrasta com os métodos clássicos de SGD que dependem apenas de estimativas imparciais do gradiente em cada iteração, que apenas obtêm taxas sublineares sob estas suposições:
$$E[e(x_o)]-e(x^{\ast })\le O(1/o)$$
O mínimo que satisfaz esta desigualdade$o$ É chamada de complexidade iterativa do algoritmo. A seguir estão a complexidade iterativa e o custo de uma iteração para variantes básicas dos métodos GD, SGD e VR:

O tempo total de execução de um algoritmo é determinado pelo produto da complexidade da iteração pelo tempo de execução da iteração.usado aqui${\kappa }_{\text{máx.}}:={máx.}_{eu}{eu}_{eu}/\mu$ .Perceber${\kappa }_{\text{máx.}}\ge \kappa$; Portanto, a complexidade da iteração do GD é menor que a do método VR.

No entanto, como o custo por iteração do GD é o do método VR $e$ vezes, o método VR é superior em termos de tempo total de execução.

A vantagem dos métodos SGD clássicos é que o seu tempo de execução e taxa de convergência não dependem de $e$, mas tem uma tolerância $ϵ$ A dependência é muito pior, o que explica o fraco desempenho do SGD quando a tolerância é pequena.

No Apêndice B, fornecemos uma prova simples mostrando que o método SGD² tem a mesma complexidade iterativa que o método VR.

2. Método básico de redução de variância

O desenvolvimento de métodos de redução de variância (VR) passou por vários estágios, e o lote inicial de métodos resultou em taxas de convergência significativamente melhoradas. O início desta série de métodos é o algoritmo SAG. Posteriormente, o algoritmo estocástico de subida de coordenadas duplas (SDCA), o algoritmo MISO, o algoritmo estocástico de redução de variância (SVRG/S2GD) e o algoritmo SAGA (que significa SAG "melhorado") surgiram um após o outro.

Neste capítulo, examinaremos mais de perto esses métodos pioneiros de RV. No Capítulo 4, exploraremos alguns métodos mais recentes que apresentam características superiores em comparação com esses métodos básicos em cenários de aplicação específicos.

2.1. Método do gradiente médio estocástico (SAG)

Nossa exploração do primeiro método de redução de variância (VR) começa com a imitação da estrutura gradiente completa.Como o gradiente completo$\nabla e(x)$ é tudo$\nabla e_{eu}(x)$ uma média simples dos gradientes, então nossa estimativa do gradiente completo$g_o$ Deve também ser a média dessas estimativas de gradiente. Essa ideia deu origem ao nosso primeiro método de VR: o método do gradiente médio estocástico (SAG).

O método SAG [37], [65] é uma versão aleatória do método de gradiente agregado incremental inicial (IAG) [4]. A ideia central do SAG é que para cada ponto de dados$eu$ manter uma estimativa${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu\; sei}\approx \nabla e_{eu}(x_o)$ .Então, use estes${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu\; sei}$ A média dos valores é utilizada como estimativa do gradiente completo, ou seja:
$${\bar{g}}_o=\frac{1}{e}\sum _{eu=1}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{brincadeira}\approx \frac{1}{e}\sum _{eu=1}^e\nabla e_{eu}(x_o)=\nabla e(x_o)(18)$$

Em cada iteração do SAG, do conjunto { 1 , … , n } {1, pontos, n}{1,…,e} Extraia um índice de${eu}_o$e, em seguida, atualizado de acordo com as seguintes regras ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{brincadeira}$：
$${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{brincadeira}^{o+1}=\{\begin{array}{ll}\nabla e_{{eu}_o}(x_o),& \text{se}eu={eu}_o\\ {vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{brincadeira}^o,& \text{se}eu\ne {eu}_o\end{array}(19)$$
Entre eles, cada${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{0eu}$ Pode ser inicializado em zero ou$\nabla e_{eu}(x_0)$ valor aproximado.Com a solução$x^{\ast }$ aproximação, cada${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu\; sei}$ convergirá gradualmente para$\nabla e_{eu}(x^{\ast })$, satisfazendo assim a propriedade VR (12).

Para implementar o SAG de forma eficiente, precisamos prestar atenção ao cálculo ${\bar{g}}_o$ para evitar começar a soma do zero todas as vezes$e$ vetor, porque isso é$e$ O custo é alto quando é grande.Felizmente, como cada iteração possui apenas um${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu\; sei}$ Os termos mudarão e não teremos que recalcular o valor total todas as vezes.Especificamente, suponha que durante a iteração$o$ Índice extraído de${eu}_o$, então há:
$${\bar{g}}_o=\frac{1}{e}\sum _{\begin{array}{c}eu=1\\ eu\ne {eu}_o\end{array}}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{brincadeira}+\frac{1}{e}{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}^o={\bar{g}}_{o-1}-\frac{1}{e}{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}^{o-1}+\frac{1}{e}{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}^o(20)$$

Já que além de ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}$ tudo exceto${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{brincadeira}$ Os valores permanecem todos os mesmos, apenas armazenamos cada um$eu$ Um vetor correspondente a${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ . O Algoritmo 1 mostra a implementação específica do método SAG.

SAG é o primeiro método estocástico a alcançar convergência linear e sua complexidade de iteração é $O(({\kappa }_{\text{máx.}}+e)\mathrm{eisg}(1/ϵ))$, usando o tamanho do passo $\gamma =O(1/{eu}_{\text{máx.}})$ . Essa convergência linear pode ser observada na Figura 1.Vale ressaltar que devido${eu}_{\text{máx.}}$-Função suave para qualquer ${eu}^{\prime }\ge {eu}_{\text{máx.}}$ Também${eu}^{\prime }$- Os métodos SAG suaves alcançam taxas de convergência linear para tamanhos de passo suficientemente pequenos, em contraste com os métodos SGD clássicos, que apenas alcançam taxas sublineares com sequências de tamanhos de passo decrescentes que são difíceis de ajustar na prática.

Na época, a convergência linear do SAG foi um avanço significativo porque computava apenas um gradiente estocástico (processando um único ponto de dados) em cada iteração. No entanto, a prova de convergência fornecida por Schmidt et al. [65] é muito complexa e depende de etapas verificadas por computador. Uma das principais razões pelas quais o SAG é difícil de analisar é que$g_o$ é uma estimativa tendenciosa do gradiente.

A seguir, apresentamos o método SAGA, uma variante do SAG que explora o conceito de covariáveis ​​para criar uma variante imparcial do método SAG que tem desempenho semelhante, mas é mais fácil de analisar.

---

Algoritmo 1: Método SAG

1. Parâmetros: tamanho do passo $\gamma >0$
2. inicialização:$x_0$，${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}=0\in {\mathbb{R}}^e$ para$eu=1,\dots ,e$
3. certo $o=1,\dots ,E-1$ implemento:
   uma. Seleção aleatória ik ∈ { 1 , … , n } i_k em {1, ldots, n}euo​∈{1,…,e}
   B. Calcular${\bar{g}}_o={\bar{g}}_{o-1}-\frac{1}{e}{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}^{o-1}$
   atualização${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}^o=\nabla e_{{eu}_o}(x_o)$
   d. Atualizar estimativa de gradiente${\bar{g}}_o={\bar{g}}_o+\frac{1}{e}{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}^o$
   e. Atualização$x_{o+1}=x_o-\gamma {\bar{g}}_o$
4. Saída:$x_E$

2.2.Método SAGA

Uma estimativa de gradiente imparcial básica reduzida $\nabla e_{{eu}_o}(x_o)$ A abordagem da variância se dá por meio do uso das chamadas covariáveis, ou variáveis ​​de controle.para$eu=1,\dots ,e$,configurar ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}\in {\mathbb{R}}^e$ é um vetor.Usando esses vetores, podemos converter o gradiente completo$\nabla e(x)$ Reescrito como:
$$\nabla e(x)=\frac{1}{e}\sum _{eu=1}^e(\nabla e_{eu}(x)-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}+{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu})=\frac{1}{e}\sum _{eu=1}^e\nabla e_{eu}(x)-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}+\frac{1}{e}\sum _{eu=1}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$$
$$:=\frac{1}{e}\sum _{eu=1}^e\nabla e_{eu}(x,vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê)(21)$$
que define$\nabla e_{eu}(x,vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê):=\nabla e_{eu}(x)-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}+\frac{1}{e}{\sum }_{eu=1}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ .Agora, podemos amostrar aleatoriamente um$\nabla e_{eu}(x,vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê)$ para construir o gradiente completo$\nabla e(x)$ Uma estimativa imparcial de eu ∈ { 1 , … , n } eu em {1, ldots, n}eu∈{1,…,e}, você pode aplicar o método SGD e usar a estimativa de gradiente:
$$g_o=\nabla e_{{eu}_o}(x_o,vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê)=\nabla e_{{eu}_o}(x_o)-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}+\frac{1}{e}\sum _{eu=1}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}(22)$$

para observação ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ A diferença do par de seleção$g_o$ influência, podemos$g_o=\nabla e_{{eu}_o}(x_o,vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê)$ Substitua e use$E_{eu}\sim \frac{1}{e}[{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}]=\frac{1}{e}{\sum }_{eu=1}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ Para calcular a expectativa, obtemos:
$$E\left[\Vert \nabla e_{eu}(x_o)-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}+E_{eu}\sim \frac{1}{e}[{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}-\nabla e_{eu}(x_o)]{\Vert }^2\right]\le E\left[\Vert \nabla e_{eu}(x_o)-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}{\Vert }^2\right](23)$$
O lema 2 é usado aqui, onde$X=\nabla e_{eu}(x_o)-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ .Este limite (23) mostra que se${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ juntamente com$o$ O aumento está próximo de$\nabla e_{eu}(x_o)$ , podemos obter atributos VR (12).É por isso que chamamos${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ são covariáveis ​​e podemos selecioná-las para reduzir a variância.

Por exemplo, esta abordagem também é implementada pelo método SGD² (13), onde ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}=\nabla e_{eu}(x^{\ast })$ .No entanto, isso não é comumente usado na prática porque geralmente não sabemos$\nabla e_{eu}(x^{\ast })$ .Uma opção mais prática é${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ como sabemos${\bar{x}}_{eu}\in {\mathbb{R}}^e$ gradiente próximo$\nabla e_{eu}({\bar{x}}_{eu})$ . SAGA para cada função$e_{eu}$ use um ponto de referência${\bar{x}}_{eu}\in {\mathbb{R}}^e$e use covariáveis ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}=\nabla e_{eu}({\bar{x}}_{eu})$, cada um dos quais ${\bar{x}}_{eu}$ será nossa última avaliação$e_{eu}$ apontar. Usando essas covariáveis, podemos construir uma estimativa de gradiente, seguindo (22), fornecendo:
$$g_o=\nabla e_{{eu}_o}(x_o)-\nabla e_{{eu}_o}({\bar{x}}_{{eu}_o})+\frac{1}{e}\sum _{eu=1}^e\nabla e_{eu}({\bar{x}}_{eu})(24)$$

Para implementar SAGA podemos armazenar gradientes $\nabla e_{eu}({\bar{x}}_{eu})$ em vez de$e$ ponto de referência${\bar{x}}_{eu}$ .Quer dizer, suponha${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}=\nabla e_{eu}({\bar{x}}_{eu})$ para j ∈ { 1 , … , n } j em {1, ldots, n}eu∈{1,…,e}, em cada iteração, atualizamos um gradiente estocástico como SAG ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$。

Algoritmo 2 SAGA

1. Parâmetros: tamanho do passo $\gamma >0$
2. inicialização:$x_0$，${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}=0\in {\mathbb{R}}^e$ para$eu=1,\dots ,e$
3. conduta $o=1,\dots ,E-1$ iterações:
   uma. Seleção aleatória ik ∈ { 1 , … , n } i_k em {1, ldots, n}euo​∈{1,…,e}
   b. Salvar valor antigo${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{\text{velho}}={vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}$
   atualização${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}=\nabla e_{{eu}_o}(x_o)$
   Atualizar$x_{o+1}=x_o-\gamma ({vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{\text{velho}}+{\bar{g}}_o)$
   e. Atualizar estimativa de gradiente${\bar{g}}_o={\bar{g}}_{o-1}+\frac{1}{e}({vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{{eu}_o}-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{\text{velho}})$
4. Saída:$x_E$

O método SAGA tem a mesma complexidade de iteração que SAG $O(({\kappa }_{\text{máx.}}+e)\mathrm{eisg}(1/ϵ))$, usando o tamanho do passo $\gamma =O(1/{eu}_{\text{máx.}})$ , mas a prova é muito mais simples.No entanto, assim como o SAG, o método SAGA requer armazenamento$e$ vetores auxiliares${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}\in {\mathbb{R}}^e$ para$eu=1,\dots ,e$, o que significa a necessidade $O(ee)$ de espaço de armazenamento.quando$e$ e$e$ Quando ambos são grandes, isso pode não ser viável. Na próxima seção, detalhamos como reduzir esse requisito de memória para modelos comuns, como modelos lineares regularizados.

quando puder $e$ Quando dois vetores auxiliares são armazenados na memória, SAG e SAGA tendem a se comportar de forma semelhante. Se este requisito de memória for muito alto, o método SVRG, que revisaremos na próxima seção, é uma boa alternativa. O método SVRG atinge a mesma taxa de convergência e é quase tão rápido na prática, mas requer apenas$O(e)$ de memória, para questões gerais.

2.3.Método SVRG

Antes do surgimento do método SAGA, alguns trabalhos iniciais introduziram covariáveis ​​​​pela primeira vez para resolver o problema de alta memória exigido pelo método SAG.Esses estudos baseiam-se em um ponto de referência fixo$\bar{x}\in {\mathbb{R}}^e$ covariáveis, calculamos o gradiente completo naquele ponto$\nabla e(\bar{x})$ .armazenando pontos de referência$\bar{x}$ e o gradiente completo correspondente$\nabla e(\bar{x})$, podemos fazer isso sem armazenar cada $\nabla e_{eu}(\bar{x})$ No caso, use${\bar{x}}_{eu}=\bar{x}$ para todos$eu$ para implementar a atualização (24).Especificamente, em vez de armazenar esses vetores, utilizamos os pontos de referência armazenados em cada iteração$\bar{x}$ calcular$\nabla e_{{eu}_o}(\bar{x})$ . Este método foi originalmente proposto por diferentes autores com nomes diferentes, mas posteriormente foi unificado como método SVRG, seguindo a nomenclatura de [28] e [84].

Formalizamos o método SVRG no Algoritmo 3.

Usando (23), podemos derivar a estimativa do gradiente $g_o$ A variância de é limitada:
$$E\left[\Vert g_o-\nabla e(x_o){\Vert }^2\right]\le E\left[\Vert \nabla e_{eu}(x_o)-\nabla e_{eu}(\bar{x}){\Vert }^2\right]\le {eu}_{\text{máx.}}^2\Vert x_o-\bar{x}{\Vert }^2$$
onde a segunda desigualdade usa cada$e_{eu}$ de${eu}_{eu}$-Suavidade.

Vale ressaltar que o ponto de referência $\bar{x}$ Quanto mais próximo do ponto atual$x_o$, menor será a variância da estimativa do gradiente.

Para que o método SVRG seja eficaz, precisamos atualizar os pontos de referência com frequência $\bar{x}$ (exigindo assim o cálculo do gradiente total) é ponderado em relação ao benefício da variância reduzida.Por esta razão, cada um de nós$para$ Atualize o ponto de referência uma vez a cada iteração para torná-lo próximo de$x_o$ (Ver linha 11 do Algoritmo II-C).Ou seja, o método SVRG contém dois loops: um loop externo$e$, onde o gradiente de referência é calculado $\nabla e({\bar{x}}_{e-1})$(linha 4), e um loop interno onde o ponto de referência é fixo e a iteração interna é atualizada com base na etapa do gradiente estocástico (22) $x_o$(Linha 10).

Ao contrário do SAG e SAGA, o SVRG requer apenas $O(e)$ de memória. As desvantagens do SVRG incluem: 1) Temos um parâmetro extra$para$, ou seja, o comprimento do loop interno, precisa ser ajustado 2) Dois gradientes precisam ser calculados para cada iteração, e o gradiente completo precisa ser calculado sempre que o ponto de referência for alterado;

Johnson e Zhang [28] mostraram que SVRG tem complexidade iterativa $O(({\kappa }_{\text{máx.}}+e)\mathrm{eisg}(1/ϵ))$ , semelhante a SAG e SAGA.Este é o número de loops dentro da hipótese$para$ da coleção { 1 , … , m } {1, pontos, m}{1,…,eu} Obtido sob condição de amostragem uniforme, onde${eu}_{\text{máx.}}$，$\mu$, tamanho do passo $\gamma$ e$para$ Certas dependências devem ser satisfeitas entre eles.Na prática, usando$\gamma =O(1/{eu}_{\text{máx.}})$ e comprimento do loop interno$para=e$, o SVRG tende a ter um bom desempenho, que é exatamente a configuração que usamos na Figura 1.

Agora, existem muitas variações do método SVRG original.Por exemplo, algumas variações usam$para$ distribuição alternativa [32], algumas variantes permitem a forma$O(1/{eu}_{\text{máx.}})$ O tamanho do passo [27], [33], [35].Existem também algumas variações usando$\nabla e(\bar{x})$ aproximação de minilote para reduzir o custo dessas avaliações de gradiente completo e aumentar o tamanho do minilote para preservar as propriedades de VR.Existem também algumas variantes onde as atualizações são repetidas no loop interno de acordo com [54]$g_o$：
[ g_k = nome f_{i_k}(x_k) - nome f_{i_k}(x_{k-1}) + g_{k-1} quad (25) ]
Isso fornece uma aproximação mais local. O uso desta variante de atualização contínua (25) mostra vantagens únicas na minimização de funções não convexas, conforme discutimos brevemente na Seção IV.Finalmente, observe que o SVRG pode aproveitar$\nabla e({\bar{x}}_e)$ valor para ajudar a decidir quando encerrar o algoritmo.

Algoritmo 3 Método SVRG

1. Parâmetros: tamanho do passo $\gamma >0$
2. Inicializar ponto de referência ${\bar{x}}_0=x_0\in {\mathbb{R}}^e$
3. Realizar circulação externa $e=1,2,\dots$：
   a. Calcular e armazenar$\nabla e({\bar{x}}_{e-1})$
   B. Suponha$x_0={\bar{x}}_{e-1}$
   c. Selecione o número de iterações do loop interno.$para$
   d. Realizar circulação interna$o=0,1,\dots ,para-1$：
   seleção aleatória ik ∈ { 1 , … , n } i_k em {1, ldots, n}euo​∈{1,…,e}
   Cálculo$g_o=\nabla e_{{eu}_o}(x_o)-\nabla e_{{eu}_o}({\bar{x}}_{e-1})+\nabla e({\bar{x}}_{e-1})$
   iii. Atualização$x_{o+1}=x_o-\gamma g_o$
   e. Atualizar ponto de referência${\bar{x}}_e=x_{para}$

2.4. SDCA e suas variantes

Uma desvantagem dos métodos SAG e SVRG é que o tamanho do passo depende de valores desconhecidos que podem ser desconhecidos em alguns problemas. ${eu}_{\text{máx.}}$ . Antes do SVRG, o método SDCA [70], como um dos primeiros métodos de RV, estendeu a pesquisa sobre métodos de descida coordenada para problemas de soma finita. A ideia por trás do SDCA e suas variantes é que as coordenadas do gradiente forneçam uma estimativa natural do gradiente que reduz a variância.Especificamente, suponha j ∈ { 1 , … , d } j em {1, ldots, d}eu∈{1,…,e}e definir ${\nabla }_{eu}e(x):=\left(\frac{\partial e(x)}{\partial x_{eu}}\right)e_{eu}$ é o décimo de (f (x))$eu$ derivadas em direções coordenadas, onde$e_{eu}\in {\mathbb{R}}^e$ É o primeiro$eu$ vetor unitário.Uma propriedade chave das derivadas de coordenadas é que${\nabla }_{eu}e(x^{\ast })=0$, porque sabemos $\nabla e(x^{\ast })=0$ .A derivada disso com cada ponto de dados$\nabla e_{eu}$ diferente, o último é$x^{\ast }$ pode não ser zero. Portanto temos:
$$\Vert \nabla e(x)-{\nabla }_{eu}e(x){\Vert }^2\to 0\text{quando}x\to x^{\ast }(26)$$
Isso significa que a derivada coordenada satisfaz a propriedade de redução de variância (12).Além disso, podemos usar${\nabla }_{eu}e(x)$ construir$\nabla e(x)$ uma estimativa imparcial de.Por exemplo, suponha$eu$ é da coleção { 1 , … , d } {1, ldots, d}{1,…,e} Um índice uniformemente selecionado aleatoriamente em .Portanto, para qualquer eu ∈ { 1 , … , d } eu em {1, ldots, d}eu∈{1,…,e},Nós temos $P[eu=eu]=\frac{1}{e}$ . portanto,$e\times {\nabla }_{eu}e(x)$ sim$\nabla e(x)$ Uma estimativa imparcial de porque:
$$E\left[e{\nabla }_{eu}e(x)\right]=e\sum _{eu=1}^{e}P[eu=eu]\frac{\partial e(x)}{\partial x_{eu}}{e}_{eu}=\sum _{eu=1}^e\frac{\partial e(x)}{\partial x_{eu}}{e}_{eu}=\nabla e(x)$$

portanto,${\nabla }_{eu}e(x)$ Tem todas as propriedades ideais que esperaríamos para VR estimando gradientes completos, sem a necessidade de usar covariáveis. Uma desvantagem de usar esse gradiente de coordenadas é que ele é computacionalmente caro para o nosso problema de soma (2).Isso ocorre porque o cálculo${\nabla }_{eu}e(x)$ Precisa percorrer todo o conjunto de dados porque${\nabla }_{eu}e(x)=\frac{1}{e}{\sum }_{eu=1}^e{\nabla }_{eu}{e}_{eu}(x)$ . Portanto, usar derivadas coordenadas parece incompatível com a estrutura do nosso problema de soma. No entanto, muitas vezes podemos reescrever o problema original (2) numa chamada formulação dual, onde as derivadas coordenadas podem explorar a estrutura inerente.

Por exemplo, a fórmula dupla do modelo linear regularizado L2 (15) é:
$${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}^{\ast }\in \arg \underset{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê\in {\mathbb{R}}^e}{máx.}\frac{1}{e}\sum _{eu=1}^e-{\ell }_{eu}^{\ast }(-{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu})-\frac{\lambda }{2}{\Vert \frac{1}{\lambda }\sum _{eu=1}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}{a}_{eu}\Vert }^2(27)$$
em${\ell }_{eu}^{\ast }(vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê)$ sim${\ell }_{eu}$ conjugado convexo.Podemos usar mapeamento$x=\frac{1}{\lambda }{\sum }_{eu=1}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}{a}_{eu}$ para restaurar o problema original (15)$x$ variável.resolverá${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}^{\ast }$ Substituindo no lado direito do mapeamento acima, podemos obter a solução de (15)$x^{\ast }$。

Observe que esse duplo problema tem $e$ variáveis ​​reais${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}\in \mathbb{R}$ , correspondendo a um para cada amostra de treinamento.Além disso, cada função de perda dupla${\ell }_{eu}^{\ast }$ apenas${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ A função. Ou seja, o primeiro termo da função de perda é separável coordenadamente. Esta separabilidade em coordenadas, aliada à forma simples do segundo termo, permite-nos implementar de forma eficiente o método de subida de coordenadas.Na verdade, Shalev-Shwartz e Zhang mostraram que a subida coordenada neste problema tem complexidade iterativa semelhante a SAG, SAGA e SVRG$O(({\kappa }_{\text{máx.}}+e)\mathrm{eisg}(1/ϵ))$。

O custo da iteração e a estrutura do algoritmo também são muito semelhantes: soma por rastreamento ${\sum }_{eu=1}^e{vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}{a}_{eu}$ Para lidar com o segundo termo em (27), cada iteração de subida de coordenadas duplas precisa considerar apenas uma amostra de treinamento, e o custo de cada iteração é o mesmo que$e$ Nada para fazer.Além disso, podemos usar uma pesquisa de linha 1D para calcular com eficiência o tamanho do passo para maximizar o máximo possível.${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ Duplo objetivo da função.Isto significa que mesmo sem${eu}_{\text{máx.}}$ Ou com o conhecimento de quantidades relevantes, também é possível obter tempos de execução rápidos no pior caso para métodos de VR.

3. Questões práticas de redução de variância

Para implementar o método básico de redução de variância (RV) e obter um desempenho razoável, vários problemas de implementação devem ser abordados. Nesta seção, discutimos vários assuntos não abordados acima.

3.1.Tamanho do passo de configuração SAG/SAGA/SVRG

No campo dos algoritmos de otimização, especialmente em métodos de redução de variação, como gradiente médio estocástico (SAG), algoritmo de gradiente médio estocástico (SAGA) e gradiente estocástico (SVRG), a configuração do tamanho do passo é uma questão fundamental.Embora para o método estocástico de subida de coordenadas duplas (SDCA) possamos usar o objetivo duplo para determinar o tamanho do passo, a base teórica para os métodos de variáveis ​​originais de SAG, SAGA e SVRG é que o tamanho do passo deve ser$\gamma =O\left(\frac{1}{{eu}_{\text{máx.}}}\right)$ forma.No entanto, em aplicações práticas, muitas vezes não sabemos${eu}_{\text{máx.}}$ O valor exato de e o uso de outros tamanhos de passo pode proporcionar melhor desempenho.

Uma estratégia clássica para definir o tamanho do passo no método de descida gradiente total (GD completo) é a pesquisa de linha Armijo.dado ponto atual$x_o$ e direção de pesquisa$g_o$, Pesquisa de linha Armijo em ${\gamma }_o$ é realizado na linha, que é definida como γ k ∈ { γ : xk + γ gk } gama_k em {gama : x_k + gama g_k}γo​∈{γ:xo​+γgo​}, e a função deve ser suficientemente reduzida, ou seja:
$$e(x_o+{\gamma }_o{g}_o)<e(x_o)-c{\gamma }_o\Vert \nabla e(x_o){\Vert }^2$$
No entanto, esta abordagem requer múltiplas etapas candidatas${\gamma }_o$ Cálculo$e(x_o+{\gamma }_o{g}_o)$, que avalia $e(x)$ Custo proibitivo quando se trata de percorrer todo o conjunto de dados.

Para resolver este problema, um método de variação aleatória pode ser usado para encontrar aqueles que atendem às seguintes condições ${\gamma }_o$：
$$e_{eu\; sei}(x_o+{\gamma }_o{g}_o)<e_{eu\; sei}(x_o)-c{\gamma }_o\Vert \nabla e_{eu\; sei}(x_o){\Vert }^2$$
Esta abordagem geralmente funciona bem na prática, especialmente quando$\Vert \nabla e_{eu\; sei}(x_o)\Vert$ não está perto de zero, embora não exista actualmente nenhuma teoria que apoie esta abordagem.

Além disso, Mairal propôs uma "técnica Bottou" para definir o tamanho do passo na prática. Este método realiza uma pesquisa binária pegando uma pequena porção do conjunto de dados (por exemplo, 5%) para tentar encontrar o tamanho ideal do passo em uma única passagem por esta amostra. Semelhante à busca linear Armijo, este método geralmente funciona bem na prática, mas novamente carece de uma base teórica.

Observe que o conteúdo acima é uma reformulação do texto original, usando o formato Markdown para representar fórmulas e variáveis ​​matemáticas.

No entanto, o método SDCA também apresenta algumas desvantagens.Primeiro, é necessário calcular o conjugado convexo${\ell }_{eu}^{\ast }$ em vez de um simples gradiente. Não temos um equivalente diferencial automático para conjugados convexos, portanto isso pode aumentar o esforço de implementação. Trabalhos recentes propuseram métodos SDCA "dual-free" que não requerem conjugação e, em vez disso, usam gradientes diretamente. Entretanto, nesses métodos não é mais possível rastrear o alvo duplo para definir o tamanho do passo.Em segundo lugar, embora a SDCA exija apenas$O(e+e)$ memória para resolver o problema (15), mas para esta categoria de problema, SAG/SAGA só precisa$O(e+e)$ de memória (veja a Seção 3).Uma variante do SDCA adequada para problemas mais gerais com SAG/SAGA$O(ee)$ memória porque${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu}$ tornar-se tendo$e$ vetor de elementos. Uma última desvantagem sutil do SDCA é que ele assume implicitamente uma forte constante de convexidade$\mu$ igual$\lambda$ .para$\mu$ mais do que o$\lambda$ problema, o método VR original geralmente supera significativamente o SDCA.

3.2. Determinação das condições de rescisão

No campo da otimização de algoritmos, muitas vezes confiamos em resultados teóricos de complexidade iterativa para prever o pior número de iterações necessárias para que um algoritmo atinja uma precisão específica. No entanto, estes limites teóricos baseiam-se frequentemente em algumas constantes que não podemos prever e, em aplicações práticas, o algoritmo pode muitas vezes atingir a precisão esperada em menos iterações. Portanto, precisamos definir alguns critérios de teste para determinar quando o algoritmo deve ser finalizado.

No método tradicional de gradiente descendente completo (GD completo), geralmente usamos a norma do gradiente $\Vert \nabla e(x_o)\Vert$ Ou alguma outra quantidade relacionada a isso para decidir quando parar a iteração.Para o método SVRG podemos adotar o mesmo critério mas usar$\Vert \nabla e({\bar{x}}_e)\Vert$ como base para julgamento.Para o método SAG/SAGA, embora não calculemos explicitamente o gradiente completo, a quantidade $ g_{bar{k}} $ irá gradualmente se aproximar$\nabla e(x_o)$, portanto, use $\Vert g_{\bar{o}}\Vert$ como condição de parada é uma heurística razoável.

No método SDCA, com algum trabalho adicional de registro, podemos rastrear o gradiente do objetivo duplo sem adicionar custo assintótico adicional.Além disso, uma abordagem mais sistemática seria acompanhar a dupla lacuna, embora isso aumentasse a$O(e)$ custo, mas é capaz de fornecer condições de rescisão com provas de lacuna dupla. Além disso, com base na condição de otimalidade de alvos fortemente convexos, o método MISO adota um método de princípios baseado no limite inferior quadrático [41].

A seguir estão fórmulas matemáticas e variáveis ​​expressas no formato Markdown:

• Norma de gradiente:$\Vert \nabla e(x_o)\Vert$
• Norma de gradiente no método SVRG:$\Vert \nabla e({\bar{x}}_e)\Vert$
• A quantidade de gradiente de aproximação no método SAG/SAGA: $ g_{bar{k}} $
• Aumento do custo por iteração:$O(e)$
• Método MISO
• limite inferior quadrático

Observe que o conteúdo acima é uma reformulação do texto original, usando o formato Markdown para representar fórmulas e variáveis ​​matemáticas.

3.3. Reduza os requisitos de memória

Embora o algoritmo Stochastic Variational Reduction of Gradient (SVRG) elimine os requisitos de memória dos métodos anteriores de redução de variação, em aplicações práticas, os algoritmos SAG (Stochastic Average Gradient Descent) e SAGA (Stochastic Average Gradient Descent with Gradient Accumulation) são usados ​​em muitos problemas. . tendem a exigir menos iterações do que o algoritmo SVRG.Isso desencadeou um pensamento: existem certos problemas que permitem que o SAG/SAGA$O(ee)$ Os requisitos de memória são implementados abaixo. Esta seção explora uma classe de modelos lineares para os quais os requisitos de memória podem ser significativamente reduzidos.

Considere um modelo linear onde cada função $e_{eu}(x)$ Pode ser expresso como${\xi }_{eu}({\mathbf{a}}_{eu}^{\top }x)$ .certo$x$ A derivada fornece a forma gradiente:
$$\nabla e_{eu}(x)={\xi }^{\prime }({\mathbf{a}}_{eu}^{\top }x){\mathbf{a}}_{eu}$$
aqui,${\xi }^{\prime }$ expressar$\xi$ a derivada de.Supondo que tenhamos acesso direto aos autovetores${\mathbf{a}}_{eu}$, então, para implementar o método SAG/SAGA, precisamos apenas armazenar o escalar $\xi ({\mathbf{a}}_{eu}^{\top }x)$ .Desta forma, os requisitos de memória variam de$O(ee)$ reduzido a$O(e)$ . O algoritmo SVRG também pode tirar vantagem desta estrutura de gradientes: armazenando este$e$ escalar, podemos reduzir o número de avaliações de gradiente necessárias por iteração "interna" do SVRG para 1 para esta classe de problemas.

Existem outros tipos de problemas, como modelos gráficos probabilísticos, que também oferecem a possibilidade de reduzir os requisitos de memória [66]. Através de estrutura de dados específica e otimização de algoritmo, os recursos de memória exigidos pelo algoritmo em tempo de execução podem ser ainda mais reduzidos.

A seguir estão fórmulas matemáticas e variáveis ​​expressas no formato Markdown:

• Função do modelo linear:$e_{eu}(x)={\xi }_{eu}({\mathbf{a}}_{eu}^{\top }x)$
• Expressão gradiente:$\nabla e_{eu}(x)={\xi }^{\prime }({\mathbf{a}}_{eu}^{\top }x){\mathbf{a}}_{eu}$
• Vetor de recursos:${\mathbf{a}}_{eu}$
• Os requisitos de memória variam de $O(ee)$ Reduzir para$O(e)$。

3.4. Processamento de gradientes esparsos

Em alguns problemas, o gradiente $\nabla e_{eu}(x)$ Pode conter um grande número de valores zero, como um modelo linear com recursos esparsos.Neste caso, o algoritmo tradicional de descida gradiente estocástica (SGD) pode ser implementado de forma eficiente, com complexidade computacional linear no número de elementos diferentes de zero no gradiente, que geralmente é muito menor que a dimensão do problema$e$ . No entanto, nos métodos padrão de redução variacional (VR), esta vantagem não é explorada. Felizmente, existem duas maneiras conhecidas de melhorar isso.

A primeira melhoria foi proposta por Schmidt et al., que aproveita a simplicidade do processo de atualização e implementa uma variante de computação "on-the-fly" tal que o custo de cada iteração é proporcional ao número de números diferentes de zero. elementos.Tomando o SAG como exemplo (mas esta abordagem funciona para todas as variantes), isso é feito não armazenando o vetor completo após cada iteração${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu\; sei}$, mas calcula apenas aqueles correspondentes a elementos diferentes de zero ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu{o}_{eu}}$, atualizando cada variável desde a última vez que esse elemento foi diferente de zero ${vocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocêocê}_{eu{o}_{eu}}$。

O segundo método de melhoria foi proposto por Leblond et al para SAGA, que atualiza a fórmula. $x_{o+1}=x_o-\gamma (\nabla e_{eu\; sei}(x_o)-\nabla e_{eu\; sei}({\bar{x}}_{eu\; sei})+{\bar{g}}_o)$ Aleatoriedade adicional é introduzida. aqui,$\nabla e_{eu\; sei}(x_o)$ e$\nabla e_{eu\; sei}({\bar{x}}_{eu\; sei})$ é escasso e${\bar{g}}_o$ é denso.Neste método, o termo denso$({\bar{g}}_o{)}_{eu}$ Cada componente de é substituído por$c_{eu}({\bar{g}}_o{)}_{eu}$,em $c\in {\mathbb{R}}^e$ é um vetor esparso aleatório cujo conjunto de suporte está contido em$\nabla e_{eu\; sei}(x_o)$ , e espera-se que seja um vetor constante com todos os elementos iguais a 1. Dessa forma, o processo de atualização permanece imparcial (embora agora esparso), e o aumento da variância não afeta a taxa de convergência do algoritmo. Mais detalhes são fornecidos por Leblond et al.

A seguir estão fórmulas matemáticas e variáveis ​​expressas no formato Markdown:

• gradiente:$\nabla e_{eu}(x)$
• Atualização SGD:$x_{o+1}=x_o-\gamma (\nabla e_{eu\; sei}(x_o)-\nabla e_{eu\; sei}({\bar{x}}_{eu\; sei})+{\bar{g}}_o)$
• Gradiente esparso:$\nabla e_{eu\; sei}(x_o)$ e$\nabla e_{eu\; sei}({\bar{x}}_{eu\; sei})$
• Gradiente denso:${\bar{g}}_o$
• Vetores esparsos aleatórios:$c$
• Espera um vetor constante: um vetor com todos os elementos iguais a 1.