Modello LaTeX per articolo scientifico
Un modello LaTeX gratuito per articolo scientifico con la classe article standard: titolo, abstract, sezioni e bibliografia già pronti, così puoi concentrarti sul contenuto.
Apri l'editor Torna ai modelli
Codice LaTeX
% Modello di articolo scientifico: titolo, autori con affiliazioni, sommario e parole chiave, sezioni numerate,
% teorema, tabella, grafico e bibliografia. Contiene un breve esempio (il momento nei problemi quadratici)
% per mostrare come funziona ogni parte. Sostituisci il testo, la tabella e il grafico con i tuoi.
\documentclass[a4paper,11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[italian]{babel}
\usepackage[margin=2.5cm]{geometry}
\usepackage{microtype}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage{graphicx} % serve solo se inserisci file immagine con \includegraphics
\usepackage{authblk}
\usepackage{pgfplots}
\usetikzlibrary{babel}
\usepackage[hidelinks]{hyperref}
% Bibliografia: le voci sono in references.bib; citale con \cite{chiave} o \citet{chiave}
\usepackage[numbers,sort&compress]{natbib}
\pgfplotsset{compat=1.18}
\newtheorem{theorem}{Teorema}
\theoremstyle{remark}
\newtheorem*{remark}{Osservazione}
% ---- Titolo e autori: modificali ----
\title{Il momento accelera la discesa del gradiente su problemi quadratici mal condizionati}
\author[1]{Giulia Romano\thanks{Autrice di riferimento: \texttt{giulia.romano@example.com}}}
\author[2]{Marco Bianchi}
\affil[1]{Dipartimento di Matematica, Università di Esempio, Bologna, Italia}
\affil[2]{Istituto di Informatica, Politecnico di Prova, Milano, Italia}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
% Riassumi il problema, il metodo, il risultato principale e la sua importanza, in circa 150 parole.
La discesa del gradiente rallenta quando il problema è mal condizionato. Confrontiamo la discesa del
gradiente semplice con il metodo della palla pesante su funzioni obiettivo quadratiche e mostriamo che il
momento riduce il numero di iterazioni necessarie dall'ordine di $\kappa$ all'ordine di $\sqrt{\kappa}$, dove
$\kappa$ è il numero di condizionamento. Dimostriamo i tassi asintotici, li verifichiamo numericamente per
numeri di condizionamento fino a $10^3$ e discutiamo quando il guadagno di velocità si estende ad altri problemi.
\end{abstract}
\noindent\textbf{Parole chiave:} ottimizzazione, discesa del gradiente, momento, numero di condizionamento
\section{Introduzione}
% Presenta il problema, ciò che è noto, la lacuna e il tuo contributo.
Molti problemi della scienza e dell'ingegneria si riducono a minimizzare una funzione regolare, e la discesa del
gradiente è il metodo più semplice per farlo \citep{boyd2004}. La sua velocità dipende molto dalla forma della
funzione obiettivo: quando gli insiemi di livello sono lunghi e stretti, le iterate procedono a zigzag e il
progresso è lento. Aggiungere un termine di momento \citep{polyak1964} smorza lo zigzag, e l'effetto si vede
facilmente sulle funzioni quadratiche \citep{goh2017}.
I contributi di questo articolo sono:
\begin{itemize}
\item una derivazione autonoma dei tassi asintotici di entrambi i metodi sulle funzioni quadratiche, e
\item una verifica numerica del numero di iterazioni previsto per tre numeri di condizionamento.
\end{itemize}
La sezione~\ref{sec:method} introduce il contesto, la sezione~\ref{sec:results} mostra i risultati e
la sezione~\ref{sec:conclusions} conclude.
\section{Metodi}\label{sec:method}
% Descrivi il modello, gli algoritmi e le ipotesi necessarie per ripetere il tuo lavoro.
Minimizziamo la funzione quadratica $f(x) = \tfrac12 x^{\top}Ax$, dove $A$ è simmetrica definita positiva
con autovalore minimo $\mu$ e massimo $L$. Il numero di condizionamento è $\kappa = L/\mu$ e il
minimizzatore è $x^{\star}=0$. A partire da $x_0$, la discesa del gradiente con passo $\alpha$ e il metodo della
palla pesante con momento $\beta$ aggiornano
\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}
Con $\alpha = 2/(L+\mu)$, il metodo \eqref{eq:gd} soddisfa $\|x_k\| \le \rho_{\mathrm{GD}}^{\,k}\|x_0\|$ con
$\rho_{\mathrm{GD}} = \dfrac{\kappa-1}{\kappa+1}$. Con $\alpha = 4/(\sqrt{L}+\sqrt{\mu})^2$ e
$\beta = \bigl(\tfrac{\sqrt\kappa-1}{\sqrt\kappa+1}\bigr)^2$, il metodo \eqref{eq:hb} converge con il
tasso asintotico $\rho_{\mathrm{HB}} = \dfrac{\sqrt\kappa-1}{\sqrt\kappa+1}$.
\end{theorem}
\begin{proof}
Si diagonalizza $A$ e si tratta separatamente ogni autovalore $\lambda\in[\mu,L]$. Per la discesa del
gradiente, l'iterata lungo quella direzione viene moltiplicata per $1-\alpha\lambda$, il cui modulo è massimo
in $\lambda=\mu$ e $\lambda=L$ e vale $\rho_{\mathrm{GD}}$ per il passo indicato. Per il metodo della palla
pesante, la coppia $(x_k, x_{k-1})$ evolve con una matrice $2\times2$ i cui autovalori sono le radici di
$z^2-(1+\beta-\alpha\lambda)z+\beta=0$. Per gli $\alpha$ e $\beta$ indicati, queste radici sono complesse
con modulo $\sqrt\beta=\rho_{\mathrm{HB}}$ per ogni $\lambda\in[\mu,L]$ \citep{polyak1964}.
\end{proof}
\begin{remark}
Poiché $-\ln\rho \approx 2/\kappa$ per la discesa del gradiente e $\approx 2/\sqrt\kappa$ per la palla pesante,
raggiungere una tolleranza $\varepsilon$ richiede circa $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ e
$\tfrac{\sqrt\kappa}{2}\ln(1/\varepsilon)$ iterazioni, rispettivamente \citep{nesterov2004}.
\end{remark}
\section{Risultati}\label{sec:results}
% Presenta i risultati senza interpretarli; richiama nel testo ogni tabella e ogni figura.
La tabella~\ref{tab:iterations} riporta le iterazioni necessarie per ridurre l'errore di un fattore $10^{6}$,
calcolate dai tassi del teorema~\ref{thm:rates}, e la figura~\ref{fig:convergence} mostra il limite
superiore dell'errore per $\kappa=100$.
\begin{table}[htbp]
\centering
\caption{Iterazioni necessarie per ridurre l'errore di un fattore $10^{6}$.}
\label{tab:iterations}
\begin{tabular}{rrrr}
\toprule
$\kappa$ & Discesa del gradiente & Palla pesante & Rapporto \\
\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
% Il grafico è disegnato con pgfplots, quindi non serve alcun file immagine. Per usare invece un'immagine:
% \includegraphics[width=0.8\linewidth]{figure.png}
\begin{tikzpicture}
\begin{axis}[
width=0.8\linewidth, height=6cm,
xlabel={Iterazione $k$}, ylabel={Limite dell'errore $\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{Discesa del gradiente, Palla pesante}
\end{axis}
\end{tikzpicture}
\caption{Limite superiore dell'errore dopo $k$ iterazioni per $\kappa=100$.}
\label{fig:convergence}
\end{figure}
\section{Discussione}
Il numero di iterazioni cresce linearmente con $\kappa$ per la discesa del gradiente e con $\sqrt\kappa$ per la
palla pesante, quindi il vantaggio del momento aumenta man mano che il problema si fa più difficile: un fattore
3 per $\kappa=10$ e più di 30 per $\kappa=10^{3}$. L'analisi vale solo per le funzioni quadratiche; per le
funzioni convesse generali il metodo della palla pesante richiede altri parametri e può non convergere, ed è per
questo che nella pratica si preferiscono le varianti accelerate \citep{nesterov2004}.
\section{Conclusioni}\label{sec:conclusions}
% Riprendi il risultato principale, i suoi limiti e i passi successivi.
Sui problemi quadratici, il momento trasforma un numero di iterazioni dell'ordine di $\kappa$ in uno dell'ordine
di $\sqrt\kappa$. Lavori futuri dovrebbero verificare quanta parte di questo guadagno resta su obiettivi non
quadratici e in presenza di rumore.
\section*{Ringraziamenti}
Questo lavoro è stato finanziato dalla Fondazione Esempio, progetto 000000.
\bibliographystyle{unsrtnat}
\bibliography{references}
\end{document}