Descenso de gradiente

En matemáticas, descenso de gradiente (también llamado descenso más pronunciado) es un algoritmo de optimización iterativo de primer orden para encontrar un mínimo local de una función diferenciable. La idea es dar pasos repetidos en la dirección opuesta del gradiente (o gradiente aproximado) de la función en el punto actual, porque esta es la dirección del descenso más pronunciado. Por el contrario, avanzar en la dirección del gradiente conducirá a un máximo local de esa función; el procedimiento se conoce entonces como ascenso de gradiente. Es particularmente útil en el aprendizaje automático para minimizar la función de costo o pérdida. El descenso de gradiente no debe confundirse con los algoritmos de búsqueda local, aunque todos son métodos iterativos para la optimización.

El descenso de gradiente generalmente se atribuye a Augustin-Louis Cauchy, quien lo sugirió por primera vez en 1847. Jacques Hadamard propuso de forma independiente un método similar en 1907. Sus propiedades de convergencia para problemas de optimización no lineal fueron estudiadas por primera vez por Haskell Curry en 1944, con el método se volvió cada vez más estudiado y utilizado en las décadas siguientes.

Una extensión simple del descenso de gradiente, el descenso de gradiente estocástico, sirve como el algoritmo más básico que se usa para entrenar la mayoría de las redes profundas en la actualidad.

Descripción

Ilustración de descenso de gradiente en una serie de conjuntos de nivel

El descenso del gradiente se basa en la observación de que si la función multivariable F()x){displaystyle F(mathbf {x})} es definido y diferenciable en un barrio de un punto a{displaystyle mathbf {a}, entonces F()x){displaystyle F(mathbf {x})} disminuciones más rápido si uno va de a{displaystyle mathbf {a} en la dirección del gradiente negativo de F{displaystyle F} a a,− − Silencio Silencio F()a){displaystyle mathbf {a}-nabla F(mathbf {a}}. De ello se desprende, si

an+1=an− − γ γ Silencio Silencio F()an){displaystyle mathbf {a} ¿Qué? ¿Por qué?

para un pequeño tamaño de paso o tasa de aprendizaje γ γ ▪ ▪ R+{displaystyle gamma in mathbb [R] _{+}, entonces F()an)≥ ≥ F()an+1){displaystyle F(mathbf {a_{n})geq F(mathbf {a_{n+1}}}}. En otras palabras, el término γ γ Silencio Silencio F()a){displaystyle gamma nabla F(mathbf {a})} se restringe de a{displaystyle mathbf {a} porque queremos movernos contra el gradiente, hacia el mínimo local. Con esta observación en mente, uno comienza con una conjetura x0{displaystyle mathbf {x} ¿Qué? para un mínimo local F{displaystyle F}, y considera la secuencia x0,x1,x2,...... {displaystyle mathbf {x} _{0},mathbf {x} ¿Qué? tales que

xn+1=xn− − γ γ nSilencio Silencio F()xn),n≥ ≥ 0.{displaystyle mathbf {x} _{n+1}=mathbf {x} _{n}-gamma _{n}nabla F(mathbf {x} _{n}), ngeq 0}

Tenemos una secuencia monótona

F()x0)≥ ≥ F()x1)≥ ≥ F()x2)≥ ≥ ⋯ ⋯ ,{displaystyle F(mathbf {x} _{0})geq F(mathbf {x} _{1})geq F(mathbf {x} _{2})geq cdots}

Así que, con suerte, la secuencia ()xn){displaystyle (mathbf {x} _{n})} converge al mínimo local deseado. Note que el valor del tamaño del paso γ γ {displaystyle gamma } se permite cambiar en cada iteración. Con ciertas suposiciones sobre la función F{displaystyle F} (por ejemplo, F{displaystyle F} convex y Silencio Silencio F{displaystyle nabla F} Lipschitz) y opciones particulares de γ γ {displaystyle gamma } (por ejemplo, elegido ya sea a través de una búsqueda de línea que satisface las condiciones de Wolfe, o el método Barzilai-Borwein demostrado como sigue),

