Κατάλογος Εκδηλώσεων

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

Ιωάννη Χαριομπόλη

με θέμα
Αλγόριθμοι Κατανεμημένης Βελτιστοποίησης: Μελέτη Απόδοσης και Εφαρμογή σε Προβλήματα Μηχανικής Μάθησης
Distributed Optimization Algorithms: Performance Analysis and Application in Machine Learning Problems

Εξεταστική Επιτροπή
Καθηγητής Αθανάσιος Λιάβας (επιβλέπων)
Καθηγητής Γεώργιος Καρυστινός
Καθηγητής Θρασύβουλος Σπυρόπουλος

Περίληψη
Οι αλγόριθμοι κατανεμημένης βελτιστοποίησης επιτρέπουν σε ένα σετ από πράκτορες να λύσουν συλλογικά ένα καθολικό πρόβλημα ελαχιστοποίησης, ορισμένο ως τον αριθμητικό μέσο της τοπικής συνάρτησης κάθε πράκτορα. Σε αυτή τη διπλωματική εργασία εξετάζουμε κατανεμημένους αλγόριθμους βελτιστοποίησης στο πλαίσιο όπου οι πράκτορες επικοινωνούν μέσω ενός δικτύου, όπου κάθε πράκτορας μπορεί να επικοινωνήσει μόνο με τους άμεσους γείτονες του, και δεν μπορεί να μοιραστεί την αντικειμενική συνάρτηση (και κατ’ επέκταση τα δεδομένα εκπαίδευσης) άμεσα. Πιο συγκεκριμένα, ερευνούμε πως αυτοί οι αλγόριθμοι μπορούν να εφαρμοστούν στο κλασσικό πλαίσιο Μηχανικής Μάθησης της εκπαίδευσης ενός παραμετρικού μοντέλου ώστε να προβλέπει ετικέτες y από δεδομένα εισόδου x. Συνήθως, οι κατανεμημένοι αλγόριθμοι βελτιστοποίησης σε δίκτυα αποτελούνται από δύο βήματα: τη συγκέντρωση και υπολογισμό της μέσης τιμής των παραμέτρων των γειτόνων κάθε πράκτορα, και ένα βήμα καθόδου βαθμίδας προς το ελάχιστο της τοπικής συνάρτησης κάθε πράκτορα.  Επιπλέον, θεωρούμε αλγορίθμους που χτίζουν πάνω σε αυτό το σχέδιο με την ενσωμάτωση όρων διόρθωσης, επιτάχυνσης μέσω ορμής, διπλής ανάβασης, και πολλαπλών γύρων επικοινωνίας για κάθε υπολογισμό βαθμίδας. Αξιολογούμε πειραματικά την απόδοση ορισμένων κατανεμημένων αλγορίθμων για συναρτήσεις διαφορετικών κλάσεων, συγκεκριμένα ομαλές, και ισχυρά κυρτές συναρτήσεις, καθώς και προβλήματα με περιορισμούς.

Abstract 
Distributed optimization allows a set of agents to collectively solve a global minimization problem, defined as the numerical average of each agent’s local objective function. In this thesis we examine distributed optimization algorithms in the setting where the agents communicate via a network, where each agent can only communicate with its immediate neighbors, and can not share its objective function (and by extension its training data) directly. More specifically, we investigate how these algorithms can be applied to the classical Machine Learning framework of training a parametrized model to predict labels y from input data x. Typically, distributed optimization algorithms over networks have two main steps: the pooling and then averaging of the parameters of each agent’s neighbors via the consensus protocol, and a gradient descent step towards the minimum of the local function of each agent. We also consider algorithms that build on this scheme by incorporating correction terms, acceleration via momentum, dual ascent, and multiple communication rounds per gradient computation. We experimentally evaluate the performance of a number of distributed algorithms for functions of different classes, namely smooth, and strongly convex functions, as well as objectives with constraints.