Bundle Level Type Gradient Sliding Methods for Large Scale Convex Optimization

这项研究的目标是开发新的算法，以解决涉及分析数据的巨大数据集应用程序的计算挑战。这些包括，例如，图像处理，数据挖掘，生物信息学和统计学习。本研究开发的算法将能够显著减少所需的昂贵计算次数，从而可以应用于从大量数据集中有效地提取有用信息。该研究具有推进大规模问题算法的潜力，并大大提高了许多新兴技术的适用性。一个例子是利用部分平行磁共振成像获得的图像的有效重建。新方法的发展也将使研究人员能够建立多层次的复杂网络，以便在许多应用中更好地学习和预测。该项目还通过本科生和研究生培训、课程开发、研讨会和会议演讲来支持教育。本研究旨在发展一类新的加速束水平型梯度滑动方法及其相关理论，用于求解大规模复合凸优化问题和泛函约束凸优化问题。这类新算法有望分别实现每个组件的最优迭代复杂度，但将更加通用，能够以不同程度的平滑度处理函数的组合。该算法具有有效利用历史信息的优点，具有可扩展的方案来解决所涉及的子问题，为梯度滑动提供实际的终止条件，并且不限制步长或要求成本函数中的Lipschitz常数信息。此外，这些技术对功能约束问题的发展将显著降低迭代复杂性，提高现有技术对光滑或弱光滑函数的实际性能。此外，复合梯度滑动和加速方法在不增加迭代复杂度的情况下减少了梯度求值的次数，同时保持了复合凸问题现有方法的良好性质。将分析所有新算法的迭代复杂性，并通过数值模拟以及成像和机器学习中的实际应用验证其实际性能。

The goal of this research is to develop novel algorithms for tackling the computational challenges involved in analyzing data for applications with huge data sets. These include, for example, image processing, data mining, bioinformatics, and statistical learning. The algorithms to be developed in this research will be able to significantly reduce the number of required expensive computations, so that they can be applied to efficiently extract useful information from massive data sets. The research has the potential to advance the algorithms for large scale problems, and greatly increase the applicability for many emerging technologies. An example is the efficient reconstruction of images acquired using partial parallel magnetic resonance imaging. The development of the new methods will also enable researchers to build multi-level complex networks for better learning and prediction in many applications. This project also supports education through undergraduate and graduate student training, course development, and seminar and conference presentations. This research intends to develop a novel class of accelerated bundle level type gradient sliding methods and related theories for solving large scale composite convex optimization problems and functional constrained convex optimization problems. This new class of algorithms is expected to achieve optimal iteration complexity for each component separately, but will be more general and able to handle the composition of functions with various degrees of smoothness. The algorithms offer the advantages of effectively using historical information, having a scalable scheme for solving the involved sub-problem, providing practical termination conditions for the gradient sliding, and do not impose restrictions on step sizes or require the information on the Lipschitz constants in the cost functions. Moreover, the development of these techniques for the functionally constrained problems will significantly reduce the iteration complexities and improve the practical performance of the existing techniques for functions that are smooth or weakly smooth. Further, the composite gradient sliding and accelerated approach reduces the number of gradient evaluations without increasing the iteration complexity, while maintaining existing good properties of the approaches for the composite convex problems. The iteration complexity of all the new algorithms will be analyzed, and the practical performance will be validated through numerical simulations and for practical applications arising from imaging and machine learning.