Lehigh ISE Professors, Daniel P. Robinson (PI) and Frank E. Curtis (Co-PI) were awarded a three-year grant from the NSF Division of Mathematical Sciences to design, analyze, implement, and validate a new optimization framework that can manage more complex “sparsity” problems beyond the fundamental ones being used in practice.
Problems to minimize a function composed of a loss/data-fitting term and a regularizer have been of interest for decades throughout science and engineering. In particular, the past decade has witnessed an explosion of interest in problems involving sparsity-promoting regularizers such as the l1-norm, which are popular in compressed sensing, computer vision, machine learning, deep learning, and other areas. Moving past l1-norm regularization, researchers have realized the potential benefits of more complicated regularizers that promote structured sparsity, such as the group l1-norm and elastic net regularizers. Problems with such regularizers are significantly more difficult to solve. Therefore, the field demands new algorithms that are efficient and scalable, are applicable for problems with a wide range of structured sparsity-promoting regularizers, possess strong worst-case performance guarantees, and reliably offer accurate solution support estimates (i.e., predictions of the variables that are (non)zero at a minimizer).
During this project, algorithms will be designed to be broadly applicable, scalable, and efficient, and will be shown to possess strong convergence rate guarantees. The novelty of the proposed algorithms is that they will significantly build upon a “space decomposition with subspace acceleration” methodology recently developed by the PIs. This methodology, which the PIs have shown to yield state-of-the-art results for solving l1-norm regularized problems, adaptively decomposes the search space, then employs subspace steps based on proximal point and/or reduced-space Newton-type techniques.
Numerous science and engineering disciplines would benefit from scalable, efficient, and reliable algorithms for minimizing a loss function plus a term promoting structured sparsity. These include applications in computer vision (e.g., motion segmentation and face clustering), matrix completion, dimension reduction in multivariate regression, multi-task and label learning, and cost-driven prediction in healthcare, just to name a few. The PIs have strong expertise in the design, analysis, and implementation of algorithms for solving such problems, meaning that the project has a high probability of success.
Professor Robinson commented “Our team is excited because of the tremendously positive effect that our research will have in enabling smarter decisions in areas such as healthcare, medicine, and computer vision, to name a few.”