Modèle d’article scientifique LaTeX
Un modèle d’article scientifique LaTeX gratuit avec la classe article standard : titre, résumé, sections et références déjà en place, pour te concentrer sur le contenu.
Ouvrir l’éditeur Retour aux modèles
Code LaTeX
% Modèle d'article scientifique : titre, auteurs avec affiliations, résumé et mots-clés, sections numérotées,
% théorème, tableau, graphique et bibliographie. Il contient un court exemple (l'inertie sur des problèmes
% quadratiques) pour montrer le rôle de chaque partie. Remplacez le texte, le tableau et le graphique par les vôtres.
\documentclass[a4paper,11pt]{article}
% Bibliographie : natbib, à charger avant babel ; les références sont dans references.bib ; citez-les avec \cite{clé} ou \citet{clé}
\usepackage[numbers,sort&compress]{natbib}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[french]{babel}
\usepackage[margin=2.5cm]{geometry}
\usepackage{microtype}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{booktabs}
\usepackage{graphicx} % nécessaire seulement pour insérer des images avec \includegraphics
\usepackage{authblk}
\usepackage{pgfplots}
\usetikzlibrary{babel}
\usepackage[hidelinks]{hyperref}
\pgfplotsset{compat=1.18}
\newtheorem{theorem}{Théorème}
\theoremstyle{remark}
\newtheorem*{remark}{Remarque}
% ---- Titre et auteurs : à modifier ----
\title{L'inertie accélère la descente de gradient sur les problèmes quadratiques mal conditionnés}
\author[1]{Camille Dubois\thanks{Auteure correspondante : \texttt{camille.dubois@example.com}}}
\author[2]{Thomas Lefèvre}
\affil[1]{Département de mathématiques, Université d'Exemple, Lyon, France}
\affil[2]{Institut d'informatique, École d'ingénieurs de démonstration, Paris, France}
\date{\today}
\begin{document}
\maketitle
\begin{abstract}
% Résumez le problème, la méthode, le résultat principal et son intérêt, en 150 mots environ.
La descente de gradient ralentit lorsque le problème est mal conditionné. Nous comparons la descente de
gradient simple à la méthode de la boule lourde sur des objectifs quadratiques et montrons que l'inertie
réduit le nombre d'itérations nécessaires de l'ordre de $\kappa$ à l'ordre de $\sqrt{\kappa}$, où $\kappa$ est
le nombre de conditionnement. Nous démontrons les taux asymptotiques, les vérifions numériquement pour des
nombres de conditionnement allant jusqu'à $10^3$ et discutons des cas où ce gain se retrouve sur d'autres
problèmes.
\end{abstract}
\noindent\textbf{Mots-clés :} optimisation, descente de gradient, inertie, nombre de conditionnement
\section{Introduction}
% Présentez le problème, l'état des connaissances, ce qui manque et votre contribution.
De nombreux problèmes scientifiques et techniques se ramènent à la minimisation d'une fonction régulière, et la
descente de gradient est la méthode la plus simple pour cela \citep{boyd2004}. Sa vitesse dépend fortement de la
forme de l'objectif : lorsque les ensembles de niveau sont longs et étroits, les itérés zigzaguent et la
progression est lente. Ajouter un terme d'inertie \citep{polyak1964} amortit ce zigzag, et l'effet se voit
facilement sur les fonctions quadratiques \citep{goh2017}.
Les contributions de cet article sont :
\begin{itemize}
\item une démonstration autonome des taux asymptotiques des deux méthodes sur les fonctions quadratiques, et
\item une vérification numérique du nombre d'itérations prévu pour trois nombres de conditionnement.
\end{itemize}
La section~\ref{sec:method} présente le cadre, la section~\ref{sec:results} montre les résultats et
la section~\ref{sec:conclusions} conclut.
\section{Méthodes}\label{sec:method}
% Décrivez le modèle, les algorithmes et les hypothèses nécessaires pour reproduire votre travail.
Nous minimisons la fonction quadratique $f(x) = \tfrac12 x^{\top}Ax$, où $A$ est symétrique définie positive
de plus petite et plus grande valeurs propres $\mu$ et $L$. Le nombre de conditionnement est $\kappa = L/\mu$ et
le minimiseur est $x^{\star}=0$. À partir de $x_0$, la descente de gradient de pas $\alpha$ et la méthode de la
boule lourde d'inertie $\beta$ s'écrivent
\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}
Avec $\alpha = 2/(L+\mu)$, la méthode \eqref{eq:gd} vérifie $\|x_k\| \le \rho_{\mathrm{GD}}^{\,k}\|x_0\|$ avec
$\rho_{\mathrm{GD}} = \dfrac{\kappa-1}{\kappa+1}$. Avec $\alpha = 4/(\sqrt{L}+\sqrt{\mu})^2$ et
$\beta = \bigl(\tfrac{\sqrt\kappa-1}{\sqrt\kappa+1}\bigr)^2$, la méthode \eqref{eq:hb} converge au
taux asymptotique $\rho_{\mathrm{HB}} = \dfrac{\sqrt\kappa-1}{\sqrt\kappa+1}$.
\end{theorem}
\begin{proof}
On diagonalise $A$ et on traite séparément chaque valeur propre $\lambda\in[\mu,L]$. Pour la descente de
gradient, l'itéré dans cette direction est multiplié par $1-\alpha\lambda$, dont le module est maximal en
$\lambda=\mu$ et $\lambda=L$ et vaut $\rho_{\mathrm{GD}}$ pour le pas indiqué. Pour la méthode de la boule
lourde, le couple $(x_k, x_{k-1})$ évolue selon une matrice $2\times2$ dont les valeurs propres sont les racines de
$z^2-(1+\beta-\alpha\lambda)z+\beta=0$. Pour les $\alpha$ et $\beta$ indiqués, ces racines sont complexes
de module $\sqrt\beta=\rho_{\mathrm{HB}}$ pour tout $\lambda\in[\mu,L]$ \citep{polyak1964}.
\end{proof}
\begin{remark}
Comme $-\ln\rho \approx 2/\kappa$ pour la descente de gradient et $\approx 2/\sqrt\kappa$ pour la boule lourde,
atteindre une tolérance $\varepsilon$ demande environ $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ et
$\tfrac{\sqrt\kappa}{2}\ln(1/\varepsilon)$ itérations, respectivement \citep{nesterov2004}.
\end{remark}
\section{Résultats}\label{sec:results}
% Présentez les résultats sans les interpréter ; mentionnez chaque tableau et chaque figure dans le texte.
Le tableau~\ref{tab:iterations} donne le nombre d'itérations nécessaires pour réduire l'erreur d'un facteur $10^{6}$,
calculé à partir des taux du théorème~\ref{thm:rates}, et la figure~\ref{fig:convergence} montre la borne
d'erreur pour $\kappa=100$.
\begin{table}[htbp]
\centering
\caption{Nombre d'itérations nécessaires pour réduire l'erreur d'un facteur $10^{6}$.}
\label{tab:iterations}
\begin{tabular}{rrrr}
\toprule
$\kappa$ & Descente de gradient & Boule lourde & Rapport \\
\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
% Le graphique est tracé avec pgfplots, aucun fichier image n'est donc nécessaire. Pour utiliser une image :
% \includegraphics[width=0.8\linewidth]{figure.png}
\begin{tikzpicture}
\begin{axis}[
width=0.8\linewidth, height=6cm,
xlabel={Itération $k$}, ylabel={Borne d'erreur $\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{Descente de gradient, Boule lourde}
\end{axis}
\end{tikzpicture}
\caption{Borne de l'erreur après $k$ itérations pour $\kappa=100$.}
\label{fig:convergence}
\end{figure}
\section{Discussion}
Le nombre d'itérations croît linéairement avec $\kappa$ pour la descente de gradient et avec $\sqrt\kappa$ pour la
boule lourde, si bien que l'avantage de l'inertie augmente à mesure que le problème devient plus difficile : un
facteur 3 pour $\kappa=10$ et plus de 30 pour $\kappa=10^{3}$. L'analyse ne vaut que pour les fonctions
quadratiques ; pour des fonctions convexes générales, la méthode de la boule lourde demande d'autres paramètres et
peut ne pas converger, c'est pourquoi on préfère en pratique les variantes accélérées \citep{nesterov2004}.
\section{Conclusions}\label{sec:conclusions}
% Rappelez le résultat principal, ses limites et les suites à donner.
Sur les problèmes quadratiques, l'inertie transforme un nombre d'itérations de l'ordre de $\kappa$ en un nombre de
l'ordre de $\sqrt\kappa$. Des travaux futurs devraient vérifier quelle part de ce gain subsiste pour des objectifs
non quadratiques et en présence de bruit.
\section*{Remerciements}
Ce travail a été soutenu par la Fondation Exemple, subvention 000000.
\bibliographystyle{unsrtnat}
\bibliography{references}
\end{document}