Efficient and convergent natural gradient based optimization algorithms for machine learning

Abstract

[eng] Many times machine learning is casted as an optimization problem. This is the case when an objective function assesses the success of an agent in a certain task and hence, learning is accomplished by optimizing that function. Furthermore, gradient descent is an optimization algorithm that has proven to be a powerful tool, becoming the cornerstone to solving most machine learning challenges. Among its strengths, there are the low computational complexity and the convergence guarantee property to the optimum of the function, after certain regularities on the function. Nevertheless, large dimension scenarios show sudden drops in convergence rates which inhibit further improvements in an acceptable amount of time. For this reason, the field has contemplated the natural gradient to tackle this issue. The natural gradient is defined on a Riemannian manifold (M, g). A Riemannian manifold is a manifold M equipped with a metric g. The natural gradient vector of a function f at a point p in (M, g) is a vector in the tangent space at p that points to the direction in which f locally increases its value faster taking into account the metric attached to the manifold. It turns out that the manifold of probability distributions of the same family, usually considered in machine learning, has a natural metric associated, namely the fisher information metric. While natural gradient based algorithms show a better convergence speed in some limited examples, they often fail in providing good estimates or they even diverge. Moreover, they demand more calculations than the ones performed by gradient descent algorithms, increasing the computational complexity order. This thesis explores the natural gradient descent algorithm for the function optimization task. Our research aims at designing a natural gradient based algorithm to solve a function optimization problem, whose computational complexity is comparable to those gradient based and such that it benefits from higher rates of convergence compared to standard gradient based methods. To reach our objectives, the hypothesis formulated in this thesis is that the convergence property guarantee stabilizes natural gradient algorithms and it gives access to fast rates of convergence. Furthermore, the natural gradient can be computed fast for particular manifolds named dually flat manifolds, and hence, fast natural gradient optimization methods become available. The beginning of our research is mainly focused on the convergence property for natural gradient methods. We develop some strategies to define natural gradient methods whose convergence can be proven. The main assumptions require (M, g) to be a Riemannian manifold and f to be a differentiable function on M. Moreover, it turns out that the multinomial logistic regression problem, a widely considered machine learning problem, can be adapted and solved by taking a dually flat manifolds as the model. Hence, this problem is our most promising target in which the objective of the thesis can be completely accomplished.

[cat] L’aprenentatge automàtic sovint es relaciona amb un problema d’optimització. Quan l’éxit o l’error d’un agent en una determinada tasca ve donat per una funció, aprendre a realitzar correctament la tasca equival a optimitzar la funció en questió. El descens del gradient és un mètode d’optimització emprat per resoldre la majoria d’aquest tipus de problemes. Aquest algorisme és eficient i, donades certes condicions, convergeix a la solució. No obstant, la convergència pot esdevenir molt lenta en problemes de dimensió alta, on l’algorisme requerix un temps desmesurat. El gradient natural és emprat, sense gaire èxit, per tal d’evitar aquest fet. En una varietat de Riemann (M, g) amb mètrica g, el gradient natural d’una funció "f" en un punt "p" és un vector del espai tangent en "p" que assenyala la direcció on "f" creix localment més intensament, tenint en compte la mètrica del espai. En teoria, el gradient natural té propietats que podrien afavorir la velocitat de convergència, però en problemes pràctics no s’observa cap millora. Alguns algorismes basats en el gradient natural fins i tot divergeixen essent superats pel descens del gradient standard. A més a més, el gradient natural en general té una complexitat computacional més elevada. Aquesta tesis explora els algorismes basats en el gradient natural. En moltes ocasions, l’aprenentatge automàtic es du a terme en families de distribucions de probabilitat, on la mètrica associada a aquest tipus d’espais és la mètrica de Fisher. La nostra hipòtesi és que per obtenir una velocitat de convergència alta és suficient l’assoliment de la propietat de convergència. L’objectiu és definir exemples d’aquest tipus d’algorismes que siguin convergents i amb un cost computacional reduït per tal que pugui ser emprat en problemes actuals de dimensió alta. Per assolir el nostre objectiu, hem trobat indispensable limitar-nos al conjunt de varietats de Riemann anomenades varietats dualment planes. En particular, afrontem el problema de regressió logística multinomial. Aquest espai ens permet definir un algorisme efficient i convergent basat en el gradient natural gràcies a propietats intrínseques de la varietat.