Direct search for stochastic optimization in random subspaces with zeroth-, first-, and second-order convergence and expected complexity

Abstract

Abstract Stochastic directional direct-search (SDDS) algorithms were recently introduced as an extension to stochastically noisy objectives of a broad class of algorithms including the well-known mesh adaptive direct-search (MADS) algorithms developed for the minimization of deterministic functions in a blackbox optimization framework. However, since SDDS methods explore the variable space via directions selected at each iteration from search sets of cardinality depending on the problem dimension, their performance quickly deteriorates as the dimension gets larger. This work introduces StoDARS, a framework for large-scale stochastic blackbox optimization that not only is both an algorithmic and theoretical extension of the SDDS framework but also extends to noisy objectives a recent framework of direct-search algorithms in reduced spaces (DARS). Unlike SDDS, StoDARS achieves scalability by using m search directions generated in random subspaces defined through the columns of Johnson–Lindenstrauss transforms (JLTs) obtained from Haar-distributed orthogonal matrices, where the user-determined parameter m is independent of the dimension of the problem. For theoretical needs, the quality of these subspaces and the accuracy of random estimates used by the algorithm are required to hold with sufficiently large, but fixed, probabilities. In particular, the almost sure convergence to zero of the sequence of the algorithm’s stepsize parameters, referred to as zeroth-order convergence, is demonstrated by using the theory of stochastic processes. Then, leveraging an existing supermartingale-based framework, the expected complexity of StoDARS is proved to be similar to that of SDDS and other stochastic full-space methods up to constants, when the objective function is continuously differentiable. By dropping the latter assumption, the ability of StoDARS to generate a dense set of subspace directions by means of the aforementioned JLTs allows its analysis to be the first of a JLT-based subspace algorithm establishing convergence to Clarke stationary points with probability one, unlike prior works on subspace methods where the use of gradient is inevitable. Moreover, the analysis of the second-order behavior of MADS using a second-order-like extension of the Rademacher’s theorem-based definition of the Clarke subdifferential (so-called generalized Hessian) is extended to the StoDARS framework, making it the first in a stochastic direct-search setting, to the best of our knowledge.