Os métodos de aproximação estocástica são uma família de métodos iterativos tipicamente usados para problemas de busca de raízes ou para problemas de otimização. As regras de atualização recursiva dos métodos de aproximação estocástica podem ser usadas, entre outras coisas, para resolver sistemas lineares quando os dados coletados são corrompidos por ruído, ou para aproximar valores extremos de funções que não podem ser computadas diretamente, mas apenas estimadas via observações ruidosas. Em resumo, os algoritmos de aproximação estocástica lidam com uma função da forma
f ( θ ) =
E
ξ
[ F ( θ , ξ ) ]
{\textstyle f(\theta )=\operatorname {E} _{\xi }[F(\theta ,\xi )]}
que é o valor esperado de uma função que depende de uma variável aleatória
ξ
{\textstyle \xi }
. O objetivo é recuperar propriedades de tal função
f
{\textstyle f}
sem avaliá-la diretamente. Em vez disso, algoritmos de aproximação estocástica usam amostras aleatórias de
F ( θ , ξ )
{\textstyle F(\theta ,\xi )}
para aproximar eficientemente propriedades de
f
{\textstyle f}
, como zeros ou extremos. Recentemente, as aproximações estocásticas encontraram extensas aplicações nas áreas de estatística e aprendizado de máquina, especialmente em configurações com big data. Estas aplicações variam desde métodos e algoritmos de otimização estocástica, a formas online do algoritmo EM, aprendizado por reforço via diferenças temporais, e aprendizado profundo (deep learning), entre outros. Algoritmos de aproximação estocástica também têm sido usados nas ciências sociais para descrever dinâmicas coletivas: a jogada fictícia (fictitious play) na teoria do aprendizado e os algoritmos de consenso podem ser estudados usando a sua teoria. Os algoritmos mais antigos, e prototípicos, deste tipo são os algoritmos de Robbins-Monro e Kiefer-Wolfowitz, introduzidos respetivamente em 1951 e 1952.
Algoritmo de Robbins-Monro O algoritmo de Robbins-Monro, introduzido em 1951 por Herbert Robbins e Sutton Monro, apresentou uma metodologia para resolver um problema de busca de raízes, onde a função é representada como um valor esperado. Assuma que temos uma função
M ( θ )
{\textstyle M(\theta )}
, e uma constante
α
{\textstyle \alpha }
, de modo que a equação
M ( θ ) = α
{\textstyle M(\theta )=\alpha }
tenha uma raiz única em
θ
∗
.
{\textstyle \theta ^{*}.}
Presume-se que, embora não possamos observar diretamente a função
M ( θ ) ,
{\textstyle M(\theta ),}
podemos, em vez disso, obter medições da variável aleatória
N ( θ )
{\textstyle N(\theta )}
onde
E [ N ( θ ) ] = M ( θ )
{\textstyle \operatorname {E} [N(\theta )]=M(\theta )}
. A estrutura do algoritmo consiste então em gerar iterações da forma:
θ
n + 1
=
θ
n
−
a
n
( N (
θ
n
) − α )
{\displaystyle \theta _{n+1}=\theta _{n}-a_{n}(N(\theta _{n})-\alpha )}
Aqui,
a
1
,
a
2
, ...
{\displaystyle a_{1},a_{2},\dots }
é uma sequência de tamanhos de passo positivos. Robbins e Monro provaram, Teorema 2 que
θ
n
{\displaystyle \theta _{n}}
converge em
L
2
{\displaystyle L^{2}}
(e, portanto, também em probabilidade) para
θ
∗
{\displaystyle \theta ^{*}}
, e Blum provou mais tarde que a convergência é, na verdade, com probabilidade um, desde que:
N ( θ )
{\textstyle N(\theta )}
seja uniformemente limitada,
M ( θ )
{\textstyle M(\theta )}
seja não decrescente,
M ′
(
θ
∗
)
{\textstyle M'(\theta ^{*})}
exista e seja positiva, e A sequência
a
n
{\textstyle a_{n}}
satisfaça os seguintes requisitos:
∑
n = 0
∞
a
n
= ∞
e
∑
n = 0
∞
a
n
2
< ∞
{\displaystyle \qquad \sum _{n=0}^{\infty }a_{n}=\infty \quad {\mbox{ e }}\quad \sum _{n=0}^{\infty }a_{n}^{2}<\infty \quad }
Uma sequência particular de passos que satisfaz essas condições, e que foi sugerida por Robbins-Monro, tem a forma:
a
n
= a
/
n
{\textstyle a_{n}=a/n}
, para
a > 0
{\textstyle a>0}
. Outras séries, como
a
n
=
1
n ln n
,
1
n ln n ln ln n
, ...
{\displaystyle a_{n}={\frac {1}{n\ln n}},{\frac {1}{n\ln n\ln \ln n}},\dots }
são possíveis, mas para calcular a média do ruído em
N ( θ )
{\textstyle N(\theta )}
, a condição acima deve ser atendida.
Exemplo Considere o problema de estimar a média
θ
∗
{\displaystyle \theta ^{*}}
de uma distribuição de probabilidade a partir de um fluxo de amostras independentes
X
1
,
X
2
, ...
{\displaystyle X_{1},X_{2},\dots }
. Seja
N ( θ ) := θ − X
{\displaystyle N(\theta ):=\theta -X}
, então a solução única para
E [ N ( θ ) ] = 0
{\textstyle \operatorname {E} [N(\theta )]=0}
é a média desejada
θ
∗
{\displaystyle \theta ^{*}}
. O algoritmo RM dá-nos
θ
n + 1
=
θ
n
−
a
n
(
θ
n
−
X
n
)
{\displaystyle \theta _{n+1}=\theta _{n}-a_{n}(\theta _{n}-X_{n})}
Isto é equivalente à descida de gradiente estocástico com a função de perda
L ( θ ) =
1 2
‖ X − θ
‖
2
{\displaystyle L(\theta )={\frac {1}{2}}\|X-\theta \|^{2}}
. Também é equivalente a uma média ponderada:
θ
n + 1
= ( 1 −
a
n
)
θ
n
+
a
n
X
n
{\displaystyle \theta _{n+1}=(1-a_{n})\theta _{n}+a_{n}X_{n}}
No geral, se existe alguma função
L
{\displaystyle L}
tal que
∇ L ( θ ) = N ( θ ) − α
{\displaystyle \nabla L(\theta )=N(\theta )-\alpha }
, então o algoritmo de Robbins-Monro é equivalente à descida de gradiente estocástico com a função de perda
L ( θ )
{\displaystyle L(\theta )}
. No entanto, o algoritmo RM não exige que
L
{\displaystyle L}
exista para convergir.
Resultados de complexidade Se
f ( θ )
{\textstyle f(\theta )}
for duas vezes continuamente diferenciável, e fortemente convexa, e o minimizador de
f ( θ )
{\textstyle f(\theta )}
pertencer ao interior de
Θ
{\textstyle \Theta }
, então o algoritmo de Robbins-Monro alcançará a taxa de convergência assintoticamente ótima, com respeito à função objetivo, sendo
E [ f (
θ
n
) −
f
∗
] = O ( 1
/
n )
{\textstyle \operatorname {E} [f(\theta _{n})-f^{*}]=O(1/n)}
, onde
f
∗
{\textstyle f^{*}}
é o valor mínimo de
f ( θ )
{\textstyle f(\theta )}
sobre
θ ∈ Θ
{\textstyle \theta \in \Theta }
. Por outro lado, no caso convexo geral, onde carecemos tanto da suposição de suavidade quanto de forte convexidade, Nemirovski e Yudin mostraram que a taxa de convergência assintoticamente ótima, com relação aos valores da função objetivo, é
O ( 1
/
n
)
{\textstyle O(1/{\sqrt {n}})}
. Eles também provaram que essa taxa não pode ser melhorada.
Desenvolvimentos subsequentes e cálculo de média de Polyak-Ruppert Embora o algoritmo de Robbins-Monro seja teoricamente capaz de alcançar
O ( 1
/
n )
{\textstyle O(1/n)}
sob a suposição de diferenciabilidade contínua dupla e forte convexidade, ele pode ter um desempenho bastante fraco na implementação. Isto deve-se principalmente ao facto de que o algoritmo é muito sensível à escolha da sequência de tamanhos de passo, e a suposta política de tamanho de passo assintoticamente ideal pode ser bastante prejudicial no início. Chung (1954) e Fabian (1968) mostraram que alcançaríamos a taxa de convergência ótima
O ( 1
/
n
)
{\textstyle O(1/{\sqrt {n}})}
com
a
n
=
▽
2
f (
θ
∗
)
− 1
/
n
{\textstyle a_{n}=\bigtriangledown ^{2}f(\theta ^{*})^{-1}/n}
(ou
a
n
=
1
( n
M ′
(
θ
∗
) )
{\textstyle a_{n}={\frac {1}{(nM'(\theta ^{*}))}}}
). Lai e Robbins desenvolveram procedimentos adaptativos para estimar
M ′
(
θ
∗
)
{\textstyle M'(\theta ^{*})}
de tal modo que
θ
n
{\textstyle \theta _{n}}
tenha variância assintótica mínima. Contudo, a aplicação de tais métodos ótimos requer muita informação a priori que é difícil de obter na maioria das situações. Para superar essa deficiência, Polyak (1991) e Ruppert (1988) desenvolveram independentemente um novo algoritmo ótimo baseado na ideia de calcular a média das trajetórias. Polyak e Juditsky também apresentaram um método para acelerar o Robbins-Monro para problemas de busca de raízes lineares e não lineares através do uso de passos mais longos, e do cálculo da média das iterações. O algoritmo teria a seguinte estrutura:
θ
n + 1
−
θ
n
=
a
n
( α − N (
θ
n
) ) ,
θ ̄
n
=
1 n
∑
i = 0
n − 1
θ
i
{\displaystyle \theta _{n+1}-\theta _{n}=a_{n}(\alpha -N(\theta _{n})),\qquad {\bar {\theta }}_{n}={\frac {1}{n}}\sum _{i=0}^{n-1}\theta _{i}}
A convergência de
θ ̄
n
{\displaystyle {\bar {\theta }}_{n}}
para a raiz única
θ
∗
{\displaystyle \theta ^{*}}
baseia-se na condição de que a sequência de passos
{
a
n
}
{\displaystyle \{a_{n}\}}
diminua suficientemente devagar. Isso é A1)
a
n
→ 0 ,
a
n
−
a
n + 1
a
n
= o (
a
n
)
{\displaystyle a_{n}\rightarrow 0,\qquad {\frac {a_{n}-a_{n+1}}{a_{n}}}=o(a_{n})}
Portanto, a sequência
a
n
=
n
− α
{\textstyle a_{n}=n^{-\alpha }}
com
0 < α < 1
{\textstyle 0<\alpha <1}
satisfaz esta restrição, mas
α = 1
{\textstyle \alpha =1}
não, daí os passos mais longos. Sob as suposições delineadas no algoritmo de Robbins-Monro, a modificação resultante resultará na mesma taxa de convergência assintoticamente ótima
O ( 1
/
n
)
{\textstyle O(1/{\sqrt {n}})}
, mas com uma política de tamanho de passo mais robusta. Antes disto, a ideia de usar passos mais longos e calcular a média das iterações já havia sido proposta por Nemirovski e Yudin para os casos de resolução do problema de otimização estocástica com objetivos convexos contínuos e para problemas de ponto de sela convexo-côncavo. Observou-se que esses algoritmos atingem a taxa não assintótica
O ( 1
/
n
)
{\textstyle O(1/{\sqrt {n}})}
. Um resultado mais geral é dado no Capítulo 11 de Kushner e Yin definindo o tempo interpolado
t
n
=
∑
i = 0
n − 1
a
i
{\textstyle t_{n}=\sum _{i=0}^{n-1}a_{i}}
, o processo interpolado
θ
n
( ⋅ )
{\textstyle \theta ^{n}(\cdot )}
e o processo normalizado interpolado
U
n
( ⋅ )
{\textstyle U^{n}(\cdot )}
como
θ
n
( t ) =
θ
n + i
,
U
n
( t ) = (
θ
n + i
−
θ
∗
)
/
a
n + i
para
t ∈ [
t
n + i
−
t
n
,
t
n + i + 1
−
t
n
) , i ≥ 0
{\displaystyle \theta ^{n}(t)=\theta _{n+i},\quad U^{n}(t)=(\theta _{n+i}-\theta ^{*})/{\sqrt {a_{n+i}}}\quad {\mbox{para}}\quad t\in [t_{n+i}-t_{n},t_{n+i+1}-t_{n}),i\geq 0}
Seja a média da iteração
Θ
n
=
a
n
t
∑
i = n
n + t
/
a
n
− 1
θ
i
{\displaystyle \Theta _{n}={\frac {a_{n}}{t}}\sum _{i=n}^{n+t/a_{n}-1}\theta _{i}}
e o erro normalizado associado seja
U ^
n
( t ) =
a
n
t
∑
i = n
n + t
/
a
n
− 1
(
θ
i
−
θ
∗
)
{\displaystyle {\hat {U}}^{n}(t)={\frac {\sqrt {a_{n}}}{t}}\sum _{i=n}^{n+t/a_{n}-1}(\theta _{i}-\theta ^{*})}
. Com a suposição A1) e a seguinte A2) A2) Existe uma matriz de Hurwitz
A
{\textstyle A}
e uma matriz simétrica e positiva definida
Σ
{\textstyle \Sigma }
de tal modo que
{
U
n
( ⋅ ) }
{\textstyle \{U^{n}(\cdot )\}}
converge fracamente para
U ( ⋅ )
{\textstyle U(\cdot )}
, onde
U ( ⋅ )
{\textstyle U(\cdot )}
é a solução estacionária para
d U = A U
d t +
Σ
1
/
2
d w
{\displaystyle dU=AU\,dt+\Sigma ^{1/2}\,dw}
onde
w ( ⋅ )
{\textstyle w(\cdot )}
é um processo de Wiener padrão. Satisfeita, e defina
V ̄
= (
A
− 1
) ′
Σ (
A ′
)
− 1
{\textstyle {\bar {V}}=(A^{-1})'\Sigma (A')^{-1}}
. Então para cada
t
{\textstyle t}
,
U ^
n
( t )
⟶
D
N
( 0 ,
V
t
) ,
onde
V
t
=
V ̄
/
t + O ( 1
/
t
2
) .
{\displaystyle {\hat {U}}^{n}(t){\stackrel {\mathcal {D}}{\longrightarrow }}{\mathcal {N}}(0,V_{t}),\quad {\text{onde}}\quad V_{t}={\bar {V}}/t+O(1/t^{2}).}
O sucesso da ideia de calcular a média deve-se à separação da escala de tempo da sequência original
{
θ
n
}
{\textstyle \{\theta _{n}\}}
e da sequência com a média
{
Θ
n
}
{\textstyle \{\Theta _{n}\}}
, sendo a escala de tempo da primeira mais rápida.
Aplicação em otimização estocástica Suponha que queremos resolver o seguinte problema de otimização estocástica
g (
θ
∗
) =
min
θ ∈ Θ
E [ Q ( θ , X ) ] ,
{\displaystyle g(\theta ^{*})=\min _{\theta \in \Theta }\operatorname {E} [Q(\theta ,X)],}
onde
g ( θ ) = E [ Q ( θ , X ) ]
{\textstyle g(\theta )=\operatorname {E} [Q(\theta ,X)]}
é diferenciável e convexa, então este problema é equivalente a encontrar a raiz
θ
∗
{\displaystyle \theta ^{*}}
de
∇ g ( θ ) = 0
{\displaystyle \nabla g(\theta )=0}
. Aqui
Q ( θ , X )
{\displaystyle Q(\theta ,X)}
pode ser interpretado como algum custo "observado" em função do
θ
{\displaystyle \theta }
escolhido e dos efeitos aleatórios
X
{\displaystyle X}
. Na prática, pode ser difícil obter uma forma analítica de
∇ g ( θ )
{\displaystyle \nabla g(\theta )}
. O método de Robbins-Monro consegue gerar uma sequência
(
θ
n
)
n ≥ 0
{\displaystyle (\theta _{n})_{n\geq 0}}
para aproximar
θ
∗
{\displaystyle \theta ^{*}}
se for possível gerar
(
X
n
)
n ≥ 0
{\displaystyle (X_{n})_{n\geq 0}}
, no qual a expectativa condicional de
X
n
{\displaystyle X_{n}}
dado
θ
n
{\displaystyle \theta _{n}}
é exatamente
∇ g (
θ
n
)
{\displaystyle \nabla g(\theta _{n})}
, ou seja,
X
n
{\displaystyle X_{n}}
é simulado a partir de uma distribuição condicional definida por
E [ H ( θ , X )
|
θ =
θ
n
] = ∇ g (
θ
n
) .
{\displaystyle \operatorname {E} [H(\theta ,X)|\theta =\theta _{n}]=\nabla g(\theta _{n}).}
Aqui
H ( θ , X )
{\displaystyle H(\theta ,X)}
é um estimador imparcial (não enviesado) de
∇ g ( θ )
{\displaystyle \nabla g(\theta )}
. Se
X
{\displaystyle X}
depende de
θ
{\displaystyle \theta }
, geralmente não há uma maneira natural de gerar um resultado aleatório
H ( θ , X )
{\displaystyle H(\theta ,X)}
que seja um estimador imparcial do gradiente. Em alguns casos especiais, quando os métodos de IPA ou razão de verossimilhança são aplicáveis, é possível obter um estimador de gradiente imparcial
H ( θ , X )
{\displaystyle H(\theta ,X)}
. Se
X
{\displaystyle X}
é visto como algum processo aleatório "fundamental" subjacente que é gerado independentemente de
θ
{\displaystyle \theta }
, e sob algumas condições de regularização para operações de troca derivativa-integral de modo que
E
[
∂
∂ θ
Q ( θ , X )
]
= ∇ g ( θ )
{\displaystyle \operatorname {E} {\Big [}{\frac {\partial }{\partial \theta }}Q(\theta ,X){\Big ]}=\nabla g(\theta )}
, então
H ( θ , X ) =
∂
∂ θ
Q ( θ , X )
{\displaystyle H(\theta ,X)={\frac {\partial }{\partial \theta }}Q(\theta ,X)}
fornece a estimativa fundamental e imparcial do gradiente. Contudo, para algumas aplicações temos de usar métodos de diferenças finitas nos quais
H ( θ , X )
{\displaystyle H(\theta ,X)}
tem uma expectativa condicional próxima de
∇ g ( θ )
{\displaystyle \nabla g(\theta )}
, mas não exatamente igual a ela. Ao identificar a minimização com o problema de busca de raízes
∇ g ( θ ) = 0
{\displaystyle \nabla g(\theta )=0}
, a aproximação estocástica pode ser aplicada para definir uma solução recursiva para o mínimo, análoga ao algoritmo de Robbins-Monro:
θ
n + 1
=
θ
n
−
ε
n
H (
θ
n
,
X
n + 1
) .
{\displaystyle \theta _{n+1}=\theta _{n}-\varepsilon _{n}H(\theta _{n},X_{n+1}).}
Convergência do algoritmo O resultado seguinte fornece condições suficientes em
θ
n
{\displaystyle \theta _{n}}
para o algoritmo convergir: C1)
ε
n
≥ 0 , ∀
n ≥ 0.
{\displaystyle \varepsilon _{n}\geq 0,\forall \;n\geq 0.}
C2)
∑
n = 0
∞
ε
n
= ∞
{\displaystyle \sum _{n=0}^{\infty }\varepsilon _{n}=\infty }
C3)
∑
n = 0
∞
ε
n
2
< ∞
{\displaystyle \sum _{n=0}^{\infty }\varepsilon _{n}^{2}<\infty }
C4)
|
X
n
|
≤ B
{\displaystyle |X_{n}|\leq B}
, para um limite fixo
B
{\displaystyle B}
. C5)
g ( θ )
{\displaystyle g(\theta )}
é estritamente convexa, isto é:
inf
δ ≤
|
θ −
θ
∗
|
≤ 1
/
δ
⟨ θ −
θ
∗
, ∇ g ( θ ) ⟩ > 0 ,
para todo
0 < δ < 1.
{\displaystyle \inf _{\delta \leq |\theta -\theta ^{*}|\leq 1/\delta }\langle \theta -\theta ^{*},\nabla g(\theta )\rangle >0,{\text{ para todo }}0<\delta <1.}
Então
θ
n
{\displaystyle \theta _{n}}
converge para
θ
∗
{\displaystyle \theta ^{*}}
quase certamente. Aqui estão algumas explicações intuitivas sobre essas condições. Suponha que
H (
θ
n
,
X
n + 1
)
{\displaystyle H(\theta _{n},X_{n+1})}
seja uma variável aleatória uniformemente limitada. Se a C2) não for satisfeita, ou seja,
∑
n = 0
∞
ε
n
< ∞
{\displaystyle \sum _{n=0}^{\infty }\varepsilon _{n}<\infty }
, então
θ
n
−
θ
0
= −
∑
i = 0
n − 1
ε
i
H (
θ
i
,
X
i + 1
)
{\displaystyle \theta _{n}-\theta _{0}=-\sum _{i=0}^{n-1}\varepsilon _{i}H(\theta _{i},X_{i+1})}
é uma sequência limitada, portanto a iteração não pode convergir para
θ
∗
{\displaystyle \theta ^{*}}
se a suposição inicial
θ
0
{\displaystyle \theta _{0}}
estiver muito distante de
θ
∗
{\displaystyle \theta ^{*}}
. Quanto à C3), observe que se
θ
n
{\displaystyle \theta _{n}}
convergir para
θ
∗
{\displaystyle \theta ^{*}}
então
θ
n + 1
−
θ
n
= −
ε
n
H (
θ
n
,
X
n + 1
) → 0 ,
à medida que
n → ∞ .
{\displaystyle \theta _{n+1}-\theta _{n}=-\varepsilon _{n}H(\theta _{n},X_{n+1})\rightarrow 0,{\text{ à medida que }}n\rightarrow \infty .}
então devemos ter
ε
n
↓ 0
{\displaystyle \varepsilon _{n}\downarrow 0}
, e a condição C3) assegura isso. Uma escolha natural seria
ε
n
= 1
/
n
{\displaystyle \varepsilon _{n}=1/n}
. A condição C5) é uma condição bastante rigorosa sobre a forma de
g ( θ )
{\displaystyle g(\theta )}
; ela fornece a direção de busca do algoritmo.
Exemplo (onde o método do gradiente estocástico é apropriado) Suponha que
Q ( θ , X ) = f ( θ ) +
θ
T
X
{\displaystyle Q(\theta ,X)=f(\theta )+\theta ^{T}X}
, onde
f
{\displaystyle f}
é diferenciável e
X ∈
R
p
{\displaystyle X\in \mathbb {R} ^{p}}
é uma variável aleatória independente de
θ
{\displaystyle \theta }
. Então
g ( θ ) = E [ Q ( θ , X ) ] = f ( θ ) +
θ
T
E X
{\displaystyle g(\theta )=\operatorname {E} [Q(\theta ,X)]=f(\theta )+\theta ^{T}\operatorname {E} X}
depende da média de
X
{\displaystyle X}
, e o método do gradiente estocástico seria apropriado neste problema. Podemos escolher
H ( θ , X ) =
∂
∂ θ
Q ( θ , X ) =
∂
∂ θ
f ( θ ) + X .
{\displaystyle H(\theta ,X)={\frac {\partial }{\partial \theta }}Q(\theta ,X)={\frac {\partial }{\partial \theta }}f(\theta )+X.}
Algoritmo de Kiefer-Wolfowitz O algoritmo de Kiefer-Wolfowitz foi introduzido em 1952 por Jacob Wolfowitz e Jack Kiefer, e foi motivado pela publicação do algoritmo de Robbins-Monro. No entanto, o algoritmo foi apresentado como um método que estimaria estocasticamente o máximo de uma função. Seja
M ( x )
{\displaystyle M(x)}
uma função que tem um máximo no ponto
θ
{\displaystyle \theta }
. Presume-se que
M ( x )
{\displaystyle M(x)}
seja desconhecida; no entanto, certas observações
N ( x )
{\displaystyle N(x)}
, onde
E [ N ( x ) ] = M ( x )
{\displaystyle \operatorname {E} [N(x)]=M(x)}
, podem ser feitas em qualquer ponto
x
{\displaystyle x}
. A estrutura do algoritmo segue um método do tipo gradiente, com as iterações sendo geradas como
x
n + 1
=
x
n
+
a
n
⋅
(
N (
x
n
+
c
n
) − N (
x
n
−
c
n
)
2
c
n
)
{\displaystyle x_{n+1}=x_{n}+a_{n}\cdot \left({\frac {N(x_{n}+c_{n})-N(x_{n}-c_{n})}{2c_{n}}}\right)}
onde
N (
x
n
+
c
n
)
{\displaystyle N(x_{n}+c_{n})}
e
N (
x
n
−
c
n
)
{\displaystyle N(x_{n}-c_{n})}
são independentes. A cada passo, o gradiente de
M ( x )
{\displaystyle M(x)}
é aproximado de forma semelhante a um método de diferenças centrais com
h = 2
c
n
{\displaystyle h=2c_{n}}
. Portanto a sequência
{
c
n
}
{\displaystyle \{c_{n}\}}
especifica a sequência de larguras de diferenças finitas usadas para a aproximação do gradiente, enquanto a sequência
{
a
n
}
{\displaystyle \{a_{n}\}}
especifica uma sequência de tamanhos de passo positivos dados ao longo dessa direção. Kiefer e Wolfowitz provaram que, se
M ( x )
{\displaystyle M(x)}
satisfizesse certas condições de regularidade, então
x
n
{\displaystyle x_{n}}
convergiria para
θ
{\displaystyle \theta }
em probabilidade à medida que
n → ∞
{\displaystyle n\to \infty }
, e mais tarde Blum em 1954 mostrou que
x
n
{\displaystyle x_{n}}
converge para
θ
{\displaystyle \theta }
quase certamente, desde que:
Var ( N ( x ) ) ≤ S < ∞
{\displaystyle \operatorname {Var} (N(x))\leq S<\infty }
para todo
x
{\displaystyle x}
. A função
M ( x )
{\displaystyle M(x)}
tenha um único ponto de máximo (mínimo) e seja fortemente côncava (convexa) O algoritmo foi primeiro apresentado com o requisito de que a função
M ( ⋅ )
{\displaystyle M(\cdot )}
mantivesse forte convexidade (concavidade) global sobre todo o espaço viável. Como essa condição é demasiado restritiva para ser imposta sobre todo o domínio, Kiefer e Wolfowitz propuseram que é suficiente impor a condição sobre um conjunto compacto
C
0
⊂
R
d
{\displaystyle C_{0}\subset \mathbb {R} ^{d}}
que se sabe incluir a solução ótima. A função
M ( x )
{\displaystyle M(x)}
satisfaça as condições de regularidade a seguir: Existam
β > 0
{\displaystyle \beta >0}
e
B > 0
{\displaystyle B>0}
tais que
|
x ′
− θ
|
+
|
x ′′
− θ
|
< β
⟹
|
M (
x ′
) − M (
x ′′
)
|
< B
|
x ′
−
x ′′
|
{\displaystyle |x'-\theta |+|x''-\theta |<\beta \quad \Longrightarrow \quad |M(x')-M(x'')|<B|x'-x''|}
Existam
ρ > 0
{\displaystyle \rho >0}
e
R > 0
{\displaystyle R>0}
tais que
|
x ′
−
x ′′
|
< ρ
⟹
|
M (
x ′
) − M (
x ′′
)
|
< R
{\displaystyle |x'-x''|<\rho \quad \Longrightarrow \quad |M(x')-M(x'')|<R}
Para cada
δ > 0
{\displaystyle \delta >0}
, exista algum
π ( δ ) > 0
{\displaystyle \pi (\delta )>0}
tal que
|
z − θ
|
> δ
⟹
inf
δ
/
2 > ε > 0
|
M ( z + ε ) − M ( z − ε )
|
ε
> π ( δ )
{\displaystyle |z-\theta |>\delta \quad \Longrightarrow \quad \inf _{\delta /2>\varepsilon >0}{\frac {|M(z+\varepsilon )-M(z-\varepsilon )|}{\varepsilon }}>\pi (\delta )}
As sequências selecionadas
{
a
n
}
{\displaystyle \{a_{n}\}}
e
{
c
n
}
{\displaystyle \{c_{n}\}}
devem ser sequências infinitas de números positivos tais que
c
n
→ 0
à medida que
n → ∞
{\displaystyle \quad c_{n}\rightarrow 0\quad {\text{à medida que}}\quad n\to \infty }
∑
n = 0
∞
a
n
= ∞
{\displaystyle \sum _{n=0}^{\infty }a_{n}=\infty }
∑
n = 0
∞
a
n
c
n
< ∞
{\displaystyle \sum _{n=0}^{\infty }a_{n}c_{n}<\infty }
∑
n = 0
∞
a
n
2
c
n
− 2
< ∞
{\displaystyle \sum _{n=0}^{\infty }a_{n}^{2}c_{n}^{-2}<\infty }
Uma escolha adequada de sequências, conforme recomendado por Kiefer e Wolfowitz, seria
a
n
= 1
/
n
{\displaystyle a_{n}=1/n}
e
c
n
=
n
− 1
/
3
{\displaystyle c_{n}=n^{-1/3}}
.
Desenvolvimentos subsequentes e questões importantes O algoritmo de Kiefer-Wolfowitz exige que, para cada computação de gradiente, pelo menos
d + 1
{\displaystyle d+1}
diferentes valores de parâmetros sejam simulados a cada iteração do algoritmo, onde
d
{\displaystyle d}
é a dimensão do espaço de busca. Isso significa que quando
d
{\displaystyle d}
é grande, o algoritmo de Kiefer-Wolfowitz exigirá um esforço computacional substancial por iteração, levando a uma convergência lenta. Para resolver este problema, Spall propôs o uso de perturbações simultâneas para estimar o gradiente. Este método exigiria apenas duas simulações por iteração, independentemente da dimensão
d
{\displaystyle d}
. Nas condições requeridas para convergência, a capacidade de especificar um conjunto compacto predeterminado que cumpra forte convexidade (ou concavidade) e contenha a solução única pode ser difícil de encontrar. No que diz respeito a aplicações do mundo real, se o domínio for muito grande, essas suposições podem ser bastante restritivas e altamente irrealistas.
Desenvolvimentos posteriores Uma extensa literatura teórica cresceu em torno desses algoritmos, em relação às condições para convergência, taxas de convergência, generalizações multivariadas e outras, escolha adequada do tamanho do passo, modelos de ruído possíveis, e assim por diante. Esses métodos também são aplicados na teoria de controle, caso em que a função desconhecida que desejamos otimizar ou cuja raiz desejamos encontrar pode variar no tempo. Neste caso, o tamanho do passo
a
n
{\displaystyle a_{n}}
não deve convergir para zero, mas deve ser escolhido de modo a rastrear a função., 2a ed., capítulo 3 C. Johan Masreliez e R. Douglas Martin foram os primeiros a aplicar a aproximação estocástica à estimativa robusta. A principal ferramenta para analisar algoritmos de aproximações estocásticas (incluindo os algoritmos de Robbins-Monro e Kiefer-Wolfowitz) é um teorema de Aryeh Dvoretzky publicado em 1956.
Ver também Método do gradiente estocástico Redução da variância estocástica
Referências
