# Thesis Defense: Addressing Missing Data and Scalable Optimization for Data-driven Decision Making

Thursday, May 6, 2021 - 1:00pm to 2:00pm

### Event Calendar Category

LIDS Thesis Defense

Dogyoon Song

LIDS

### Abstract

THESIS COMMITTEE:
In the second part of the talk, I will discuss the tradeoff between the scalability and the quality of optimal solutions in the context of approximate semidefinite programming. Specifically, I ask the question: how closely can we approximate the set of unit-trace $n \times n$ positive semidefinite (PSD) matrices, denoted by $D$, using at most $N$ number of $k \times k$ PSD constraints?'' I will argue that any set $S$ that approximates $D$ within a constant approximation ratio must have superpolynomial semidefinite extension complexity. This result implies the impossibility of global, non-adaptive approximation of the cone of $n \times n$ PSD matrices by a polynomial number of $k \times k$ PSD constraints for any $k = o(n / \log n)$.