Comparative Analysis of Geometric Random Walks for Sampling in High-Dimensional Convex Polytopes

Η παρούσα μεταπτυχιακή διατριβή επικεντρώνεται στην ομοιόμορφη δειγματοληψία από κυρτά πολύτοπα υψηλών διαστάσεων, ένα θεμελιώδες πρόβλημα με κρίσιμες εφαρμογές στη στατιστική, τη μηχανική μάθηση και τη συστημική βιολογία. Η μελέτη εμβαθύνει στο θεωρητικό υπόβαθρο των μεθόδων Markov Chain Monte Carlo (MCMC), εξετάζοντας όχι μόνο τους παραδοσιακούς γεωμετρικούς τυχαίους περιπάτους (όπως Ball Walk, Hit-and-Run, Coordinate-Directions Hit-and-Run και Billiard Walks), αλλά και πιο εξειδικευμένες μεθόδους (Barrier Walks, π.χ. Dikin, Vaidya, John, Constrained Riemannian Hamiltonian Monte Carlo - CRHMC). Ο πυρήνας της εργασίας συνίσταται στην ενδελεχή, εμπειρική συγκριτική αξιολόγηση αυτών των αλγορίθμων, γεφυρώνοντας το χάσμα μεταξύ της υπάρχουσας βιβλιογραφίας και της πρακτικής εφαρμογής. Τίθενται σε άμεση αντιπαράθεση οι κορυφαίες βιβλιοθήκες λογισμικού του χώρου (Volesti, PolytopeWalk, PolytopeSampler), με την υποστήριξη εξειδικευμένων εργαλείων προεπεξεργασίας (PolyRound, Dingo). Το πειραματικό πλαίσιο κλιμακώνεται συστηματικά: από θεμελιώδη θεωρητικά σχήματα (πυκνοί υπερκύβοι, simplex και πολύτοπα Birkhoff έως 10^4 διαστάσεων) έως εξαιρετικά πολύπλοκα, πραγματικά μοντέλα περιορισμών προερχόμενα από βιολογικά μεταβολικά δίκτυα και παθολογικά προβλήματα γραμμικού προγραμματισμού (Netlib). Μέσα από αυστηρούς χρονικούς και υπολογιστικούς περιορισμούς, η διατριβή εστιάζει στη σύγκριση των χρόνων μίξης (mixing times) και της συνολικής χρονικής αποδοτικότητας (time efficiency) των αλγορίθμων. Τα αποτελέσματα καταδεικνύουν ρητά ότι, στην πράξη, οι αλγόριθμοι αυτοί επιτυγχάνουν ταχύτερη παραγωγή ανεξάρτητων δειγμάτων σε σχέση με τις ιδιαίτερα συντηρητικές θεωρητικές προβλέψεις της βιβλιογραφίας. Παράλληλα, αναδεικνύονται ξεκάθαρα σημεία καμπής στην απόδοση: ενώ οι μέθοδοι Billiard κυριαρχούν απόλυτα σε χαμηλές και μεσαίες διαστάσεις, η μέθοδος CRHMC επικρατεί καθολικά σε ακραίες διαστάσεις και αναπαραστάσεις αραιών μητρώων (sparse matrices). Τέλος, ποσοτικοποιείται το σημαντικό υπολογιστικό κόστος και οι περιορισμοί που επιβάλλει η μαθηματική στρογγυλοποίηση, παρέχοντας έτσι έναν ολοκληρωμένο, πρακτικό οδηγό για την επιλογή του κατάλληλου αλγορίθμου και λογισμικού ανάλογα με τη γεωμετρική φύση του εκάστοτε προβλήματος. Για την εκτίμηση της αποδοτικότητας και της ακρίβειας των αλγορίθμων, χρησιμοποιούνται μετρικές σύγκλισης όπως ο παράγοντας PSRF, το Effective Sample Size (ESS) και το τεστ Kolmogorov-Smirnov. Η διατριβή ολοκληρώνεται με μια εκτενή συγκριτική αξιολόγηση, όπου εξετάζονται οι χρόνοι μίξης (mixing times) και η χρονική απόδοση των μεθόδων σε διάφορες γεωμετρίες — συμπεριλαμβανομένων υπερκύβων, simplices, πολυτόπων Birkhoff και βιολογικών μοντέλων (π.χ. E. coli). Τα αποτελέσματα προσφέρουν μια κριτική ματιά στο πώς ανταποκρίνονται οι διαφορετικοί τυχαίοι περίπατοι και οι τεχνικές στρογγυλοποίησης (rounding) καθώς αυξάνεται η διάσταση του προβλήματος, καθώς και στην απόδοσή τους σε σχέση με τα θεωρητικώς αποδεδειγμένα όρια.

Authors dc:creator

• ΖΑΧΑΡΗΣ ΧΡΙΣΤΟΦΟΡΟΣ
• ZACHARIS CHRISTOFOROS

• Θετικές Επιστήμες
• Science

Language dc:language

English

Identifier

uoadl:5374086

OAI identifier oai:identifier

oai:lib.uoa.gr:uoadl:5374086