[Theory] FW: Theory Lunch 2023-04-05T17:30:00.000Z

[Christopher Kang]

________________________________
From: noreply+automations at airtableemail.com <noreply+automations at airtableemail.com>On Behalf OfTheoryBot (via Airtable) <noreply+automations at airtableemail.com>
Sent: Wednesday, April 5, 2023 12:11:27 AM (UTC-06:00) Central Time (US & Canada)
To: Antares Chen <antaresc at uchicago.edu>
Cc: Christopher Kang <ctkang at uchicago.edu>
Subject: Theory Lunch 2023-04-05T17:30:00.000Z


Today's Theory Lunch talk:

Vaidehi Srinivas (Northwestern): The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound

https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09<https://urldefense.com/v3/__https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09__;!!BpyFHLRN4TMTrA!-xsd_U8B6-THb-OIb1GBU3X-H_1K9oGuz_Q_3XUgeCN05Y_rI1QqaqEq60DHPOYPb9FW5hHb087Wd7kL2kd3iT9phqg4fnqp9BU$>

Description: Semidefinite programs (SDPs) are powerful algorithmic tool with wide-ranging applications in combinatorial optimization, control theory, machine learning, and operations research. They are convex problems, so they can be solved in polynomial time. However, in practice, algorithms with worst-case guarantees face a large memory bottleneck, so SDPs are usually solved using the low-memory non-convex Burer-Monteiro method. Previous work has given guarantees for the Burer-Monteiro method in the paradigm of smoothed analysis. In this work, we show that the Burer-Monteiro method can fail in the worst-case, justifying the use of beyond worst-case paradigms like smoothed analysis. We will discuss the techniques used to reason about the optimization landscape, which harness the geometry of the problem quite differently than previous approaches. We hope that these techniques can be extended more broadly to other important non-convex optimization problems. This is joint work with Liam O'Carroll and Aravindan Vijayaraghavan.

Sent via Automations on         [Airtable] <https://urldefense.com/v3/__https://airtable.com?utm_medium=email&utm_source=product_team&utm_content=transactional-alerts__;!!BpyFHLRN4TMTrA!-xsd_U8B6-THb-OIb1GBU3X-H_1K9oGuz_Q_3XUgeCN05Y_rI1QqaqEq60DHPOYPb9FW5hHb087Wd7kL2kd3iT9phqg41lAjwH0$>
©2023 Airtable
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230405/7fd8b86a/attachment.html>