γ γ n=Silencio()xn− − xn− − 1)T[Silencio Silencio F()xn)− − Silencio Silencio F()xn− − 1)]Silencio.Silencio Silencio F()xn)− − Silencio Silencio F()xn− − 1).2{fn} {fn} {fn} {fn} {fn}fn}fn} {fn} {fn}fn} {cHFF}cHFF}cHFF}cHFF}cH00}}cH00}cH00}cHFF}

Se puede garantizar la convergencia a un mínimo local. Cuando la función F{displaystyle F} es convex, todas las minima locales son también minima global, por lo que en este caso el descenso gradiente puede converger a la solución global.

Este proceso se ilustra en la imagen adyacente. Aquí, F{displaystyle F} se supone que se define en el plano, y que su gráfico tiene una forma de tazón. Las curvas azules son las líneas de contorno, es decir, las regiones en las que el valor F{displaystyle F} es constante. Una flecha roja originada en un punto muestra la dirección del gradiente negativo en ese punto. Tenga en cuenta que el gradiente (negativo) en un punto es ortogonal a la línea de contorno pasando por ese punto. Vemos ese gradiente descenso nos lleva al fondo del tazón, es decir, al punto donde el valor de la función F{displaystyle F} es mínimo.

Una analogía para entender el gradiente descendente

Fog en las montañas

La intuición básica detrás del descenso de gradiente se puede ilustrar con un escenario hipotético. Una persona está atrapada en las montañas y está tratando de bajar (es decir, tratando de encontrar el mínimo global). Hay mucha niebla, por lo que la visibilidad es extremadamente baja. Por lo tanto, el camino que baja de la montaña no es visible, por lo que deben usar la información local para encontrar el mínimo. Pueden usar el método de descenso de pendiente, que consiste en observar la inclinación de la colina en su posición actual y luego proceder en la dirección con el descenso más pronunciado (es decir, cuesta abajo). Si estuvieran tratando de encontrar la cima de la montaña (es decir, el máximo), entonces procederían en la dirección del ascenso más empinado (es decir, cuesta arriba). Usando este método, eventualmente encontrarían su camino montaña abajo o posiblemente quedarían atrapados en algún agujero (es decir, mínimo local o punto de silla), como un lago de montaña. Sin embargo, asuma también que la inclinación de la colina no es inmediatamente obvia con una simple observación, sino que requiere un instrumento sofisticado para medir, que la persona tiene en ese momento. Lleva bastante tiempo medir la inclinación de la colina con el instrumento, por lo que deben minimizar el uso del instrumento si quieren bajar de la montaña antes del atardecer. La dificultad entonces es elegir la frecuencia con la que se debe medir la pendiente del cerro para no desviarse.

En esta analogía, la persona representa el algoritmo y el camino recorrido por la montaña representa la secuencia de configuración de parámetros que explorará el algoritmo. La pendiente de la colina representa la pendiente de la función en ese punto. El instrumento utilizado para medir la inclinación es la diferenciación. La dirección en la que eligen viajar se alinea con el gradiente de la función en ese punto. La cantidad de tiempo que viajan antes de tomar otra medida es el tamaño del paso.

Elegir el tamaño del paso y la dirección de descenso

Desde el uso de un tamaño de paso γ γ {displaystyle gamma } que es demasiado pequeño retrasaría la convergencia, y γ γ {displaystyle gamma } demasiado grande conduciría a la divergencia, encontrando un buen entorno γ γ {displaystyle gamma } es un problema práctico importante. Philip Wolfe también abogó por utilizar en la práctica "opciones más claras de la dirección [descendente]". Mientras que usando una dirección que se desvía de la dirección de descenso más pronunciada puede parecer contra-intuitiva, la idea es que la pendiente más pequeña puede ser compensada por ser sostenida a una distancia mucho más larga.

