¿Por qué la optimización convexa es tan importante en el aprendizaje automático?

Muchos métodos en el aprendizaje automático se basan en encontrar parámetros que minimicen alguna función objetiva. Muy a menudo, la función objetivo es una suma ponderada de dos términos: una función de costo y regularización. En términos estadísticos, la probabilidad (log-) y (log-) anterior. Si ambos componentes son convexos, entonces su suma también es convexa.

Ejemplos de problemas de optimización convexa en el aprendizaje automático:

• regresión lineal / regresión de cresta, con regularización de Tikhonov, etc.
• regresión lineal dispersa con regularización L1, como lazo
• soporte de máquinas de vectores
• estimación de parámetros en series temporales lineal-gaussianas (filtro de Kalman y amigos)

Ejemplos típicos de optimización no convexa en ML son

• Redes neuronales
• mezclas de máxima verosimilitud de gaussianos

Si la función objetivo es convexa, eso viene con buenas garantías. Lo más importante, si una función es estrictamente convexa, se garantiza que tiene un mínimo global único , y se puede encontrar por varios métodos estándar.
Las funciones no convexas pueden tener varios mínimos locales, es decir, múltiples puntos que satisfacen que son el mejor punto en su vecindario local, pero que no son óptimos a nivel mundial. Por lo tanto, si tiene un problema no convexo, generalmente no hay forma de probar si la solución que ha encontrado es realmente la mejor solución.
Además, si un problema es convexo, generalmente es más fácil analizar el comportamiento asintótico del algoritmo, es decir, qué tan rápido converge a medida que observa más y más datos.

Existen múltiples escuelas de pensamiento en el aprendizaje automático, algunas están más obsesionadas con la convexidad que otras. Dependiendo de dónde vienes y cuáles son tus objetivos, la convexidad puede ser más o menos importante para ti. En cualquier caso, es importante que comprenda los beneficios de la convexidad y que tenga un conocimiento decente de varios métodos de programación lineal, cuadrática y convexa que puede usar para resolver problemas convexos.

Casi todos los algoritmos de aprendizaje automático que he visto pueden tratarse como un problema de optimización. Regresión lineal / SVM / K-means / Redes neuronales / … lo que sea. Algunos de ellos son convexos, otros no. Es por eso que la optimización es un gran problema en el aprendizaje automático. Escuché que un tipo con un doctorado en aprendizaje automático dijo: “Considero que cada problema de aprendizaje automático es un problema de optimización”.

Entonces, ¿por qué la optimización “convexa” es tan importante? Bueno, porque no podemos manejar muy bien la optimización no convexa. El problema convexo tiene una propiedad tan buena que óptimo local == óptimo global. Es una clase muy pequeña de problemas en todo el conjunto de problemas de optimización, pero lamentablemente los humanos solo pueden manejar esto bien actualmente.

Este es un tema bastante antiguo, pero me gustaría agregar a las numerosas explicaciones ya proporcionadas.

En el aprendizaje supervisado, nuestro objetivo es obtener los parámetros de una función que devuelve el error mínimo cuando hacemos una predicción. Esta función se conoce como función de pérdida de error y normalmente tiene forma de “U” cuando se visualiza en un plano bidimensional, es decir, existe un punto que da el error mínimo. La parte central representa el error mínimo y con las técnicas de optimización convexa podemos minimizar la función hasta que haya convergencia hacia este punto.

Los diferentes algoritmos de optimización convexa tienen diferentes propiedades de convergencia con los que se puede medir en términos del número de filas o columnas en los datos de entrenamiento. En esta era de Big Data, se vuelve más importante comprender los diferentes algoritmos y determinar la mejor opción para el tipo de problema que nos gustaría resolver.

Agregaré una razón más:
Para problemas de optimización convexa, la brecha de dualidad [1] es cero bajo una condición de calificación de restricción.
Por lo tanto, una solución al problema dual proporciona un límite en el valor de la solución al problema primario; cuando el problema es convexo y satisface una calificación de restricción, entonces el valor de una solución óptima del problema primario viene dado por el problema dual.
[1] los valores óptimos de los problemas primarios y duales no necesitan ser iguales. Su diferencia se llama brecha de dualidad.
ejemplo: el problema de la ruta más corta (en un gráfico ponderado +) se puede formular como un problema de flujo de costo mínimo (forma primaria) y los Dijkstra (& A *) son algoritmos primarios-duales que resuelven la forma dual.

1. El análisis local ofrece una solución global si el problema es convexo, esto simplifica el análisis y garantiza la unicidad de la solución. Ahora entrando en el contexto de ML, la mayoría de los problemas son convexos o, si no son convexos, se produce su aproximación convexa. Como la aproximación L2 de diferentes normas. Es por eso que la optimización convexa es tan importante en el aprendizaje automático

La conveniencia no es un motivo de importancia. La razón fundamental es que, al formular un modelo, tendemos a hacer que el problema sea convexo sin darse cuenta; y muchos fenómenos en el mundo exhiben convexidad o convexidad por partes.

Si quieres una respuesta corta: porque el problema convexo no tiene un mínimo local.