Exploiting Smooth Substructure in Non-Smooth Stochastic Optimization

Recent years have seen an unprecedented growth of the use of large data sets in various high impact fields, such as signal processing, imaging, and artificial intelligence. The task of extracting useful information from vast amounts of data typically leads to solving large-scale optimization problems. The size of such problems poses a variety of challenges for computation and is the bottleneck for further progress in applications. The investigator aims to advance techniques of large-scale optimization, with applications throughout science and engineering. The resulting algorithms will enable discovery of trends and patterns in the observed data and will enable accurate predictions about unobserved data. The technical aspects of the project combine elements from a variety of mathematical and applied disciplines, and an effective mix of numerical experimentation, teaching, and discovery is central to the proposal. Graduate students and postdocs will participate in all aspects of the project.

Statistical estimation, signal processing, and learning from data rely on solving challenging optimization problems that are large-scale, stochastic, nonsmooth, and often nonconvex. Despite such irregularity, the domains of typical optimization problems decompose into “active manifolds”, which common algorithms “identify” in finite time, thereby opening the door to second-order acceleration strategies. This project studies the stochastic subgradient method and its common variants, which power modern large-scale optimization, and its numerous applications in data science and engineering. The goal of the project is to investigate how the performance of influential stochastic algorithms benefit from active manifolds and to develop novel algorithms that exploit this structure. The strategy for achieving this goal will be based on a recently discovered family of regularity conditions---originating in stratification theory and semi-algebraic geometry---that have been shown to hold along active manifolds in concrete circumstances. Utilizing such regularity conditions for active manifolds, the investigator will develop new efficiency guarantees for the subgradient method, show that the algorithm converges only to local minimizers while bypassing all extraneous saddle points, and establish the asymptotic distribution of the stochastic gradient iterates. In parallel, the investigator will explore the use of noise injection to learn the tangent spaces to the active manifold in order to accelerate the algorithm. This approach is highly interdisciplinary, relying on techniques from nonsmooth optimization, statistics, probability, and semialgebraic geometry.

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.

Award Number: 2552323
Principal Investigator: Dmitriy Drusvyatskiy
Funds Obligated: $181,124
State: CA