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.
