An Invariant Information Geometric Method for High-dimensional Online Optimization

Thank you for your detailed and insightful review, which provides a second perspective on our work. For a better discussion, we would like to address your concerns in turn.

Responses to Questions :

• (A1) We admit that the theoretical guarantees are weak compared with some existing work on online optimization , and are considering changing the theorems to propositions. However, comparing with other first-order method in the black-box setting with arbitrary objective which is too hard for a regret or convergence bound, our results match the theoretical strength. Also, we perceive our work as a clear theoretical framework plus a derived powerful algorithms, of which we are inclined to focus on the latter.

• (A2) We'll definitely consider your suggestion! Putting the limitation and future directions in the last section will give more room for an overall discussion. Currently, it is in Section 3.3 to follow with theoretical comparisons of SynCMA. As the same reason mentioned in (A1), in black-box objective, people usually tend to focus on a practical method with comparison and empirical study. And we decide to follow this preference.

• (A3 & A4) Yes, you are right, we'll consider change the notion of these propositions.

• (A5) Similar to the reasons given in (A1) and (A2), too little prior knowledge and the current focus of the broad zero-order optimization community (including ES and BO) lead us to weight more the practical part, as shown in Section 3.

• (A6) Yes, the Fisher metric and the induced natural gradient flow are invariant, but a practical algorithm may introduce a first-order error for each step when discretizing such an invariant flow. These first-order errors can be relatively large for robust objectives such as the Discus function and neural networks, and can cumulate exponentially for typical objectives. In addition to full invariance, our novelty also consists in the first full incorporation of historical information (ref. A7) and fewer hyper-parameters compared to previous methods.

• (A7) To the best of our knowledge, historical data is widely used in online optimization, but there is no general standard. Different specific settings may have different recognition on the use of historical data. For example, in convex optimization, Nesterov momentum is proven to be optimal. And in evolution strategies, all previous methods based on Gaussian do not incorporate historical data in mean update (or they claim that it is unstable to do so as in the paper of the compared method TR-CMA-ES[1]). This is a waste and we fix it.

[1]Abdolmaleki, A., Price, B., Lau, N., Reis, L. P., & Neumann, G. (2017, July). Deriving and improving cma-es with information geometric trust regions. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 657-664). https://dl.acm.org/doi/abs/10.1145/3071178.3071252

Thank you for your detailed review! We understand your concerns from an evolutionary perspective. Indeed, our work is built on the foundation of ES. Before we address your concerns about the method and code, a statement about the motivation for our work may help us understand each other better:

We agree with you on the potentially underappreciated reality of evolutionary strategy. Bayesian optimization, on the other hand, is gaining more recognition while dealing with black-box function optimization problems. To this end, we want to systematically develop methods that are competitive with state-of-the-art Bayesian optimization. All choices of criteria, such as natural axis instead of logarithmic axis and Mujoco tasks instead of COCO framework/BBOB testbeds, are made to meet the convenient setting in Bayesian optimization and the general online optimization community.

Response to weaknesses:

• (A1 to 'efficiency of ES') As far as we know, in the context of black-box optimization complexity, which serves as a lower bound, ES is optimal under some specific settings, such as convex or OneMax problems. But in a general setting, we do not find any material proving the optimality of ES. We would be really grateful if you could offer us some supporting work in the general setting!

On the empirical level, however, Bayesian optimization usually outperforms ES in terms of sampling efficiency, as shown in experiments on Mujoco and other non-synthetic tasks. However, its computational complexity can grow exponentially with increasing dimension.

• (A2 to 'IGO is built around invariance') On the one hand, a general first order error may cumulate exponentially in rugged task. On the other hand, under limited resources, a over small step size in high dimension may fail to offer competitive result. The room for a fully invariant optimizer may exist thereby.

• (A3 to 'Section 2') Please refer first to the above statement, as Section 2 mainly serves as a link to the communities outside ES. A systematic framework for incorporating historical information synchronously and invariably for all parameters is offered, which we consider to be one of our novelties (in the content of Gaussian, there is no algorithm that stably incorporates historical information in the mean).

• (A4 to 'No external learning rate') We denote the self-evolved term $\sigma$ as external learning rate, its initial value has to be tuned. SynCMA, on the other hand, does not have this parameter. In short, the only coefficient that has to be tuned in SynCMA is $\lambda_0$, of which the corresponding ablation study was executed in Section 4.4. In all other optimizers, coefficients that serve as the similar role as $\lambda_0$ are used as well.

