Lipschitz optimization with contemporary structure

Modern Data Science, with its emphasis on "Big Data", presents a challenge for more traditional mathematical disciplines like Optimization. The mathematical techniques to be developed as part of this project aim to transform the design and analysis of algorithms across Optimization, bridging from current scholarship to vital computation in Data Science, robust control engineering and beyond. Graduate students will be central to this research, working in collaboration with the principal investigator on methodology and computation as well as preparing journal articles and conference presentations. This research will be incorporated into graduate coursework, made broadly accessible to the scientific community through targeted expository articles, involve collaboration across diverse fields, and be disseminated in international lectures to audiences across science and engineering. This project involves a multi-pronged approach to the fresh challenges posed by Big Data in contemporary optimization, relying heavily on the underlying problems' rich inherent mathematical structure. First, relying on the semi-algebraic nature of all computer-representable objectives, the project will extend classical Lojasiewicz-type rescaling techniques to design and analyze the complexity of first-order and active-set optimization algorithms in hyperbolic and other non-Euclidean and infinite-dimensional settings. Such nonlinear spaces model diverse data, ranging from mass distributions separated by Wasserstein earth-mover distances, to phylogenetic trees in Computational Biology. Secondly, the principal invesigator will analyze condition measures of nonsmoothness and nonconvexity in Lipschitz optimization, and their impact on popular computational heuristics: such heuristics apparently converge nearly linearly and yet currently lack rigorous complexity guarantees. To this end, the project pursues a shift from point- to path-based analysis, and to distributional derivatives. Thirdly, informed by these condition measures, the project envisages reliable new algorithms, fast and intuitive enough to satisfy practitioners in Machine Learning, High-Dimensional Statistics, and Imaging Science, and also (at more moderate scale) in Systems Control and beyond. The project thus pursues a transformation of the modern continuous optimization toolkit, with potential impact across the computational sciences. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.