An Accelerated Decomposition Framework for Structured Sparse Optimization

Lehigh University, Bethlehem PA

Investigators

Abstract

There has been an explosion in the availability of data that is collected from countless sources and through various modalities. For instance, medical image archives are increasing by 20-40% each year and over 400 million procedures per year involve at least one medical image. A goal among engineers and scientists is the design of advanced scientific tools that can use data to aid humanity. Many such tools already exist but their success is tightly bound to the idea of problem “sparsity”. For example, when predicting whether a patient in an intensive care unit will develop septic shock, only a few medical measurements are truly helpful in making such predictions. Since there are few important measurements compared to the total measurements available to a doctor, the prediction problem can be viewed as “sparse”. Despite the success of existing methods for sparse problems, their inadequacy for many modern machine learning and other types of problems has gradually been noticed by researchers. Since covariates often come in groups (e.g., genes that regulate hormone levels), one may wish to select them jointly instead of individually so that the models deployed make practical sense. Similar concerns occur in other important healthcare settings such as in the prediction of Parkinson's disease. This project will design, analyze, implement, and validate a new optimization framework that can handle these more complicated notions of “sparsity” beyond the simplest ones currently analyzed in theory and used in practice. This project provides research training opportunities for graduate students. The minimization of a function composed of a loss/data-fitting term and a regularization function is of immense interest throughout science and engineering. The past decade has witnessed an explosion of interest in problems involving sparsity-promoting regularization such as the L1-norm. Moving past simple L1-norm regularization, researchers are continually realizing the potential benefits of using more intricate regularization functions that promote structured sparsity, such as the group L1-norm and elastic net functions. The proposed project involves the design, analysis, and implementation of new algorithms for solving optimization problems that involve such structure promoting regularization. The 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 algorithmic framework is a carefully defined "space decomposition with subspace acceleration" mechanism. This mechanism adaptively decomposes the search space, and employs subspace steps based on proximal point and reduced-space Newton-type techniques. The step decomposition aspect of the methodology makes it more scalable and efficient than, say, straightforward first-order methods. The PIs will also enhance their general approach by designing new innovative strategies that combine domain decomposition and subspace acceleration in such a way that good complexity properties are obtained, accurate solution support estimates can be reliably achieved, and state-of-the-art numerical performance is attained. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.