Accelerated Gradient Descent através do espelho ou como acelerar o Mirror Descent
Carregando...
Arquivos
Data
2025-09-30
Autores
Orientador(res)
Costa, Bernardo Freitas Paulo da
Métricas
Título da Revista
ISSN da Revista
Título de Volume
Resumo
Nesta dissertação, consideramos três métodos de primeira ordem com passo fixo para a resolução aproximada de problemas de otimização convexa. São eles: o método do gradiente descendente, o método de Nesterov (gradiente descendente acelerado) e o método de Bregman, ou Mirror Descent. Propomos ainda um quarto método, o Accelerated Mirror Descent (método de Bregman acelerado), concebido como uma versão acelerada (inspirada no método de Nesterov) do Mirror Descent, analisando duas possibilidades de aceleração: uma no espaço primal e outra no espaço dual. A formulação apresentada difere da versão do Accelerated Mirror Descent introduzida por [KBB15]. Além disso, apresentamos as equações diferenciais ordinárias (EDOs) associadas a cada método, cujas discretizaçõesdas das soluções correspondem às trajetórias dos algoritmos, incluindo a EDO do Accelerated Mirror Descent. Para esta última, demonstramos a existência e unicidade de solução dada uma condição inicial, bem como a convergência dos pontos gerados pelo método em direção à trajetória da solução, o que fornece uma prova mais detalhada também para resultados análogos ao método de Nesterov acelerado. Por fim, realizamos um experimento numérico para avaliar os efeitos das acelerações e da implementação do paradigma mirror na resolução de um problema de mínimos quadrados restrito ao simplex, em dimensões baixa (100) e alta (10.000). Os resultados indicam que ambas as estratégias melhoram substancialmente a convergência em alta dimensão.