2026-10-09T01:26:21Zhttps://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh

oai:lib.uoa.gr:uoadl:5410203 2026-06-18T05:34:00.663Z born_digital_postgraduate_thesis

uoadl:5410203 https://pergamos.lib.uoa.gr/uoa/dl/object/5410203 born_digital_postgraduate_thesis Διπλωματική Εργασία Postgraduate Thesis RESTARTING POLICIES FOR ACCELERATED GRADIENT METHODS 2026 English ΚΟΥΤΣΗΣ ΠΕΤΡΟΣ ΑΝΤΩΝΙΟΣ KOUTSIS PETROS ANTONIOS Η παρούσα διπλωματική εργασία έχει ως σκοπό να παράσχει μία αυτοτελή περιγραφή της μεθόδου βελτιστοποίησης με επιτάχυνση και της heavy-ball μεθόδου με επανεκκίνηση. Στο πρώτο μέρος της εισάγονται οι μέθοδοι πρώτης τάξης για βελτιστοποίηση λείων κυρτών συναρτήσεων, η ιδιότητα καθόδου και οι ιδιότητες τύπου Fejer της καθόδου κλίσεως, και το χάσμα πολυπλοκότητας-μαντείου που οδηγεί στην επιτάχυνση. Στο δεύτερο μέρος παρουσιάζεται η οπτική γωνία των δυναμικών συστημάτων: η κάθοδος κλίσεως εμφανίζεται ως μία διακριτοποίηση κατά Euler της ροής καθόδου, ενώ οι αλγόριθμοι heavy-ball και τύπου Nesterov αντιστοιχούν σε ένα αποσβεστικό σύστημα δεύτερης τάξης. Στο τρίτο μέρος μελετώνται πολιτικές επανεκκίνησης σε μεθόδους επιτάχυνσης. Οι σταθερές επανεκκινήσεις επιτυγχάνουν έναν γραμμικό ρυθμό σύγκλισης στην περίπτωση της ισχυρής κυρτότητας όταν η περίοδος επανεκκίνησης επιλεγεί κατάλληλα για τον αριθμό συνθήκης της συνάρτησης, ενώ οι προσαρμοστικοί κανόνες επανεκκίνησης προσπαθούν να ανιχνεύσουν την έναρξη των ταλαντώσεων χωρίς προηγούμενη γνώση της παραμέτρου της ισχυρής κυρτότητας. Την ραχοκοκαλιά της παρούσας διπλωματικής αποτελούν: η ερμηνεία ως διαφορική εξίσωση της επιτάχυνσης Nesterov των by Su et al. [10], η θεωρία της ασυμπτωτικής μηδενικής απόσβεσης των Attouch et al. [11], και οι εξαρτώμενοι από τη γεωμετρία βελτιωμένοι ρυθμοί για αδρανειακούς αλγορίθμους βαθμίδας των Apidopoulos et al. [12]. This report aims to provide a self-contained account of accelerated and heavy-ball optimization methods with restart. The first part introduces first-order methods for smooth convex minimization, the descent and Fejer-type properties of gradient descent, and the oracle-complexity gap that motivates acceleration. The second part explains the dynamical-systems viewpoint: gradient descent appears as an Euler discretization of the gradient flow, while heavy-ball and Nesterov-type algorithms correspond to second-order dissipative systems. The third part studies restarting policies for accelerated methods. Fixed restarts recover a linear rate in the strongly convex case when the restart period is tuned to the condition number, whereas adaptive restart rules try to detect the onset of oscillations without prior knowledge of the strong convexity parameter. The report incorporates the following elements in its backbone: the differential-equation interpretation of Nesterov acceleration by Su et al. [10]; the asymptotic vanishing-damping theory of Attouch et al. [11]; and the refined geometry-dependent rates for inertial gradient descent by Apidopoulos et al. [12]. Θετικές Επιστήμες Science