Exterior-Point Operator Splitting for Nonconvex Learning

Wednesday, February 24, 2021 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Shuvomoy Das Gupta



Zoom meeting id

936 4141 1580

Join Zoom meeting



We present the nonconvex exterior-point operator splitting algorithm (NExOS), a novel linearly convergent first-order algorithm tailored for constrained nonconvex learning problems. We consider the problem of minimizing a convex cost function over a nonconvex constraint set, where projection onto the constraint set is single-valued around points of interest. A wide range of nonconvex learning problems have this structure including (but not limited to) sparse and low-rank optimization problems.

By exploiting the underlying geometry of the constraint set, NExOS finds a locally optimal point by solving a sequence of penalized problems with strictly decreasing penalty parameters. NExOS solves each penalized problem by applying an outer iteration operator splitting algorithm, which converges linearly to a local minimum of the corresponding penalized formulation under regularity conditions. Furthermore, the local minima of the penalized problems converge to a local minimum of the original problem as the penalty parameter goes to zero.

We implement NExOS in the open-source Julia package NExOS.jl, which has been extensively tested on many instances from a wide variety of learning problems. We study several examples of well-known nonconvex learning problems, and we show that in spite of being general-purpose, NExOS is able to compute high-quality solutions very quickly and is competitive with specialized algorithms.



Shuvomoy Das Gupta is a second-year Ph.D. student at the Operations Research Center advised by Professor Bart Van Parys. He obtained his Master of Applied Science from the ECE Department at the University of Toronto in 2016. Afterward, he worked as a researcher at the Research & Technology Department of Thales Canada. His Master of Applied Science research work focused on optimization models to compute energy-efficient railway timetables has been integrated with the largest installed base of communication-based train control systems worldwide. Previously, he obtained a Bachelor of Science in Electrical and Electronic Engineering from Bangladesh University of Engineering and Technology.