ATTENTION/WARNING - NE PAS DÉPOSER ICI/DO NOT SUBMIT HERE

Ceci est la version de TEST de DIAL.mem. Veuillez ne pas soumettre votre mémoire sur ce site mais bien à l'URL suivante: 'https://thesis.dial.uclouvain.be'.
This is the TEST version of DIAL.mem. Please use the following URL to submit your master thesis: 'https://thesis.dial.uclouvain.be'.
 

Tight convergence analysis of exact and inexact gradient methods with constant and silver schedules

Vernimmen, Pierre
(2024)

Files

Vernimmen_07491900_2024.pdf
  • Open access
  • Adobe PDF
  • 1.09 MB
Download

Details

Supervisors
Glineur, François
Faculty
Ecole polytechnique de Louvain
Degree label
Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée
Abstract
This work explores optimization and first-order algorithms, beginning with an introduction to these concepts in Section 1, followed by an explanation of the recently developed Performance Estimation framework. This framework treats the worst-case convergence analysis of an algorithm on a given class of functions as an optimization problem itself. Next, we discuss the concept of relative inexact gradient, where first-order optimization algorithms are applied using inexact gradient information. Taking account of imprecision makes perfect sense in today's world. In many of today's applications, we want to optimise processes and all we have is inexact information, for example in machine learning. In Section 2, we theoretically analyze constant step size first-order optimization algorithms, considering both exact and inexact gradients. We derive theoretical bounds on the rate of convergence. We investigate the effects of inexactness on these methods, compare our findings with numerical results, and propose conjectures on the best step sizes to use based on the number of iterations and the level of inexactness. Section 3 introduces and experimentally analyzes a new step size schedule, the silver step size schedule, designed to accelerate the gradient method without requiring memory storage. Using the Performance Estimation methodology, we obtain tight bounds not presented in the original paper. We also analyze this method when dealing with inexact gradient and develop new algorithms to tackle the challenges posed by inexactness. Finally, Section 4 compares the different methods from both theoretical and practical perspectives, including a linear regression experiment. This last section also includes a discussion of the optimal method to choose, depending on the properties of the problem being addressed.

Citations

  • APA

Vernimmen, P. (2024). Tight convergence analysis of exact and inexact gradient methods with constant and silver schedules. https://dial-mem.test.bib.ucl.ac.be/handle/2078.2/38434