En la optimización matemática, ¿por qué alguien usaría el descenso de gradiente para una función convexa? ¿Por qué no encontrarían simplemente la derivada de esta función y buscarían el mínimo de la manera tradicional?

Como señala Priyanshu Ranjit, si n – el número de parámetros – es grande, entonces encontrar el mínimo de la función implica resolver un sistema de n ecuaciones. En el caso más simple, como en la regresión lineal, cuando este es un sistema de n ecuaciones lineales, esto implicará en general invertir una matriz nxn. El algoritmo estándar de inversión matricial es el tiempo O (n ^ 3). Entonces, cuando n es grande, incluso la regresión lineal puede tomar mucho tiempo para resolverse directamente. Y si las ecuaciones ni siquiera son lineales, entonces el problema de encontrar una solución exacta será aún más difícil, si no imposible (debe haber algunos resultados insolubles de tipo teoría de Galois en la optimización convexa, ¿verdad?).

El descenso de gradiente a menudo nos permite evitar tales cuellos de botella. Pero el problema es que no se puede encontrar rigurosamente un límite sobre el tiempo que tardará en converger (por lo que sé, aunque soy nuevo en este tema). Sin embargo, el argumento principal para el descenso de gradiente parece ser que, en la práctica, parece funcionar bien y converger al mínimo muy rápidamente .

Otro problema con el descenso de gradiente es que, en general, cuando la función no es convexa, encontrará un mínimo local, y no necesariamente un mínimo global, aunque no tendrá este problema si la función es convexa, por ejemplo en regresión lineal .

Un tercer problema es el hecho de que el descenso de gradiente, estrictamente hablando, solo produce una solución aproximada, y nunca una solución exacta. Pero nuevamente, en la práctica, esto generalmente parece no ser realmente un problema.

El descenso de gradiente se puede modificar con bastante facilidad para hacer frente a las restricciones, mientras que encontrar una solución analítica a los problemas de optimización restringidos es generalmente un error.

Si es una función convexa, y el número de parámetros de optimización es grande (digamos n), es decir, la función de costo es n-variable; usando el método grad (f) = 0, necesitaría resolver un sistema de n ecuaciones correspondientes a cada derivada parcial, para obtener la solución.

Esto puede incurrir en un costo computacional mucho más alto (especialmente si el sistema de ecuaciones no es lineal) que usar el descenso de gradiente, donde calcula las n derivadas parciales en cada paso e itera hasta llegar a la solución, sin necesidad de resolver ningún sistema de ecuaciones .

El punto de usar el descenso de gradiente para problemas de optimización convexa es proponer aproximaciones numéricas a la solución ideal, basadas en un proceso iterativo. Calcular los gradientes y actualizar nuestra estimación para el mínimo nos permite explorar incluso espacios de diseño complejos de muchas dimensiones (variables) que juntas constituyen la función objetivo del problema de optimización.

Las soluciones numéricas tienen la ventaja de poder simularse en una computadora, con el resultado de que puede tener una gran cantidad de iteraciones y una solución “lo suficientemente buena” o “casi ideal”, que es lo suficientemente buena para problemas de ingeniería y datos análisis.

Si está interesado en aprender sobre el descenso de gradiente, aquí hay 3 referencias que personalmente he encontrado útiles:

• La optimización convexa de Boyd es famosa, legible y gratuita.
• Las conferencias introductorias de Nesterov sobre optimización convexa están escritas en un estilo más conciso, pero asume más conocimientos matemáticos.
• El blog de Sebastian Bubeck, que tiene notas de su curso sobre optimización en Princeton, ORF523.

Si lee estas cosas, encontrará pruebas sobre límites inferiores en las tasas de optimización cuando solo hay derivados de primer orden disponibles. Para ciertas clases de funciones convexas, puede probar que tiene que mirar un cierto número de valores derivados para llegar a una solución que esté dentro de [math] \ epsilon [\ math] del valor óptimo de la función. Y a menudo hay algoritmos de descenso de gradiente que alcanzan estos límites inferiores; en cierto sentido, no se pueden mejorar para esa clase de problema. Por lo tanto, los algoritmos de descenso de gradiente no son necesariamente más lentos que otros métodos.

El descenso de gradiente está utilizando la derivada de la función en un punto inicial, avanzando a lo largo de ella, luego encontrando la derivada nuevamente, etc.

Veo que te refieres a resolver d / dx = 0

