UMN Machine Learning Seminar: First-order methods for nonlinear-constrained optimization
The UMN Machine Learning Seminar Series brings together faculty, students, and local industrial partners who are interested in the theoretical, computational, and applied aspects of machine learning, to pose problems, exchange ideas, and foster collaborations. The talks are every Thursday from 12 p.m. - 1 p.m. during the Fall 2021 semester.
This week's speaker, Yangyang Xu (Rensselaer Polytechnic Institute), will be giving a talk titled "First-order methods for nonlinear-constrained optimization."
First-order methods (FOMs) have recently been applied and analyzed for solving problems with complicated functional constraints. Existing works show that FOMs for functional constrained problems have lower-order convergence rates than those for unconstrained problems. In particular, an FOM for a smooth strongly-convex problem can have linear convergence, while it can only converge sublinearly for a constrained problem if the projection onto the constraint set is prohibited. In this talk, I will first give a lower-bound result of FOM for solving affine-constrained problems. Then I will show that the slower convergence is caused by the large number of functional constraints but not the constraints themselves. When there are only O(1) functional constraints, I will show that an FOM can have almost the same convergence rate as that for solving an unconstrained problem, even without the projection onto the feasible set. Finally, I will give an adaptive primal-dual method for problems with many constraints. Experimental results on quadratically-constrained quadratic programs will be shown to demonstrate the theory.
Yangyang Xu is now a tenure-track assistant professor in the Department of Mathematical Sciences at Rensselaer Polytechnic Institute. He received his B.S. in Computational Mathematics from Nanjing University in 2007, M.S. in Operations Research from the Chinese Academy of Sciences in 2010, and Ph.D. from the Department of Computational and Applied Mathematics at Rice University in 2014. His research interests are mainly in optimization theory and methods and their applications, such as in machine learning, statistics, and signal processing. His research has been supported by NSF and IBM. He was awarded the gold medal in the 2017 International Consortium of Chinese Mathematicians (ICCM).