Title: Reimagining Algorithmic Efficiency: The Role of Data Structures in Machine Learning and Continuous Optimization
Li Chen, ACO PhD candidate, School of Computer Science
Link to Thesis draft: https://drive.google.com/file/d/1xwfkd-Ixo5jCKhJnuwKtFY3uh9NsR2TQ/view?u...
Date: July 10, 2023
Time: 11:00 AM (EST)
Location: Zoom (link TBD)
Committee:
Dr. Santosh Vempala, School of Computer Science, Georgia Institute of Technology
Dr. Mohit Singh, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Swati Gupta, School of Industrial and Systems Engineering, Georgia Institute of Technology, and School of Management, Massachusetts Institute of Technology
Advisor: Dr. Richard Peng, School of Computer Science, Georgia Institute of Technology, and Computer Science Department, Carnegie Mellon University
Reader: Dr. Jan van den Brand, School of Computer Science, Georgia Institute of Technology
Abstract: This thesis centers around the development of efficient data structures for applications in machine learning and continuous optimization. It introduces dynamic graph data structures based on Low-Stretch Decompositions and presents the first approximate fully dynamic all-pair min-cut/shortest-path data structure with sublinear update time, a near-linear time algorithm for the 2-Norm Flow Diffusion problem, and the first almost-linear time algorithm for maximum flows and minimum-cost flows. Beyond these, the thesis also presents developments of learning-augmented search trees. With appropriate learning oracles, it is possible to create theoretically superior search trees that fulfill essential performance measures. Importantly, this thesis also unveils the first B-Tree that achieves the Working Set Theorem in the external memory model.
Contrasting the typical adaptivity analysis of data structures, this thesis emphasizes examining the performance of data structures under more realistic usage conditions. It highlights how continuous optimization algorithms and real-world applications, like search and indexing, often interact with data structures in non-adaptive, non-worst-case ways.
