Derivative-free optimization (DFO) using trust region methods is frequently used for machine learning applications, such as (hyper-)parameter optimization without the derivatives of objective functions known.   Inspired by the recent work in continuous-time minimizers, our work models the common trust region methods with the exploration-exploitation using a dynamical system coupling a pair of dynamical processes. While the first exploration process searches the minimum of the blackbox function through minimizing a time-evolving surrogation function, another exploitation process updates the surrogation function time-to-time using the points traversed by the exploration process. The efficiency of derivative-free optimization thus depends on ways the two processes couple. In this paper, we propose a novel dynamical system, namely \ThePrev---\underline{S}tochastic \underline{H}amiltonian \underline{E}xploration and \underline{E}xploitation, that surrogates the subregions of blackbox function using a time-evolving quadratic function, then explores and tracks the minimum of the quadratic functions using a fast-converging Hamiltonian system. The \ThePrev\ algorithm is later provided as a discrete-time numerical approximation to the system. To further accelerate optimization, we present \TheName\ that parallelizes multiple \ThePrev\ threads for concurrent exploration and exploitation. Experiment results based on a wide range of machine learning applications show that \TheName\ outperform a boarder range of derivative-free optimization algorithms with faster convergence speed under the same settings. Derivative-free optimization (DFO) techniques BID31 , such as Bayesian optimization algorithms BID43 BID24 , non-differentiable coordinate descent BID4 , natural gradient method BID12 BID14 , and natural evolution strategies BID41 , have been widely used for black-box function optimization. DFO techniques have been viewed as one of promising solutions, when the first-order/higher-order derivatives of the objective functions are not available. For example, to train large-scale machine learning models, parameter tuning is sometimes required. The problem to find the best parameters from the high-dimensional parameter space is frequently formalized as a black-box optimization problem, as the function that maps the specific parameter settings to the performance of models is not known BID11 BID9 BID48 BID21 . The evaluation of the black-box function is often computationally expensive, and there thus needs DFO algorithms to converge fast with global/local minimum guarantee.Backgrounds. To ensure the performance of DFO algorithms, a series of pioneering work has been done BID5 BID36 BID16 BID2 BID11 . Especially, Powell et al. (Powell, 1964; BID33 proposed Trust-Region methods that intends to "surrogate" the DFO solutions through exploring the minimum in the trust regions of the blackbox objective functions, where the trust regions are tightly approximated using model functions (e.g., quadratic functions or Gaussian process) via interpolation. Such two processes for exploration and exploitation are usually alternatively iterated, so as to pursue the global/local minimum BID2 . With exploration and exploitation BID7 , a wide range of algorithms have been proposed using trust region for DFO surrogation BID34 BID38 BID43 BID45 BID42 BID46 BID39 BID0 BID30 BID23 BID1 .Technical Challenges. Though trust region methods have been successfully used for derivative-free optimization for decades, the drawbacks of these methods are still significant:• The computational and storage complexity for (convex) surrogates is extremely high. To approximate the trust regions of blackbox functions, quadratic functions BID34 BID39 and Gaussian process BID43 BID46 BID23 are frequently used as (convex) surrogates. However, fitting the quadratic functions and Gaussian process through interpolation is quite time-consuming with high sample complexity. For example, using quadratic functions as surrogates (i.e., approximation to the second-order Taylor's expansion) needs to estimate the gradient and inverse Hessian matrix BID34 BID39 , where a large number of samples are required to avoid ill-conditioned inverse Hessian approximation; while the surrogate function in GP is nonconvex, which is even more sophisticated to optimize.• The convergence of trust region methods cannot be guaranteed for high-dimensional nonconvex DFO. Compared to the derivative-based algorithms such as stochastic gradient descent and accelerated gradient methods BID3 BID44 , the convergence of DFO algorithms usually are not theoretically guaranteed. Jamieson et al. BID16 provided the lower bound for algorithms based on boolean-based comparison of function evaluation. It shows that DFO algorithms can converge at Ω(1/ √ T ) rate in the best case (T refers to the total number of iterations), without assumptions on convexity and smoothness, even when the evaluation of black-box function is noisy.Our Intuitions. To tackle the technical challenges, we are motivated to study novel trust region methods with following properties 1. Low-complexity Quadratic Surrogates with Limited Memory. To lower the computational complexity, we propose to use quadratic functions with identity Hessian matrices as surrogates. Rather than incorporating all evaluated samples in quadratic form approximation, our algorithm only works with the most-recently evaluated sample points. In this way, the memory consumption required can be further reduced. However, the use of identity Hessian matrices for quadratic form loses the information about the distribution (e.g., Fisher information or covariance BID13 ) of evaluated sample points. 2. Fast Quadratic Exploration with Stochastic Hamiltonian Dynamical Systems. Though it is difficult to improve the convergence rate of the DFO algorithms in general nonconvex settings with less oracle calls (i.e., times of function evaluation), one can make the exploration over the quadratic trust region even faster. Note that exploration requires to cover a trust region rather than running on the fastest path (e.g., the gradient flow BID15 ) towards the minimum of trust region. In this case, there needs an exploration mechanism traversing the whole quadratic trust region in a fast manner and (asymptotically) approaching to the minimum. FIG0 illustrates the examples of exploration processes over the quadratic region via its gradient flows (i.e., gradient descent) or using Hamiltonian dynamics with gradients BID25 as well as their stochastic variants with explicit perturbation, all in the same length of time. It shows that the stochastic Hamiltonian dynamics (shown in FIG0 (d)) can well balance the needs of fast-approaching the minimum while sampling the quadratic region with its trajectories. Compared to the (stochastic) gradient flow, which leads to the convergence to the minimum in the fast manner, the stochastic Hamiltonian system are expected to well explore the quadratic trust region with the convergence kept. Inspired by theoretical convergence consequences of Hamiltonian dynamics with Quadratic form BID44 BID25 , we propose to use stochastic Hamiltonian dynamical system for exploring the quadratic surrogates. 3. Multiple Quadratic Trust Regions with Parallel Exploration-Exploitation. Instead of using one quadratic cone as the surrogate, our method constructs the trust regions using multiple quadratic surrogates, where every surrogate is centered by one sample point. In this way, the information of multiple sample points can be still preserved. Further, to enjoy the speedup of parallel computation, the proposed method can be accelerated through exploring the minimum from multiple trust regions (using multiple Hamiltonian dynamical sys- Our work is inspired by the recent progress in the continuous-time convex minimizers BID44 BID15 BID47 on convex functions, where the optimization algorithms are considered as the discrete-time numerical approximation to some (stochastic) ordinary differential equations (ODEs) or dynamics, such as Itô processes for SGD algorithms BID15 or Hamiltonian systems for Nesterov's accelerated SGD BID44 . We intend to first study the new ODE and dynamical system as a continuous-time DFO minimizer that addresses above three research issues. With the new ODE, we aim at proposing the discrete-time approximation as the algorithms for black-box optimization .Our Contributions. Specifically, we make following contributions. (1) To address the three technical challenges, a continuous-time minimizer for derivative-free optimization based on a Hamiltonian system coupling two processes for exploration and exploitation respectively. (2) Based on the proposed dynamical system, an algorithm, namely SHE 2 -Stochastic Hamiltonian Exploration and Exploitation, as a discrete-time version of the proposed dynamical system, as well as P-SHE 2 that parallelizes SHE 2 for acceleration. (3) With the proposed algorithms, a series of experiments to evaluate SHE 2 and P-SHE 2 using real-world applications. The two algorithms outperform a wide range of DFO algorithms with better convergence. To the best of our knowledge, this work is the first to use a Hamiltonian system with coupled process for DFO algorithm design and analysis . In this paper, we present SHE 2 and P-SHE 2 -two derivative-free optimization algorithms that leverage a Hamiltonian exploration and exploitation dynamical systems for black-box function optimization. Under mild condition SHE 2 algorithm behaves as a discrete-time approximation to a Nestereov's scheme ODE BID44 over the quadratic trust region of the blackbox function. Moreover, we propose P-SHE 2 to further accelerate the minimum search through parallelizing multiple SHE 2 -alike search threads with simple synchronization.Compared to the existing trust region methods, P-SHE 2 uses multiple quadratic trust regions with multiple (coupled) stochastic Hamiltonian dynamics to accelerate the exploration-exploitation processes, while avoiding the needs of Hessian matrix estimation for quadratic function approximation. Instead of interpolating sampled points in one quadratic function, P-SHE 2 defacto constructs one quadratic surrogate (with identity Hessian) for each sampled point and leverages parallel search threads with parallel black-box function evaluation to boost the performance. Experiment results show that P-SHE 2 can compete a wide range of DFO algorithms to minimize nonconvex benchmark functions, train supervised learning models via parameter optimization, and fine-tune deep neural networks via hyperparameter optimization. Here we provide a short discussion on the convergence rate of the algorithm SHE2. In the previous appendix we have demonstrated that the system (4) converges via two steps.Step 1 in Lemma 1 shows that the differential equation modeling Nesterov's accelerated gradient descent (see BID44 ) helps the process X(t) to "catch up" with the minimum point Y (t) on its path.Step 2 in Lemma 2 shows that when t → ∞ the noise term ζ(t) helps the process X(t) to reach local
a new derivative-free optimization algorithms derived from Nesterov's accelerated gradient methods and Hamiltonian dynamics
{"src": "scitldr-AIC_train", "paper_id": "rklEUjR5tm"}