An Accelerated Decomposition Framework for Structured Sparse Optimization

从无数来源和通过各种方式收集的数据呈爆炸式增长。例如，医学图像档案每年以20%-40%的速度增长，每年有超过4亿次的手术至少涉及一张医学图像。工程师和科学家的一个目标是设计先进的科学工具，可以利用数据来帮助人类。许多这样的工具已经存在，但它们的成功与问题“稀疏性”的想法紧密相连。例如，在预测重症监护病房的患者是否会发生感染性休克时，只有少数医学测量真正有助于做出这样的预测。由于与医生可用的总测量值相比，几乎没有重要的测量值，因此可以将预测问题视为“稀疏”问题。尽管已有的稀疏问题方法取得了成功，但它们对于许多现代机器学习和其他类型问题的不足逐渐被研究者们所注意到。由于协变量通常是成组的(例如，调节激素水平的基因)，人们可能希望联合选择它们，而不是单独选择，以便所部署的模型具有实际意义。类似的担忧也出现在其他重要的医疗保健环境中，例如预测帕金森氏症。这个项目将设计、分析、实现和验证一个新的优化框架，该框架可以处理这些更复杂的“稀疏性”概念，而不是目前在理论上分析和实践中使用的最简单的概念。这个项目为研究生提供了研究培训的机会。由损失/数据拟合项和正则化函数组成的函数的最小化在整个科学和工程中都是非常有趣的。在过去的十年里，人们对L1范数等涉及稀疏性促进正则化的问题产生了极大的兴趣。在简单的L1范数正则化之后，研究人员不断地认识到使用更复杂的正则化函数来促进结构稀疏性的潜在好处，例如群L1范数和弹性网函数。建议的项目包括设计、分析和实施新的算法来解决涉及这种促进正则化的结构的优化问题。这些算法将被设计成具有广泛的适用性、可伸缩性和高效，并将被证明具有很强的收敛速度保证。所提出的算法框架的新奇之处在于定义了一种精心定义的“子空间加速空间分解”机制。该机制对搜索空间进行自适应分解，并采用基于邻近点的子空间步长和缩减空间的牛顿型技术。该方法的步骤分解方面使其比直接的一阶方法更具伸缩性和效率。PIs还将通过设计新的创新策略来增强他们的一般方法，这些策略结合了区域分解和子空间加速，从而获得了良好的复杂性属性，可以可靠地实现准确的解决方案支持估计，并获得了最先进的数值性能。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.