← List all talks ...

Scalable semidefinite programming

Joel Tropp – Professor, Caltech

Thu, 8-Apr-2021 / 4:30pm / Zoom: https://stanford.zoom.us/meeting/register/tJckfuCurzkvEtKKOBvDCrPv3McapgP6HygJ

Talk

• Video

Abstract

Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This talk describes a provably correct randomized algorithm for solving large, weakly constrained SDP problems by economizing on the storage and arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment problems. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over 10^14 entries.

This talk will highlight the ideas behind the algorithm in a streamlined setting. The insights include a careful problem formulation, design of a bespoke optimization method, use of randomized eigenvalue computations, and use of randomized sketching methods.

Joint work with Alp Yurtsever, Olivier Fercoq, Madeleine Udell, and Volkan Cevher. Based on arXiv 1912.02949 (Scalable SDP, SIMODS 2021) and other papers (SketchyCGM in AISTATS 2017, Nyström sketch in NeurIPS 2017).

Bio

Joel A. Tropp is Steele Family Professor of Applied and Computational Mathematics at Caltech. His research centers on data science, applied mathematics, numerical algorithms, and random matrix theory. He attained the Ph.D. degree in Computational Applied Mathematics at the University of Texas at Austin in 2004, and he joined Caltech in 2007. Prof. Tropp won the PECASE in 2008, and he was recognized as a Highly Cited Researcher in Computer Science each year from 2014–2018. He is co-founder and Section Editor of the SIAM Journal on Mathematics of Data Science (SIMODS), and he was co-chair of the inaugural 2020 SIAM Conference on the Mathematics of Data Science. Prof. Tropp was elected SIAM Fellow in 2019 and IEEE Fellow in 2020.