Computer Science Department
School of Computer Science, Carnegie Mellon University
Graphs and Beyond: Faster Algorithms
for High Dimensional Convex Optimization
Convex Optimization, Linear System Solvers, Spectral Graph Theory
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
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:
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.
- 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
Gary L. Miller (Chair)
Shang-Hua Teng (University of Southern California)
Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science