Cientistas da Computação Descobrem Os Limites do Algoritmo de Pesquisa Principal

Muitos aspectos da pesquisa aplicada moderna contam com um algoritmo crucial chamado gradiente descendente. Este é um procedimento geralmente usado para encontrar os maiores ou menores valores de uma função matemática específica – um processo conhecido como otimização da função. Ele pode ser usado para calcular qualquer coisa, desde a maneira mais lucrativa de fabricar um produto até a melhor maneira de atribuir turnos aos trabalhadores.

No entanto, apesar dessa utilidade generalizada, os pesquisadores nunca compreenderam completamente com quais situações o algoritmo mais luta. Agora, um novo trabalho explica isso, estabelecendo que a descida gradiente, no fundo, aborda um problema computacional fundamentalmente difícil. O novo resultado impõe limites ao tipo de desempenho que os pesquisadores podem esperar da técnica em aplicações específicas.

“Há uma espécie de pior caso de dureza que vale a pena conhecer”, disse Paul Goldberg da Universidade de Oxford, co-autor do trabalho junto com John Fearnley e Rahul Savani da Universidade de Liverpool e Alexandros Hollender de Oxford. O resultado recebeu o prêmio de Melhor Artigo em junho no Simpósio anual de Teoria da Computação.

Você pode imaginar uma função como uma paisagem, onde a elevação do terreno é igual ao valor da função (o “lucro”) naquele local específico. A descida gradiente procura o mínimo local da função procurando a direção da subida mais íngreme em um determinado local e procurando na descida longe dela. A inclinação da paisagem é chamada gradiente, daí o nome gradiente descida.

O gradiente descendente é uma ferramenta essencial da pesquisa aplicada moderna, mas existem muitos problemas comuns para os quais não funciona bem. Mas antes desta pesquisa, não havia uma compreensão abrangente do que exatamente faz com que a descida de gradiente tenha dificuldades e quando – questões que outra área da ciência da computação conhecida como teoria da complexidade computacional ajudaram a responder.

“Muito do trabalho na descida gradiente não estava relacionado à teoria da complexidade”, disse Costis Daskalakis, do Instituto de Tecnologia de Massachusetts.

A complexidade computacional é o estudo dos recursos, muitas vezes tempo de computação, necessários para resolver ou verificar as soluções para diferentes problemas de computação. Os pesquisadores classificam os problemas em classes diferentes, com todos os problemas da mesma classe compartilhando algumas características computacionais fundamentais.

Para dar um exemplo – relevante para o novo jornal – imagine uma cidade onde há mais pessoas do que casas e todos moram em uma casa. Você recebe uma lista telefônica com os nomes e endereços de todas as pessoas da cidade e pede para encontrar duas pessoas que morem na mesma casa. Você sabe que pode encontrar uma resposta, porque há mais pessoas do que casas, mas pode demorar um pouco para procurar (especialmente se não houver sobrenome).

Esta questão pertence a uma classe de complexidade chamada TFNP, abreviação de “polinômio de função total não determinística”. É a coleção de todos os problemas computacionais que têm soluções garantidas e cujas soluções podem ser verificadas quanto à exatidão rapidamente. Os pesquisadores se concentraram na interseção de dois subconjuntos de problemas no TFNP.

 O primeiro subconjunto é denominado PLS (pesquisa local polinomial). Esta é uma coleção de problemas que envolvem encontrar o valor mínimo ou máximo de uma função em uma determinada região. É garantido que esses problemas tenham respostas que podem ser encontradas por meio de um raciocínio relativamente direto.

Um problema que se enquadra na categoria PLS é a tarefa de planejar uma rota que permite que você visite um número fixo de cidades com a distância de viagem mais curta possível, uma vez que você só pode alterar a viagem mudando a ordem de qualquer par de cidades consecutivas no passeio. É fácil calcular o comprimento de qualquer rota proposta e, com um limite nas maneiras de ajustar o itinerário, é fácil ver quais mudanças encurtam a viagem. Você certamente encontrará uma rota que não pode melhorar com uma mudança aceitável – um mínimo local.

