CAREER: Structure, Complexity, and Conditioning in Nonsmooth Optimization

University Of Washington, Seattle WA

Investigators

Abstract

Recent years have seen an unprecedented growth of large data sets in various high-impact fields, such as seismology, data science, information technology, and environmental science. The task of extracting useful information from such data sets typically leads to solving a large-scale optimization problem. The sheer size of such problems poses great challenges for optimization specialists. The investigator aims to advance the reach of large-scale optimization in such settings, with vital applications throughout science and engineering. The resulting methodology and algorithms create a systematic approach to discover trends and phenomena underlying the observed data, and lead to a well-grounded mechanism for making predictions about unobserved data. The project lies firmly at the interface between theory and computation. Therefore, an effective mix of numerical experimentation, teaching, and discovery is central to the proposal. Graduate students participate in the work of the project. The investigator's strategy rests on three interrelated pillars: structure, computational complexity, and conditioning in nonsmooth optimization. Efficiency of numerical methods is best judged through rigorous rates of convergence. Convergence guarantees of an algorithm become much more potent, however, if they match best possible guarantees that any algorithm can have within the problem class. The search for such "optimal methods" underpins computational complexity. Measures of the problem's conditioning -- an indication of its difficulty -- play a central role in the subject and are intimately tied to stability of the underlying problem. The theory and algorithms, moreover, benefit greatly from exploiting rich underlying structure prevalent in applications, such as separation of smooth and simple nonsmooth functional components, smooth conjugate representations, saddle-point reformulations, etc. Convex optimization techniques and variational analytic insight guide the investigator's approach. Pervasive large-scale problems in data science and engineering can directly benefit from this work. The project integrates research and teaching in all aspects. Graduate students participate in the work of the project.