An Accelerated Decomposition Framework for Structured Sparse Optimization

结构化稀疏优化的加速分解框架

• 批准号: 2012243
• 负责人: Daniel Robinson
• 金额: $ 20万
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-15 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2012243&HistoricalAwards=false
• 关键词: Accelerated; Decomposition; Framework; Structured; Sparse

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.

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

项目成果

A Variance-Reduced and Stabilized Proximal Stochastic Gradient Method with Support Identification Guarantees for Structured Optimization

• 发表时间: 2023-02
• 期刊: Optimization Letters
• 影响因子: 1.6
• 作者: Yutong Dai;Guanyi Wang;Frank E. Curtis;Daniel P. Robinson

A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer

涉及群稀疏诱导正则化器的最小化子空间加速方法

• DOI: 10.1137/21m1411111
• 发表时间: 2022
• 期刊: SIAM Journal on Optimization
• 影响因子: 3.1
• 作者: Curtis, Frank E.;Dai, Yutong;Robinson, Daniel P.
• 通讯作者: Robinson, Daniel P.

An Adaptive Half-Space Projection Method for Stochastic Optimization Problems with Group Sparse Regularization

• 发表时间: 2023
• 作者: Yutong Dai;Tianyi Chen;Guanyi Wang;Daniel P. Robinson

Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization

• DOI: 10.1137/19m130563x
• 发表时间: 2019-12
• 期刊: SIAM J. Optim.
• 作者: Frank E. Curtis;Daniel P. Robinson;C. Royer;Stephen J. Wright