Desafortunadamente, no siempre puedes hacer esto directamente. considere mínimos cuadrados: la fórmula normal para resolver esto se basa en d / dx = 0, pero desafortunadamente crece cúbicamente (no cuadráticamente; whoops) en el número de variables. Esto es muy malo a veces.

Los métodos de descenso de gradiente, especialmente las variantes estocásticas (que toman datos uno por uno en lugar de todos a la vez, tratándolos como muestras de la función real) pueden implementarse linealmente en la dimensionalidad de los datos.

Por lo que aprendí cuando estaba haciendo mi proyecto de maestría.

Los siguientes tres factores interactúan para determinar qué tan difícil es encontrar una solución óptima para cualquier problema de optimización y por qué los métodos tradicionales simplemente no son suficientes.

1. Las relaciones entre el objetivo y las restricciones con respecto a las variables de optimización : si un problema de optimización consiste principalmente en relaciones lineales e incluso unas pocas relaciones no lineales, entonces debe resolverse utilizando métodos sofisticados de optimización no lineal.

2. El tamaño del problema de optimización: un problema de optimización se vuelve difícil de resolver a medida que aumenta el número de variables y restricciones.

3. El uso de variables enteras: si un problema de optimización se ocupa de los requisitos de memoria de las variables enteras y el tiempo de resolución crece exponencialmente con respecto al número de variables primarias.

PD: Una vez intenté resolver un problema de optimización convexa, créanme que todo en este mundo no es TAN simple, ni siquiera pensé en el descenso del gradiente.

No soy un experto de ninguna manera, de hecho, probablemente sea un novato en el mejor de los casos, así que corrígeme si estoy equivocado, pero pensé que el punto principal del aprendizaje automático es que no sabes cuál es la naturaleza de la función que eres tratar de optimizar es / no conoce la estructura dentro de los datos, por lo tanto, utiliza gradiente decente como método para encontrar lo óptimo dentro de los datos sin conocer la función. El uso de información previa como ‘la derivada de una función convexa’ supone asumir que sabe algo sobre lo que está tratando de optimizar antes de optimizarlo.

Gracias a todos por todas esas excelentes respuestas.

Sin ir por esos tecnicismos y rigor matemático, es importante comprender un hecho simple de que, estrictamente hablando sobre la aplicación del descenso de gradiente en el aprendizaje automático, realmente no tenemos ninguna información previa sobre la función para optimizar. Por el contrario, se nos han dado un montón de puntos de datos (vectores de características y categorías de clase en el aprendizaje supervisado como en la retropropagación en Perceptrón de múltiples capas, etc.) y se supone que debemos encontrar (aproximar) la función de los datos dados optimizando el costo (error o pérdida) función.

Usamos el descenso de gradiente para optimizar la función de costo y obtenemos valores apropiados (los puntos de datos dados más adecuados) de los parámetros para la función que modela aproximadamente los datos dados (en el caso de una red neutral artificial llamamos a este entrenamiento y venimos con pesas entrenadas).

En tales casos, realmente no tenemos ninguna función para aplicar la “forma tradicional”.

Primero, el descenso de gradiente está tratando de encontrar el punto con gradiente cero. Segundo, consideremos un ejemplo simple. Sabemos que el polinomio de grado mayor 4 no tiene una solución de forma cerrada. Entonces, incluso si tomamos un polinomio convexo (una función variable) de grado mayor que 5, obtenemos que la derivada (o gradiente) tiene un grado de al menos 5 para el cual no tenemos una solución de forma cerrada. Pero sí sabemos que la función es convexa y el gradiente apunta hacia la dirección en que aumenta la función (argumento simple de la serie de Taylor). Combinando estos dos, nos acercamos al punto óptimo.

Porque para una función convexa, el descenso de gradiente siempre convergerá eventualmente dado un tamaño de paso lo suficientemente pequeño y un tiempo infinito

Supongo que la pregunta asume implícitamente: 1 descenso de gradiente estocástico puede resolver la solución global cuando el objetivo no es convexo. 2 ¿por qué no usar el método original de newton-raphson?
para 1: tenga en cuenta que la versión de vainilla simple del descenso de gradiente asume convexidad
para 2: nr requiere una inversión de matriz en cada paso, que es inestable y lenta, a pesar de que la iteración externa converge cuadráticamente. A este respecto, el descenso de gradiente es una adaptación codiciosa de la idea básica de newton-raphson para eliminar la inversión a costa de tamaños de escalón subóptimos.