|
CMU-CS-22-107
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMU-CS-22-107
Speeding Up Optimizations via Data Structures:
Faster Search, Sample and Maintenance
Lichen Zhang
M.S. Thesis
May 2022
CMU-CS-22-107.pdf
Keywords:
Data Structure, Discrete Optimization, Continuous Optimization
In this thesis, we present novel techniques to solve various fundamental discrete and continuous optimization problems, with the deployment of highly-efficient data structures.
- Sparsification: We obtain fast deterministic and randomized algorithms for spectral sparsification and its variants. We give a deterministic algorithm for constructing linear-sized spectral sparsifier in time O(dω+1) where ω ≈ 2.37 is the exponent of matrix multiplication, breaking the Ω(d4) barrier for all prior deterministic methods.
- Non-Convex Optimization: We present the first algorithm to train deep and over-parametrized neural networks in truly sub-quadratic time. It has a training cost of O(m2.25-α), where m is the width of the network and α ≈ 0.31 is the dual exponent of matrix multiplication.
The main theme of these major improvements is the novel adaption of data structures in different iterative processes. We show that for different optimization problems, we can frame their iterations as solving certain data structure problems. We design different data structures that are efficient and adaptively robust to realize such speedup.
175 pages
Thesis Committee:
Gary Miller (Chair)
Anil Ada
Zhao Song (Adobe Research)
Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science
|