Dear Reviewer ErqJ,

We thank you for your feedback on our work.

I don't think the analysis result of...

We provide detailed answers to all questions below, including concerns about the significance and novelty of our results.

Line 77 is not finished. Line 78...

Thank you, we will correct those typos.

It would be good to put the GRM...

Due to space limitations in the main part of the paper, we had to move the GRM algorithm (which is not small) to Appendix. However, we have provided all the important information needed to understand our results in the main part of the paper.

Line 179: I'd suggest using...

In choosing the notations, we were guided by the traditions of previous works. It is tacitly accepted that the accuracy of the problem solution is denoted as $\varepsilon$ or $\epsilon$. Since in our work we are essentially solving two optimization problems, we have chosen these two notations accordingly. However, if you recommend the most appropriate notation for solving the inner optimization problem (linear search), we will be happy to change the notation.

In (8), it would be better...

Thank you for this comment, we will correct this typo.

Why is coordinate descent the best thing to do? To me...

First of all, we would like to mention that in previous works (with the Order Oracle) the authors used various schemes (including the transition to the normalized gradient algorithm), but all these works, including a very recent paper [1] (which appeared after our submission to the conference) achieved only unaccelerated estimates, moreover, all these estimates contain explicit dimensionality. This fact demonstrates that it has not yet been possible to find such an accelerated method that is satisfied with only the direction of the gradient (without knowledge of the modulus)... This includes among various methods with auxiliary low-dimensional minimization [2-4]. In all the accelerated methods known to us, the computation of the real gradient was assumed in one way or another. Therefore, the approach proposed in our paper is perhaps the only feasible scenario at the moment. Moreover, prior to our work, it was not clear that it was possible in any existing accelerated coordinate algorithm to completely get rid of the knowledge of directional derivatives and reduce everything to one-dimensional searches. It is worth noting that this observation is not trivial. For example, this was not the case with full-gradient accelerated algorithms. Moreover, we did not immediately succeed with coordinate algorithms, since there are already many of them. We had to find one for which it was possible to prove the corresponding statement.

Regarding non-accelerated methods, our approach explicitly demonstrates the following: we achieve SOTA results for a class of unaccelerated algorithms up to logarithm factor (see Table 1). Moreover, since the dimensionality dependence is hidden in parameters such as $S_{\alpha}$, in some cases (e.g., the asymmetric case: when the trace of the Hessian matrix has the same order as the largest eigenvalue) this dependence is reduced (this is typical for the class of coordinate descent), thus outperforming previous work in the high-dimensional problem.

Moreover, we did not stop there and provided an algorithm that improves the already accelerated convergence estimates in the case of the low-dimensional problem (see Appendix G). Finally, in Section 5 of our paper, we opened a new research direction (stochastic order oracle) by providing the first convergence results of another algorithm, but already in the stochastic oracle concept.

Algorithm 1 as stated works...

As we mention in Section 3, in the problem formulation, the stochasticity $\xi$ for Algorithm 1 and 2 denotes the $i$-th coordinate, and $\mathcal{D}$ represents the distribution $p_{\alpha}(i)$. But for the algorithm described in Section 5, stochasticity means the $\xi$-th realization of the function.

The accelerated algorithm 2 has several loops...

Regarding the use of the second linear search, it is currently necessary to use the linear search twice per iteration for the theoretical proof of estimates. But the good news is that in practical experiments (all the ones we have encountered), using only the first linear search allows us not only to significantly reduce the running time of the algorithm, but also to improve the convergence itself (see Figure 4). Regarding the noise $\delta(x,y)$, in this paper, for simplicity of presentation, we omitted it (we assumed that it does not exist), since our goal was to show that acceleration in such an oracle concept exists. However, the analysis for the case when there is noise will not be very different from the proposed one. We left this technical moment as a future work.

Similarly in Section 5, these reductions to existing methods...

In order to talk about the optimality of certain algorithms, we need to compare our upper estimates with the lower ones. However, as far as we know, there are currently no lower estimates for algorithms using the Order Oracle. So now we can only compare with existing SOTA results and assume that these estimates are likely to be optimal.

[1] Zhang, C., & Li, T. (2024). Comparisons Are All You Need for Optimizing Smooth Functions. arXiv preprint arXiv:2405.11454.

[2] Drori, Y., & Taylor, A. B. (2020). Efficient first-order methods for convex minimization: a constructive approach. Mathematical Programming, 184(1), 183-220.