Para razonar sobre esto matemáticamente, considerar una dirección pn{displaystyle mathbf {p} _{n} y tamaño del paso γ γ n{displaystyle gamma _{n} y considerar la actualización más general:

an+1=an− − γ γ npn{displaystyle mathbf {a} ¿Qué? _{n}-gamma ¿Qué?.

Encontrar buenas configuraciones de pn{displaystyle mathbf {p} _{n} y γ γ n{displaystyle gamma _{n} requiere un poco de pensamiento. En primer lugar, nos gustaría la dirección de actualización para apuntar cuesta abajo. Matemáticamente, dejando Silencio Silencio n{displaystyle theta _{n} denota el ángulo entre − − Silencio Silencio F()an){displaystyle - 'nabla F(mathbf {a_{n}}} y pn{displaystyle mathbf {p} _{n}, esto requiere que 0.}" xmlns="http://www.w3.org/1998/Math/MathML">#⁡ ⁡ Silencio Silencio n■0.{displaystyle cos theta _{n} {0}0.}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/54c11842aa128a748a96c2103dcf0a266806b6ba" style="vertical-align: -0.671ex; width:10.715ex; height:2.509ex;"/> Para decir más, necesitamos más información sobre la función objetiva que estamos optimizando. Bajo la hipótesis bastante débil F{displaystyle F} es continuamente diferente, podemos probar que:

F()an+1)≤ ≤ F()an)− − γ γ n.. Silencio Silencio F()an).. 2.. pn.. 2[#⁡ ⁡ Silencio Silencio n− − maxt▪ ▪ [0,1].. Silencio Silencio F()an− − tγ γ npn)− − Silencio Silencio F()an).. 2.. Silencio Silencio F()an).. 2]{displaystyle F(mathbf {a} _{n+1})leq F(mathbf {a} _{n})-gamma _{n}fn}fnbla F(mathbf {a} _{n})fn}fn}fn}fnhncH3} ¿Por qué? _{n}-tgamma _{n}mathbf {p})-nabla F(mathbf {a} _{n}) imper_{2}{fnbla F(mathbf {a} ¿Qué?

()1)

Esta desigualdad implica que la cantidad por la que podemos estar seguros de la función F{displaystyle F} la disminución depende de un intercambio entre los dos términos entre corchetes. El primer término entre corchetes mide el ángulo entre la dirección de descenso y el gradiente negativo. El segundo término mide lo rápido que el gradiente cambia a lo largo de la dirección de descenso.

En principio la desigualdad (1) se puede optimizar sobre pn{displaystyle mathbf {p} _{n} y γ γ n{displaystyle gamma _{n} para elegir un tamaño y dirección de paso óptimos. El problema es que la evaluación del segundo término entre corchetes requiere la evaluación Silencio Silencio F()an− − tγ γ npn){displaystyle nabla F(mathbf {a} ¿Por qué?, y evaluaciones extra gradientes son generalmente costosas e indeseables. Algunas maneras en torno a este problema son:

• Forja los beneficios de una dirección de ascendencia inteligente estableciendo pn=Silencio Silencio F()an){displaystyle mathbf {p} _{n}=nabla F(mathbf {a_{n}) }, y utilizar la búsqueda de línea para encontrar un tamaño paso adecuado γ γ n{displaystyle gamma _{n}, como uno que satisface las condiciones de Wolfe. Una manera más económica de elegir las tasas de aprendizaje es la búsqueda de líneas de retroceso, un método que tiene buenas garantías teóricas y resultados experimentales. Note que uno no necesita elegir pn{displaystyle mathbf {p} _{n} para ser el gradiente; cualquier dirección que tenga producto de intersección positivo con el gradiente resultará en una reducción del valor de la función (para un valor suficientemente pequeño γ γ n{displaystyle gamma _{n}).
• Suponiendo que F{displaystyle F} es dos veces diferente, utilizar su Hessian Silencio Silencio 2F{displaystyle nabla ^{2}F} estimación .. Silencio Silencio F()an− − tγ γ npn)− − Silencio Silencio F()an).. 2.. .. tγ γ nSilencio Silencio 2F()an)pn.. .{displaystyle {fnMicrosoft} ¿Por qué? "Mathbf"Entonces elija pn{displaystyle mathbf {p} _{n} y γ γ n{displaystyle gamma _{n} optimizando la desigualdad (1).
• Suponiendo que Silencio Silencio F{displaystyle nabla F} es Lipschitz, utiliza su constante de Lipschitz L{displaystyle L. a límites .. Silencio Silencio F()an− − tγ γ npn)− − Silencio Silencio F()an).. 2≤ ≤ Ltγ γ n.. pn.. .{displaystyle {fnMicrosoft} - No. _{n} Ltgamma ¿Qué? Entonces elija pn{displaystyle mathbf {p} _{n} y γ γ n{displaystyle gamma _{n} optimizando la desigualdad (1).
• Construya un modelo personalizado maxt▪ ▪ [0,1].. Silencio Silencio F()an− − tγ γ npn)− − Silencio Silencio F()an).. 2.. Silencio Silencio F()an).. 2{displaystyle max _{tin [0,1]}{frac {fncipenabla F(mathbf {a} _{n}-tgamma _{n}mathbf {p})-nabla F(mathbf {a} _{n}) imper_{2}{ perpetuanabla F(mathbf {a} ¿Qué? para F{displaystyle F}. Entonces elija pn{displaystyle mathbf {p} _{n} y γ γ n{displaystyle gamma _{n} optimizando la desigualdad (1).
• Bajo hipótesis más firmes sobre la función F{displaystyle F} como la convexidad, las técnicas más avanzadas pueden ser posibles.

Por lo general siguiendo una de las recetas anteriores, se puede garantizar la convergencia a un mínimo local. Cuando la función F{displaystyle F} es convex, todas las minima locales son también minima global, por lo que en este caso el descenso gradiente puede converger a la solución global.

Resolución de un sistema lineal

El algoritmo de descenso más pronunciado aplicado al filtro Wiener

El descenso de gradiente se puede utilizar para resolver un sistema de ecuaciones lineales

Ax− − b=0{displaystyle Amathbf {x} =0}

reformulado como un problema de minimización cuadrática. Si la matriz del sistema A{displaystyle A} es simétrico real y positivo-definido, una función objetiva se define como la función cuadrática, con minimización de

F()x)=xTAx− − 2xTb,{displaystyle F(mathbf {x}=mathbf {x} ^{T}Amathbf {x} -2mathbf {x}

para que

Silencio Silencio F()x)=2()Ax− − b).{displaystyle nabla F(mathbf {x})=2(Amathbf {x} -mathbf {b}).}

Para una matriz real general A{displaystyle A}, linear mínimo cuadrados definir

F()x)=.Ax− − b.2.{displaystyle F(mathbf {x}=leftAmathbf {x} -mathbf {b} {2}

En los cuadrados tradicionales lineales mínimos para real A{displaystyle A} y b{displaystyle mathbf {b} la norma Euclideana se utiliza, en cuyo caso

Silencio Silencio F()x)=2AT()Ax− − b).{displaystyle nabla F(mathbf {x})=2A^{T}(Amathbf {x} -mathbf {b}).}

La minimización de la búsqueda de líneas, encontrando el tamaño de paso óptimo localmente γ γ {displaystyle gamma } en cada iteración, se puede realizar analíticamente para funciones cuadráticas, y fórmulas explícitas para el localmente óptimo γ γ {displaystyle gamma } son conocidos.

Por ejemplo, para la matriz simétrica real y definitiva A{displaystyle A}, un algoritmo simple puede ser como sigue,

repetir en el bucle:r:=b− − Axγ γ :=rTr/rTArx:=x+γ γ rsirTres suficientemente pequeño, luego bucle de salidade repetición finalretornoxcomo resultado{begin{aligned} {text{repeat in the loop:}\\qquad mathbf {r}:=mathbf {b} -mathbf {m}cH00}cH00}mcH00} Mathbf {Ar}\\qquadmathbf {x}:=mathbf {x} {fnMicrosoft}fnMithbf {f}mhbox {f}mhbf {}m}mthbf {}cH}cH00}cH00} {text{ is enough small, then exit loop}}\\\text{end repeat loop}\ {text{return}}mathbf {x} {text{ as the result}end{aligned}}

Para evitar multiplicarse por A{displaystyle A} dos veces por iteración, notamos que x:=x+γ γ r{displaystyle mathbf {x}:=mathbf {x} +gamma mathbf {r} implicación r:=r− − γ γ Ar{displaystyle mathbf {r}:=mathbf {r} - 'gamma mathbf {Ar}, que da el algoritmo tradicional,

r:=b− − Axrepetir en el bucle:γ γ :=rTr/rTArx:=x+γ γ rsirTres suficientemente pequeño, luego bucle de salidar:=r− − γ γ Arde repetición finalretornoxcomo resultado{begin{aligned}mathbf {r}:=mathbf {b} -mathbf {Ax}\\\\cH00}\cH00}\cH00}\cH00}mcH00} {cH00}cH00}cH00} {cH0}cH00}}cH00}}}cH00}}}cH00}}cH00}}}cH0}cH0}cH00}cH0}cH0}cH0}cH00}cH00}cH0}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}}cH0}cH00}cH00}cH00}}}cH00}}}cH0} Mathbf {Ar}\\qquadmathbf {x}:=mathbf {x} {fnMicrosoft}fnMithbf {f}mhbox {f}mhbf {}m}mthbf {}cH}cH00}cH00} {text{ is enough small, then exit loop}\\qquadmathbf {r}:=mathbf {r} -gammamathbf {Ar}\\\fnK}\\fnK}Mathbf {x} {text{ as the result}end{aligned}}

