Purdue University Graduate School
Browse

Matrix Sketching in Optimization

Download (2.78 MB)
thesis
posted on 2024-04-19, 20:29 authored by Gregory Paul DexterGregory Paul Dexter

Continuous optimization is a fundamental topic both in theoretical computer science and applications of machine learning. Meanwhile, an important idea in the development modern algorithms it the use of randomness to achieve empirical speedup and improved theoretical runtimes. Stochastic gradient descent (SGD) and matrix-multiplication time linear program solvers [1] are two important examples of such achievements. Matrix sketching and related ideas provide a theoretical framework for the behavior of random matrices and vectors that arise in these algorithms, thereby provide a natural way to better understand the behavior of such randomized algorithms. In this dissertation, we consider three general problems in this area.

History

Degree Type

  • Doctor of Philosophy

Department

  • Computer Science

Campus location

  • West Lafayette

Advisor/Supervisor/Committee Chair

Petros Drineas

Advisor/Supervisor/Committee co-chair

Rajiv Khanna

Additional Committee Member 2

Cameron Musco

Additional Committee Member 3

Anuran Makur

Additional Committee Member 4

Kent Quanrud

Usage metrics

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC