30/03/2026
Με μεγάλη χαρά σας προσκαλούμε στην παρουσίαση της διπλωματικής εργασίας του Χριστόφορου Ζαχαρή, φοιτητή του μεταπτυχιακού προγράμματος στην Πληροφορική του Τμήματος Πληροφορικής & Τηλεπικοινωνιών, η οποία θα γίνει την Τετάρτη 1 Απριλίου, ώρα 13:00 - 14:00, στην αίθουσα Α56, στο Τμήμα Πληροφορικής & Τηλεπικοινωνιών του ΕΚΠΑ.
Η διπλωματική εργασία του Χριστόφορου έχει τίτλο "Comparative Analysis of Geometric Random Walks for Sampling in High-Dimensional Convex Polytopes".
Σας περιμένουμε όλες και όλους την Τετάρτη στην παρουσίαση της διπλωματικής εργασίας του Χριστόφορου!
Βησσαρίων Φυσικόπουλος
————————————————————————
Abstract: This master’s thesis focuses on uniform sampling from high-dimensional convex polytopes, a fundamental problem with critical applications in statistics, machine learning, and systems biology. The study delves into the theoretical background of Markov Chain Monte Carlo (MCMC) methods, examining not only traditional geometric random walks (such as the Ball Walk, Hit-and-Run, Coordinate-Directions Hit-and-Run, and Billiard Walks) but also more specialized methods (Barrier walks, e.g., Dikin, Vaidya, John, and Constrained Riemannian Hamiltonian Monte Carlo - CRHMC).
The core of this work consists of a thorough, empirical comparative evaluation of these algorithms, bridging the gap between existing literature and practical application. The top-tier software libraries in the field (Volesti, PolytopeWalk, PolytopeSampler) are directly compared against each other, supported by specialized preprocessing tools like PolyRound, Dingo. The experimental framework scales systematically: from fundamental shapes (hypercubes, simplices, and Birkhoff polytopes up to 10^4 dimensions) to highly complex, real-world constraint models derived from biological metabolic networks and pathological linear programming problems (Netlib).
Under strict time and computational constraints, the thesis focuses on comparing the mixing times and overall time efficiency of the algorithms. The results explicitly demonstrate that, in practice, these algorithms achieve a faster generation of independent samples compared to the highly conservative theoretical predictions found in the literature. Concurrently, clear crossover points in performance are highlighted: while Billiard methods absolutely dominate in low and medium dimensions, the CRHMC method universally prevails in extreme dimensions and sparse matrix representations.
Finally, the significant computational cost and constraints imposed by mathematical rounding are quantified, thus providing a comprehensive, practical guide for selecting the appropriate algorithm and software depending on the geometric nature of the given problem. To evaluate the efficiency and accuracy of the algorithms, convergence metrics such as the Potential Scale Reduction Factor (PSRF), Effective Sample Size (ESS), and the Kolmogorov-Smirnov test are employed. The thesis concludes with an extensive comparative evaluation examining the mixing times and time efficiency of the methods across various geometries including hypercubes, simplices, Birkhoff polytopes, and biological models (e.g., E. coli). The results offer a critical perspective on how different random walks and rounding techniques respond as the dimensionality of the problem increases, as well as their performance relative to theoretically proven bounds.
News Theme