El método se utiliza raramente para resolver ecuaciones lineales, siendo el método conjugado de gradiente una de las alternativas más populares. El número de iteraciones de descenso gradiente es comúnmente proporcional al número de condición espectral κ κ ()A){displaystyle kappa (A)} de la matriz del sistema A{displaystyle A} (la proporción de los eigenvalues máximos a mínimos ATA{displaystyle A.), mientras que la convergencia del método de gradiente conjugado se determina típicamente por una raíz cuadrada del número de condición, es decir, es mucho más rápido. Ambos métodos pueden beneficiarse del preacondicionamiento, donde el descenso de gradiente puede requerir menos supuestos en el precondicionador.

Resolución de un sistema no lineal

El descenso de gradiente también se puede usar para resolver un sistema de ecuaciones no lineales. A continuación se muestra un ejemplo que muestra cómo usar el descenso de gradiente para resolver tres variables desconocidas, x₁, x₂ y x₃. Este ejemplo muestra una iteración del descenso de gradiente.

Considere el sistema no lineal de ecuaciones

{}3x1− − #⁡ ⁡ ()x2x3)− − 32=04x12− − 625x22+2x2− − 1=0exp⁡ ⁡ ()− − x1x2)+20x3+10π π − − 33=0{displaystyle {begin{cases}3x_{1}-cos(x_{2}x_{3})-{tfrac {3}{2}=04x_{1}{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{tfrac {10pipi} -3}=0end{cases}

Introduzcamos la función asociada

G()x)=[3x1− − #⁡ ⁡ ()x2x3)− − 324x12− − 625x22+2x2− − 1exp⁡ ⁡ ()− − x1x2)+20x3+10π π − − 33],{displaystyle G(mathbf {x})={begin{bmatrix}3x_{1}-cos (x_{2}x_{3})-{tfrac {3}{2}4x_{1}{2}-625x_{2}{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{tfrac {10pi -3}{3}}\end{bmatrix}}}}}}}}}}\\\\\\\\4x_}}}}}}}}}}}\\\\\4}}}}}\\\\\\\\\\\\\\4}}}}}}}}}}}}\\\\\\\\\\\\\\\\4}}}}}}}}}}}}}}\\\\\\\\\\\\

dónde

x=[x1x2x3].{displaystyle mathbf {x} ={begin{bmatrix}x_{1}x_{2}x_{3}\end{bmatrix}}}

Ahora se podría definir la función objetivo

F()x)=12GT()x)G()x)=12[()3x1− − #⁡ ⁡ ()x2x3)− − 32)2+()4x12− − 625x22+2x2− − 1)2+()exp⁡ ⁡ ()− − x1x2)+20x3+10π π − − 33)2],{displaystyle {begin{aligned}F(mathbf {x}) {1}{2}}G^{mathrm {T}(mathbf {x})G(mathbf {x})\\\\\fnMicroc {2}{2}{2}} {2}{2}}{2}}} {2}}}}} {2}}} {2}} {2}}}}}}} {2}}}}} {2}}}} {2}}}}} {2}}}}} {2} {2}{2}}}}{2}}}d}}}}}{2}}{2}}}}}}}}}}}}}}}{2}{2}{2}}{2}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}{2}{2}{2}{2}{2}{2}}{2}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}{2}{2}}}}}}}

que intentaremos minimizar. Como suposición inicial, usemos

x()0)=0=[000].{displaystyle mathbf {x} {}=mathbf {0} ={begin{bmatrix}0\0end{bmatrix}}}}

