First-Order Methods for Large Scale Convex Optimization

Book excerpt: The revolution of storage technology in the past few decades made it possible to gather tremendous amount of data anywhere from demand and sales records to web user behavior, customer ratings, software logs and patient data in healthcare. Recognizing patterns and discovering knowledge from large amount of data becomes more and more important, and has attracted significant attention in operations research (OR), statistics and computer science field. Mathematical programming is an essential tool within these fields, and especially for data mining and machine learning, and it plays a significant role for data-driven predictions/decisions and pattern recognition.The major challenge while solving those large-scale optimization problems is to process large data sets within practically tolerable run-times. This is where the advantages of first-order algorithms becomes clearly apparent. These methods only use gradient information, and are particularly good at computing medium accuracy solutions. In contrast, interior point method computations that exploit second-order information quickly become intractable, even for moderate-size problems, since the complexity of each factorization of a n n matrix in interior point methods is O(n^3). The memory required for second-order methods could also be an issue in practice for problems with dense data matrices due to limited RAM. Another benefit of using first-order methods is that one can exploit additional structural information of the problem to further improve the efficiency of these algorithms.In this dissertation, we studied convex regression, and multi-agent consensus optimization problems; and developed new fast first-order iterative algorithms to efficiently compute -optimal and -feasible solutions to these large-scale optimization problems in parallel, distributed, or asynchronous computation settings while carefully managing memory usage. The proposed algorithms are able to take advantage of the structural information of the specific problems we considered in this dissertation, and have strong capability to deal with large-scale problems. Our numerical results showed the advantages of our proposed methods over other traditional methods in terms of speed, memory usage, and especially communication requirements for distributed methods.