Nesterov Acceleration Schemes for Group Lasso
Author
Catalina Feliú, AlejandroAdvisor
Dorronsoro Ibero, José RamónEntity
UAM. Departamento de Ingeniería InformáticaDate
2017-06Subjects
Teoría de optimización convexa; Convex optimization; Group Lasso; InformáticaNote
Master’s degree of Investigation and Innovation in Information and Communications TechnologiesEsta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
Abstract
La teoría de optimización convexa es cuerpo fundamental para la resolución de muchos problemas
de aprendizaje automático y problemas del día a día. Estudiar y alcanzar una mejor
comprensión de estos métodos es por tanto un aspecto fundamental de cara a construir buenas soluciones y extraer conclusiones adecuadas. Además, centraremos también nuestra
atención en el estudio de modelos lineales como Lasso o Group Lasso, que incorporan varias
ventajas, siendo las más importantes el bajo coste computacional y la interpretabilidad de
los modelos finales.
En esta tesis de máster realizaremos en primer lugar un estudio del campo de la teoría
de optimización convexa desde un punto de vista puramente teórico, estudiando conceptos
como subdiferencial y minimización de problemas proximales de cara a minimizar funciones
compuestas donde alguna de sus componentes es no diferenciable. Este cuerpo teórico es
la base para estudiar ISTA, un primer enfoque iterativo para la minimización de tales
funciones. Para mejorar la convergencia de ISTA, Nesterov introdujo una optimización
para alcanzar una convergencia _optima de O(1=k2) que supone una mejora sustancial
frente al O(1=k) de ISTA. Este método optimizado se conoce hoy en día como FISTA. No
obstante, a pesar de que esta optimización nos permite alcanzar una convergencia teórica más rápida, en la práctica puede resultar en una evolución no monótona, que normalmente
afecta la convergencia haciéndola más lenta. Para resolver estos problemas se han propuesto
ciertas mejoras en la literatura. En este sentido hemos estudiado los esquemas de reinicio
propuestos por O'Donogue y Candes y posteriores optimizaciones incluidas por Ito en su
método FAPG.
A la hora de mostrar los efectos de estas optimizaciones presentaremos varios experimentos.
Un primer experimento consistirá en datos generados de forma sintética con
propósitos ilustrativos. Este experimento se centrará en el estudio de los efectos que las
distintas optimizaciones tienen sobre los métodos y su ventaja sobre FISTA. En este experimento
podemos ver claramente como los métodos optimizados son mejores en términos
de iteraciones para converger. No obstante, un ejemplo sintético no nos permite extraer
resultados concluyentes. Para ello hemos aplicado estos mismos métodos a un problema
de predicción de energía eólica en Sotavento, un parque eólico situado en Galicia. En este
experimento perseguimos dos objetivos. En primer lugar, comparar Group Lasso como
método competitivo contra otros modelos lineales como pueden ser Lasso y Ridge Regression.
Por otro lado, perseguimos replicar los experimentos del ejemplo sintético, estudiando
el efecto de las distintas optimizaciones en situaciones complejas de cross validation.
En resumen, hemos observado que las optimizaciones no son solo útiles en un contexto
de único experimento, sino que en el peor caso los métodos optimizados muestran un
rendimiento similar a los demás, y que por tanto podemos obtener un mayor beneficio
en contextos de cross validation, donde probamos muchos modelos y por tanto el coste
computacional es mayor. Esto tiene que ver con la forma del problema y del termino de
regularización. Una penalización pequeña supone un área muy amplia para buscar la solución, y por tanto podemos esperar una optimización mayor. Por otro lado, una penalización
muy grande simplifica demasiado el problema y hace que, en esencia, todos los modelos se
comporten de forma similar. En términos de competitividad, Group Lasso se comporta de
manera muy similar a los demás, teniendo una pequeña ventaja en expresividad cuando
hablamos de la interpretabilidad final del modelo. Convex optimization is a fundamental theoretical core for many well known machine learning
models used in day-to-day problems. Studying and getting a better understanding of
these methods is an important aspect to build good models and extract proper conclusions.
Furthermore, we will also focus on the study of linear models such as Lasso and Group
Lasso, which incorporates several advantages, being the most important ones the cheap
computational cost and the interpretability of the resulting models.
In this Master's Thesis we will rst review the eld of convex optimization from a pure
theoretical point of view, studying concepts such as subdi erential and proximal descent
minimization in order to minimize composite functions where one of its components is
non di erentiable. This theoretical background is the base to study ISTA, a rst iterative
approach to minimize such functions. To improve the convergence of ISTA, Nesterov rst
introduced an optimization to reach an optimal convergence ratio of O(1=k2), which is
a signi cant improvement over the O(1=k) convergence of ISTA. This optimized method
is known as FISTA. Nonetheless, even if this optimization allows us to reach a faster
theoretical convergence, in practice we see that it may not be monotone, which usually
a ects the convergence, making it slower in real applications. To solve these issues there
have been several proposals. We have studied here some restarting schemes proposed by
O'Donoghe and Candes and further optimizations introduced by Ito and colleagues that
actually make FISTA faster in practice.
To show the e ects of these optimizations we have ended this work by presenting some
real experiments. A rst experiment consists on synthetic data generated from a Gaussian
distribution. This experiment focuses on exploring the e ects of the di erent proposed
optimizations and its advantage over standard FISTA. In this experiment we clearly see
how the optimized methods are clearly better in terms of iterations to convergence than
FISTA. Nonetheless, a synthetic experiment is not a conclusive demonstration. For this, we
have also applied these methods to a real problem of wind energy prediction in Sotavento,
a wind farm located in Galicia, northwest Spain. In this experiment we pursue two goals.
First, to test the usefulness of the optimized methods in a complex cross-validation setup
where we test many hyperparameters and the e ects of such strategies. Second, to test
Group Lasso as a competitive model against state of art models such as Lasso and Ridge.
In summary, we have observed that the optimizations are not only useful in a singlerun
setup, where the worst case shows a performance similar to standard FISTA, but in a
cross-validation setup, where the bene t is actually greater. This has to do with the shape
of the problem and the penalization term. A small penalization implies a very wide area
to nd the solution, and then a greater optimization may be expected. On the other hand,
a big penalization makes the problem pretty much \straightforward", making all models
behave similarly. In terms of competitiveness, we see that Group Lasso performs similarly
to other methods such as Lasso, and better than Ridge, with the added advantage of a
grouped structure and thus an interesting interpretation of the nal model in terms of
feature selection.
Files in this item
Google Scholar:Catalina Feliú, Alejandro
This item appears in the following Collection(s)
Except where otherwise noted, this item's license is described as https://creativecommons.org/licenses/by-nc-nd/4.0/
Related items
Showing items related by title, author, creator and subject.