Black-box optimization of noisy functions with unknown smoothness
We study the problem of black-box optimization of a function f of any dimension, given function evaluations perturbed by noise. The function is assumed to be locally smooth around one of its global optima, but this smoothness is unknown. Our contribution is an adaptive optimization algorithm, POO or parallel optimistic optimization, that is able to deal with this setting. POO performs almost as well as the best known algorithms requiring the knowledge of the smoothness. Furthermore, POO works for a larger class of functions than what was previously considered, especially for functions that are difficult to optimize, in a very precise sense. We provide a finite-time analysis of POO's performance, which shows that its error after n evaluations is at most a factor of √ ln n away from the error of the best known optimization algorithms using the knowledge of the smoothness.
The problem of bandit optimization of a noisy function without an explicit knowledge of smoothness is considered.The paper introduces a new variant ofthe existing HOO algorithm to solve this problem. The main idea is that to run Ninstances HOO in parallel for different choice of smoothness and then to choose the instance with the highest average reward.Theoretical guaranteesin the form of simple expected regret bound has been provided. The paper is in most part well-written and easy to follow.Also the idea of using multiple instances of HOOwith different smoothness parameters seems a promising idea to deal with thecase of unknown smoothness. However I am not sure the currentversion of POO really addresses the problem of unknown smoothness in online optimization. The main reason is thatthe current version of proposed algorithm still needs to receivesome upper bounds of the smoothness as the input. Also regret bounds strongly depend on the value of these upper bounds(both the rate and constant). The paper suggests to deal with the problem of unknown \rho_\max and \nu_\max by gradually increasing thevalue of smoothness parameters until they becomelarger than \rho^* and \nu^*. In particular the paper suggests to increase \rho_\max and \nu_\max such that the factor D_\max \nu_\max D_\max increases with the slow (logarithmic) rate which keeps the rate of regretintact (up to a logarithmic factor). The problem with this approach is 1- it leads to an extra constant regret term with double exponential dependency on 1/log(1/\rho).The term 1/\log(1/\rho ) approximately equals to 1/(1-\rho) for\rho s close to 1 which makes this constant regret termhuge andthe whole regret bound vacuous. 2- the idea of increasing \rho and \nu, combined with doubling trick, could be already applied to theoriginal HOO algorithm without any need for parallelization. In fact I think by using doubling trick with increasing \rho and \nu one could achieve a better regret than what we can get with POO (the constant term would be smaller and the dependency on log(n) would be quadratic instead of cubicin the case of POO with increasing \rho_{\max}). Therefore I am not sure the new algorithm is the best way to deal with the problem of unknown smoothness since the standard methods (e.g., using doubling trick with increasing parameters) seems to provides us with a better solution.