P.D. / Wikimedia
Uma técnica matemática de Isaac Newton amplamente utilizada foi atualizada e poderá agora, finalmente, ser aplicada a problemas infinitamente complexos.
Há 300 anos, Isaac Newton desenvolveu um algoritmo bastante simples para encontrar o valor mínimo de uma função.
Séculos mais tarde, o método de Newton continua a ser crucial para a resolução de problemas atuais em logística, finanças, computação.
Embora extremamente poderoso, também tem uma falha significativa. Como aponta a Quanta Magazine, não funciona com todas as funções.
Por esse motivo, os matemáticos têm continuado a estudar a técnica, descobrindo diferentes formas de alargar o seu âmbito sem sacrificar a eficiência.
Um estudo publicado recentemente no arXiv anunciou a última melhoria do método de Newton.
Amir Ali Ahmadi, da Universidade de Princeton, juntamente com os seus alunos Abraar Chaudhry e Jeffrey Zhang, alargaram o método de Newton para trabalhar eficientemente na classe mais vasta de funções até agora.
Método com séculos de existência
As funções podem ter dezenas de variáveis elevadas a potências elevadas, desafiando a análise de fórmulas. Os gráficos das suas soluções formam paisagens de grande dimensão que são impossíveis de explorar a partir de uma vista aérea.
Na década de 1680, Newton reconheceu que, mesmo quando estamos a lidar com uma função muito complicada, temos sempre acesso a pelo menos duas informações que nos ajudam a encontrar o seu vale mais profundo.
É possível calcular a chamada primeira derivada da função, ou declive: a inclinação da função num determinado ponto. Depois, podemos calcular a taxa a que o declive está a mudar (a segunda derivada da função).
Newton provou que, se repetirmos o processo continuamente, acabamos por chegar ao valor mínimo da função original, mais complicada. O método nem sempre funciona, especialmente se começarmos num ponto demasiado afastado do mínimo verdadeiro. Mas, na maior parte das vezes, funciona.
O método de Newton converge para o mínimo verdadeiro muito mais rapidamente: a uma taxa “quadrática”.
Newton poderia ter escrito o seu método para convergir para o verdadeiro valor mínimo ainda mais rapidamente se, em vez de tomar apenas a primeira e a segunda derivadas em cada ponto, tivesse tomado também a terceira e a quarta derivadas. Isso ter-lhe-ia dado aproximações de Taylor mais complicadas, com expoentes superiores a 2.
Mas o objetivo da sua estratégia era transformar uma função complicada numa mais simples. Estas equações de Taylor mais complicadas eram mais do que Newton conseguia lidar matematicamente.
Desafio: alargar o método de Newton
Nos séculos que se seguiram, os matemáticos esforçaram-se por alargar o método de Newton, para investigar a quantidade de informação que podem extrair das aproximações de Taylor mais complicadas das suas funções.
Como relata a Quanta Magazine, em 2021, Yurii Nesterov demonstrou como aproximar eficientemente funções de qualquer número de variáveis com equações cúbicas. Mas o seu método não podia ser alargado para aproximar funções utilizando equações quárticas, quínticas, etc., sem perder a sua eficiência. No entanto, a prova foi um grande avanço neste domínio.
Agora, o novo estudo leva a teoria de Nesterov mais longe. O algoritmo funciona para qualquer número de variáveis e para um número arbitrário de derivadas. Além disso, mantém-se eficiente em todos estes casos – algo que até agora não era possível.
Como?
Não existe um método rápido e de uso geral para encontrar os mínimos de funções elevadas a expoentes elevados. Essa foi sempre a principal limitação do método de Newton.
Mas, como escreve a Quanta Magazine, há certos tipos de funções que têm caraterísticas que as tornam fáceis de minimizar.
No novo estudo, Ahmadi, Chaudhry e Zhang provam que é sempre possível encontrar equações de aproximação que tenham essas caraterísticas.
Que propriedades tornam uma equação fácil de minimizar? Duas coisas.
A primeira é que a equação deve ser em forma de taça, ou “convexa”. Em vez de ter muitos vales, tem apenas um (o que significa que quando tentamos minimizá-la, não temos de nos preocupar em confundir um vale arbitrário com o vale mais baixo). A segunda é que a equação pode ser escrita como uma soma de quadrados.
Ahmadi, Chaudhry e Zhang descobriram como usar uma técnica chamada “programação semidefinida” que cumpre os requisitos; e conseguiram criar uma versão mais poderosa do método de Newton – capaz de atingir o valor mínimo verdadeiro de uma função em menos iterações do que as técnicas anteriores.
Se, com o tempo, a tecnologia computacional subjacente necessária para executar o método de Newton se tornar mais eficiente, então o algoritmo desenvolvido por Ahmadi, Chaudhry e Zhang poderá eventualmente ultrapassar a descida gradiente para todo o tipo de aplicações, incluindo a aprendizagem automática.
“O nosso algoritmo é, neste momento, comprovadamente mais rápido, em teoria”, afirmou Ahmadi. Tem esperança de que dentro de 10 a 20 anos também o seja na prática.
