Gradient Sampling Methods for Noisy Nonconvex Nonsmooth Optimization

Computational techniques for solving problems in image processing, statistical learning, robust control, distance geometry, and other areas require that large-scale unstructured optimization problems be solved. To obtain solutions that translate best into real-world settings, these problems should involve models of the real world that are as accurate as possible, which in a mathematical context means that the problems may need to involve a large number of decision variables and complicated formulas with features such as nonsmoothness. Thanks to the thriving field of mathematical optimization, there exist algorithmic methodologies for solving certain instances of problems of this type. However, contemporary methodologies also have limitations that preclude their use for solving complex problems robustly and efficiently. for example, it may be that with respect to an objective that is optimized, only the consequences of a certain set of decisions can be estimated (in terms of a cost, error, or other measure). This can occur, when the value can only be determined through a computer simulation or as a statistical prediction over only partially observed data. Such a context demands that contemporary approaches be extended so that they can intelligently handle noisy or stochastic (i.e., randomized) estimates of the value of decisions. This project aims to design such algorithmic extensions for solving important classes of optimization problems arising in these prevalent and challenging application areas. This project will involve the design, analysis, and implementation of gradient-sampling-based algorithms for solving locally Lipschitz optimization problems, specifically those that have nonconvex and nonsmooth objective functions. The main scope of the project is to extend contemporary gradient-sampling-based algorithms for settings when function and derivative evaluations are corrupted by computational and/or stochastic noise. In settings with such noise, fundamental properties on which gradient-sampling methods rely for their convergence guarantees break down, meaning that these fundamental properties need to be revisited and enhanced for settings with computational and/or stochastic noise. These, in turn, will necessitate careful redesigns of complete algorithmic methodologies along with their corresponding convergence theories. The real-world impact of the project will be enhanced by the fact that it will translate into enhancements to the state-of-the-art software developed by the principal investigator. 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.