Armadilhas do não convexo e reinícios

Quando há mais de um vale

A maioria dos modelos interessantes não é convexa. Seus objetivos têm vários mínimos locais, pontos de sela e platôs, e a descida do gradiente simplesmente rola para o vale em que começa. Tome $f(x)=x^4-3x^2+x$. Sua derivada $4x^3-6x+1$ se anula em $x=-1.301$, $x=0.170$ e $x=1.131$. O primeiro e o último são mínimos com $f=-3.514$ e $f=-1.070$, e o do meio é uma lombada entre eles. A descida com passo pequeno a partir de $x_0=2$ termina em $1.131$, apenas um mínimo local, e a partir de $x_0=-2$ termina em $-1.301$, o global. Dois inícios tão próximos quanto $x_0=0.1$ e $x_0=0.2$, dos dois lados da lombada em $0.170$, terminam em vales diferentes.

Pontos de sela são a outra armadilha. Neles o gradiente é zero mas a hessiana tem autovalores de ambos os sinais, então a função desce em algumas direções e sobe em outras. Em altas dimensões a maioria dos pontos estacionários são selas, e a descida do gradiente simples se arrasta perto delas. O momento, o ruído dos minilotes e a informação de segunda ordem ajudam a escapar. Platôs, em que o gradiente é minúsculo numa região ampla, parecem convergência mas não são.

O remédio padrão é reiniciar. Execute o otimizador a partir de $K$ pontos de partida diferentes e fique com o resultado de menor valor do objetivo. Se cada início cai independentemente no vale global com probabilidade $p$, então pelo menos um dos $K$ inícios o faz com probabilidade $1-(1-p)^K$. Para $p=0.2$ e $K=10$ isso dá $0.893$, e chegar a $99\%$ exige $K\ge\ln0.01/\ln0.8=20.6$, ou seja 21 inícios. Melhores pontos de partida também ajudam: uma solução de um relaxamento convexo, a calibração de ontem ou uma busca em grade nos poucos parâmetros que mais importam.

• Mínimos locais: a descida termina no vale em que começa, então o início decide a resposta.
• Selas e platôs: gradiente zero ou minúsculo sem mínimo; momento e ruído ajudam.
• Reinícios: $K$ inícios têm sucesso com probabilidade $1-(1-p)^K$; guarde o melhor valor do objetivo.

Lab: o que é avaliado

• O valor do mínimo global15 pts
• Começar em x = 215 pts
• Dois inícios próximos15 pts
• Sucesso de reinícios aleatórios15 pts
• Quantos reinícios15 pts
• Perto de um ponto de sela10 pts
• Comparar os resultados dos reinícios15 pts