Sabemos que

x()1)=0− − γ γ 0Silencio Silencio F()0)=0− − γ γ 0JG()0)TG()0),{displaystyle mathbf {x} {(1)}=mathbf {0} -gamma _{0}nabla F(mathbf {0})=mathbf {0} - 'gamma ¿Qué?

donde la matriz Jacobiana JG{displaystyle J_{G} es dado por

JG()x)=[3pecado⁡ ⁡ ()x2x3)x3pecado⁡ ⁡ ()x2x3)x28x1− − 1250x2+20− − x2exp⁡ ⁡ ()− − x1x2)− − x1exp⁡ ⁡ ()− − x1x2)20].{displaystyle J_{G}(mathbf {x})={begin{bmatrix}3 limitsin(x_{2}x_{3})x_{3} {3}sin(x_{2}x_{3})x_{2}8x_{1} limit50x_{2}+2 limit0\-x_{2} {-x_{1}x_{2}}}} {-x_{1}exp(-x_{1}x_{2} {20\\end{bmatrix}}}}

Calculamos:

JG()0)=[3000200020],G()0)=[− − 2.5− − 110.472].{displaystyle J_{G}(mathbf {0})={begin{bmatrix}3 limitada0 limitada0 limitada0 730 Umm2},qquad G(mathbf {0})={begin{bmatrix}-2.5\\\\10.472end}{bmatrix}} {betrix}} {cH0}cH00}}}}cH00cH00}cH00}cH00}cH00}cH00}cH00cH0}cH00cH0}cH00cH00cH00cH00}cH0}cH0}cH00}cH00cH00cH00cH00cH0}cH00}cH0}cH00cH00}cH00}cH00}cH00}cH00

