Otimização matemática em uma função barulhenta

Seja uma função bastante agradável (por exemplo, contínua, diferenciável, não há máximos locais demais, talvez côncavos etc.). Quero encontrar um máximo de f : um valor x ∈ R d que faça f ( x ) o maior possível.$f:\mathbb{R}^d \to \mathbb{R}$$f$$x \in \mathbb{R}^d$$f(x)$

Se eu tivesse um procedimento para avaliar precisão em qualquer entrada de minha escolha, eu poderia usar técnicas padrão de otimização matemática : escalada, descida de gradiente (bem, ascensão de gradiente), etc. No entanto, em meu aplicativo, não maneira de avaliar f ( x ) exatamente. Em vez disso, tenho uma maneira de estimar o valor de f ( x ) .$f$$f(x)$$f(x)$

Em particular, dado qualquer e qualquer ε , eu tenho um oráculo que produzirá uma estimativa de f ( x ) e cujo erro esperado é aproximadamente ε . O tempo de execução dessa invocação do oracle é proporcional a 1 / ε 2 . (É implementado por um tipo de simulação; a precisão da simulação aumenta com a raiz quadrada do número de tentativas, e posso escolher quantas tentativas executar, para poder escolher a precisão desejada.) Portanto, isso me dá uma maneira de obter uma estimativa de qualquer precisão que eu deseje, mas quanto mais preciso eu quero que a estimativa seja, mais tempo levará.$x$$\varepsilon$$f(x)$$\varepsilon$$1/\varepsilon^2$

Dado esse oráculo barulhento para , existem técnicas para calcular o máximo de f da forma mais eficiente possível? (Ou, mais precisamente, encontrando um máximo aproximado.) Existem variantes de escalada, descida de gradiente etc. que funcionam nesse modelo?$f$$f$

É claro que eu poderia fixar um valor muito pequeno de e aplicar escalada ou descida de gradiente com este oráculo, mantendo o mesmo ε por toda parte. No entanto, isso pode ser desnecessariamente ineficiente: talvez não precisemos de uma estimativa tão precisa perto do início, enquanto a precisão perto do fim, quando você estiver se concentrando na solução, é mais importante. Existe alguma maneira de tirar proveito da minha capacidade de controlar a precisão de minha estimativa dinamicamente, para tornar o processo de otimização mais eficiente? Esse tipo de problema já foi estudado antes?$\varepsilon$$\varepsilon$

$f(x,p)$$f(x+\Delta x, p + \Delta p)$$p$$\Delta x$$\Delta p$

• Algumas técnicas usadas na otimização estocástica e otimização robusta podem ser aplicáveis.
• $\frac{\partial f}{\partial x}\approx 0$$\Delta x$$\Delta p$
• $\frac{\partial f}{\partial x}(\tilde{x}, \tilde{p})$$f(\tilde{x}, \tilde{p})$
• $\Delta p$$\Delta x$$1/\epsilon^2$
• A troca de ruído versus tempo de execução é o que diferencia esse problema dos problemas mais bem estudados. Os problemas em que o ruído é inevitável são mais comuns e melhor estudados.