Est-il inutile de fournir des gradients approximatifs à un optimiseur basé sur un gradient?

Est-il inutile d'utiliser des algorithmes d'optimisation basés sur un gradient si vous ne pouvez fournir qu'un gradient numérique? Sinon, pourquoi fournir un gradient numérique en premier lieu s'il est trivial d'effectuer une différenciation finie pour la bibliothèque d'optimisation elle-même?

[ÉDITER]

• Juste pour clarifier, ma question est en effet dans un sens plus général qu'une application spécifique. Bien que mon domaine d'application se trouve être l'optimisation de vraisemblance sous divers cadres statistiques.

• Mon problème avec la différenciation automatique est qu'il semble toujours y avoir un problème. Soit la bibliothèque AD ne peut pas se propager aux appels de bibliothèque externes (comme BLAS), soit vous devez retravailler votre flux de travail de manière si drastique que cela rend la tâche difficile à gérer ... surtout si vous travaillez avec des langages sensibles au type. Mes reproches avec AD sont un problème distinct. Mais je veux y croire!

• Je suppose que je dois mieux formuler ma question, mais j'en fais un mauvais travail. Si vous avez la possibilité d'utiliser soit un algorithme d'optimisation sans dérivé, soit un algorithme d'optimisation basé sur dérivé avec la réserve que je ne peux que lui donner un gradient numérique, lequel sera en moyenne supérieur?

Pour compléter l'excellente réponse de Brian, permettez-moi de donner un peu de contexte (éditorial). Les méthodes d'optimisation sans dérivées sont définies comme des méthodes qui n'utilisent que des évaluations de fonctions, et sont essentiellement toutes les variantes de "échantillonner l'ensemble admissible plus ou moins systématiquement et enregistrer la meilleure valeur de fonction" - c'est tout ce que vous pouvez faire compte tenu des informations. Ces méthodes peuvent être grossièrement subdivisées en

1. Méthodes stochastiques , où la sélection des échantillons est fondamentalement aléatoire (ce qui signifie que le caractère aléatoire est un élément crucial; il peut y avoir d'autres éléments déterministes). Ces méthodes sont souvent motivées par des processus physiques ou biologiques et portent des noms correspondants comme "recuit simulé", "algorithmes génétiques" ou "méthode essaim de particules / luciole / fourmilière". Il y a rarement une théorie de convergence au-delà "si vous essayez assez longtemps, vous atteindrez tous les points (y compris le minimiseur) avec la probabilité " (que cela se produise - avec une probabilité quelconque - avant que la mort par la chaleur de l'univers soit une autre affaire ...) En tant que mathématicien, je considérerais ces méthodes en dernier recours: si vous ne savez rien$1$ sur votre fonction, c'est tout ce que vous pouvez faire, et vous pourriez avoir de la chance.

2. Méthodes déterministes , où la sélection des échantillons n'est pas aléatoire, c'est-à-dire basée uniquement sur des évaluations de fonctions précédentes. L'exemple le plus célèbre est probablement la méthode Nelder-Mead simplex; d'autres génèrent des méthodes de recherche d'ensemble . Il est important de réaliser que cela ne peut fonctionner que s'il existe une relation (exploitable) entre la valeur de la fonction à différents points - c'est-à-dire une certaine fluidité de la fonction. En fait, la théorie de convergence pour, par exemple, la méthode Nelder-Mead est basée sur la construction d'un non uniformeapproximation par différence finie du gradient basée sur les valeurs de la fonction aux sommets du simplexe et montrant qu'il converge à la fois avec le gradient exact et zéro lorsque le simplex se contracte en un point. (La variante basée sur une approximation standard aux différences finies est appelée recherche au compas .)

3. Méthodes basées sur un modèle , où les valeurs de fonction sont utilisées pour construire un modèle local de la fonction (par exemple, par interpolation), qui est ensuite minimisé à l'aide de méthodes standard (basées sur le gradient / la Hesse) Puisqu'une approximation aux différences finies est équivalente à la dérivée exacte d'un interpolant polynomial, l'approche classique du «gradient numérique» entre également dans cette classe.

Comme vous pouvez le voir, les frontières entre ces classes sont fluides et souvent juste une question d'interprétation. Mais la morale doit être claire: assurez-vous d'utiliser toutes les informations disponibles sur la fonction que vous minimisez. Pour citer Cornelius Lanczos:

Un manque d'information ne peut être corrigé par aucune ruse mathématique.

Après tout, si vous ne savez rien de votre fonction, elle pourrait tout aussi bien être complètement aléatoire, et minimiser une valeur aléatoire est une course de dupes ...

Si votre objectif est lisse, il est souvent plus efficace d'utiliser des approximations de différences finies avec la dérivée que d'utiliser un algorithme d'optimisation sans dérivée. Si vous avez du code qui calcule exactement les dérivées, il est normalement préférable d'utiliser ce code plutôt que d'utiliser des approximations de différences finies.

Bien que certaines bibliothèques d'optimisation calculent automatiquement pour vous des approximations de différences finies à l'aide d'heuristiques pour déterminer les paramètres de taille de pas, il peut être préférable d'utiliser vos propres routines pour calculer les approximations de différences finies soit parce que vous avez une meilleure connaissance des tailles de pas appropriées, soit à cause de structure spéciale dans la fonction que votre code peut exploiter.

Une autre option qui vaut souvent la peine consiste à utiliser des techniques de différenciation automatique pour produire un sous-programme qui calcule les dérivées analytiques à partir du code source pour calculer la fonction objective elle-même.

Votre question porte sur les optimiseurs basés sur le gradient, donc je pense que Brian avait raison. Je voudrais seulement partager, puisque je suis actuellement aux prises avec cela moi-même, certains des problèmes.

Les problèmes de différence finie sont 1) les performances, car vous devez réévaluer la fonction pour chaque dimension, et 2) il peut être difficile de choisir une bonne taille de pas. Si le pas est trop grand, l'hypothèse de linéarité de la fonction peut ne pas tenir. Si le pas est trop petit, il peut se heurter au bruit dans la fonction elle-même, car les dérivés amplifient le bruit. Ce dernier peut être un vrai problème si la fonction implique la résolution d'équations différentielles. S'il est possible de calculer les gradients analytiquement ou en utilisant des équations de sensibilité, ce sera certainement plus précis et peut-être plus rapide.

Il existe une autre approche que vous pouvez essayer si vous n'avez pas déjà investi trop de temps dans le logiciel, et c'est de l'exécuter avec une arithmétique complexe. Cela s'appelle la différenciation des étapes complexes . L'idée de base est lorsque vous évaluez la fonction, si vous voulez son gradient par rapport au paramètre X, vous définissez la partie imaginaire de X sur un très petit nombre eps . Après avoir fait le calcul, la partie imaginaire de la valeur de la fonction, divisée par eps , est le gradient par rapport à X. Lorsque vous voulez le gradient par rapport à Y, vous devez bien sûr tout recommencer. Ce qui est intéressant c'est que epspeut être rendu très petit. La raison pour laquelle cela fonctionne est que les règles normales du calcul différentiel se reflètent précisément dans les règles de l'arithmétique complexe.

Cela dit, je considère comme pas une panacée, car ce n'est pas toujours facile de faire une fonction compliquée en arithmétique complexe, il ne vaut pas si le gradient peut être calculé analytiquement, et dans le cas d'équations différentielles , il est exactement équivalent à des équations de sensibilité , ce que je fais si nécessaire.