Speaker: Armin Eftekhari, Department of Mathematics and Mathematical Statistics, Umeå University
Title: Old Tricks for New Problems: Homotopy for Constrained Nonconvex Optimization and Langevin Sampling
Abstract:
The Augmented Lagrangian Method (ALM) and its variants are the workhorses of convex constrained optimization. The simple but powerful idea of enforcing constraints using penalty functions has interesting applications beyond convex optimization, and this talk focuses on two of them.
In the first part of the talk, we will design efficient and intuitive ALM algorithms to solve constrained nonconvex optimization problems, improving the best available convergence rates. We show how the ubiquitous Slater's condition in convex optimization gives its place to a geometric condition which is reminiscent of the Mangasarian-Fromovitz constraint qualification. We then apply these new algorithms to a variety of applications, including clustering, generalized eigenvalue decomposition, sparse regression, and even defense against adversarial attacks in deep neural networks.
In the second part of the talk, we will use the same ideas to address a key shortcoming of the popular Langevin Monte Carlo technique by sampling from distributions with limited support, e.g., a convex polytope or an affine subspace. Some of our results are new and the rest improve the best-known iteration complexities for Langevin sampling.
