Maximum Noise Level as Third Optimality Criterion in Black-box Optimization Problem

Dear Reviewer ubQW,

Thank you for your feedback. The specific comments are addressed below:

Throughout the paper, the authors claim to be the first paper taking into account biases of oracles. This is simply incorrect…

With all due respect, we disagree with your comment that we claim to be the first to account for bias in the oracle. For example, on line 189 we say that Assumption 2.3 is standard (not new). Moreover, on line 437 we say that in [1] we considered a deterministic concept of noise. However, we agree that we missed some references, including [2-3], which show that the summands in Theorem 2.6 (accumulation of inaccuracy due to bias) appear to be unimprovable. Furthermore, we would like to draw the Reviewer's attention to the originality of our paper: we emphasize the importance of considering the three optimality criteria together for gradient-free algorithms. In particular, through the maximal noise level, we can control the error floor (asymptote) to which we want to converge. Theorem 3.1 shows a rather surprising result, namely the maximum noise level can be improved by overbatching (after a threshold of $4d\kappa$, the maximum noise level depends on both the batch size $B$ and the smoothness order $\beta$). A more prominent example is Remark 3.3 because of the deterministic nature of the adversarial noise (smoothness order affects the improvement - this is a very non-trivial and novel result). In the practical part of our work (experiments), we confirm the importance of considering the presence of inaccuracy in the algorithm (by tuning the algorithm parameters).

Moreover, other topics which are touched upon in this work are missing the key citations, and instead cite only very previous works by a small subset of researchers. Some examples…

Thank you for drawing our attention to this issue, of course we will expand the Related Work section.

he writing style in the intro is rather vague. For example, "some companies, due to secrecy, can’t hand over all the information". What information? How does this relate to the exactness of a function-value oracle in optimization?

We highlighted this example as another motivation in the search for maximum noise level. Inter-company information (in the context of optimization), for example, can be function values or a gradient vector. In particular, this problem is addressed in federated learning, by increasing the number of local iterations. We emphasize, however, on an alternative approach - biased oracle.

Some of the writing of the technical parts is incomprehensible…

In Definition 1.3, we stated that $\xi_1$ and $\xi_2$ are stochastic noise that satisfies the following conditions: 1) $\xi_1 \neq \xi_2$; 2) bounded second moment: $\mathbb{E} [\xi_1^2] \leq \Delta^2$ , $\mathbb{E} [\xi_2^2] \leq \Delta^2$; 3) independence from $e \in S^d(1)$ and $r$ is a random value uniformly distributed on the interval [-1,1]. Nevertheless, we thank you for drawing our attention to the double notation of $r$. We will change the notation.

In addition to the main point that I made about the lack of novelty…

Indeed, by concurrency we have achieved an optimal estimate on the iteration complexity ($B = 4d\kappa$), but at first glance it seems unreasonable to take $B > 4d\kappa$. In our work, we show that when $B > 4d\kappa$ the maximum noise level takes advantage of the increased smoothness (the higher the smoothness order - the higher the maximum noise level - the more accurately the algorithm converges).

After Theorem 2.6, the authors write that "the third summand does not affect convergence much...

If you recommend, we will not ignore this summand. However, even in this case the result of the main theorems will remain unchanged.

Remark 3.4 "High probability deviations bound" - the use of Markov's inequality trivially holds always…

We have indicated this in the remark, as it is a useful clarification for future work, given the consistency of the results (linear convergence and the presence of randomization).

There are many grammar issues…

Thanks, we'll fix it.

The term "adversarial attacks" is typically used in ML…

We will add references to relevant works to confirm the terms used.

Lemma 2.5: "with the chosen parameters"...

We have used this sentence, for brevity (e.g., in Theorem 2.6 we explicitly stated these parameters).

[1] https://arxiv.org/pdf/1802.09022

[2] https://dial.uclouvain.be/pr/boreal/object/boreal%3A128257/datastream/PDF_01/view

[3] https://www.tandfonline.com/doi/pdf/10.1080/10556788.2023.2212503

If you agree that we managed to address all issues, please consider raising your grade to support our work. If you believe this is not the case, please let us know so that we have a chance to respond.

