Location: Zoom https://harvard.zoom.us/j/779283357 

Time: Tuesday, September 15, 2020, 10:00 AM (Eastern US), 16:00 (Central Europe), 22:00 (China)

Title:  Optimization, Complexity and Math

Abstract: (1) The most basic tools of convex optimization in Euclidean space extend to a far more general setting of Riemannian manifolds that arise from the symmetries of non-commutative groups. We develop first-order and second-order algorithms, and analyze their performance in general. While proving convergence bounds requires heavy algebraic and analytic tools, convergence itself depends in an elegant way on natural ``smoothness’’ parameters, in analogy with the Euclidean (commutative) case.

(2) These algorithms give exponential (or better) improvements in run-time for solving algorithmic many problems across CS, Math and Physics. In particular, these include problems in algebra (e.g. testing rational identities in non-commutative variables), in analysis (testing the feasibility and tightness of Brascamp-Lieb inequalities), in quantum information theory (to the quantum marginals problem), in algebraic geometry (to computing Kronecker coefficients), in computational complexity (to derandomizing new special cases of the PIT problem) and in optimization (to testing membership in large, implicitly described polytopes).

(3) The focus on symmetries exposes old and reveals new relations between the problems above. Essentially, they are all membership problems in null cones and moment polytopes of natural group actions on natural spaces. Invariant theory, which studies such group actions, plays an essential role in this development. In particular, a beautiful non-commutative duality theory (expending linear programming duality in the commutative case), and notions of geodesic convexity (extending the Euclidean one) and moment maps (extending the Euclidean gradient) are central to the algorithms and their analysis. Interestingly, most algorithms in invariant theory are symbolic/algebraic, and these new numeric/analytic algorithms proposed here often significantly improve on them.
Based on joint works with Zeyuan Allen-Zhu, Peter Burgisser, Cole Franks, Ankit Garg, Leonid Gurvits, Pavel Hrubes, Yuanzhi Li, Visu Makam, Rafael Oliveira and Michael Walter.

Additional Ways to Join
Join by telephone (use any number to dial in)
        +1 929 436 2866
        +1 312 626 6799
        +1 669 900 6833
        400 669 9381 China Toll-free

International numbers available: https://harvard.zoom.us/u/aclg6kOggb

One tap mobile: +19294362866,,779283357# US (New York)
    
Join by SIP conference room system
Meeting ID: 779 283 357
779283357@zoomcrc.com

Attachments