[3] Narkiss, G., & Zibulevsky, M. (2005). SESOP: Sequential Subspace Optimization Method.

[4] Hager, W. W., & Zhang, H. (2006). A survey of nonlinear conjugate gradient methods. Pacific journal of Optimization, 2(1), 35-58.

With Respect,

Authors

Dear Reviewer ErqJ,

We thank you for your prompt feedback! Perhaps we have not clearly described the full importance of our results in Rebuttal, so with all due respect to you, we would like to reiterate the full novelty and significance of our results for the optimization community and beyond.

We would like to point out that our work focuses on the case where the oracle cannot return the objective function values $f(x)$ at the requested point $x$, much less the function gradient. Our oracle can only compare the objective function values (see the definition of Order Oracle (2)). There are a number of works in such an oracle concept (see Table 1). As shown in Table 1, the research on the optimization problem with such an oracle is at least c 2019 and the question of the existence of an accelerated algorithm in such oracle concept remained open until our work. For example, in [1] an attempt was made to create an accelerated algorithm using the heavy ball momentum, but the result was still an unaccelerated algorithm. Moreover, as mentioned earlier above, a recent paper [2] (which appeared after our conference submission) proposes another (alternative) approach that also does not produce an accelerated algorithm in the Order Oracle concept.

Thus, one of the main contributions of our paper is the proposed new approach to create (both unaccelerated and accelerated) optimization algorithms (1) using only Order Oracle (2). We agree that our approach for creating unaccelerated algorithms is quite simple, but we have demonstrated the effectiveness of this approach by proposing an alternative to the existing ones. But the value of the approach proposed in our work demonstrates the possibility of creating an accelerated algorithm (using Order Oracle).

The same trick, of course...

We cannot agree with this statement. Unlike the unaccelerated algorithm, it is not obvious that a linear search can be applied to the accelerated method of coordinate descent (see any accelerated algorithm of coordinate descent). Moreover, it is even more not obvious, and even surprising, that to create an accelerated algorithm with Order Oracle, it is necessary to use not one linear search, but two. As we said, there are a number of accelerated coordinate descent algorithms, and one of the problems we faced while preparing this article was to find the most appropriate accelerated coordinate descent algorithm on the basis of which we could create an already accelerated algorithm with Order Oracle.

There seems to be various hidden $d$ dependence...

As we have already mentioned, we have retained the hidden dimensionality dependence from the coordinate algorithm class. Indeed, comparable to other algorithms using Order Oracle concepts (see Related Work, namely "Algorithms with Order Oracle"), there are cases where hidden dimensionality dependence demonstrates superiority over explicit dependence.

In our opinion, the proposed approach demonstrating the first accelerated algorithm in the Order Oracle concept is no longer a minor contribution to the paper. Nevertheless, we also have equally significant results, namely, we show how to improve the estimates of the proposed accelerated algorithm with Order Oracle (the low-dimensional problem case). Finally, we provide the first convergence result of the algorithm using the already stochastic concept of Order Oracle (see the definition in (8)).

[1] Gorbunov, E. et. al (2019, September). A Stochastic Derivative Free Optimization Method with Momentum. In International Conference on Learning Representations.

[2] Zhang, C., & Li, T. (2024). Comparisons Are All You Need for Optimizing Smooth Functions. arXiv preprint arXiv:2405.11454.

With Respect,

Authors

Dear Reviewer WKzP,

We thank you for your feedback on our work. We provide detailed answers to the comments and questions raised in the review below.

Elaboration on Motivation.

Despite the potential motivation given in the introduction, as well as the mention of Appendix A, which details an application (startup: smart coffee machine), we are convinced that problem setting with such an oracle has a huge number of potential applications, in particular, such an oracle is organic to perhaps the most popular setting at the moment, namely Reinforcement learning with Human Feedback (RLHF). And we agree that the paper will become stronger and potentially have even more impact when we add more mentions of RLHF in the motivational part of the main paper.

Comprehensive Experimental Validation.

