Investigation of self-learned zeroth-order optimization algorithms

Abstract

Designing optimization algorithms manually is a laborious process. In Addition, many optimization algorithms rely on hand-crafted heuristics and perform poorly in applications for which they are not specifically designed. Thus, automating the algorithm design process is very appealing. Moreover, learned algorithms minimize the amount of a priori assumptions and do not rely on hyperparameters after training. Several works exist that present methods to learn an optimization algorithm. In this project, we focus on the reinforcement learning perspective. Therefore, any particular optimization algorithm is represented as a policy. Evaluation of the existing methods shows, learned algorithms outperform existing algorithms in terms of convergence speed and final objective value on particular training tasks. However, the inner mechanisms of learned algorithms largely remain a mystery. A first work has discovered that learned first-order algorithms show a set of intuitive mechanisms that are tuned to the training task. We aim to explore the inner workings of learned zeroth-order algorithms and compare our discoveries to previous works. To address this issue, we study properties of learned zeroth-order algorithms to understand the relationship between what is learned and the quantitative and qualitative properties, e.g., curvature or convexity of the objective function. Furthermore, we study the generalization in relation to these properties. Moreover, we explore the feasibility of finetuning a learned zeroth-order optimization algorithm to a related objective function. Finally we provide guidelines for training and application of learned zeroth-order optimization algorithms.

Die manuelle Entwicklung von Optimierungsalgorithmen ist ein mühsames Verfahren. Hinzu kommt, dass viele Optimierungsalgorithmen auf handgefertigten Heuristiken beruhen und in Anwendungen, für die sie nicht speziell entwickelt wurden, schlecht abschneiden. Daher ist die Automatisierung des Algorithmusentwurfs sehr vielversprechend. Außerdem minimieren gelernte Algorithmen die Anzahl der a priori Annahmen und sind nicht auf Hyperparameter nach dem Training angewiesen. Es gibt mehrere Arbeiten, die Methoden zum Erlernen eines Optimierungsalgorithmus vorstellen. In diesem Projekt konzentrieren wir uns auf die Perspektive des Bestärkenden Lernens. Dadurch wird jeder bestimmte Optimierungsalgorithmus als eine Strategie (policy) dargestellt. Die Bewertung der vorhandenen Methoden zeigt, dass die gelernten Algorithmen die vorhandenen Algorithmen in Bezug auf die Konvergenzgeschwindigkeit und den endgültigen Zielwert bei bestimmten Trainingsaufgaben übertreffen. Die inneren Mechanismen der gelernten Algorithmen bleiben jedoch weitgehend ein Rätsel. In einer ersten Arbeit wurde entdeckt, dass gelernte Algorithmen erster Ordnung eine Reihe von intuitiven Mechanismen aufweisen, die auf die Trainingsaufgabe abgestimmt sind. Unser Ziel ist es, die inneren Mechanismen von gelernten Algorithmen nullter Ordnung zu erforschen und unsere Entdeckungen mit früheren Arbeiten zu vergleichen. Zu diesem Zweck untersuchen wir die Eigenschaften gelernter Algorithmen nullter Ordnung, um die Beziehung zwischen dem Gelernten und den quantitativen und qualitativen Eigenschaften, z. B. der Krümmung oder Konvexität der Zielfunktion, zu verstehen. Außerdem untersuchen wir die Übertragbarkeit in Bezug auf diese Eigenschaften. Darüber hinaus untersuchen wir die Möglichkeit der Feinabstimmung eines erlernten Optimierungsalgorithmus der nullten Ordnung auf eine verwandte Zielfunktion. Schließlich geben wir Richtlinien für das Training und die Anwendung von erlernten Optimierungsalgorithmen der nullten Ordnung.