Ist es nutzlos, einem gradientenbasierten Optimierer ungefähre Verläufe bereitzustellen?

Ist es sinnlos, gradientenbasierte Optimierungsalgorithmen zu verwenden, wenn Sie nur einen numerischen Gradienten bereitstellen können? Wenn nicht, warum überhaupt einen numerischen Gradienten bereitstellen, wenn es trivial ist, eine endliche Differenzierung für die Optimierungsbibliothek selbst durchzuführen?

[BEARBEITEN]

• Zur Verdeutlichung ist meine Frage in der Tat allgemeiner als eine spezifische Anwendung. Obwohl mein Anwendungsbereich zufällig die Wahrscheinlichkeitsoptimierung unter verschiedenen statistischen Rahmenbedingungen ist.

• Mein Problem bei der automatischen Differenzierung ist, dass es immer einen Haken zu geben scheint. Entweder kann die AD-Bibliothek nicht an externe Bibliotheksaufrufe (wie BLAS) weitergegeben werden, oder Sie müssen Ihren Workflow so drastisch überarbeiten, dass es schwierig wird, damit umzugehen ... insbesondere, wenn Sie mit typsensitiven Sprachen arbeiten. Meine Probleme mit AD sind ein ganz anderes Thema. Aber ich möchte glauben!

• Ich denke, ich muss meine Frage besser formulieren, aber ich mache einen schlechten Job. Wenn Sie die Option haben, entweder einen ableitungsfreien Optimierungsalgorithmus oder einen derivatbasierten Optimierungsalgorithmus mit der Einschränkung zu verwenden, dass ich ihm nur einen numerischen Gradienten geben kann, welcher ist im Durchschnitt überlegen?

Lassen Sie mich als Ergänzung zu Brians hervorragender Antwort ein wenig (redaktionellen) Hintergrund geben. Derivatfreie Optimierungsmethoden werden als Methoden definiert, die nur Funktionsbewertungen verwenden. Grundsätzlich handelt es sich um alle Variationen von "Die zulässige Menge mehr oder weniger systematisch abtasten und den besten Funktionswert speichern" - das ist alles, was Sie angesichts der Informationen tun können. Diese Methoden können grob unterteilt werden in

1. $1$ Dies ist alles, was Sie tun können, und Sie könnten Glück haben.

2. Deterministische Methoden , bei denen die Auswahl der Stichproben nicht zufällig ist, dh nur auf früheren Funktionsbewertungen basiert. Das bekannteste Beispiel ist wahrscheinlich die Nelder-Mead-Simplex-Methode; andere generieren festgelegte Suchmethoden . Es ist wichtig zu wissen, dass dies nur funktionieren kann, wenn eine (ausnutzbare) Beziehung zwischen dem Wert der Funktion an verschiedenen Punkten besteht - dh eine gewisse Glätte der Funktion. Tatsächlich basiert die Konvergenztheorie für z. B. die Nelder-Mead-Methode auf der Konstruktion einer UngleichmäßigkeitFinite-Differenzen-Approximation des Gradienten basierend auf den Funktionswerten an den Eckpunkten des Simplex und zeigt, dass er sowohl zum exakten Gradienten als auch zur Null konvergiert, wenn sich der Simplex zu einem Punkt zusammenzieht. (Die auf einer Standard-Finite-Differenzen-Näherung basierende Variante wird als Kompasssuche bezeichnet .)

3. Modellbasierte Methoden , bei denen die Funktionswerte verwendet werden, um ein lokales Modell der Funktion zu erstellen (z. B. durch Interpolation), das dann mithilfe von Standardmethoden (gradienten- / hessisch-basiert) minimiert wird. Da eine Näherung mit endlicher Differenz der exakten Ableitung eines Polynominterpolanten entspricht, fällt der klassische Ansatz des "numerischen Gradienten" ebenfalls in diese Klasse.

