Optimisation mathématique sur une fonction bruyante

Soit une fonction assez agréable (par exemple, continue, différenciable, pas trop de maxima locaux, peut-être concave, etc.). Je veux trouver un maximum de : une valeur qui rend aussi grand que possible. f x ∈ R d f ( x $f:\mathbb{R}^d \to \mathbb{R}$$f$$x \in \mathbb{R}^d$$f(x)$

Si j'avais une procédure pour évaluer précisément sur n'importe quelle entrée de mon choix, je pourrais utiliser des techniques standard d' optimisation mathématique : escalade, descente en pente (enfin, montée en gradient), etc. Cependant, dans mon application, je n'ai pas de moyen d'évaluer exactement . Au lieu de cela, j'ai un moyen d'estimer la valeur de .$f$f ( x $f(x)$$f(x)$

En particulier, étant donné tout et tout , j'ai un oracle qui produira une estimation de , et dont l'erreur attendue est d'environ . Le temps d'exécution de cette invocation Oracle est proportionnel à . (Il est mis en œuvre par une sorte de simulation; la précision de la simulation augmente avec la racine carrée du nombre d'essais, et je peux choisir le nombre d'essais à exécuter, donc je peux choisir la précision souhaitée.) Cela me donne donc une moyen d'obtenir une estimation de la précision que je souhaite, mais plus je veux que l'estimation soit précise, plus cela me prendra de temps.ε f ( x ) ε 1 / ε $x$$\varepsilon$$f(x)$$\varepsilon$$1/\varepsilon^2$

Compte tenu de cet oracle bruyant pour , existe-t-il des techniques pour calculer un maximum de aussi efficacement que possible? (Ou, plus précisément, trouver des maxima approximatifs.) Existe-t-il des variantes d'escalade, de descente en pente, etc. qui fonctionnent dans ce modèle?$f$$f$

Bien sûr, je pouvais fixer une très petite valeur de et appliquer l'escalade ou la descente en pente avec cet oracle, en gardant le même tout au long. Cependant, cela peut être inutilement inefficace: nous pourrions ne pas avoir besoin d'une estimation aussi précise près du début, tandis que la précision près de la fin lorsque vous vous concentrez sur la solution est plus importante. Existe-t-il un moyen de profiter de ma capacité à contrôler la précision de mon estimation de manière dynamique, pour rendre le processus d'optimisation plus efficace? Ce type de problème a-t-il déjà été étudié?$\varepsilon$$\varepsilon$

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

• Certaines techniques utilisées dans l'optimisation stochastique et l' optimisation robuste pourraient être applicables.
• $\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$
• Le compromis entre le bruit et l'exécution est ce qui distingue ce problème des problèmes mieux étudiés. Les problèmes où le bruit est tout simplement inévitable sont plus courants et mieux étudiés.