Noise-Aware Stochastic Optimization

Abstract

Sochastische Optimierungsverfahren erster Ordnung, wie zum Beispiel das stochastische Gradientenverfahren (stochastic gradient descent, SGD), sind das Arbeitstier des modernen maschinellen Lernens. Mit ihrer Einfachheit und niedrigen Kosten pro Iteration haben sie den immensen Erfolg künstlicher neuronaler Netze maßgeblich vorangetrieben. Überraschender Weise sind diese stochastischen Optimierungsmethoden blind gegenüber Stochastizität. Weder sammeln sie Informationen über das stochastische Rauschen der verwendeten Gradientenauswertungen, noch verfügen sie über explizite Mechanismen, um ihr Verhalten an dieses Rauschen anzupassen. Diese Arbeit präsentiert Ansätze, stochastischen Optimierungsverfahren mittels Schätzung der (Ko- )Varianz der stochastischen Gradienten ein “Bewusstsein” für dieses Rauschen zu geben.

Zuerst zeigen wir, wie solche Varianzschätzungen genutzt werden können, um die sogenannte Minibatchgröße bei SGD automatisch anzupassen. Dies kann eine üblicherweise verwendete ab- nehmende Schrittweite ersetzten, welche ihrerseits sehr viel schwerer zu automatisieren ist. Wir stellen heraus, dass beide Herangehensweisen aus einer gemeinsamen Perspektive betrachtet werden können, nämlich als Reduktion der mittleren quadratischen Abweichung des Gradientenschätzers.

Als nächstes identifizieren wir in der außergewöhnlich populären Adam-Methode einen impliziten Varianzadaptierungsmechanismus. Wir betrachten Adam als eine Version von sign-SGD mit koordinatenweiser “Dämpfung” auf Basis des Signal-zu-Rausch-Verhältnisses des stochastischen Gradienten. Wir machen diesen Mechanismus explizit, formalisieren ihn, und übertragen ihn von sign-SGD zu SGD.

Abschließend folgt eine kritische Diskussion einer Methodenfamilie, welche SGD mit der sogenannten “empirischen Fisher-Matrix” präkonditionert. Diese Matrix ist eng mit der Kovarianzmatrix des stochastischen Gradienten verwandt. Die empirische Fisher-Matrix wird üblicherweise als Approximation für die Fisher-Matrix und somit aus informationsgeometrischen Überlegungen motiviert. Wir kritisieren dieses Argument und zeigen, dass diese Approximation fundamentale theoretische Schwächen hat. Wir argumentieren, dass die Präkonditionierung mit der empirischen Fisher-Matrix besser als eine Form von Varianzadaptierung gesehen werden sollte.

First-order stochastic optimization algorithms like stochastic gradient descent (SGD) are the workhorse of modern machine learning. With their simplicity and low per-iteration cost, they have powered the immense success of deep artificial neural network models. Surprisingly, these stochastic optimization methods are essentially unaware of stochasticity. Neither do they collect information about the stochastic noise associated with their gradient evaluations, nor do they have explicit mechanisms to adjust their behavior accordingly. This thesis presents approaches to make stochastic optimization methods noise-aware using estimates of the (co-)variance of stochastic gradients.

First, we show how such variance estimates can be used to automatically adapt the minibatch size for SGD, i.e., the number of data points sampled in each iteration. This can replace the usual decreasing step size schedule required for convergence, which is much more challenging to automate. We highlight that both approaches can be viewed through the same lens of reducing the mean squared error of the gradient estimate.

Next, we identify an implicit variance adaptation mechanism in the ubiquitous Adam method. In particular, we show that it can be seen as a version of sign-SGD with a coordinatewise “damping” based on the stochastic gradient’s signal-to-noise ratio. We make this variance adaptation mechanism explicit, formalize it, and transfer it from sign-SGD to SGD.

Finally, we critically discuss a family of methods that preconditions stochastic gradient descent updates with the so-called “empirical Fisher” matrix, which is closely related to the stochastic gradient covariance matrix. This is usually motivated from information- geometric considerations as an approximation to the Fisher information matrix. We caution against this argument and show that the empirical Fisher approximation has fundamental theoretical flaws. We argue that preconditioning with the empirical Fisher is better understood as a form of variance adaptation.