O segundo subconjunto de problemas é PPAD (argumentos de paridade polinomial em gráficos direcionados). Esses problemas têm soluções que emergem de um processo mais complicado chamado teorema do ponto fixo de Brouwer. O teorema diz que, para qualquer função contínua, é garantido haver um ponto que a função não altera – um ponto fixo, como é conhecido. Isso é verdade na vida diária. Se você mexer um copo d’água, o teorema garante que deve haver absolutamente uma partícula de água que vai acabar no mesmo lugar de onde começou.

A própria interseção das classes PLS e PPAD forma uma classe de problemas conhecida como PLS int PPAD. Ele contém muitos problemas naturais relevantes para pesquisadores da complexidade. No entanto, até agora, os pesquisadores não conseguiram encontrar um problema natural que fosse completo para PLS int PPAD – o que significa que é um exemplo dos problemas mais difíceis possíveis que se enquadram na classe.

Esse resultado põe freios em tudo o que você poderia atirar.

Antes deste artigo, o único problema PLS int PPAD-completo conhecido era uma construção um tanto artificial – um problema às vezes chamado de “Ambas as Soluções”. Esse problema juntou um problema completo do PLS e um problema completo do PPAD, formando algo que um pesquisador dificilmente encontraria fora desse contexto. No novo artigo, os pesquisadores provaram que a descida de gradiente é tão difícil quanto qualquer solução, tornando a própria descida de gradiente PLS int PPAD-complete.

“[A natureza da computação] é algo que nós, como espécie, devemos tentar compreender profundamente em todas as suas muitas formas. E eu acho que isso deve ser motivo suficiente para estar animado com este resultado ”, disse Tim Roughgarden, da Universidade de Columbia.

Nada disso significa que a descida gradiente sempre terá dificuldade. Na verdade, é tão rápido e eficaz como sempre para a maioria dos usos.

“Há um estereótipo ligeiramente humorístico sobre a complexidade computacional que diz que o que muitas vezes acabamos fazendo é pegar um problema que é resolvido na prática muitas vezes e provar que é realmente muito difícil”, disse Goldberg.

Mas o resultado significa que os pesquisadores aplicados não devem esperar que a descida gradiente forneça soluções precisas para alguns problemas onde a precisão é importante.

A questão da precisão fala à preocupação central da complexidade computacional – a avaliação dos requisitos de recursos. Existe uma ligação fundamental entre precisão e velocidade em muitas questões de complexidade. Para que um algoritmo seja considerado eficiente, você deve ser capaz de aumentar a precisão de uma solução sem pagar um preço correspondentemente alto no tempo que leva para encontrar essa solução. O novo resultado significa que, para aplicações que requerem soluções muito precisas, a descida gradiente pode não ser uma abordagem viável.

Por exemplo, a descida gradiente costuma ser usada no aprendizado de máquina de maneiras que não exigem precisão extrema. Mas um pesquisador de aprendizado de máquina pode querer dobrar a precisão de um experimento. Nesse caso, o novo resultado implica que eles podem ter que quadruplicar o tempo de execução de seu algoritmo de descida gradiente. Isso não é o ideal, mas não é um obstáculo.

Mas para outras aplicações, como em análise numérica, os pesquisadores podem precisar ajustar a precisão ao quadrado. Para alcançar tal melhoria, eles podem ter que ajustar o tempo de execução da descida do gradiente, tornando o cálculo completamente intratável.

“[Isso] põe um freio no que [eles] podem atirar”, disse Daskalakis.

Eles devem, e na prática fazem, se comprometer em algum lugar. Eles aceitam uma solução menos precisa, se limitam a problemas um pouco mais fáceis ou encontram uma maneira de gerenciar um tempo de execução difícil.

Mas isso não quer dizer que não exista um algoritmo rápido para descida gradiente. Pode ser. Mas o resultado significa que qualquer algoritmo implicaria imediatamente na existência de algoritmos rápidos para todos os outros problemas em PLS int PPAD – uma barra muito mais alta do que simplesmente encontrar um algoritmo rápido para a própria descida do gradiente.

“Muitos problemas que podem representar algum avanço na matemática podem ser resolvidos”, disse Daskalakis. “É por isso que gostamos de ter um problema muito natural, como a descida em gradiente, que captura a complexidade de toda a interseção.”

Fonte Principal