Accelerated Gradient Descent através do espelho ou como acelerar o Mirror Descent

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.

Ficha do documento

Tipo

Dissertação

Ano

2025

Instituição

Fundação Getulio Vargas

Fonte

Repositório da FGV

Idioma

Português

Acesso

Acesso aberto

Identificador

oai:repositorio.fgv.br:10438/37929

Palavras-chave

Otimização convexaMétodos de primeira ordemAceleração de NesterovDivergência de BregmanMirror DescentConvex optimizationFirst order methodsNesterov’s accelerationBregman divergenceMatemáticaOtimização matemáticaAnálise matemáticaAnálise numérica