Así

x()1)=0− − γ γ 0[− − 7.5− − 2209.44],{displaystyle mathbf {x} {(1)}=mathbf {0} {0} {begin{bmatrix}-7.5\209.44end{bmatrix}}}

y

F()0)=0.5()()− − 2.5)2+()− − 1)2+()10.472)2)=58.456.{displaystyle F(mathbf {0})=0.5left(-2.5)^{2}+(-1)^{2}+(10.472)^{2}right)=58.456.}

Una animación que muestra las primeras 83 iteraciones de descenso gradiente aplicadas a este ejemplo. Las superficies son isosurfaces de F()x()n)){displaystyle F(mathbf {x} { n)}} en la actualidad x()n){displaystyle mathbf {x} { n)}, y las flechas muestran la dirección del descenso. Debido a un pequeño y constante tamaño de paso, la convergencia es lenta.

Ahora, un adecuado γ γ 0{displaystyle gamma _{0} debe encontrarse tal que

F()x()1))≤ ≤ F()x()0))=F()0).{displaystyle Fleft(mathbf {x} ^{(1)}right)leq Fleft(mathbf {x} ^{(0)}right)=F(mathbf {0}}

Esto se puede hacer con cualquiera de una variedad de algoritmos de búsqueda de línea. Uno podría simplemente adivinar γ γ 0=0,001,{displaystyle gamma _{0}=0.001,} que da

x()1)=[0,00750,002− − 0.20944].{displaystyle mathbf {x} ^{(1)}={begin{bmatrix}0.0075\0.002\0.20944\\\end{bmatrix}}}

