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

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

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.