Bundle Level Type Gradient Sliding Methods for Large Scale Convex Optimization

University Of Florida, Gainesville FL

Investigators

Abstract

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.