Online convex optimization: algorithms, learning, and duality (2019)
- Authors:
- Autor USP: PORTELLA, VICTOR SANCHES - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: ALGORITMOS; OTIMIZAÇÃO CONVEXA
- Keywords: Algorithms; Convex; Convex Optimization; Convexa; Dualidade; Duality; Learning; Online; Online convex optimization; Otimização; Otimização convexa online
- Agências de fomento:
- Language: Inglês
- Abstract: Otimização Convexa Online (OCO) é uma área na intersecção de teoria dos jogos, otimização e aprendizado de máquina que tem recebido maior atenção recentemente devido a suas recentes aplicações em uma grande gama de áreas como complexidade computacional e esparsificação de grafos. Além dos algoritmos de OCO usualmente terem descrições diretas e poderem ser implementados de forma relativamente simples, muito do recente sucesso da área foi possível graças a um melhor entendimento do cenário e dos algoritmos de OCO que se deu com uso de conhecidas ideias de análise e otimização convexa como a poderosa teoria de dualidade convexa. Nesse texto nós apresentamos uma introdução (em sua maioria auto-contida) à área de otimização convexa online. Primeiro, descrevemos os cenários de aprendizado online e de otimização convexa online, propondo uma forma alternativa de formalizar ambos os modelos de forma que conseguimos enunciar afirmações claras e formais de forma que não atrapalha o entendimento do leitor. Nós então apresentamos um resumo dos principais conceitos e resultados de análise convexa que usamos no texto com um foco em criar intuição sobre os mesmos. Com relação a algoritmos para OCO, nós começamos apresentando o algoritmo Adaptive Follow the Regularized Leader (AdaFTRL) e analisamos sua eficácia com um resultado sobre a dualidade de funções strongly convex e strongly smooth. Na sequência, descrevemos os algoritmos Adaptive Online Mirror Descent (AdaOMD) e Adaptive DualAveraging (AdaDA), analisando a eficácia de cada um escrevendo eles como instâncias do algoritmo AdaFTRL. Além disso, nós mostramos condições simples para que as versões Eager e Lazy do Online Mirror Descent (que são as versões não adaptativas do AdaOMD e do AdaDA, respectivamente) sejam equivalentes. Também apresentamos os algoritmos AdaGrad e Online Newton Step, bem conhecidos na literatura sobre OCO, como casos especiais do algoritmo AdaReg, esse último um algoritmo proposto por Gupta, Koren, and Singer, que, por sua vez, é um caso especial do algoritmo AdaOMD. Nós concluímos o texto com uma visão global das conexões entre os algoritmos que mostramos durante o texto, formando uma \"genealogia\" de algoritmos para OCO, além de discutirmos possíveis direções futuras de pesquisa
- Imprenta:
- Data da defesa: 03.05.2019
-
ABNT
PORTELLA, Victor Sanches. Online convex optimization: algorithms, learning, and duality. 2019. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2019. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05062019-165924/. Acesso em: 23 abr. 2024. -
APA
Portella, V. S. (2019). Online convex optimization: algorithms, learning, and duality (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05062019-165924/ -
NLM
Portella VS. Online convex optimization: algorithms, learning, and duality [Internet]. 2019 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05062019-165924/ -
Vancouver
Portella VS. Online convex optimization: algorithms, learning, and duality [Internet]. 2019 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-05062019-165924/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
