Métodos estocásticos de optimización

Abstract

The main purpose of this work is to study stochastic optimization methods used to minimize the problem of finite sums for convex functions. Within these methods, the method of gradient descent with mini-batch and the stochastic version of the Frank-Wolfe method (or Conditional Gradient) are specifically exposed in the work. For the gradient descent method with mini-batch, a limit was shown on the number of iterations necessary to converge, which depends on the size of the batch used in the algorithm. Later an optimal size of this was found where the number of iterations necessary for convergence is minimized. On the other hand, in the part dedicated to the study of the new stochastic version of the Frank-Wolfe algorithm, the operation of the algorithm was explicitly shown. In addition, lemmas and theorems were demonstrated that guarantee their convergence in a time less than or equal to the original method. The algorithm's stop method was redefined, showing that it is a stochastic version equivalent to the original stop method. Finally, the algorithms were implemented with real data using the loss functions of the logistic and linear regressions as the functions of the problem stated at the beginning of this summary. To evaluate the performance of these algorithms, they were compared with stochastic noise reduction algorithms known as SAGA and SVRG.

El propósito principal de este trabajo es estudiar métodos de optimización estocástica usados para minimizar el problema de sumas finitas para funciones convexas. Dentro de dichos métodos se exponen, puntualmente, en el trabajo el método del descenso del gradiente con mini-batch, y la versión estocástica del método de Frank-Wolfe (o Gradiente condicionado). Para el método del descenso del gradiente con mini-batch se mostró una cota sobre el número de iteraciones necesarias para converger, que depende del tamaño del batch usado en el algoritmo. Posteriormente se encontró un tamaño óptimo de este donde se minimiza el número de iteraciones necesarias para la convergencia. Por otro lado, en la parte dedicada al estudio de la nueva versión estocástica del algoritmo de Frank-Wolfe, se mostró explícitamente el funcionamiento del algoritmo. Además, se demostraron lemas y teoremas que garantizan su convergencia en un tiempo menor o igual que el método original. Se redefinió el método de parada del algoritmo, mostrando que es una versión estocástica equivalente al método de parada original. Finalmente, se implementaron los algoritmos con datos reales usando las funciones de perdida de las regresiones logísticas y lineales como las funciones del problema enunciado al principio de este resumen. Para evaluar el rendimiento de estos algoritmos, se compararon con algoritmos estocásticos de reducción de ruido conocidos como SAGA y SVRG.