[Ml-stat-talks] Princeton Optimization Seminar -- Moses Charikar

Amir Ali Ahmadi a_a_a at princeton.edu
Wed Nov 19 11:02:24 EST 2014

Hello all,
The optimization seminar this week is by Moses Charikar and could be of interest to researchers in machine learning (abstract below).

If you would like to subscribe to the mailing list of the optimization seminar series, please visit the link below or send an email with
SUBSCRIBE opt-seminar in the body to listserv at lists.princeton.edu<mailto:listserv at lists.princeton.edu>.



===   Princeton Optimization Seminar   ===

DATE:  Thursday, November 20, 2014

TIME:  4:30pm   ***new time***

LOCATION:  Sherrerd Hall room 101   ***new room***

SPEAKER:  Moses Charikar, Computer Science Dept., Princeton University

TITLE:  Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

ABSTRACT:  We introduce and study a new notion of graph partitioning, intimately connected to k-means clustering. Informally, our graph partitioning objective asks for the optimal spectral simplification of a graph as a disjoint union of k normalized cliques. It is a variant of graph decomposition into expanders (where expansion is not measured w.r.t. the induced graph). Optimizing this new objective is equivalent to clustering the effective resistance embedding of the original graph. Our semidefinite programming based approximation algorithm for the new objective is closely related to spectral clustering: it optimizes the k-means objective on a certain smoothed version of the resistive distance embedding. We also show that spectral clustering applied directly to the original graph gives guarantees for our new objective function.

In order to illustrate the power of our new notion, we show that approximation algorithms for our new objective can be used in a black box fashion to approximately recover a partition of a graph into k pieces given a guarantee that a good partition exists with sufficiently large gap in internal and external conductance.

Joint work with Pranjal Awasthi, Ravishankar Krishnaswamy, and Ali Kemal Sinop.

> Brief bio:
> Moses Charikar is a professor of Computer Science at Princeton
> University. He obtained his PhD from Stanford University in 2000,
> spent a year in the research group at Google and has been at
> Princeton since 2001. He is broadly interested in the design and
> analysis of algorithms with an emphasis on approximation algorithms
> for hard problems, metric embeddings and algorithmic techniques for
> big data. His work on dimension reduction won the best paper award
> at FOCS 2003. He was awarded the 2012 Paris Kanellakis Theory and
> Practice Award for his work on locality sensitive hashing, and was
> recently named a Simons Investigator in theoretical computer
> science.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20141119/a7954a9a/attachment.html>

More information about the Ml-stat-talks mailing list