Accelerated Algorithms for a Class of Saddle Point problems and Variational Inequalities

一类鞍点问题和变分不等式的加速算法

• 批准号: 1319050
• 负责人: Yunmei Chen
• 金额: $ 16万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319050&HistoricalAwards=false
• 关键词: Accelerated; Algorithms; Class; Saddle; Point

This project will develop novel theories and optimal numerical methods for solving certain classes of deterministic and stochastic saddle point and variational inequality problems arising from large-scale data analysis in various disciplines. The proposed accelerated primal-dual (APD) algorithm is based on the integration of a multi-step acceleration scheme with the primal-dual method, and expected to exhibit an optimal rate of convergence as the one obtained by Nesterov for a different scheme. The proposed stochastic APD algorithm is also expected to possess an optimal rate of convergence for solving stochastic saddle point problems, while no stochastic primal-dual algorithms have been developed in the literature. Moreover, the research will be extended to the development of optimal methods for solving a class of composite variational inequalities (VI) that includes the class of the saddle point problems to be studied as a special case. This study provides some important insights on the decomposition of a general VI problem to potentially accelerate its solution. Furthermore, the theoretical analysis on optimal convergence rate, and optimal estimation of the bound for duality gap, especially, the dependence on the distance between the initial and saddle points (or the diameter of the feasible set, if they are bounded), of all the proposed algorithms will be investigated. The project will investigate and develop backtracking strategies for the proposed algorithms to enhance their practical performance. The new methods will be applied to several image reconstruction and machine learning problems. The class of the deterministic and stochastic saddle point and variational inequality problems studied in this proposal has been considered as a framework of ill-posed inverse problems regularized by a non-smooth functional in many data analysis problems, such as image reconstruction, compressed sensing and machine learning. The success of the proposed research will significantly advance non-smooth convex optimization solvers by enriching solver's abilities in accelerating computation with good theoretical performance guaranteed. Therefore, this project is expected to greatly increase the applicability of many emerging technologies, such as partially parallel imaging and dynamic multi-tracer PET. Those imaging methods can significantly reduce scan time and improve image quality. However, their clinical applications have been hindered by our incapability to efficiently solve the large-scale ill-posed and ill-conditioned inverse image reconstruction problems. Moreover, the development of stochastic APD algorithms will greatly enhance learning power. For instance, these optimal methods will enable researchers to build high-level, class specific feature detectors from massive datasets. The new methods to be developed have a wide range of applications in large-scale data analysis problems from various disciplines. Therefore, the research will contribute to the research communities and industry with mutual interest. The algorithms developed during the research will be made freely available on the World Wide Web. The graduate students of the PIs will be involved in all aspects of the research, both theoretical analysis as well as practical implementation of algorithms. The research will be made accessible to more graduate and senior undergraduate students through seminars and course developments. The PIs intend to teach courses based on the proposed research.

该项目将开发新的理论和最佳数值方法，用于解决各种学科中大规模数据分析所产生的某些确定性和随机鞍点和变分不等式问题。建议的加速原始-对偶（APD）算法是基于多步加速计划与原始-对偶方法的集成，并预计将表现出最佳的收敛速度，如Nesterov获得的一个不同的计划。所提出的随机APD算法也有望具有最佳的收敛速度求解随机鞍点问题，而没有随机原始对偶算法已在文献中开发。此外，研究将扩展到解决一类复合变分不等式（VI），其中包括一类鞍点问题作为特殊情况进行研究的最优方法的发展。这项研究提供了一些重要的见解一般VI问题的分解，以潜在地加速其解决方案。此外，理论分析的最佳收敛速度，最佳估计的对偶差距，特别是，依赖于初始点和鞍点之间的距离（或可行集的直径，如果它们是有界的），所有提出的算法将进行调查。该项目将研究和开发所提出的算法的回溯策略，以提高其实际性能。 新方法将被应用到几个图像重建和机器学习问题。在许多数据分析问题中，如图像重建、压缩感知和机器学习等，本文研究的一类确定性和随机鞍点问题以及变分不等式问题被认为是由非光滑泛函正则化的不适定反问题的框架。 该研究的成功将大大提高非光滑凸优化求解器的能力，在加速计算与良好的理论性能保证。因此，该项目有望大大提高许多新兴技术的适用性，如部分并行成像和动态多示踪剂PET。这些成像方法可以显著减少扫描时间并提高图像质量。然而，他们的临床应用受到阻碍，我们无法有效地解决大规模的不适定和病态逆图像重建问题。此外，随机APD算法的发展将大大提高学习能力。例如，这些最佳方法将使研究人员能够从大量数据集中构建高级的、特定于类别的特征检测器。这些新方法在不同学科的大规模数据分析问题中有着广泛的应用。因此，这项研究将有助于研究社区和行业的共同利益。研究期间开发的算法将在万维网上免费提供。PI的研究生将参与研究的各个方面，包括理论分析和算法的实际实现。这项研究将通过研讨会和课程开发向更多的研究生和高年级本科生开放。PI打算根据拟议的研究来教授课程。