Al evaluar la función objetivo en este valor, se obtiene

F()x()1))=0.5()()− − 2.48)2+()− − 1.00)2+()6.28)2)=23.306.{displaystyle Fleft(mathbf {x} ^{(1)}right)=0.5left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}right)=23.306}

La disminución de F()0)=58.456{displaystyle F(mathbf {0})=58.456} al valor del siguiente paso

F()x()1))=23.306{displaystyle Fleft(mathbf {x} ^{(1)}right)=23.306}

es una disminución considerable en la función objetivo. Otros pasos reducirían aún más su valor hasta que se encontrara una solución aproximada para el sistema.

Comentarios

El descenso de gradiente funciona en espacios de cualquier número de dimensiones, incluso en dimensiones infinitas. En el último caso, el espacio de búsqueda es típicamente un espacio funcional, y se calcula la derivada de Fréchet del funcional a minimizar para determinar la dirección de descenso.

Que el descenso de gradiente funcione en cualquier cantidad de dimensiones (al menos en un número finito) puede verse como una consecuencia de la desigualdad de Cauchy-Schwarz. Ese artículo prueba que la magnitud del producto interno (punto) de dos vectores de cualquier dimensión se maximiza cuando son colineales. En el caso de descenso de gradiente, sería cuando el vector de ajustes de la variable independiente es proporcional al vector gradiente de derivadas parciales.

El descenso del gradiente puede requerir muchas iteraciones para calcular un mínimo local con la precisión requerida, si la curvatura en diferentes direcciones es muy diferente para la función dada. Para tales funciones, el preacondicionamiento, que cambia la geometría del espacio para dar forma a los conjuntos de niveles de función como círculos concéntricos, cura la convergencia lenta. Sin embargo, construir y aplicar el preacondicionamiento puede ser computacionalmente costoso.

El descenso gradiente se puede combinar con una búsqueda en línea, encontrando el tamaño de paso localmente óptimo γ γ {displaystyle gamma } en cada iteración. Realizar la búsqueda de la línea puede llevar mucho tiempo. Por el contrario, usando un pequeño fijo γ γ {displaystyle gamma } puede producir pobre convergencia.

Los métodos basados en el método de Newton y la inversión del Hessian utilizando técnicas de gradiente conjugada pueden ser mejores alternativas. Generalmente, estos métodos convergen en menos iteraciones, pero el costo de cada iteración es mayor. Un ejemplo es el método BFGS que consiste en calcular en cada paso una matriz por la que se multiplica el vector gradiente para entrar en una dirección "mejor", combinado con un algoritmo de búsqueda de líneas más sofisticado, para encontrar el valor "mejor" de γ γ .{displaystyle gamma.} Para problemas extremadamente grandes, donde predominan las cuestiones de memoria computarizada, se debe utilizar un método de memoria limitada como L-BFGS en lugar de BFGS o el descenso más pronunciado.

Si bien a veces es posible sustituir el descenso de gradiente por un algoritmo de búsqueda local, el descenso de gradiente no pertenece a la misma familia: aunque es un método iterativo para la optimización local, se basa en el gradiente de una función objetiva en lugar de una exploración explícita de un espacio de solución.

