VIRTUAL IDeAS Seminar: Tim Kunisky - Courant Institute of Mathematical Sciences at New York University

Wed, Dec 9, 2020, 12:00 pm

Spectral barriers in random certification problems

Certifying bounds on optimization problems---bounding the best-possible solution rather than merely producing a single good solution---is an important class of algorithmic tasks ubiquitous in combinatorial and continuous optimization, and especially intimately related to convex relaxation techniques. I will present theoretical evidence that, for a class of random problems including max-cut, graph coloring, and various structured PCA problems, there is a fundamental obstruction to efficiently certifying bounds better than a naive spectral bound. Consequently, even sophisticated linear and semidefinite programming relaxations perform no better on average than a simple spectral relaxation. I will show how this conclusion follows from the possibility of "planting" high-quality solutions in a problem instance in a way that is "quiet" or difficult to detect. Time permitting, I will also discuss how this quietness may be predicted with hypothesis testing algorithms based on low-degree polynomials, as well as how this framework suggests a new approach to lower bounds in the sum-of-squares semidefinite programming hierarchy, as well as joint work with Afonso Bandeira and Alex Wein.

Tim Kunisky is a fifth-year PhD student in the Courant Institute of Mathematical Sciences at New York University, advised by Afonso Bandeira and G‌érard Ben Arous.  His current research interests include: Computational "hard regimes" in problems arising in data science and optimization; convex relaxations and their average-case performance on random problems; and random optimization landscapes and the relationship between their high-dimensional geometry and the computational hardness of optimization.


Event category: 

Upcoming Events

POSTPONED: PACM Colloquium: Luigi Martinelli, Mechanical and Aerospace Engineering - Princeton University

Mon, Jan 31, 2022, 4:30 pm
Location: 214 Fine Hall (Postponed till FALL 2022)

Journal Club

Tue, Feb 1, 2022, 10:00 am
Location: Fine Hall 224

PACM Colloquium: Waheed Bajwa, Visiting Fellow at Princeton University and Associate Professor, Rutgers University, INSPIRE Lab

Mon, Feb 7, 2022, 4:30 pm
Location: 214 Fine Hall (In Person - Princeton ID Holders Only)