Login
Talks & Seminars
Title: Algorithms for Lipschitz Learning on Graphs
Dr. Sushant Sachdeva, Yale Institute of Network Sciences
Date & Time: July 24, 2015 10:30
Venue: Conference Room, C Block, 01st Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
In this talk, we'll discuss some interpolation problems on graphs. Given real-valued observations on some of the vertices, our goal is to compute a smooth (Lipschitz) extension to all vertices. Our focus will be the absolutely minimal Lipschitz extension, which is the limit of p-Laplacian regularization for large p. We'll present algorithmic results for computing these extensions efficiently -- a minimal Lipschitz extension in expected linear time, and an absolutely minimal Lipschitz extension in expected O(mn) time. We have implemented variants of the latter algorithm that run on graphs with millions of edges in a few minutes. Our algorithms naturally extend to directed graphs. We'll present some experimental results for detecting spam webpages using our algorithms. Finally, we'll discuss how these extensions are particularly suited for regularization and outlier removal, which is surprising since outlier removal is NP-hard for other natural extensions. This is joint work with Rasmus Kyng, Anup Rao, and Daniel Spielman.
Speaker Profile:
Sushant Sachdeva is currently a postdoctoral researcher with Daniel Spielman at the Yale Institute of Network Sciences. He works in Theory, with a focus on fast graph algorithms. He completed his B. Tech. in CSE from IITB in 2008, and received his Ph. D. from Princeton in 2013 under Sanjeev Arora. Before moving to Yale, he spent a semester at the Simons Institute at Berkeley.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback