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

9

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?

professeur bigglesworth
la source
2
Essayez-vous de demander pourquoi fournir un gradient analytique au lieu de simplement calculer un gradient approximatif en utilisant des différences finies?
spektr
1
Ma question est, d'une autre manière, supposons que vos équations soient bien trop impliquées pour que vous puissiez calculer des gradients analytiques, les algorithmes d'optimisation dépendants du gradient peuvent-ils encore être supérieurs à ceux qui ne nécessitent pas du tout de gradients?
professeur bigglesworth
C'est une question différente de celle que vous avez posée ci-dessus. Vous pourriez être en mesure de calculer des dérivées numériques par d'autres moyens, par exemple des éléments finis.
nicoguaro
1
@nicoguaro Oui, dans le contexte de l'optimisation avec des équations aux dérivées partielles, c'est certainement le cas (et, ceci étant l'un de mes domaines de recherche, c'était aussi ma première pensée). Mais la question ne mentionne rien dans ce sens (et est plus utile dans cette généralité. Je pense).
Christian Clason
1
De plus, même dans ce cas, c'est une question raisonnable: que se passe-t-il si votre (système de) PDE (s) est si compliqué que vous ne pouvez pas dériver une équation adjointe à résoudre numériquement pour obtenir le gradient? (Ces choses peuvent devenir assez désagréables, surtout si des conditions aux limites non standard sont impliquées.)
Christian Clason

Réponses:

11

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 rien1 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 ...

Christian Clason
la source
17

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.

Brian Borchers
la source
3
+1 pour la différenciation automatique . C'est souvent beaucoup mieux qu'une expression symbolique a priori pour le gradient ou une approximation de différence finie.
leftaroundabout
Je recommanderais également d'utiliser la différenciation automatique. Pour fortran, essayez la tapenade de l'INRIA Sophia-Antipolis, basée sur la transformation des sources. Pour C / C ++, il y a plus de choix comme adol-c, adept, sacado (qui fait partie de Trilinos). Tous ces éléments sont basés sur la surcharge de l'opérateur et plus faciles à utiliser, mais pas très efficaces pour les très gros problèmes.
cfdlab
Il existe également des circonstances dans lesquelles la différenciation automatique (AD) peut être difficile à appliquer, mais une différenciation d'étape complexe, qui peut parfois équivaloir à presque la même chose que AD (autre que la possibilité de calculer un dégradé entier à la fois par le mode inverse). AD) peut être applicable et relativement facile à appliquer.
Mark L. Stone,
En réponse à la question révisée: si votre objectif est lisse (il ne sert à rien d'utiliser un algorithme d'optimisation dérivé s'il ne l'est pas) et si le nombre de variables est raisonnablement petit (faire des dérivés de différence finie ne fonctionne pas dans l'optimisation contrainte PDE ), alors il est plus probable que vous feriez mieux d'utiliser une méthode d'optimisation basée sur les dérivés avec des approximations de différences finies plutôt que d'utiliser une technique MPO.
Brian Borchers
4

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.

Mike Dunlavey
la source
Je pense que l'un des principaux avantages est le fait que vous ne faites aucune soustraction dans cette formule complexe de différence finie. Lorsque j'ai lu un article il y a quelque temps sur les dérivations de cette méthode, c'était l'un des points qu'ils semblaient valider expérimentalement par rapport à d'autres formules de différences finies. Cette différence a permis de choisir des tailles de pas plus petites avant que les erreurs d'arrondi ne deviennent un problème.
spektr
@choward: C'est vrai. C'est ça qui est joli. J'étais cependant sceptique. Certains de mes collègues semblaient penser que c'était une solution miracle. Je soupçonnais que c'était l'équivalent des équations de sensibilité, et l'un de mes collègues, un mathématicien appliqué, l'a prouvé.
Mike Dunlavey
C'est cool à propos de l'équation de sensibilité. C'est une approche intéressante, mais elle peut certainement avoir ses compromis de mise en œuvre. En supposant que vous souhaitiez l'utiliser, vous devez définir des versions complexes de vos fonctions, puis effectuer l'algèbre / les calculs de variables complexes supplémentaires, ce qui rallonge l'évaluation de chaque fonction. C'est une de ces choses que vous devez déterminer si l'évaluation plus lente de la fonction vaut la précision de dérivation supplémentaire.
spektr
@choward: C'est la conclusion à laquelle je suis arrivé, et nous optimisons généralement un vecteur, ce qui signifie une évaluation répétitive. Bien sûr, l'alternative est que les équations de sensibilité peuvent être difficiles à dériver. J'utilise la différenciation symbolique, et elles sont toujours délicates. Tout le sujet est un peu un champ de mines.
Mike Dunlavey