La bajada gradual se puede ver como aplicar el método de Euler para resolver ecuaciones diferenciales ordinarias x.()t)=− − Silencio Silencio f()x()t)){displaystyle x'(t)=-nabla f(x(t)} a un flujo gradiente. A su vez, esta ecuación puede derivarse como un controlador óptimo para el sistema de control x.()t)=u()t){displaystyle x'(t)=u(t)} con u()t){displaystyle u(t)} dado en forma de retroalimentación u()t)=− − Silencio Silencio f()x()t)){displaystyle u(t)=-nabla f(x(t)}.

Se puede demostrar que existe una correspondencia entre la neuroevolución y el descenso de gradiente.

Modificaciones

El descenso de gradiente puede converger a un mínimo local y disminuir la velocidad en la vecindad de un punto de silla. Incluso para la minimización cuadrática sin restricciones, el descenso de gradiente desarrolla un patrón en zig-zag de iteraciones posteriores a medida que avanzan las iteraciones, lo que da como resultado una convergencia lenta. Se han propuesto múltiples modificaciones del descenso de gradiente para abordar estas deficiencias.

Métodos de gradiente rápido

Yurii Nesterov ha propuesto una simple modificación que permite una convergencia más rápida para problemas convexos y desde entonces se ha generalizado. Para problemas lisos no constreñidos, el método se llama el método gradiente rápido (FGM) o el método gradiente acelerado (AGM). Específicamente, si la función diferenciable F{displaystyle F} es convexo y Silencio Silencio F{displaystyle nabla F} es Lipschitz, y no se supone que F{displaystyle F} es fuertemente convex, entonces el error en el valor objetivo generado en cada paso k{displaystyle k} por el método de descenso gradiente será atado por O()1k){fnMitcal {fnK}m} {fnMicroc}}derecho)}. Utilizando la técnica de aceleración Nesterov, el error disminuye en O()1k2){fnMicrosoft {fnMicrosoft}fnMicroc {1}{k^{2}}derecha)}. Se sabe que la tasa O()k− − 2){displaystyle {mathcal}left({k^{-2}right)} para la disminución de la función de coste es óptima para los métodos de optimización de primer orden. Sin embargo, hay la oportunidad de mejorar el algoritmo reduciendo el factor constante. El método de gradiente optimizado (OGM) reduce esa constante por un factor de dos y es un método óptimo de primer orden para problemas a gran escala.

Para problemas restringidos o no uniformes, la FGM de Nesterov se denomina método de gradiente proximal rápido (FPGM), un método de aceleración del gradiente proximal.

Método de impulso o bola pesada

Tratando de romper el patrón en zig-zag del descenso del gradiente, el método del impulso o bola pesada utiliza un término de impulso en analogía con una bola pesada deslizándose sobre la superficie de los valores de la función que se minimiza, o al movimiento de masas en la dinámica newtoniana a través de un medio viscoso en un campo de fuerza conservativo. El descenso de gradiente con impulso recuerda la actualización de la solución en cada iteración y determina la próxima actualización como una combinación lineal del gradiente y la actualización anterior. Para la minimización cuadrática sin restricciones, el límite de la tasa de convergencia teórica del método de la bola pesada es asintóticamente el mismo que el del método del gradiente conjugado óptimo.

Esta técnica se usa en el descenso de gradiente estocástico y como una extensión de los algoritmos de retropropagación que se usan para entrenar redes neuronales artificiales. En la dirección de actualización, el descenso de gradiente estocástico agrega una propiedad estocástica. Los pesos se pueden utilizar para calcular las derivadas.

Extensiones

El descenso de gradiente se puede extender para manejar restricciones al incluir una proyección en el conjunto de restricciones. Este método solo es factible cuando la proyección es eficientemente computable en una computadora. Bajo suposiciones adecuadas, este método converge. Este método es un caso específico del algoritmo adelante-atrás para inclusiones monótonas (que incluye programación convexa y desigualdades variacionales).

El descenso de gradiente es un caso especial de descenso de espejo que usa la distancia euclidiana al cuadrado como la divergencia de Bregman dada.