An Accelerated Decomposition Framework for Structured Sparse Optimization

从无数来源和通过各种方式收集的数据数量激增。例如，医学图像档案每年以20-40%的速度增长，每年有超过4亿个程序涉及至少一个医学图像。 工程师和科学家的一个目标是设计先进的科学工具，可以使用数据来帮助人类。 许多这样的工具已经存在，但它们的成功与问题的“稀疏性”思想紧密相关。 例如，当预测重症监护病房的病人是否会发生败血性休克时，只有少数医学测量方法真正有助于做出这样的预测。由于与医生可用的总测量值相比，很少有重要的测量值，因此预测问题可以被视为“稀疏”。尽管现有的方法在稀疏问题上取得了成功，但研究人员逐渐注意到它们对许多现代机器学习和其他类型问题的不足。由于协变量通常是分组的（例如，调节激素水平的基因），人们可能希望联合而不是单独选择它们，以便部署的模型具有实际意义。类似的担忧也发生在其他重要的医疗保健环境中，例如帕金森病的预测。这个项目将设计，分析，实现和验证一个新的优化框架，可以处理这些更复杂的“稀疏”概念，而不是目前在理论上分析和实践中使用的最简单的概念。本项目为研究生提供了研究训练的机会。由损失/数据拟合项和正则化函数组成的函数的最小化在整个科学和工程中具有巨大的兴趣。 在过去的十年里，人们对稀疏促进正则化（如L1-norm）问题的兴趣激增。超越简单的L1范数正则化，研究人员不断意识到使用更复杂的正则化函数来促进结构化稀疏性的潜在好处，例如群L1范数和弹性网络函数。拟议的项目涉及设计，分析和实现新的算法，用于解决涉及这种结构促进正则化的优化问题。 该算法将被设计为广泛适用，可扩展，高效，并将被证明具有强大的收敛速度保证。 所提出的算法框架的新奇是一个仔细定义的“空间分解与子空间加速”机制。 该机制自适应地分解搜索空间，并采用基于邻近点的子空间步长和缩减空间牛顿型技术。 该方法的步骤分解方面使其比简单的一阶方法更具可扩展性和效率。 PI还将通过设计新的创新策略来增强其通用方法，这些策略将联合收割机域分解和子空间加速相结合，以获得良好的复杂性特性，可以可靠地实现准确的解决方案支持估计，和国家的该奖项反映了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.