À¶Ý®ÊÓƵ

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 À¶Ý®ÊÓƵ 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 À¶Ý®ÊÓƵ 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.

Ìý

Ìý

Title:Strongly connected orientations and integer lattices

Abstract: Let D = (V, A) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper 'slanted' face F of P. We prove under a mild necessary condition that the 0,1 points in FÌýcontain anÌýintegralÌýbasisÌýB, i.e., B is linearly independent, and every integral vector in the linear of span of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form aÌýHilbert basis.

Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say k, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any odd prime number p, a p-adic packing of dijoins of value k and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by the 0,1 points in F, where F is the face of P satisfying x(C) = 1 for every minimum dicut C.

This is based on joint work with Gerard Cornuejols, Siyue Liu, and Olha Silina.

Ìý

Ìý

Title:Faster linear algebra using treewidth

Abstract:

: We look at the complexity of solving sparse linear systems as a function of the treewidth of the instance. That is, the sparse matrix is associated with a sparse graph, and solutions can be found faster when that graph has low treewidth. We give a parameterized algorithm in system size and treewidth achieving the conjectured optimal performance.

This is joint work with Daniel Grier.

Ìý

Title:Constraining moduli space cohomology by counting graphs

Abstract: In 1992, Kontsevich defined complexes spanned by graphs. TheseÌý
complexes are increasingly prominent in algebraic topology, geometricÌý
group theory and mathematical physics. For instance, a 2021 theorem byÌý
Chan-Galatius and Payne implies that the top-weight cohomology of theÌý
moduli space of curves of genus g is equal to the homology of a specificÌý
graph complex. I will present a new theorem on the asymptotic growthÌý
rate of the Euler characteristic of this graph complex and explain itsÌý
implication on the cohomology of the moduli space of curves. The proofÌý
involves solving a specific graph counting problem.

Ìý

Title:Splitting algorithms for monotone inclusions with minimalÌýdimension

Abstract: Many situations in convex optimization can be modeled as the problem ofÌýfinding a zero of a monotone operator, which can be regarded as aÌýgeneralization of the gradient of a differentiable convex function. InÌýorder to numerically address this monotone inclusion problem, it isÌývital to be able to exploit the inherent structure of the operatorÌýdefining it. The algorithms in the family of the splitting methodsÌýachieve this by iteratively solving simpler subtasks that are defined byÌýseparately using some parts of the original problem.

In the first part of this talk, we will introduce some of the mostÌýrelevant monotone inclusion problems and present their applications toÌýoptimization. Subsequently, we will draw our attention to a commonÌýanomaly that has persisted in the design of methods in this family: theÌýdimension of the underlying space —which we denote as lifting— of theÌýalgorithms abnormally increases as the problem size grows. This hasÌýdirect implications on the computational performance of the method as aÌýresult of the increase of memory requirements. In this framework, weÌýcharacterize the minimal lifting that can be obtained by splittingÌýalgorithms adept at solving certain general monotone inclusions.ÌýMoreover, we present splitting methods matching these lifting bounds, and thusÌýhaving minimal lifting.

Ìý