Indeed, this paper was initiated due to a challenge faced by one of the co-authors in the realization of a startup (a smart coffee machine). Already in the process of preparing the paper, we started testing it. At the moment we have ready experiments on more than a real problem, where the coffee machine uses the algorithms presented in this paper, with a deterministic oracle. However, we have encountered some difficulties: since the coffee machine is not yet patented (we've started the patenting process), we have not been able to insert these experiments. Regardless, we thought we found a decent temporary alternative - model examples that clearly verify the theoretical results. Nevertheless, we realize that adding these results will further strengthen our work. Currently we expect the patenting process for the coffee machine to be completed in September-October this year, so in case of a positive decision (acceptance at the conference) on our paper, we are confident that we will have time to add the experiments on real problems to the camera-ready version.

Performance in High-Dimensional Space.

The high-dimensional challenge problem is typical for a class of coordinate algorithms. And since we are based on such an algorithm, we expectedly inherit this challenge. However, as you have already noticed below (in the Questions section), there is no explicit dependence on dimensionality in the final estimates (unlike previous work with Order Oracle). This fact is an advantage of our scheme (approach), since there are cases (e.g., the asymmetric case: when the trace of the Hessian matrix has the same order as the largest eigenvalue) where the dimensionality dependence is reduced (again, this is typical for the class of coordinate algorithms). In this case, our algorithm will be significantly superior to all previous algorithms, since in alternative algorithms the explicit dependence on dimension $d$ does not disappear anywhere.

Technical Challenges compared to Nesterov's 2012 Work.

To begin with, we would like to clarify that indeed the optimization problem formulation is somewhat similar to the one considered in [1], with perhaps a serious exception: we cannot use information about the function (Order Oracle concept). As can be seen from Table 1, all previous optimization algorithms using the Order Oracle achieved only unaccelerated convergence estimates. Moreover, a recent paper [2], which appeared on the arXiv after our submission to the conference also provided only an unaccelerated algorithm. This fact demonstrates that it has not yet been possible to find such an accelerated method that is satisfied with only the direction of the gradient (without knowledge of the modulus)... This includes among various methods with auxiliary low-dimensional minimization [3-5]. In all the accelerated methods known to us, the computation of the real gradient was assumed in one way or another. Therefore, it is important to take into account the following:

• The approach proposed in our paper is perhaps the only feasible scenario at the moment.
• Prior to our work, it was not clear that it was possible in any existing accelerated coordinate algorithm to completely get rid of the knowledge of directional derivatives and reduce everything to one-dimensional searches. It is worth noting that this observation is not trivial. For example, this was not the case with full-gradient accelerated algorithms.
• We did not immediately succeed with coordinate algorithms, since there are already many of them. We had to find one for which it was possible to prove the corresponding statement.

However, we did not stop there and provide an algorithm (see Appendix G) that shows the possibility of improving convergence estimates in the case of a low-dimensional optimization problem. Finally, we opened a new research direction by providing the first convergence results for an optimization algorithm with a stochastic Order Oracle (see Section 5), which uses a different approach.

Dimension-Independent Complexity.

This is an interesting question! Yes, by using unusual sampling of the active coordinate, the dependence on dimensionality is implicitly hidden in parameters such as $S_{\alpha} = \sum_{i}^{d} L_{i}^{\alpha}$. For example, if we consider a uniform distribution ($\alpha = 0$), then $S_0 = d$. Also, we propagate the best results among accelerated coordinate descent algorithms by using the following distribution to select the active coordinate: $i=\mathcal{R_{\alpha/2}}(L)$. This is to get rid of the dimension dependence in the estimates, since $S_{\alpha/2} \leq \sqrt{d S_{\alpha}}$.

[1] Nesterov, Y. (2012). Efficiency of coordinate descent methods on huge-scale optimization problems.

[2] Zhang, C. et al. (2024). Comparisons Are All You Need for Optimizing Smooth Functions.

[3] Drori, Y. et al. (2020). Efficient first-order methods for convex minimization: a constructive approach.

[4] Narkiss, G. et al. (2005). SESOP: Sequential Subspace Optimization Method.

[5] Hager, W. et al. (2006). A survey of nonlinear conjugate gradient methods.

With Respect,

Authors

Dear Reviewer uSy5,

We thank you for your interest in our work. We attach below detailed responses to the comments and questions raised in the review.

i have some concerns on the novelty of this paper...

We tried to prepare the text of the paper so that it would be easily accessible to readers not only for the optimization community, as we believe that the results of the paper can have an impact on various areas. In particular, perhaps the most popular area at the moment is Reinforcement learning with Human Feedback (RLHF).

Perhaps it is precisely because of the simplicity and accessibility of the presentation of the paper that the misunderstanding arose. With all due respect to you, we would like to emphasize the significance and novelty of our work. As can be seen from Table 1, all previous optimization algorithms using the Order Oracle achieved only unaccelerated convergence estimates. Moreover, a recent paper [1], which appeared on the arXiv after our submission to the conference also provided only an unaccelerated algorithm. This fact demonstrates that it has not yet been possible to find such an accelerated method that is satisfied with only the direction of the gradient (without knowledge of the modulus)... This includes among various methods with auxiliary low-dimensional minimization [2-4]. In all the accelerated methods known to us, the computation of the real gradient was assumed in one way or another. Therefore, it is important to take into account the following:

• The approach proposed in our paper is perhaps the only feasible scenario at the moment.
• Prior to our work, it was not clear that it was possible in any existing accelerated coordinate algorithm to completely get rid of the knowledge of directional derivatives and reduce everything to linear search. It is worth noting that this observation is not trivial. For example, this was not the case with full-gradient accelerated algorithms.
• We did not immediately succeed with coordinate algorithms, since there are already many of them. We had to find one for which it was possible to prove the corresponding statement.

However, we did`t stop there and provide an algorithm (see Appendix G) that shows the possibility of improving convergence estimates in the case of a low-dimensional optimization problem. Finally, we opened a new research direction by providing the first convergence results for an optimization algorithm with a stochastic Order Oracle (see Section 5), which uses a different approach. As can be seen, all of these results individually, and even more so in combination, are novel and are especially needed in various applications.

both of the proposed algorithms are...

We do not quite agree with this remark, since for us the notation $\tilde{O}(\cdot)$ is equivalent to explicitly writing the logarithm in the estimates. Moreover, in Section 1.2 (Notation) we introduced this notation ($\tilde{O}(\cdot)$, where we explained that it hides the logarithmic coefficient, which is standard among optimization works) to reduce the length of the formulas, in particular in Table 1. To be fair, we spell out the presence of the logarithm in the estimates in all discussions of the results, and even more so in the abstract of the paper. However, if you strongly recommend explicitly stating the logarithm in the estimates, we will of course do so.

the numerical experiment is too simple...

As written in Appendix A1, this paper was initiated due to a challenge faced by one of the co-authors in the realization of a startup (a smart coffee machine). Already in the process of preparing the paper, we started testing it. At the moment we have ready experiments on more than a real problem, where the coffee machine uses the algorithms presented in this paper, with a deterministic oracle. However, we have encountered some difficulties: since the coffee machine is not yet patented (we've started the patenting process), we have not been able to insert these experiments. Regardless, we thought we found a decent temporary alternative - model examples that clearly verify the theoretical results. Nevertheless, we realize that adding these results will further strengthen our work. Currently we expect the patenting process for the coffee machine to be completed in September-October this year, so in case of a positive decision (acceptance at the conference) on our paper, we are confident that we will have time to add the experiments on real problems to the camera-ready version.

in the accelerated case, it's not clear to me...

We would like to clarify that all figures show convergence depending on the iteration complexity. As shown by theoretical evaluations, the iteration complexities of the proposed algorithms match those of the coordinate descent (first order) algorithms, but already the oracle complexities lose by a logarithmic factor. We mention this in the discussion under each result. Moreover, in Figure 4, we compare the proposed accelerated algorithm with the ACDM algorithm of [5]. In Figure 4, we show that in numerical experiments, using only the first linear search not only improves the running speed of the algorithm, but also improves the convergence itself.

minor issues.

Thank you, we will correct those typos.

in assumption 1.1, can...

Assumption 1.1 is standard for the class of coordintate algorithms and implies some L-smooth over each coordinates.

[1] Zhang, C. et al. (2024). Comparisons Are All You Need for Optimizing Smooth Functions.

[2] Drori, Y. et al. (2020). Efficient first-order methods for convex minimization: a constructive approach.

[3] Narkiss, G. et al. (2005). SESOP: Sequential Subspace Optimization Method.

[4] Hager, W. W. et al. (2006). A survey of nonlinear conjugate gradient methods.

[5] Nesterov, Y. et al. (2017). Efficiency of the accelerated coordinate descent method on structured optimization problems.

With Respect,

Authors

Dear Reviewer K16N,

We thank you for your positive evaluation of our work! Below we provide detailed answers to all comments and questions that arose in the review.

The authors have motivated the use of this oracle, but it would be useful to have some concrete examples on how is it being used in practice.

With all due respect to you, we do not fully agree with this comment, as a more concrete example given in Appendix A1 (startup: smart coffee machine) seems hard to think of. But despite the fact that this research was indeed initiated due to a problem faced by one of the co-authors in implementing a startup, we are convinced that problem setting with such an oracle has a huge number of potential applications, in particular, such an oracle is organic in perhaps the most popular setting at the moment, namely Reinforcement learning with Human Feedback (RLHF). And we agree that the article will become stronger and potentially have even more impact when we add more mentions of RLHF in the motivational part of the main paper.

When you say adaptive in the text, what does that mean?

This is a really interesting question! The unaccelerated algorithm presented in Section 3 can be classified as an adaptive algorithm (especially in the case of uniformly distributed selection of the active coordinate $\alpha = 0$), since the iteration step and the value of the gradient coordinate are found without any parameters (in particular without the $L$-coordinate-Lipschitz constants) by solving an internal linear problem. This adaptability is clearly shown in Figure 2, where OrderRCD outperforms the first-order RCD algorithm, which uses the gradient coordinate with a theoretical step value using the constant $L_i$. That is, the advantage of our algorithm arises because we adaptively select the iteration step of the algorithm in contrast to the first-order algorithm.

The algorithms basically seem like you are performing coordinate descent, but instead of using gradients step size, you want to directly compute this quantity using the GRM line search. So implicitly this is a first order method being implemented using an order oracle? If this is the case, is it possible to show an equivalence between the order oracle and gradient oracle?

Indeed, the class of coordinate algorithms was chosen as a basis because the issue of not knowing the function gradient was organically solved by using the golden ratio method (linear search), where the Order Oracle is already used. Therefore, our algorithm almost completely adopted both all the advantages of the coordinate algorithm (which was our goal) and the disadvantages. Moreover, as often mentioned in this paper, we cannot say that these algorithms are equivalent, because the oracle complexity differs by a logarithm. This is the cost of using linear search.

What is the notation with $\alpha$?

By $\alpha$ we mean that this is the parameter used in generating the active coordinate $i_k$ with the following distribution: $p_{\alpha}(i) = L_i^{\alpha} / S_\alpha,$ where $i \in [d]$, and $S_{\alpha} = \sum_{i}^{d} L_i^{\alpha}$. This choice of active coordinate is already standard in works devoted to coordinate descent and is actively used in various works, e.g., [1-4].

Are there examples (even experiments) that can say something about the difference between the order oracle and usual first order oracles?

Yes, Figure 2 and 4 show the comparison of unaccelerated and accelerated algorithms respectively. The algorithms proposed in this paper (Order Oracle) are compared with SOTA coordinate descent algorithms (first order oracle). It is worth noting, as discussed above, the unaccelerated algorithm with Order Oracle can quite expectedly outperform the first order algorithm (RCD) due to adaptivity. But the accelerated algorithm with Order Oracle with the given recommendations concerning the number of linear searches is not inferior to the first-order algorithm.

In the accelerated algorithm, are there adversarial examples where the second line search is necessary?

At the moment it is necessary to use linear search twice per iteration for theoretical proof of estimates. This is basically not bad considering that our goal was to show the possibility of acceleration. But the good news is that in practical experiments (all the ones we have encountered), using only the first linear search allows us not only to significantly reduce the running time of the algorithm, but also to improve the convergence itself (see Figure 4).

What is the barrier in extending the acceleration beyond strongly convex objectives?

As already mentioned, one of the main goals of our work is to show the existence/possibility of accelerating algorithms using the concept of the Order Oracle. We have demonstrated this on the example of a strongly convex function. By doing so, we have opened a direction for future work, in particular, to investigate already accelerated algorithms under other assumptions. Regarding obtaining convergence results of the accelerated algorithm in the convex smooth case, this is possible using standard tricks such as, for example, regularization. We left further development of the results as future work.

[1] Bubeck, S. (2015). Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning.

[2] Nesterov, Y. (2012). Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization.

[3] Nesterov, Y., & Stich, S. U. (2017). Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM Journal on Optimization.

[4] Allen-Zhu, Z., Qu, Z., Richtárik, P., & Yuan, Y. (2016, June). Even faster accelerated coordinate descent using non-uniform sampling. In International Conference on Machine Learning. PMLR.

With Respect,

Authors

Dear Reviewer XqbR,

We would like to thank you for your time for preparing the review.

The numerical experiments show the evaluation of OrderRCD and OrderACDM in standard quadratic functions. Experiments on real-world problems would strengthen the validation. The paper can include specific details about the numerical experiments, the exact values or structure of matrices and vectors $A$, $b$, and $c$, the dimensionality of the problems tested, datasets used etc. The paper does not deeply explore the scalability of the proposed algorithms in very high-dimensional settings or large-scale datasets. While the paper addresses stochastic optimization, analysis of noise sensitivity would enhance the understanding of the algorithm's performance under various conditions.

Since the presented questions fully characterize the weaknesses mentioned in the review, we have prepared detailed answers to each of the questions. The answers can be found below.

Could you provide more specifics about the numerical experiments?

First, we would like to clarify that due to the lack of space in the main part of the paper, several numerical experiments can be found also in Appendix B. Regarding the reproducibility of the results, in our opinion it seems that there is enough information about the problem formulation and the parameters of the algorithm. However, we agree that we could be a bit more precise in describing the matrix $A$ and vectors $b,c$, namely the process of their generation. We will add this information about the problem formulation to the main part of the paper.

Could you show numerical validation in real-world problems and datasets?

As written in Appendix A1, this paper was initiated due to a challenge faced by one of the co-authors in the realization of a startup (a smart coffee machine). Already in the process of preparing the paper, we started testing it. At the moment we have ready experiments on more than a real problem, where the coffee machine uses the algorithms presented in this paper, with a deterministic oracle. However, we have encountered some difficulties: since the coffee machine is not yet patented (we've started the patenting process), we have not been able to insert these experiments. Regardless, we thought we found a decent temporary alternative - model examples that clearly verify the theoretical results. Nevertheless, we realize that adding these results will further strengthen our work. Currently we expect the patenting process for the coffee machine to be completed in September-October this year, so in case of a positive decision (acceptance at the conference) on our paper, we are confident that we will have time to add the experiments on real problems to the camera-ready version.

Are there any experiments being conducted for the stochastic order oracle? Could you show the results in that setting?

Of course, yes, they are being conducted! To be more specific, there are tests of the coffee machine at the moment, where the ideal coffee is created already for a certain group of people on average. We also want to add the results of the experiments to the Appendix section in the final version of the paper after obtaining a patent for the coffee machine.

Limitations.

Thank you, we will be sure to add a "Limitations" section to the main part of the paper.

Significance and novelty of our results

In conclusion, as already mentioned, this work was motivated by a specific application (startup), but the results presented are not limited to it! This oracle concept has a number of applications, including perhaps the most popular setup, namely Reinforcement learning with Human Feedback (RLHF). It is worth noting that all previous works (see Section 2 and Table 1) have only achieved unaccelerated estimates under various convexity assumptions. Moreover, the work [1] that appeared after our submit also achieves only unaccelerated algorithms. This fact demonstrates that it has not yet been possible to find such an accelerated method that is satisfied with only the direction of the gradient (without knowledge of the modulus, see the definition of the Order Oracle)... This includes among various methods with auxiliary low-dimensional minimization [2-4]. In all the accelerated methods known to us, the computation of the real gradient was assumed in one way or another. Therefore, the approach proposed in our paper is perhaps the only feasible scenario at the moment. Moreover, prior to our work, it was not clear that it was possible in any existing accelerated coordinate algorithm to completely get rid of the knowledge of directional derivatives and reduce everything to one-dimensional searches. It is worth noting that this observation is not trivial. For example, this was not the case with full-gradient accelerated algorithms. Moreover, we did not immediately succeed with coordinate algorithms, since there are already many of them. We had to find one for which it was possible to prove the corresponding statement. Further, we did not stop there and provided (see Appendix G) an algorithm that improves the already accelerated convergence estimates in the case of a low-dimensional problem. Finally, in Section 5 of our paper, we opened a new research direction (stochastic order oracle) by providing the first convergence results (of another algorithm), but already in the stochastic oracle concept.

[1] Zhang, C., & Li, T. (2024). Comparisons Are All You Need for Optimizing Smooth Functions. arXiv preprint arXiv:2405.11454.

[2] Drori, Y., & Taylor, A. B. (2020). Efficient first-order methods for convex minimization: a constructive approach. Mathematical Programming, 184(1), 183-220.

[3] Narkiss, G., & Zibulevsky, M. (2005). SESOP: Sequential Subspace Optimization Method.

[4] Hager, W. W., & Zhang, H. (2006). A survey of nonlinear conjugate gradient methods. Pacific journal of Optimization, 2(1), 35-58.

With Respect,

Authors