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 derivativefree optimization thus depends on how the two processes couple. In this paper, we propose a novel dynamical system, namely SHE 2 -Stochastic Hamiltonian Exploration and Exploitation, 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 SHE 2 algorithm is later provided as a discrete-time numerical approximation to the system. To further accelerate optimization, we present P-SHE 2 that parallelizes multiple SHE 2 threads for concurrent exploration and exploitation. Experiment results based on a wide range of machine learning applications show that P-SHE 2 outperform a boarder range of derivative-free optimization algorithms with faster convergence speed under the same settings.
This paper suggests a continuous-time framework consisting of two coupled processes in order to perform derivative-free optimization. The first process optimizes a surrogate function, while the second process updates the surrogate function. This continuous-time process is then discretized in order to be run on various machine learning datasets. Overall, I think this is an interesting idea as competing methods do have high computational complexity costs. However, I’m not satisfied with the current state of the paper that does not properly discuss notions of complexity of their own method compared to existing methods.
1) “The computational and storage complexity for (convex) surrogates is extremely high.” The discussion in this paragraph is too superficial and not precise enough.
a) First of all, the authors only discuss quadratic models but one can of course use linear models as well, see two references below (including work by Powell referenced there):
Chapter 9 in Nocedal, J., & Wright, S. J. (2006). Numerical optimization 2nd.
Conn, A. R., Scheinberg, K., & Vicente, L. N. (2009). Global convergence of general derivative-free trust-region algorithms to first-and second-order critical points. SIAM Journal on Optimization, 20(1), 387-415.
I think this discussion should also be more precise, the authors claim the cost is extremely high but I would really expect a discussion comparing the complexity of this method with the complexity of their own approach. As discussed in Nocedal (reference above) the cost of each iteration with a linear model is O(n^3) instead of O(n^4) where n is the number of interpolation points. Perhaps this can also be improved with more recent developments, the authors should do a more thorough literature review.
b) What is the complexity of the methods cited in the paper that rely on Gaussian processes?
(including (Wu et al., 2017) and mini-batch (Lyu et al., 2018)).
2) “The convergence of trust region methods cannot be guaranteed for high-dimensional nonconvex DFO”
Two remarks: a) This statement is incorrect as there are global convergence guarantees for derivative-free trust-region algorithms, see e.g.
Conn, A. R., Scheinberg, K., & Vicente, L. N. (2009). Global convergence of general derivative-free trust-region algorithms to first-and second-order critical points. SIAM Journal on Optimization, 20(1), 387-415.
In chapter 10, you will find global convergence guarantees for both first-order and second-order critical points.
b) The authors seem to emphasize high-dimensional problems although the convergence guarantees above still apply. For high-order models, the dimension does have an effect, please elaborate on what specific comment you would like to make. Finally, can you comment on whether the lower bounds derived by Jamieson mentioned depend on the dimension.
3) Quadratic loss function
The method developed by the authors rely on the use of a quadratic loss function. Can you comment on generalizing the results derived in the paper to more general loss functions? It seems that the computational complexity wouldn’t increase as much as existing DFO methods. Again, I think it would be interesting to give a more in-depth discussion of the complexity of your approach.
4) Convergence rate
The authors used a perturbed variant of the second-order ODE defined in Su et al. 2014. The noise added to the ODE implies that the analysis derived in Su et al. 2014 does not apply as is. In order to deal with the noise the authors show that unbiased noise does not affect the asymptotic convergence. I think the authors could get strong non-asymptotic convergence results. In a nutshell, one could use tools from Ito calculus in order to bound the effect of the noise in the derivative of the Hamiltonian used in Lemma 1. See following references:
Li, Q., Tai, C., et al. (2015). Stochastic modified equations and adaptive stochastic gradient algorithms. arXiv preprint arXiv:1511.06251.
Krichene, W., Bayen, A., and Bartlett, P. L. (2015). Accelerated mirror descent in continuous
and discrete time. In Advances in neural information processing systems, pages 2845–2853.
Of course, the above works rely on the use of derivatives but as mentioned earlier, one should be able to rely on existing DFO results to prove convergence. If you check Chapter 2 in the book of Conn et al. (see reference above), you will see that linear interpolation schemes already offer some simple bounds on the distance between the true gradient of the gradient of the model (assuming Lipschitz continuity and differentiability).
5) Noise
“The noise would help the system escape from an unstable stationary point in even shorter time”
Please add a relevant citation. For isotropic noise, see
Ge, R., Huang, F., Jin, C., and Yuan, Y. Escaping from saddle points-online stochastic gradient for tensor decomposition.
Jin, C., Netrapalli, P., and Jordan, M. I. Accelerated gradient descent escapes saddle points faster than gradient descent. arXiv preprint arXiv:1711.10456,
6) Figure 2
Instead of having 2 separate plots for iteration numbers and time per iteration, why don’t you combine them to show the loss vs time. This would make it easier for the reader to see the combined effect.
7) Empirical evaluation
a) There are not enough details provided to be able to reproduce the experiments. Reporting the range of the hyperparameters (Table 2 in the appendix) is not enough. How did you select the hyperparameters for each method? Especially step-size and batch-size which are critical for the performance of most algorithms. 
b) I have to admit that I am not extremely familiar with common experimental evaluations used for derivative-free methods but the datasets used in the paper seem to be rather small. Can you please justify the choice of these datasets, perhaps citing other recent papers that use similar datasets?
8) Connection to existing solutions
The text is quite unclear but the authors seem to claim they establish a rigorous connection between their approach and particle swarm (“In terms of contribution, our research made as yet an rigorous analysis for Particle Swarm”). This however is not **rigorously** established and needs further explanation. The reference cited in the text (Kennedy 2011) does not appear to make any connection between particle swarm and accelerated gradient descent. Please elaborate.
9) SGD results
Why are the results for SGD only reported in Table 1 and not in the figure? Some results for SGD are better than for P-SHE2 so why are you bolding the numbers for P-SHE2?
It also seem surprising that SGD would achieve better results than the accelerated SGD method. What are the possible explanations?
10) Minor comments
- Corollaries 1 and 2 should probably be named as theorems. They are not derived from any other theorem in the paper. They are also not Corollaries in Su et al. 2014.
- Corollary 2 uses both X and Z.
- Equation 5, the last equation with \dot{V}(t): there is a dot missing on top of the first X(t)
“SHE2 should enjoy the same convergence rate Ω(1/T) without addressing any further assumptions” => What do you mean by “should”?
- There are **many** typos in the text!! e.g. “the the”, “is to used”, “convergeable”,... please have someone else proofread your submission.