Modelo de artigo científico em LaTeX
Um modelo de artigo científico em LaTeX gratuito com a classe article padrão: título, resumo, seções e referências já organizados, para você se concentrar no conteúdo.
Abrir o editor Voltar aos modelos
Código LaTeX
% Modelo de artigo científico: título, autores com afiliações, resumo e palavras-chave, seções numeradas,
% teorema, tabela, gráfico e referências. Contém um exemplo curto (momento em problemas quadráticos)
% para mostrar como funciona cada parte. Substitua o texto, a tabela e o gráfico pelos seus.
\documentclass[a4paper,11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[brazilian]{babel}
\usepackage[margin=2.5cm]{geometry}
\usepackage{microtype}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage{graphicx} % necessário apenas se você incluir arquivos de imagem com \includegraphics
\usepackage{authblk}
\usepackage{pgfplots}
\usetikzlibrary{babel}
\usepackage[hidelinks]{hyperref}
% Referências: as entradas ficam em references.bib; cite-as com \cite{chave} ou \citet{chave}
\usepackage[numbers,sort&compress]{natbib}
\pgfplotsset{compat=1.18}
\newtheorem{theorem}{Teorema}
\theoremstyle{remark}
\newtheorem*{remark}{Observação}
\renewcommand{\Authand}{ e }
% ---- Título e autores: edite-os ----
\title{O momento acelera a descida do gradiente em problemas quadráticos mal condicionados}
\author[1]{Mariana Souza\thanks{Autora para correspondência: \texttt{mariana.souza@example.com}}}
\author[2]{Rafael Oliveira}
\affil[1]{Departamento de Matemática, Universidade Exemplo, São Paulo, Brasil}
\affil[2]{Instituto de Computação, Instituto de Tecnologia Modelo, Campinas, Brasil}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
% Resuma o problema, o método, o resultado principal e sua importância, em cerca de 150 palavras.
A descida do gradiente fica lenta quando o problema é mal condicionado. Comparamos a descida do gradiente
simples com o método da bola pesada em funções objetivo quadráticas e mostramos que o momento reduz o número
de iterações necessárias da ordem de $\kappa$ para a ordem de $\sqrt{\kappa}$, em que $\kappa$ é o número de
condição. Demonstramos as taxas assintóticas, verificamos numericamente para números de condição de até
$10^3$ e discutimos quando o ganho de velocidade se estende a outros problemas.
\end{abstract}
\noindent\textbf{Palavras-chave:} otimização, descida do gradiente, momento, número de condição
\section{Introdução}
% Apresente o problema, o que já se sabe, a lacuna e a sua contribuição.
Muitos problemas da ciência e da engenharia se reduzem a minimizar uma função suave, e a descida do gradiente é
o método mais simples para isso \citep{boyd2004}. Sua velocidade depende bastante da forma da função objetivo:
quando os conjuntos de nível são longos e estreitos, as iteradas avançam em zigue-zague e o progresso é lento.
Adicionar um termo de momento \citep{polyak1964} amortece o zigue-zague, e o efeito é fácil de ver em funções
quadráticas \citep{goh2017}.
As contribuições deste artigo são:
\begin{itemize}
\item uma dedução autocontida das taxas assintóticas dos dois métodos em funções quadráticas, e
\item uma verificação numérica do número de iterações previsto para três números de condição.
\end{itemize}
A Seção~\ref{sec:method} apresenta o problema, a Seção~\ref{sec:results} mostra os resultados e
a Seção~\ref{sec:conclusions} conclui.
\section{Métodos}\label{sec:method}
% Descreva o modelo, os algoritmos e as hipóteses necessárias para repetir o seu trabalho.
Minimizamos a função quadrática $f(x) = \tfrac12 x^{\top}Ax$, em que $A$ é simétrica definida positiva
com menor e maior autovalores $\mu$ e $L$. O número de condição é $\kappa = L/\mu$ e o
minimizador é $x^{\star}=0$. A partir de $x_0$, a descida do gradiente com passo $\alpha$ e o método da bola
pesada com momento $\beta$ atualizam
\begin{align}
x_{k+1} &= x_k - \alpha\,\nabla f(x_k), \label{eq:gd}\\
x_{k+1} &= x_k - \alpha\,\nabla f(x_k) + \beta\,(x_k - x_{k-1}). \label{eq:hb}
\end{align}
\begin{theorem}\label{thm:rates}
Com $\alpha = 2/(L+\mu)$, o método \eqref{eq:gd} satisfaz $\|x_k\| \le \rho_{\mathrm{GD}}^{\,k}\|x_0\|$ com
$\rho_{\mathrm{GD}} = \dfrac{\kappa-1}{\kappa+1}$. Com $\alpha = 4/(\sqrt{L}+\sqrt{\mu})^2$ e
$\beta = \bigl(\tfrac{\sqrt\kappa-1}{\sqrt\kappa+1}\bigr)^2$, o método \eqref{eq:hb} converge com a
taxa assintótica $\rho_{\mathrm{HB}} = \dfrac{\sqrt\kappa-1}{\sqrt\kappa+1}$.
\end{theorem}
\begin{proof}
Diagonaliza-se $A$ e trata-se cada autovalor $\lambda\in[\mu,L]$ separadamente. Na descida do gradiente,
a iterada nessa direção é multiplicada por $1-\alpha\lambda$, cujo módulo é máximo em
$\lambda=\mu$ e $\lambda=L$ e vale $\rho_{\mathrm{GD}}$ para o passo indicado. No método da bola
pesada, o par $(x_k, x_{k-1})$ evolui com uma matriz $2\times2$ cujos autovalores são as raízes de
$z^2-(1+\beta-\alpha\lambda)z+\beta=0$. Para os $\alpha$ e $\beta$ indicados, essas raízes são complexas
com módulo $\sqrt\beta=\rho_{\mathrm{HB}}$ para todo $\lambda\in[\mu,L]$ \citep{polyak1964}.
\end{proof}
\begin{remark}
Como $-\ln\rho \approx 2/\kappa$ na descida do gradiente e $\approx 2/\sqrt\kappa$ na bola pesada, atingir
uma tolerância $\varepsilon$ exige cerca de $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ e
$\tfrac{\sqrt\kappa}{2}\ln(1/\varepsilon)$ iterações, respectivamente \citep{nesterov2004}.
\end{remark}
\section{Resultados}\label{sec:results}
% Apresente os resultados sem interpretá-los; faça referência no texto a cada tabela e a cada figura.
A Tabela~\ref{tab:iterations} lista as iterações necessárias para reduzir o erro por um fator de $10^{6}$,
calculadas a partir das taxas do Teorema~\ref{thm:rates}, e a Figura~\ref{fig:convergence} mostra o limite
do erro para $\kappa=100$.
\begin{table}[htbp]
\centering
\caption{Iterações necessárias para reduzir o erro por um fator de $10^{6}$.}
\label{tab:iterations}
\begin{tabular}{rrrr}
\toprule
$\kappa$ & Descida do gradiente & Bola pesada & Razão \\
\midrule
10 & 69 & 22 & 3,1 \\
100 & 691 & 69 & 10,0 \\
1000 & 6908 & 219 & 31,5 \\
\bottomrule
\end{tabular}
\end{table}
\begin{figure}[htbp]
\centering
% O gráfico é desenhado com pgfplots, portanto não é preciso nenhum arquivo de imagem. Para usar uma imagem:
% \includegraphics[width=0.8\linewidth]{figure.png}
\begin{tikzpicture}
\begin{axis}[
width=0.8\linewidth, height=6cm,
xlabel={Iteração $k$}, ylabel={Limite do erro $\rho^{k}$},
ymode=log, xmin=0, xmax=300, ymin=1e-7, ymax=1,
grid=major, legend pos=south west,
]
\addplot[thick, domain=0:300, samples=2] {0.9802^x};
\addplot[thick, dashed, domain=0:300, samples=2] {0.8182^x};
\legend{Descida do gradiente, Bola pesada}
\end{axis}
\end{tikzpicture}
\caption{Limite do erro após $k$ iterações para $\kappa=100$.}
\label{fig:convergence}
\end{figure}
\section{Discussão}
O número de iterações cresce linearmente com $\kappa$ na descida do gradiente e com $\sqrt\kappa$ na bola
pesada, de modo que a vantagem do momento aumenta à medida que o problema fica mais difícil: um fator de 3 para
$\kappa=10$ e mais de 30 para $\kappa=10^{3}$. A análise vale apenas para funções quadráticas; para funções
convexas gerais, o método da bola pesada precisa de outros parâmetros e pode não convergir, e é por isso que
na prática se preferem as variantes aceleradas \citep{nesterov2004}.
\section{Conclusões}\label{sec:conclusions}
% Retome o resultado principal, seus limites e o que fazer a seguir.
Em problemas quadráticos, o momento transforma um número de iterações da ordem de $\kappa$ em um da ordem de
$\sqrt\kappa$. Trabalhos futuros devem verificar quanto desse ganho se mantém em funções objetivo não
quadráticas e na presença de ruído.
\section*{Agradecimentos}
Este trabalho foi financiado pela Fundação Exemplo, auxílio 000000.
\bibliographystyle{unsrtnat}
\bibliography{references}
\end{document}