Wie Sie sehen können, sind die Grenzen zwischen diesen Klassen fließend und oft nur eine Frage der Interpretation. Die Moral sollte jedoch klar sein: Stellen Sie sicher, dass Sie alle verfügbaren Informationen zu der Funktion verwenden, die Sie minimieren. Um Cornelius Lanczos zu zitieren:

Ein Mangel an Informationen kann nicht durch mathematische Tricks behoben werden.

Wenn Sie nichts über Ihre Funktion wissen , kann es auch völlig zufällig sein, und das Minimieren eines zufälligen Werts ist ein Kinderspiel ...

Wenn Ihr Ziel glatt ist, ist die Verwendung von Näherungen mit endlichen Differenzen an die Ableitung häufig effektiver als die Verwendung eines ableitungsfreien Optimierungsalgorithmus. Wenn Sie Code haben, der die Ableitungen genau berechnet, ist es normalerweise am besten, diesen Code zu verwenden, anstatt Näherungen mit endlichen Differenzen zu verwenden.

Obwohl einige Optimierungsbibliotheken mithilfe von Heuristiken zur Bestimmung der Schrittgrößenparameter automatisch Näherungen für endliche Differenzen berechnen, kann es besser sein, eigene Routinen zu verwenden, um die Näherungen für endliche Differenzen zu berechnen, entweder weil Sie die entsprechenden Schrittgrößen besser kennen oder weil spezielle Struktur in der Funktion, die Ihr Code ausnutzen kann.

Eine andere Option, die sich oft lohnt, ist die Verwendung automatischer Differenzierungstechniken, um eine Unterroutine zu erstellen, die die analytischen Ableitungen aus dem Quellcode zur Berechnung der Zielfunktion selbst berechnet.

In Ihrer Frage geht es um gradientenbasierte Optimierer. Ich denke, Brian hatte Recht. Ich würde nur einige der Probleme teilen, da ich derzeit selbst damit zu kämpfen habe.

Die Probleme mit der endlichen Differenz sind 1) Leistung, da Sie die Funktion für jede Dimension erneut bewerten müssen, und 2) es kann schwierig sein, eine gute Schrittgröße zu wählen. Wenn der Schritt zu groß ist, gilt die Annahme der Linearität der Funktion möglicherweise nicht. Wenn der Schritt zu klein ist, kann er in der Funktion selbst auf das Rauschen stoßen, da Ableitungen das Rauschen verstärken. Letzteres kann ein echtes Problem sein, wenn die Funktion das Lösen von Differentialgleichungen beinhaltet. Wenn es möglich ist, die Gradienten analytisch oder unter Verwendung von Empfindlichkeitsgleichungen zu berechnen, ist dies sicherlich genauer und möglicherweise schneller.

Es gibt einen anderen Ansatz, den Sie ausprobieren können, wenn Sie noch nicht zu viel Zeit in die Software investiert haben, und zwar mit komplexer Arithmetik. Es heißt komplexe Stufendifferenzierung . Die Grundidee ist, wenn Sie die Funktion auswerten, wenn Sie ihren Gradienten in Bezug auf Parameter X wünschen, setzen Sie den Imaginärteil von X auf eine sehr kleine Zahl eps . Nachdem Sie die Berechnung durchgeführt haben, ist der Imaginärteil des Funktionswerts, geteilt durch eps , der Gradient in Bezug auf X. Wenn Sie den Gradienten in Bezug auf Y wollen, müssen Sie natürlich alles noch einmal machen. Das Interessante daran ist, dass epskann sehr klein gemacht werden. Der Grund dafür ist, dass die normalen Regeln der Differentialrechnung genau in den Regeln der komplexen Arithmetik widergespiegelt werden.

Ich halte es jedoch nicht für ein Allheilmittel, da es nicht immer einfach ist, eine komplizierte Funktion in komplexer Arithmetik auszuführen. Es lohnt sich nicht, wenn der Gradient analytisch berechnet werden kann, und im Fall von Differentialgleichungen entspricht er genau den Empfindlichkeitsgleichungen , was ich nach Bedarf mache.