Ohio State nav bar

Analysis and Operator Theory Seminar - Dustin Mixon

photo of Dustin Mixon
September 19, 2017
11:30AM - 12:25PM
Cockins Hall 240

Date Range
Add to Calendar 2017-09-19 11:30:00 2017-09-19 12:25:00 Analysis and Operator Theory Seminar - Dustin Mixon Title: A semidefinite relaxation of k-means clusteringSpeaker: Dustin Mixon (Ohio State University)Abstract: Recently, Awasthi et al proved that a semidefinite relaxation of the k-means clustering problem is tight under a particular data model called the stochastic ball model. This result exhibits two shortcomings:naive solvers of the semidefinite program are computationally slow, andthe stochastic ball model prevents outliers that occur, for example, in the Gaussian mixture model.This talk will cover recent work that tackles each of these shortcomings. First, I will discuss a new type of algorithm (introduced by Bandeira) that combines fast non-convex solvers with the optimality certificates provided by convex relaxations. Second, I will discuss how to analyze the semidefinite relaxation under the Gaussian mixture model. In this case, outliers in the data obstruct tightness in the relaxation, and so fundamentally different techniques are required. Several open problems will be posed throughout. This is joint work with Takayuki Iguchi and Jesse Peterson (AFIT), as well as Soledad Villar and Rachel Ward (UT Austin). Cockins Hall 240 Department of Mathematics math@osu.edu America/New_York public

Title: A semidefinite relaxation of k-means clustering

Speaker: Dustin Mixon (Ohio State University)

Abstract: Recently, Awasthi et al proved that a semidefinite relaxation of the k-means clustering problem is tight under a particular data model called the stochastic ball model. This result exhibits two shortcomings:

  1. naive solvers of the semidefinite program are computationally slow, and
  2. the stochastic ball model prevents outliers that occur, for example, in the Gaussian mixture model.

This talk will cover recent work that tackles each of these shortcomings. First, I will discuss a new type of algorithm (introduced by Bandeira) that combines fast non-convex solvers with the optimality certificates provided by convex relaxations. Second, I will discuss how to analyze the semidefinite relaxation under the Gaussian mixture model. In this case, outliers in the data obstruct tightness in the relaxation, and so fundamentally different techniques are required. Several open problems will be posed throughout. This is joint work with Takayuki Iguchi and Jesse Peterson (AFIT), as well as Soledad Villar and Rachel Ward (UT Austin).

Events Filters: