Jakub Pachocki

Graphs and Beyond: Faster Algorithms for High Dimensional Convex Optimization Degree Type: Ph.D. in Computer Science
Advisor(s): Gary Miller
Graduated: May 2016

Abstract:

Convex optimization is one of the most robust tools for automated data analysis. It has widespread applications in fields such as machine learning, computer vision, combinatorial optimization and scientific computing. However, the rapidly increasing volume and complexity of data that needs to be processed often renders general-purpose algorithms unusable.

This thesis aims to address this issue through development of very fast algorithms for core convex optimization problems, with a focus on graphs. To this end, we:

• Develop nearly optimal algorithms for the Fermat-Weber (geometric median) problem, a fundamental task in robust estimation and clustering.
• Investigate how to approximate massive amounts of high-dimensional data in a restrictive streaming setting, achieving optimal tradeoffs.
• Develop the fastest algorithm for solving linear systems on undirected graphs. This is achieved through improved clustering algorithms and better understanding of the interplay between combinatorial and numerical aspects of previous approaches.
• Show the existence of clustering and oblivious routing algorithms for a broad family of directed graphs, in hopes of advancing the search for faster maximum flow algorithms.

Most of the presented algorithms work in time nearly linear in the sparsity of the input data. The unifying theme of these results is careful analysis of optimization algorithms in high-dimensional spaces, and mixing combinatorial and numerical approaches.

Thesis Committee:
Gary L. Miller (Chair)
Anupam Gupta
Daniel Sleator
Shang-Hua Teng (University of Southern California)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
Convex Optimization, Linear System Solvers, Spectral Graph Theory