With Respect,

Authors

Dear Area Chair and Senior Area Chair,

Please check the Official Review by Reviewer NqNV for quality, constructiveness, correctness and satisfaction with the ICML Code of Conduct.

With Respect,

Authors

Dear Reviewer Hj39,

Thanks for the insightful review. We are happy to see that the reviewer emphasized that the article provides a good theoretical analysis. The specific comments are addressed below:

This paper claimed achieving an improved iteration complexity. However, it seems that assumptions of the various related works are different from the one in Theorem 3.1 in this paper. It is better to compare the assumptions besides the iteration complexity. & Prior related works analyze the iteration-complexity for convex cases and non-convex cases under different assumptions.

Certainly, we will add columns with assumptions to the final version of the paper for a clear comparison. However, we would like to point out that the assumptions on the functions are the same (strong convexity and increased smoothness), while the assumption on the gradient approximation (Kernel approximation) differs only in the bounded noise assumption. In our work, we consider the generalized strong growth condition because we base our analysis on the work of [1] (see Section 2) to create a gradient-free algorithm. Assumption 2.4 is more general (and in the case $\rho = 0$, the assumptions coincide). We would like to note that a better estimate on the iteration complexity cannot be achieved (the estimate is optimal), provided that we create a gradient-free algorithm based on a first-order algorithm.

In this paper, the proposed method is only evaluated on one toy problem. It is unconvincing to justify the practical performance and the claim of outperforming SOTA. & Q2. Although the theoretical analysis is good. I am concerned about the practical performance of the proposed method (Algorithm 1). Could the authors provide more comparison with more black-box optimization baselines besides, e.g., CMAES?

As it is easy to see from the title, in our work we emphasize the importance of considering the three optimality criteria together. In particular, through the maximum noise level we can control the error floor (asymptote) to which we want to converge. Theorem 3.1 shows a rather surprising result, namely the maximum noise level can be improved by overbatching (after a threshold of $4d\kappa$, the maximum noise level depends on both the batch size $B$ and the smoothness order $\beta$). A more prominent example is Remark 3.3 because of the deterministic nature of the adversarial noise (improvements occur only through increased smoothness). In the practical part of our work (experiments), we confirm the importance of taking into account the presence of inaccuracy in the algorithm (by tuning the algorithm parameters). Given the theoretical nature of the work, and the narrative that we convey to the reader through a theoretical result, and confirm through a practical experiment on a9a data (comparable to the most related work: accelerated zero-order algorithms), it seems to us that performing additional practical experiments is beyond the scope of our study. Regarding the comparison with the CMAES algorithm, we will certainly add in Figure 3, but we expect ARDFDS and our algorithm to outperform CMAES due to the accelerated nature of convergence on the logistic regression function.

The zeroth-order gradient estimator in Eq.(5) is not new. For example, in Eq.(4) in [Bach et al. 2016].

Yes, indeed, we assumed that it would be clear to the reader from Table 1 that all the above algorithms use the kernel approximation. Nevertheless, we agree that adding a reference to the original source ([2]) of the gradient approximation that takes into account the information about the increased smoothness of the function would improve the quality of the text.

The black-box optimization methods in a broader context, the line of Evolutionary Strategy (e.g, ES, NES, CMAES), and the line of Bayesian Optimization (e.g., GP-UCB, TuRBO), are not discussed and compared.

Thanks for this comment, sure, we will add discussions of Evolutionary Strategy and Bayesian Optimization in the Related Work section.

Q1. What is the difference between the assumptions in this paper compared with the related works in Table 1? It is not clearly compared in the paper.

We will add additional columns to Table 1 as well as clarifications to the Assumptions in the final version of the paper.

[1] Vaswani S., Bach F., Schmidt M. Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron. The 22nd international conference on artificial intelligence and statistics (2019)

[2] Polyak B., Tsybakov A. Optimal Order of Accuracy of Search Algorithms in Stochastic Optimization. Problemy Peredachi Informatsii (1990).

If you agree that we managed to address all issues, please consider raising your grade to support our work. If you believe this is not the case, please let us know so that we have a chance to respond.

With Respect,

Authors