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


Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu