Descida de gradiente em funções não convexas

9

Que situações sabemos onde a descida do gradiente pode convergir (para um ponto crítico ou para um mínimo local / global) para funções não convexas?


Para o SGD em funções não convexas, um tipo de prova foi revisado aqui, http://www.cs.cornell.edu/courses/cs6787/2017fa/Lecture7.pdf

estudante de graduação
fonte
2
Este artigo: arxiv.org/pdf/1602.04915.pdf pode ser útil. Em particular: "se [a função] for duas vezes continuamente diferenciável e satisfizer a propriedade estrita da sela, a descida gradiente com uma inicialização aleatória e tamanho de passo constante suficientemente pequeno converge para um minimizador local ou infinito negativo quase certamente"
David Kozak
Obrigado! Gostaria de saber se há um sentido em que o artigo que você citou é mais fraco do que esse resultado mais recente, arxiv.org/abs/1709.01434 Alguma idéia?
gradstudent
Convenientemente que o trabalho já está na minha lista para ser abordado esta semana, retornarei a você com uma resposta adequada depois de digerido.
David Kozak
Obrigado! Ansioso para uma discussão! : D Deixe-me saber se você conhece algum protótipo "pequeno" de tais provas de mostrar convergência em descidas gradientes não convexas!
gradstudent

Respostas:

3

Veja o apêndice B1 em https://web.stanford.edu/~boyd/cvxbook/ .

A função e a restrição podem não ser convexas em um programa quadrático quadraticamente restrito e você ainda pode ver uma forte dualidade (é garantido se uma condição técnica conhecida como qualificador de restrição de Slater for mantida)

A forte dualidade em termos fracos significa que podemos resolver o problema de otimização. A partir do problema original chamado primal, você pode formular um problema alternativo denominado problema duplo. A solução do problema duplo fornece uma solução que, em certo sentido, é o "melhor limite inferior" para os problemas originais

Em muitos dos problemas de otimização que não são convexos, haverá uma lacuna entre as soluções primária e dupla, ou seja, o limite inferior pode estar muito abaixo do verdadeiro valor ótimo (até o infinito negativo). Em alguns casos especiais, o limite é apertado. Esses casos especiais são aqueles em que temos forte dualidade.

O algoritmo é uma TÉCNICA usada para chegar ao ponto ideal. A solução ideal e nossa capacidade de encontrá-la dependem da GEOMETRIA do problema (que é o que a dualidade tenta chegar). Em poucas palavras, a análise diz que, se a otimização configurada corretamente convergir para o mínimo.

Em geral, a descida do gradiente converge para um ponto estacionário. Este ponto pode ser um mínimo local / mínimo global / mínimo de sela. Em apenas alguns casos não convexos, podemos garantir o que converge para

Sid
fonte
O que é um QCQP e o que significa ver forte dualidade?
MachineEpsilon
@ Sid O que isso tem a ver com a convergência da descida do gradiente sobre a qual estou perguntando?
gradstudent
Eu editei minha resposta. Minhas desculpas para o respone concisa
Sid
3

Nesta resposta, explorarei dois artigos interessantes e relevantes que foram levantados nos comentários. Antes de fazer isso, tentarei formalizar o problema e lançar alguma luz sobre algumas das suposições e definições. Começo com um artigo de 2016 de Lee et al.

Buscamos minimizar uma função não-convexa que é delimitada abaixo. Exigimos que seja duas vezes diferenciável. Usamos um algoritmo de descida de gradiente da forma:f:RdR

.xxt+1=xxt-αf(xxt)

Além disso, temos o seguinte requisito:

.__f(xx1)-f(xx2)____xx1-xx2__,para todos xx1,xx2

Ou seja, exigimos que nossa função seja -Lipschitz em sua primeira derivada. Em inglês, isso se traduz na ideia de que nosso gradiente não pode mudar muito rapidamente em qualquer lugar do domínio. Essa suposição garante que podemos escolher um tamanho de etapa para que nunca terminemos com etapas que divergem.