• (A5 to 'Experimental results') The full plots showing the time evolution of performance are offered in Appendix Section B due to page limit. Also, one may refer to the statement above of choosing criteria in Bayesian optimization and the general online optimization community. The 'Near Global Optimum Performance' is illustrated in the caption of Table 1 as 'achieve value better than 0.5'.

• (A6 to 'Code on Rosenbrock') We really appreciate your detail review! First, by deleting the '*2' in line 78 of SynCMA.py and running with argument $\lambda_0 = 0$, Rosenbrock and other functions are successfully optimized to reach the optimum from 10d to 128d. We can explain these two modifications by claims in our paper : (1) In Section 4.4, we state an observation that lower dimension and simpler structure empirically calls for smaller $\lambda_0$. (2) In Appendix Section B, we state that the value of $\eta_c$ is twice of the corresponding parameter in CMA-ES as the compared CMA-ES is copied from a public github repository that uses several tricks. As you point out, these tricks may lead to an unstable behavior, we may just use the same value to eliminate the instability from aligning with the influence of these tricks.

Thank you for your detailed and insightful review, which provides a second perspective on our work. For a better discussion, we would like to address the weaknesses and questions one by one.

Responses to Weaknesses:

• (A1 to 'Online Optimization') We agree with you that the paper solves a black-box optimization problem. However, to explicitly compare with Bayesian optimization and to hint the potential application to first-order online optimization problem as discussed below Eq.(5), we adapt this name.

• (A2 to 'Fully Invariance')
  We put the evaluation of the goodness to be fully invariant in the comparison between TR-CMA-ES of the ill-scaled function Discus below Fig.1. We also realize from your review that IGO-ML is indeed invariant and we would mention it in the revised version. However, since IGO-ML itself is not a popular algorithm and it coincides with IGO algorithm for exponential family, the empirical comparison with CMA-ES should be sufficient.

• (A3 to [1]) Historical information is incorporated in several optimizers such as CMA-ES and VD-CMA[1], but none of them stably incorporate for mean update when parameterized with Gaussian. Moreover, VD-CMA is not invariant as it starts from the parameterization of (m, C) and relies on parameter-dependent settings such as $C = D(I + vv^T)D$.

[1] Youhei Akimoto, Anne Auger, and Nikolaus Hansen. 2014. Comparison-based natural gradient optimization in high dimension. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14). Association for Computing Machinery, New York, NY, USA, 373–380. https://doi.org/10.1145/2576768.2598258

• (A4 to '$\sigma$ or $\sigma^2$') We agree that we should follow the $\sigma^2$ formulation. However, since the optimizers such as CMA-ES are completely copied from public repositories, and the modifications of SynCMA only appear in the update_distribution function (except for some coefficients that are unique to SynCMA), the correctness of the experimental setup can be verified by anyone interested in it.

• (A5 to 'external learning rate') We denote tuning $\sigma$ to its initial value, as optimizers are usually sensitive to it. SynCMA, on the other hand, does not have this parameter. In short, the only coefficient that needs to be tuned in SynCMA is $\lambda_0$, where the corresponding ablation study has been performed. All other optimizers also use coefficients that play a similar role to $\lambda_0$.

• (A6 to 'Initial setting') It is our carelessness not to include the initial setting in the paper, although one can still convince oneself as in A4. The initial mean is 0, the initial covariance variance is $\sigma_{t = 0}I$ for all Gaussian-based optimizers, where $\sigma_{t = 0}$ is the initial value of $\sigma$.

• (A7 to 'Hyperparameter setting') We describe the hyperparameter setting for SynCMA at the beginning of Section B of the Appendix. In short, we set all similar or shared coefficients to be the same as in CMA-ES.

Responses to questions:

• (Q1) : First, since we mostly aim at comparison with Bayesian optimization, criteria in online optimization such as natural axis and a threshold around 0.1 are used. Second, as we discussed in the limitation part of Section 3.2, fixed and untuned parameters $\eta_m, \eta_c, \lambda_0$ make SynCMA overshoot near the optimum. Therefore, we do not use the COCO framework for comparison.

• (Q2) : As described in Section B of the Appendix, we copied existing approaches from public repositories that aim to provide competitive implementations.