Trampas de lo no convexo y reinicios

Cuando hay más de un valle

La mayoría de los modelos interesantes no son convexos. Sus objetivos tienen varios mínimos locales, puntos de silla y mesetas, y el descenso de gradiente simplemente rueda hacia el valle en que empieza. Tomemos $f(x)=x^4-3x^2+x$. Su derivada $4x^3-6x+1$ se anula en $x=-1.301$, $x=0.170$ y $x=1.131$. El primero y el último son mínimos con $f=-3.514$ y $f=-1.070$, y el del medio es una loma entre ellos. El descenso con paso pequeño desde $x_0=2$ acaba en $1.131$, solo un mínimo local, y desde $x_0=-2$ acaba en $-1.301$, el global. Dos inicios tan cercanos como $x_0=0.1$ y $x_0=0.2$, a ambos lados de la loma en $0.170$, acaban en valles distintos.

Los puntos de silla son la otra trampa. Allí el gradiente es cero pero el hessiano tiene valores propios de ambos signos, así que la función baja en unas direcciones y sube en otras. En dimensiones altas la mayoría de los puntos estacionarios son sillas, y el descenso de gradiente simple se arrastra cerca de ellas. El momento, el ruido de los minilotes y la información de segundo orden ayudan a escapar. Las mesetas, donde el gradiente es minúsculo en una región amplia, parecen convergencia pero no lo son.

El remedio habitual es reiniciar. Ejecute el optimizador desde $K$ puntos de partida distintos y quédese con el resultado de menor valor del objetivo. Si cada inicio cae independientemente en el valle global con probabilidad $p$, al menos uno de $K$ inicios lo hace con probabilidad $1-(1-p)^K$. Para $p=0.2$ y $K=10$ es $0.893$, y llegar al $99\%$ requiere $K\ge\ln0.01/\ln0.8=20.6$, es decir 21 inicios. Mejores puntos de partida también ayudan: una solución de una relajación convexa, la calibración de ayer o una búsqueda en rejilla sobre los pocos parámetros que más importan.

• Mínimos locales: el descenso acaba en el valle donde empieza, así que el inicio decide la respuesta.
• Sillas y mesetas: gradiente nulo o diminuto sin mínimo; el momento y el ruido ayudan.
• Reinicios: $K$ inicios tienen éxito con probabilidad $1-(1-p)^K$; conserve el mejor valor del objetivo.

Lab: qué se califica

• El valor del mínimo global15 pts
• Empezar en x = 215 pts
• Dos inicios cercanos15 pts
• Éxito de reinicios aleatorios15 pts
• Cuántos reinicios15 pts
• Cerca de un punto de silla10 pts
• Comparar los resultados de los reinicios15 pts