New Sampling and Descent Paradigms for Stochastic Black-Box Optimization
Abstract
Approved for Public ReleaseComputational systems in engineering, applied sciences, and artificial intelligence are becoming increasingly complex and sophisticated due to advances in mathematical modeling and the widespread availability of high-performance computing. Most of these complex systems depend on critical parameters for their design, control, or knowledge. In many applications, theirsimulation results in computationally expensive runs that can be seen as the outcome of a black-box function. The code sophistication and/or the presence of noise or non-smoothness prevents the use of automatic differentiation tools to access the derivatives of such black-box functions.Derivative-Free Optimization (DFO) is a field of mathematical optimization concerned with the optimization of functions without the knowledge of information beyond the evaluation of its values. DFO is applied when derivatives of the functions being optimized are unavailable, available at a high computational cost, or subject to noise. DFO methods have emerged as the single viable option to discover optimal values of critical parameters that lead to optimal system performance. DFO is thus extensivelyused in the engineering and applied sciences community due to its practical and simple application, and it has recently become a critical tool to machine learning researchers and practitioners, in particular for hyperparameter tuning. DFO is remarkably challenging because one optimizes without information about the variation of the functions, known to be critical to accelerate numerical algorithms. Additional challenges arise from the fact that the function values may be contaminated with noise of different origins and levels, and the underlying function landscape may be non-smooth.This proposal aims to develop state-of-the-art stochastic methodologies and rigorous theoretical analyses to expand the knowledge of DFO in many innovative directions. In particular, we introduce a new tail bound conditionfor function estimation which allows for a leap improvement in the required function sample sizing. A first paradigm is introduced from the interplay among the estimation of the function noise moments, the order of the decrease imposed in an algorithm, and the adaptive sample size used for estimation, leading to a dynamic update of all three quantities combined. A second paradigm is to combine sequential and adaptive sampling in each iteration of an algorithm, attempting to accept new points before the adaptive budgets are exhausted. Although we focus on the non-smooth case, we also aim at bringing such advances to the smooth context. The proposal also includes the development of non-monotone stochastic DFO methods, for which no progress has been made even in the derivative-based case.Other more ambitious goals include the development of convergence rates for non-smooth (totally black-box) DFO, both deterministic and stochastic, and leveraging sample sizing in all literature stochastic DFO approaches when using our tail-bound condition. Finally, we think that DFO can be instrumental in defense once framed in a bilevel optimization framework (where the lower level models an adversary response), and we would like to combine our joint expertise on bilevel and DFO to contribute to naval defense technology.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412656
Entities
People
- Luis Nunes Vicente
Organizations
- Lehigh University
- Office of Naval Research
- United States Navy