Events

Title:A bound on the quantum value of all compiled nonlocal games

Abstract: Nonlocal games provide valuable insights into quantum entanglement and even enable a classical verifier to confirm and control the behavior of entangled quantum provers. However, an issue with this approach has always been the necessity of two non-communicating quantum provers. To address this issue, a group of researchers recently introduced a "compilation procedure" that reduces the need for multiple provers and enforces non-communication through cryptographic methods. In this talk, we will show that even in this single prover "compiled setting," the prover remains fundamentally constrained. Specifically, we show that any polynomial-time quantum prover cannot win the "compiled game" with a higher probability than any quantum commuting provers could win the original nonlocal game. Our result is derived through a novel combination of techniques from cryptography and operator algebras and allows us to recover several important self-testing results in the "compiled setting".

Title:The mathematics of juggling

Abstract: I'll explain how to associate to any matrix a juggling pattern, with many examples demonstrated. This will give a decomposition of the Grassmannian Gr(k,n), of k-planes in n-space, into pieces indexed by juggling patterns. I'll explain how this "positroid decomposition" arises in (1) the very classical theory of "totally positive (real) matrices" (2) the characteristic p theory of "Frobenius splitting" and (3) Poisson geometry.

Title:The Inexact Augmented Lagrangian Method: Optimal Complexity Bounds and Applications to Solving Huge SDPs

Abstract:In the first part of this talk, we present optimal and nearly-optimal parameter-free augmented Lagrangian (AL) methods for convex and strongly optimization with linear constraints. Our AL methods employ tractable inexact criteria for solving their inner subproblems, which accelerated methods can be shown to achieve in a finite number of iterations that depends on the target accuracy.

In the second part of this talk, we present a new inexact augmented Lagrangian method, namely, HALLaR, that employs a Burer-Monteiro style low-rank factorization for solving large-scale semidefinite programs (SDPs). The AL subproblems are solved by a hybrid low-rank method, which is based on a combination of a low-rank Frank-Wolfe method and a nonconvex accelerated inexact proximal point method. In contrast to the classical low-rank method by Burer and Monteiro, HALLaR finds a near-optimal solution (with provable complexity bounds) of SDP instances satisfying strong duality. Computational results comparing HALLaR to state-of-the-art solvers on several large SDP instances show that the former finds higher accurate solutions in substantially less CPU time than the latter ones. For example, in less than 20 minutes, HALLaR can solve (on a personal laptop) a maximum stable set SDP with 1 million vertices and 10 million edges within 1e-5 relative accuracy.

This talk is based on joint work with Saeed Ghadimi and Henry Wolkowicz from University of Waterloo and Diego Cifuentes and Renato Monteiro from Georgia Tech.

Title:: The training dynamics and local geometry of high-dimensional learning

Abstract:Many modern data science tasks can be expressed as optimizing a complex, random functions in high dimensions. The go-to methods for such problems are variations of stochastic gradient descent (SGD), which perform remarkably well—c.f. the success of modern neural networks. However, the rigorous analysis of SGD on natural, high-dimensional statistical models is in its infancy. In this talk, we study a general model that captures a broad range of learning tasks, from Matrix and Tensor PCA to training two-layer neural networks to classify mixture models. We show the evolution of natural summary statistics along training converge, in the high-dimensional limit, to a closed, finite-dimensional dynamical system called their effective dynamics. We then turn to understanding the landscape of training from the point-of-view of the algorithm. We show that in this limit, the spectrum of the Hessian and Information matrices admit an effective spectral theory: the limiting empirical spectral measure and outliers have explicit characterizations that depend only on these summary statistics. I will then illustrate how these techniques can be used to give rigorous demonstrations of phenomena observed in the machine learning literature such as the lottery ticket hypothesis and the "spectral alignment" phenomenona. This talk surveys a series of joint works with G. Ben Arous (NYU), R. Gheissari (Northwestern), and J. Huang (U Penn).

This talk is based on joint work with Saeed Ghadimi and Henry Wolkowicz from University of Waterloo and Diego Cifuentes and Renato Monteiro from Georgia Tech.

Title: Exact algorithms for combinatorial interdiction problems

Abstract: Typical optimization paradigms involve a single decision maker that can control all variables involved. However, several practical situations involve multiple (potentially adversarial) decision makers. Bilevel optimization is a field that involves two decision makers. The key paradigm is that an upper-level decision maker acts first and after observing the upper-level decisions, a lower level decision maker optimizes their own objective. One particular important instance of such problems are so-called interdiction problems, where the upper-level decision is to try and forbid access to some decisions by the lower level and the goal of the upper level is to make the most impact into the lower-level decisions. These problems are, in general $\Sigma^P_2$-hard (likely harder than NP-hard). 

In this talk I will present recent work on improving significantly on state-of-the-art exact algorithms to obtain optimal solutions to some combinatorial interdiction problems. Despite the hardness results, our algorithm can solve instances consistently in a short amount of time. We also generalize our algorithms to propose a framework that could be applied to other similar problems, by deriving relaxations based on looking at these problems as games and performing operations on such games. 

This is joint work with Noah Weninger.