Lembre-se de que um ponto Diz-se que x é uma sela estrita se f ( xxx e λ min ( 2 f ( xf(xx)=0 0e λ máx ( 2 f ( xλmin(2f(xx))<0 0. Se todos os autovalores do Hessiano tiverem o mesmo sinal, o ponto será mínimo (se positivo) ou máximo (negativo). Se houver 0 autovalores de 0, é considerado degenerado e não é uma sela estrita.λmax(2f(xx))>0 0

O artigo mostra que, com as suposições acima, juntamente com a suposição de que todos os pontos de sela da função são de sela estrita, a descida do gradiente é garantida para convergir ao mínimo.

A prova é bastante técnica, mas a intuição é a seguinte: defina um conjunto , onde xWs(xxs)={xx:limkgk(xx)=xxs} é um ponto de sela. Eu não gosto dessa notação. O que eles estão tentando chegar é queWé o conjunto de valores iniciais para o qual o gradiente mapag: R d R d envia xxxsWg:RdRd a xxxk . Em termos mais claros, é o conjunto de inicializações aleatórias que acabarão convergindo para uma sela.xxs

O argumento deles baseia-se no teorema do coletor estável. Com as suposições acima e um grupo de matemática esotéricos Eles concluem que o conjunto de deve ser medida de zero, isto é, não há nenhuma probabilidade de inicializar aleatoriamente em um ponto que irá convergir para um ponto de sela. Como sabemos que a descida do gradiente em funções do tipo descrito nas suposições com tamanhos de degraus adequadamente pequenos chegará a um ponto crítico e agora sabemos (quase com certeza) que ele nunca cairá em uma sela, sabemos que converge para um minimizador.Ws

O segundo artigo, mais recente, de Reddi et al. Vou discutir em menos detalhes. Existem várias diferenças. Primeiro, eles não estão mais trabalhando em uma estrutura determinística, optando pela estrutura de aproximação estocástica mais praticamente relevante em uma soma finita (pense em Descida de gradiente estocástico). As principais diferenças são que o tamanho da etapa requer algum cuidado adicional e o gradiente se torna uma variável aleatória. Além disso, relaxam a suposição de que todas as selas são rígidas e procuram um ponto estacionário de segunda ordem. Isto é, um ponto tal que, __(f)__ϵ,e,λmin(2f(xx))-ρϵ

Onde é a constante de Lipschitz para o Hessian. (Ou seja, além do requisito de que nosso gradiente não varie muito rapidamente, agora temos um requisito semelhante em nosso Hessian. Essencialmente, os autores estão procurando por um ponto que pareça um mínimo na primeira e na segunda derivada.rho

O método pelo qual eles realizam isso é usar uma variante (escolha a sua favorita) de descida de gradiente estocástico na maioria das vezes. Mas onde quer que encontrem um ponto em que , eles usam ummétodo de segunda ordemadequadamente escolhidopara escapar da sela. Eles mostram que, incorporando essas informações de segunda ordem, conforme necessário, elas convergirão para um ponto estacionário de segunda ordem.λmin(2f(xx))0 0

Tecnicamente, este é um método de gradiente de segunda ordem, que pode ou não se enquadrar nos algoritmos em que você estava interessado.

Esta é uma área de pesquisa muito ativa e deixei de fora muitas contribuições importantes (ex Ge et al. ). Eu também sou novo no tópico, então esta pergunta me proporcionou uma oportunidade de procurar. Fico feliz em continuar a discussão, se houver interesse.

*** Escolhido adequadamente significa aquele que é mostrado para convergir para um ponto estacionário de segunda ordem. Eles usam o método Newton regularizado cúbico de Nesterov e Polyak.

David Kozak
fonte
1
Obrigado pela resposta! Dois comentários (a) Eu acho que Reddi et. al. é um resultado melhor do que Lee et. al. porque é uma convergência com uma taxa vinculada e não apenas um resultado assintótico. (b) Existe este artigo que parece reivindicar (e parece) melhor do que todos esses artigos, opt-ml.org/papers/OPT2017_paper_16.pdf
gradstudent
Concordou, e é muito mais simples matematicamente. Mas o resultado de Lee é interessante por sua abordagem única - acho que haverá mais progresso nessa direção quando começarmos a procurar maneiras de entender superfícies não-convexas de alta dimensão. Vou verificar o artigo que você referenciou, obrigado por isso!
David Kozak
Vamos acrescentar mais uma pergunta: Dado este Reddi et. al. artigo ainda existe alguma relevância no artigo mais famoso do mesmo grupo, arxiv.org/abs/1603.06160
gradstudent 15/02/18
Definitivamente, há relevância, pois a variante de descida de gradiente que eles usam em seu artigo mais recente é o SVRG. Podemos encerrar esta questão e começar de novo, para que a comunidade obtenha o benefício de participar. Ainda não li o artigo que você recomendou além do resumo, mas ele está na lista e pode inspirar mais perguntas.
David Kozak
2

Tentarei responder à parte "quando a descida do gradiente convergir para um ponto crítico" da pergunta.

O artigo "Métodos de convergência de descida para problemas semi-algébricos e mansos: algoritmos proximais, divisão para frente e para trás e métodos Gauss-Seidel regularizados"

por Attouch, Bolte e Svaiter,

mostra que, se a função objetivo satisfaz a desigualdade de Kurdyka-Lojasiewicz (KL), GD e outros métodos de descida de fato convergem para um minimizador. Observe que a condição KL é extremamente geral, mas difícil de entender. Funções que satisfazem KL são dadas, por exemplo, por funções semi-algébricas (novamente, muito geral, mas não uma noção simples).

fx¯ϕ

||(ϕf)(x)||1
xf(x¯)<f(x)<rrϕfx¯

A semialgebricidade, por outro lado, é um pouco mais difícil. O campo que o estuda também é conhecido como geometria mansa . Eu acho que o nome manso captura muito bem a essência. As funções pertencentes a essa classe não podem ser arbitrariamente "selvagens".

xel
fonte
Obrigado! Deixe-me procurar! Você pode adicionar algumas intuições sobre essa condição?
gradstudent
Atualizei minha resposta com alguma intuição. Espero que ajude.
xel