Events Calendar

Communications, Networks & Systems (CommNetS) Seminar

Speaker: Dr. Adel Javanmard, USC

Talk Title: Phase Transitions in Semidefinite Relaxations

Series: CommNetS

Abstract: Statistical inference problems arising within signal processing, data mining, and machine learning naturally give rise to hard combinatorial optimization problems. These problems become intractable when the dimensionality of the data is large, as is often the case for modern datasets. A popular idea is to construct convex relaxations of these combinatorial problems, which can be solved efficiently for large scale datasets. Semidefinite programming (SDP) relaxations are among the most powerful methods in this family, and are surprisingly well-suited for a broad range of problems where data take the form of matrices or graphs. It has been observed several times that, when the 'statistical noise' is small enough, SDP relaxations correctly detect the underlying combinatorial structures.
In this talk, I will present some classical SDP relaxations for finding hidden partitions in sparse graphs (clustering) with asymptotic predictions for its performance. Time permitting, I will compare such relaxations with the recently developed local algorithms such as non-backtracking spectral partitioning. [Based on joint work with Federico Ricci-Tersenghi and Andrea Montanari]

Biography: Adel Javanmard is an assistant professor in the department of Data Sciences and Operation, Marshall School of Business at the University of Southern California. Prior to joining USC, he was a postdoctoral research fellow for a year at the Center for Science of Information, with worksite at UC Berkeley and Stanford University. He received his PhD and MS in Electrical Engineering from Stanford University in 2014 and 2011 advised by Andrea Montanari. His research interests are broadly in the area of high-dimensional statistics, machine learning, optimization, and graphical models. Adel has won several awards and fellowships, including the Thomas Cover dissertation award from IEEE Society (2015), the CSoI Postdoctoral Fellowship (2014), the Caroline and Fabian Pease Stanford Graduate Fellowship (2010-2012).

Host: Dr. Ashutosh Nayyar

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Annie Yu