Computer Science Thesis Proposal

Tuesday, November 10, 2015 - 12:30pm

Location:

1507 Newell-Simon Hall

Speaker:

JAKUB PACHOCKI, Ph.D. Student http://www.cs.cmu.edu/~jpachock/

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. The proposed 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 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. •Investigate how to approximate massive amounts of high-dimensional data in a restrictive streaming setting, achieving optimal tradeoffs. •Develop nearly optimal algorithms for the Fermat-Weber (geometric median) problem, a fundamental task in robust estimation and clustering. •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) Copy of Thesis Summary

For More Information, Contact:

deb@cs.cmu.edu

Keywords:

Thesis Proposal