BFGS vs L-BFGS - quão diferentes eles são realmente?

Estou tentando implementar um procedimento de otimização em Python usando BFGS e L-BFGS em Python, e estou obtendo resultados surpreendentemente diferentes nos dois casos. O L-BFGS converge para o mínimo adequado super rápido, enquanto o BFGS converge muito lentamente, e isso também para um mínimo sem sentido.

PERGUNTA: Das minhas leituras, parece-me que BFGS e L-BFGS são basicamente o algoritmo (métodos quase-Newton), exceto que o último usa menos memória e, portanto, é mais rápido. Isso é verdade? Caso contrário, se eles são mais diferentes, então como?

Por fim, quero descobrir se a diferença de desempenho se deve a algumas diferenças nos algoritmos reais ou à sua implementação nos módulos SciPy do python.

EDIT: estou adicionando alguns dados para apoiar minhas alegações de comportamento divergente dos dois algoritmos.

 RUNNING THE L-BFGS-B CODE

       * * *

Machine precision = 2.220D-16
N =          147     M =           10
This problem is unconstrained.

At X0         0 variables are exactly at the bounds
At iterate    0    f=  2.56421D+04    |proj g|=  1.19078D+03
At iterate    1    f=  2.12904D+04    |proj g|=  1.04402D+03
At iterate    2    f=  1.49651D+03    |proj g|=  2.13394D+02
At iterate    3    f=  6.08288D+02    |proj g|=  9.85720D+01
At iterate    4    f=  2.91810D+02    |proj g|=  6.23062D+01
...
At iterate  142    f=  3.27609D+00    |proj g|=  8.80170D-04
Time taken for minimisation: 36.3749790192


*** BFGS code ***

At iterate    1,  f= 21249.561722 
At iterate    2,  f= 15710.435098 
At iterate    3,  f= 15443.836262 
At iterate    4,  f= 15386.035398 
At iterate    5,  f= 15311.242917 
At iterate    6,  f= 15211.986938 
At iterate    7,  f= 15022.632266
...
At iterate  524,  f= 67.898495
...
Warning: Desired error not necessarily achieved due to precision loss.
Iterations: 1239
Time taken: 340.728140116

optimization ap21
fonte

L-BFGS é literalmente uma aproximação do BFGS que usa menos memória; portanto, você pode esperar que ele converja mais lentamente. No entanto, como ambas são aproximações em um sentido, é possível que o L-BFGS tenha 'sorte' por sua entrada específica. Outra opção é sua máquina ter um forte gargalo de memória ao executar o BFGS, mas não para o L-BFGS. Portanto, se nenhum dos algoritmos tem um comportamento estranho independente um do outro, você simplesmente não possui dados para afirmar que uma implementação em particular apresenta desempenho inferior ao outro.

Lagarto discreto

@Discretelizard, compartilhei alguns dados que mostram como o BFGS e o LBFGS progridem para minha função a partir de alguma condição inicial. Observe como o valor da função diminui por ordem de grandeza para LBFGS em algumas iterações, mas caiu apenas um pouco para BFGS. Minha pergunta é basicamente sobre por que poderia / deveria haver uma discrepância tão grande no comportamento da pesquisa?

ap21

Bem, ambos aproximam o 'melhor caminho' para encontrar o melhor, portanto, seu desempenho pode diferir em uma grande quantidade de conjuntos de dados. Para obter uma resposta precisa, você pode verificar se / por que o método de L-BFGS produz uma etapa de descida de gradiente muito melhor para essa função específica. Eu acho que uma visualização do espaço da solução mostrando o 'caminho' de ambos os métodos seria útil para ter uma idéia do que está acontecendo.

Lagarto discreto

Considere usar um espaço de solução de menor dimensão. Se você estiver realmente interessado no comportamento desses algoritmos em sua função específica, precisará usar os detalhes da função (por exemplo, a função convexa, polinomial, linear, descontínua etc.) e o espaço da solução (é

R^{n}

$\mathbb{R}^n$ , um conjunto convexo, um poliedro etc.), pois duvido que exista uma condição genérica sobre a qualidade relativa desses métodos em funções arbitrárias.

Lagarto discreto

Não, é o contrário que estou dizendo. BFGS e LBFGS podem teoricamente convergir para soluções completamente diferentes (se houver vários mínimos locais) com diferentes velocidades de convergência, dependendo de como você escolhe a função e o espaço da solução. Portanto, se você quiser afirmar que a implementação tem limitações, teste uma grande quantidade de funções e espaços de solução diferentes.

Lagarto discreto

Não, eles não são os mesmos. Em certo sentido, o L-BFGS é uma aproximação ao BFGS, que requer muito menos memória. BFGS e L-BFGS são explicados em grande detalhe em muitos recursos padrão.

Muito grosseiramente, você pode pensar na diferença assim. O BFGS calcula e armazena o Hessian completo $H$ em cada passo; isto exige $\Theta(n^2)$ espaço onde $n$ conta o número de variáveis (dimensões) que você está otimizando. O L-BFGS calcula e armazena uma aproximação ao Hessian, escolhida para que a aproximação possa ser armazenada em $\Theta(n)$ espaço. Efetivamente, o L-BFGS usa a aproximação $H \approx M^\top M$ para alguns $k \times n$ matriz $M$ (Eu acho que).

Cada passo do L-BFGS é uma tentativa de aproximar / adivinhar o que o passo correspondente do BFGS faria. No entanto, uma única etapa do L-BFGS ocupa muito menos espaço e tempo do que uma única etapa do BFGS. Conseqüentemente, você pode executar muito mais etapas do L-BFGS dentro de um determinado período de tempo que o BFGS. Portanto, você pode achar que o L-BFGS converge mais rapidamente, porque ele pode fazer muito mais iterações em um determinado período de tempo do que o BFGS.

Não sei o que significa um mínimo sem sentido, ou por que o BFGS convergiria para algo pior que o L-BFGS se ambos pudessem executar por um período ilimitado de tempo.

DW
fonte

Por favor, veja os seguintes links. O mínimo sem sentido dado por BFGS - plot.ly/~apal90/162 - e o mínimo bom (um cilindro) dado por LBFGS - plot.ly/~apal90/160 .

ap21

O que você está dizendo é que o BFGS e o LBFGS devem teoricamente convergir para a mesma solução, o tempo não sendo uma barreira, certo? Então, estamos realmente analisando as limitações da implementação do algoritmo no SciPy, certo?

ap21 27/02

O L-BFGS funciona melhor nessa instância, mesmo com a mesma quantidade de iterações. Portanto, o L-BFGS com iterações mais rápidas não explica a diferença aqui.

Lagarto discreto

@Discretelizard, você está certo. As informações detalhadas sobre as duas execuções não estavam disponíveis quando eu escrevi minha resposta, então eu estava adivinhando - e parece que meu palpite não estava correto. Não sei por que o ap21 está vendo o comportamento listado na pergunta. Espero que outra pessoa seja capaz de fornecer uma resposta melhor.

BFGS vs L-BFGS - quão diferentes eles são realmente?

Respostas: