ΕΚΔΗΛΩΣΕΙΣ

ΣΕΜΙΝΑΡΙΟ ΣΤΑΤΙΣΤΙΚΗΣ & ΕΠΙΧΕΙΡΗΣΙΑΚΗΣ ΕΡΕΥΝΑΣ: ΠΡΟΣΑΡΜΟΣΤΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ ΜΑΘΗΣΗΣ ΚΑΙ ΔΡΟΜΟΛΟΓΗΣΗΣ ΥΠΟ ΣΥΝΘΗΚΕΣ ΑΒΕΒΑΙΟΤΗΤΑΣ

Wednesday 01 Μαρτίου 2023 A31
Σεμινάριο Στατιστικής & Επιχειρησιακής Έρευνας: Προσαρμοστικοί αλγόριθμοι μάθησης και δρομολόγησης υπό συνθήκες αβεβαιότητας

Σεμινάριο Στατιστικής & Επιχειρησιακής Έρευνας

Ημερομηνία: Τετάρτη, 1 Μαρτίου 2023
Ώρα: 15:00
Τόπος: Αίθουσα Α31
Oμιλητής: Π. Μερτικόπουλος (ΕΚΠΑ)
Τίτλος: Προσαρμοστικοί αλγόριθμοι μάθησης και δρομολόγησης υπό συνθήκες αβεβαιότητας
Περίληψη: Οι εφαρμογές έξυπνης – ή, μερικές φορές, όχι και τόσο έξυπνης – δρομολόγησης (Google Maps, Waze, κλπ) έχουν φέρει σημαντικές αλλαγές στον τρόπο ζωής μας, και αριθμούν πλέον εκατοντάδες εκατομμύρια χρήστες ανά την υφήλιο. Ωστόσο, πολλές φορές, οι αλγόριθμοι που χρησιμοποιούνται για να προτείνουν μία διαδρομή σε ένα χρήστη δεν έχουν την απαραίτητη προσαρμοστικότητα ώστε να ανταποκριθούν στις συνθήκες αβεβαιότητας (ή/και τυχαιότητας) υπό τις οποίες καλούνται να λειτουργήσουν.

Στην ομιλία αυτή θα εξετάσουμε το αλγοριθμικό πλαίσιο λειτουργίας αυτών των συστημάτων σε δίκτυα μεγάλης κλίμακας. Στο πρώτο μέρος της ομιλίας, θα μελετήσουμε τις ιδιότητες ισορροπίας των αλγορίθμων αυτών και, πιο συγκεκριμένα, το λεγόμενο "τίμημα της αναρχίας" (price of anarchy) που επάγεται σε συνθήκες υψηλής ή χαμηλής συμφόρησης. Κατόπιν, στο δεύτερο μέρος, θα εξετάσουμε τις ιδιότητες σύγκλισης ενός προσαρμοστικού αλγορίθμου μάθησης ο οποίος απολαμβάνει το βέλτιστο ρυθμό σύγκλισης, ανεξαρτήτως των συνθηκών που επικρατούν στο δίκτυο. [Συγκεκριμένα, συγκλίνει σε μία κατάσταση ε-ισορροπίας σε Ο(1/ε^2) επαναλήψεις υπό συνθήκες αβεβαιότητας, και Ο(1/sqrt{ε}) επαναλήψεις υπό συνθήκες στασιμότητας.]

Η ομιλία αυτή βασίζεται στις ακόλουθες εργασίες:
- R. Colini-Baldeschi, R. Cominetti, P. Mertikopoulos, and M. Scarsini, When is selfish routing bad? The price of anarchy in light and heavy traffic, Operations Research 68 (2020), no. 2, 411–434.
- D. Q. Vu, K. Antonakopoulos, and P. Mertikopoulos, Fast routing under uncertainty: Adaptive learning in congestion games with exponential weights, NeurIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
- K. Antonakopoulos, D. Q. Vu, V. Cevher, K. Y. Levy, and P. Mertikopoulos, UnderGrad: A universal black-box optimization method with almost dimension-free convergence rate guarantees, ICML ’22: Proceedings of the 39th International Conference on Machine Learning, 2022.