O fornecimento de gradientes aproximados a um otimizador baseado em gradiente é inútil?

Não faz sentido usar algoritmos de otimização baseados em gradiente se você puder fornecer apenas um gradiente numérico? Caso contrário, por que fornecer um gradiente numérico em primeiro lugar, se é trivial executar diferenciação finita para a própria biblioteca de otimização?

[EDITAR]

• Apenas para esclarecer, minha pergunta é, de fato, em um sentido mais geral do que uma aplicação específica. Embora meu campo de aplicação seja a otimização de probabilidade em várias estruturas estatísticas.

• Meu problema com a diferenciação automática é que sempre parece haver um problema. A biblioteca do AD não pode se propagar para chamadas de biblioteca externa (como BLAS) ou você precisa refazer seu fluxo de trabalho de forma tão drástica que dificulta lidar com isso ... especialmente se você estiver trabalhando com linguagens sensíveis ao tipo. Minhas queixas com o AD são uma questão completamente separada. Mas eu quero acreditar!

• Acho que preciso formular melhor minha pergunta, mas estou fazendo um péssimo trabalho. Se houver uma opção para usar um algoritmo de otimização livre de derivado ou um algoritmo de otimização baseado em derivado com a ressalva de que só posso fornecer um gradiente numérico, qual, em média, será superior?

Para complementar a excelente resposta de Brian, deixe-me dar um pouco de background (editorial). Métodos de otimização sem derivativos são definidos como métodos que utilizam apenas avaliações de função e são basicamente todas as variações de "amostrar o conjunto admissível de forma mais ou menos sistemática e salvar o melhor valor de função" - é tudo o que você pode fazer com essas informações. Esses métodos podem ser subdivididos aproximadamente em

1. $1$ sobre sua função, isso é tudo o que você pode fazer e pode ter sorte.

2. Métodos determinísticos , em que a seleção de amostras não é aleatória, ou seja, baseada puramente em avaliações de funções anteriores. O exemplo mais famoso é provavelmente o método simplex Nelder - Mead; outros estão gerando métodos de pesquisa definidos . É importante perceber que isso só funciona se houver alguma relação (explorável) entre o valor da função em diferentes pontos - ou seja, alguma suavidade da função. De fato, a teoria da convergência para, por exemplo, o método Nelder - Mead é baseada na construção de um método não uniforme.aproximação por diferença finita do gradiente com base nos valores da função nos vértices do simplex e mostrando que ele converge para o gradiente exato e zero, à medida que o simplex se contrai até um ponto. (A variante baseada em uma aproximação de diferença finita padrão é chamada de busca da bússola .)

3. Métodos baseados em modelo , em que os valores da função são usados ​​para construir um modelo local da função (por exemplo, por interpolação), que é minimizado usando métodos padrão (baseados em gradiente / Hessian). Como uma aproximação por diferença finita é equivalente à derivada exata de um interpolante polinomial, a abordagem clássica de "gradiente numérico" também se enquadra nessa classe.

Como você pode ver, os limites entre essas classes são fluidos e, muitas vezes, apenas uma questão de interpretação. Mas a moral deve ser clara: use todas as informações disponíveis sobre a função que você está minimizando. Para citar Cornelius Lanczos:

A falta de informação não pode ser remediada por nenhum truque matemático.

Afinal, se você não sabe nada sobre sua função, ela também pode ser completamente aleatória, e minimizar um valor aleatório é uma tarefa fácil.

Se seu objetivo for suave, o uso de aproximações de diferenças finitas à derivada geralmente é mais eficaz do que o algoritmo de otimização livre de derivada. Se você possui um código que calcula exatamente as derivadas, normalmente é melhor usar esse código do que usar aproximações de diferenças finitas.

Embora algumas bibliotecas de otimização calculem aproximações de diferenças finitas para você usando automaticamente heurísticas para determinar os parâmetros de tamanho da etapa, pode ser melhor usar suas próprias rotinas para calcular as aproximações de diferença finita ou porque você tem um conhecimento melhor dos tamanhos de etapas apropriados ou por causa de estrutura especial na função que seu código pode explorar.

Outra opção que geralmente vale a pena é usar técnicas de diferenciação automática para produzir uma sub-rotina que calcula as derivadas analíticas do código-fonte para calcular a própria função objetivo.

Sua pergunta é sobre otimizadores baseados em gradiente, então acho que Brian estava certo. Gostaria apenas de compartilhar, já que atualmente estou lutando com isso, algumas das questões.

Os problemas com diferença finita são 1) desempenho, porque é necessário reavaliar a função novamente para cada dimensão e 2) pode ser complicado escolher um bom tamanho de etapa. Se o passo for muito grande, a suposição de linearidade da função pode não ser válida. Se o passo for muito pequeno, poderá ocorrer ruído na própria função, porque os derivados amplificam o ruído. O último pode ser um problema real se a função envolver a solução de equações diferenciais. Se for possível calcular os gradientes analiticamente ou usando equações de sensibilidade, certamente será mais preciso e talvez mais rápido.

Há outra abordagem que você pode tentar se ainda não investiu muito tempo no software, e é executá-lo com aritmética complexa. É chamado de diferenciação de etapas complexas . A idéia básica é que, quando você avaliar a função, se desejar o gradiente em relação ao parâmetro X, defina a parte imaginária de X para um número eps muito pequeno . Depois de fazer o cálculo, a parte imaginária do valor da função, dividida por eps , é o gradiente em relação a X. Quando você deseja o gradiente em relação a Y, é necessário fazer tudo novamente, é claro. O interessante é que epspode ser feito muito pequeno. A razão pela qual isso funciona é que as regras normais do cálculo diferencial são refletidas com precisão nas regras da aritmética complexa.

Dito isso, considero que não é uma panacéia, porque nem sempre é fácil executar uma função complicada em aritmética complexa, não vale a pena se o gradiente puder ser calculado analiticamente e, no caso de equações diferenciais, é exatamente equivalente a equações de sensibilidade , o que estou fazendo conforme necessário.