Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values

Authors: aleksandr  lobanov
alexander  gasnikov
andrei  krasnov
Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-22 22:03:40

Abstract: Frequently, the burgeoning field of black-box optimization encounters challenges due to a limited understanding of the mechanisms of the objective function. To address such problems, in this work we focus on the deterministic concept of Order Oracle, which only utilizes order access between function values (possibly with some bounded noise), but without assuming access to their values. As theoretical results, we propose a new approach to create non-accelerated optimization algorithms (obtained by integrating Order Oracle into existing optimization “tools”) in non-convex, convex, and strongly convex settings that are as good as both SOTA coordinate algorithms with first-order oracle and SOTA algorithms with Order Oracle up to logarithm factor. Moreover, using the proposed approach, _we provide the first accelerated optimization algorithm using the Order Oracle_. And also, using an already different approach we provide the asymptotic convergence of _the first algorithm with the stochastic Order Oracle concept_. Finally, our theoretical results demonstrate effectiveness of proposed algorithms through numerical experiments.

Main paper: 
 introduction: 
 The black box problem has garnered extensive attention in diverse scientific and engineering domains, reflecting the challenge of optimizing systems with complex and opaque objective functions, prompting the exploration of innovative solutions Conn et al. (2009) ; Kimiaei and Neumaier (2022) . This paper focuses on solving a standard general optimization problem in the following form:EQUATIONwhere f : R d → R is a possibly non-convex, possibly stochastic function. This problem configuration encompasses a broad range of applications in ML scenarios, e.g. empirical risk minimization,where D denotes distribution across training data points, and f ξ (x) represents loss of model x on data point ξ.When the objective function f (x) has exclusive access to a zero-order oracle Rosenbrock (1960) , problem (1) falls under the classification of a black-box optimization problem. This class of problems is actively studied in various application settings, e.g., deep learning Chen et al. (2017) ; Gao et al. (2018) , federated learning Dai et al. (2020) ; Alashqar et al. (2023) ; Patel et al. (2022) , reinforcement learning Choromanski et al. (2018) ; Mania et al. (2018) , overparameterized models Lobanov and Gasnikov (2023) , online optimization (Agarwal et al., 2010; Bach and Perchet, 2016; Akhavan et al., 2022) , multi-armed bandits Shamir (2017) ; Lattimore and Gyorgy (2021) , hyperparameter settings Bergstra and Bengio (2012) ; Hernández-Lobato et al. (2014) ; Nguyen and Balasubramanian (2022) , and control system performance optimization Bansal et al. (2017) ; Xu et al. (2022) . It is important to highlight that the zero-order oracle presupposes awareness of the objective function's value f (x k ) at a specific point x k (which may be inexact), enabling the development of effective gradient-free algorithms tailored to various problem scenarios Gasnikov et al. (2022a) .38th Conference on Neural Information Processing Systems (NeurIPS 2024).Table 1 : Comparison of oracle complexity for the methods proposed in this work with SOTA methods both in the coordinate descent class and in the Order Oracle concept (2). Notation: F0 = f (x0) -f (x * ); R = ∥x0 -x * ∥; R [1-α] = R1-α(x0) = sup-convex ✗ O dSαF0 ε 2 ✗ O dLF0 ε 2 Õ SαF0 ε 2 Convex O SαR 2 [1-α] ε O dSαR 2 [1-α] ε log 1 ε O dLR 2 ε ✗ Õ SαR 2 [1-α] ε Strongly convex O Sα µ1-α log 1 ε O Sα µ1-α log 1 ε O d L µ log 1 ε ✗ Õ Sα µ1-α log 1 ε Õ Sα/2 √ µ1-α log 1 ε Order Oracle? ✗ ✓ ✓ ✓ ✓ ✓ Acceleration? ✗ ✗ ✗ ✗ ✗ ✓In this paper, we consider concept of zero-order oracle, termed Order Oracle, to address problem (1):EQUATIONwhere |δ(x, y)| ≤ ∆ is some bounded noise.The Order Oracle has the capability to compare two functions; however, in contrast to the zero-order oracle, it lacks the ability to calculate or utilize the actual value of the objective function. This concept closely mirrors the challenges encountered in real-world black-box optimization problems. The motivation for the proposed oracle concept becomes more evident when considering the ongoing developments in generative models. Companies like Valio and SberAI have already embraced the active involvement of AI in dessert creation. Notably, Valio, as illustrated in Figure 1 * , employed AI to determine the optimal concentration of milk for chocolate bars based on available data. However, envision a scenario where AI creates customized chocolate for an individual by adjusting the concentration of ingredients. In such a case, a flavor comparison procedure, depicted in one iteration, would involve determining the preference order. Given that tastes can be closely aligned, introducing bounded noise in oracle (2) mitigates the potential for errors.To address the initial deterministic problem (1) with the Order Oracle (2), we propose a novel approach to algorithm design that uses class of coordinate descent methods (CD) Bubeck et al. (2015) as an optimization "tool" to integrate our oracle into multidimensional optimization. This approach is good in that we use linear search (where the Order Oracle is directly used) to determine not only the iteration step size, but also the gradient coordinate of the objective function. Thus demonstrating that the proposed algorithms are also adaptive. And for solving the initial stochastic problem (1) with the Order Oracle, we propose an approach based on normalized SGD, providing asymptotic convergence.More specifically, our contributions are the following:• We provide a novel approach to design algorithms for solving deterministic optimization problems (1) with Order Oracle (2) that achieves SOTA convergence results up to logarithm factor in the non-convex, convex, and strongly convex settings (see Table 1 and Algorithm 1).• By using the approach proposed in this paper to create algorithms for solving deterministic optimization problem (1) with the Order Oracle (2), we have shown, on an example of strongly convex functions, that acceleration in such an oracle concept exists (see Algorithm 2 and Theorem 4.1). Moreover, we have shown how the convergence results of the accelerated algorithm can be improved when the problem is low-dimensional (the algorithm described in Appendix G shows convergence that even the Ellipsoid method cannot).• We provide the first algorithm for solving a problem (1) with the stochastic Order Oracle concept, where the order between two functions on the same realization is determined.• Through numerical experiments (see Section 7), we validate our theoretical results by comparing with first-order algorithms, as well as providing practical recommendations for implementing the first accelerated algorithm with the Order Oracle (2) (see Algorithm 2).Before discussing related works, we present the notation and main assumptions we use in our work.Notation. We use ⟨x, y⟩ := d i=1 x i y i to denote standard inner product of x, y ∈ R d . We denote Euclidean norm in R d as ∥x∥ := d i=1 x 2 i . In particular, this norm ∥x∥ := ⟨x, x⟩ is related to the inner product. We use e i ∈ R d to denote the i-th unit vector. We define the norms∥x∥ [α] := d i=1 L α i x 2 i and ∥x∥ * [α] := d i=1 1 L α ix 2 i . We denote by ∇f (x) the full gradient of function f at point x ∈ R d , and by ∇ i f (x) the i-th coordinate gradient. The sum of constant L i denotes as S α := d i L α i . We use S d (r) := x ∈ R d : ∥x∥ = r to denote Euclidean sphere. We use Õ(•) to hide the logarithmic coefficients. We denote f * := f (x * ) as the solution to initial problem. For all our theoretical results, we assume that f (x) is L i -smooth with respect to its i-th coordinate:Assumption 1.1 (Smoothness). A function f : R d → R is L-coordinate-Lipschitz for L 1 , L 2 , ..., L d > 0 if for any i ∈ [d],x ∈ R d and h ∈ R the following inequality holds:|∇ i f (x + he i ) -∇ i f (x)| ≤ L i |h|.The smoothness assumption of the function is widely used in the optimization literature (e.g. Boyd and Vandenberghe, 2004; Nesterov et al., 2018) . However, Assumption 1.1 is specific and frequently utilized in the context of optimization via the CD method Lin et al. (2014) ; Zhang and Xiao (2017) ; Mangold et al. (2023) . This assumption means that for every input point x, if we alter its i-th coordinate by at most h, then the corresponding gradient∇ i f (x + he i ) differs from ∇ i f (x) by at most L i times |h|.Throughout this paper we assume that function f (x) can be (strongly) convex w.r.t. the norm ∥•∥ [1-α] : Assumption 1.2. A function f : R d → R is µ 1-α ≥ 0 strongly convex w.r.t. the norm ∥•∥ [1-α] if for any x, y ∈ R d the following inequality holds: f (y) ≥ f (x) + ⟨∇f (x), y -x⟩ + µ 1-α 2 ∥y -x∥ 2 [1-α] .Many works in convex optimization rely on the (strong) convexity assumption, as evidenced by references such as Duchi (2016) ; Shi et al. (2019) ; Asi et al. (2021) . Since our work employs norms ∥•∥ [1-α] to derive theoretical estimates, Assumption 1.2 deviates slightly from the standard. However, this assumption of µ 1-α (strong) convexity is extensively used in the following literature: Nesterov (2012); Lee and Sidford (2013); Allen-Zhu et al. (2016) . Assumption 1.2 can conform to standard form of µ (strong) convexity via Euclidean norm if α = 1. This assumption is convex provided µ 1-α = 0.Further, this paper has the following structure. In Section 2, we provide a related work discussion. We present and analyze the non-accelerated algorithm in Section 3. Then in Section 4, we discuss the feasibility of accelerating the proposed algorithm in the concept of Order Oracle and provide theoretical guarantees. We provide the first algorithm that utilizes the stochastic concept of the Order Oracle in Section 5. In Section 6, we discuss the current results of this work. Through numerical experiments in Section 7, we validate the theoretical results. While Section 8 concludes the paper.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: For convenience, we have also added a Subsection "Our contributions" to Section 1 (Introduction). Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related works: 
 The literature in the field of optimization is already extensive and continuously expanding, encompassing various problem formulations and assumptions. In this section, we provide an overview of the most relevant contributions to our work. Namely both CD methods and algorithms with Order Oracle.Algorithms with Order Oracle. In the field of black-box optimization problem, special attention has been paid to algorithms that use only the Order Oracle. For example, Stochastic Three Points Method was proposed in Bergou et al. (2020) , which uses an oracle that compares three function values at once and achieves the following oracle complexity in the strongly convex case O (dL/µ log 1/ε).A little later, the authors of Gorbunov et al. (2019) modified the Stochastic Three Points Method to the case of importance sampling, improving the oracle complexity estimate in the strongly convex case O (S α /µ log 1/ε). Already in 2021, Saha et al. (2021) provided another algorithm in which the oracle compares two function values only once per iteration. The analysis of this algorithm is based on the Sign SGD and achieves oracle complexity in the strongly convex case O (dL/µ log 1/ε). The work of Tang et al. (2023) showed that the Order Oracle is also extensively used in Reinforcement Learning with Human Feedback, providing only in the non-convex case an estimate on oracle complexity O d/ε 2 . In this paper, we propose an alternative approach for creating optimization algorithms (via line search method), which achieves SOTA convergence results with logarithm accuracy in a class of non-accelerated algorithms, and provide the first accelerated algorithm with the Order Oracle.Coordinate descent (CD) methods. In addition to full-gradient algorithms for smooth first-order optimization, coordinate descent algorithms are categorized into accelerated and non-accelerated algorithms. Non-accelerated algorithms typically converge at rates 1/ε and 1/µ in convex (µ = 0) and strongly convex (µ > 0) cases, respectively, while accelerated algorithms achieve rates 1/ √ ε and 1/ √ µ in convex and strongly convex cases, respectively. This classification dates back to 1983 when Nesterov introduced the optimal convergence rates for first-order algorithms Nesterov (1983) . However, the fundamental difference between coordinate descent and full-gradient descent lies in the step taken along the i-th coordinate of the gradient (directional derivative). Monograph Bubeck et al. (2015) has demonstrated that if the direction is chosen uniformly, coordinate descent may require up to d times more iterations than full-gradient descent. However, authors in Nesterov (2012) have shown that considering smoothness along the direction L i can improve the number of iterationsO S α R 2 [1-α] /ε and O S α /µ 1-α log 1ε in convex and strongly convex cases, respectively, whereR [1-α] = sup x∈R d :f (x)≤f (x0) ∥x -x * ∥ [1-α] for α ∈ [0, 1].In the same paper Nesterov (2012) , the authors demonstrated the potential for acceleration in coordinate descent through the scheme proposed in Nesterov (1983) . Subsequently, in Lee and Sidford (2013) , they analyzed and presented an accelerated version of coordinate descent (ACDM), along with the corresponding number of requiredO dS α R 2 [1-α] /ε and O dS α /µ 1-α log 1ε iterations in convex and strongly convex cases, respectively. It is noteworthy that, at that time, this iteration complexity was deemed unimprovable. However, a few years later, both Nesterov and Stich (2017) and Allen-Zhu et al. (2016) independently provided same results, demonstrating that it is indeed possible to enhance the iteration complexity for accelerated coordinate descent methods by modifying the probability of choosing the i-th coordinate: L α/2 i /S α/2 . In this paper, we propose a coordinate descent algorithm with an Order Oracle (2), demonstrating that it achieves the same iteration complexity as first-order algorithms. Furthermore, based on accelerated coordinate descent Nesterov and Stich (2017) , we establish on the strongly convex case that even with an Order Oracle, acceleration can be attained, resulting in the most favorable estimates on iteration complexity known to date.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: See Section 1 (Introduction) where we formulate the problem statement. See also the statement of Theorems, where we provide conditions under which the theoretical results are guaranteed, and the discussion of them. In addition, we discuss in Section 6 (Discussion) how the algorithm would behave if we move away from the assumptions under consideration, e.g., the gradient dominance assumption (Polyak-Lojasiewicz condition). Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory Assumptions and Proofs (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
non-accelerated methods: 
 In this section, we begin to present our main results, by introducing algorithms tailored to address the initial problem (1) utilizing the Order Oracle (2). Given the demand for this oracle concept, we furnish convergence guarantees and conduct comparisons with algorithms employing alternative oracles.Our approach for developing a new algorithm involves incorporating the Order Oracle into an existing optimization method using linear search. We opt for linear search as the integration tool due to its compatibility with the Order Oracle concept. However, the choice of optimization method to which this linear search can be applied poses a crucial question. After careful consideration, we determined that the coordinate descent method (CDM) is the most suitable candidate. In each iteration, the CDM, given a step size ζ k > 0 and starting point x 0 ∈ R d , proceeds as follows:EQUATIONwhere i k is the coordinate index drawn from [d] . Note that the coordinate descent method step (3) requires both a step size ζ k and a gradient coordinate value ∇ i k f (x k ), which are scalars. Thus, by employing linear search η k = arg min η {f (x k + ηe i k )} at each iteration, we can optimally determine both the direction of steepest descent and the step size to traverse along this direction, resulting in a fully adaptive algorithm. The next consideration is the strategy for coordinate selection at each iteration. Following the trend initiated by Nesterov (2012) , we use a more general sampling distribution than the uniform one, obtaining already random coordinate descent (RCD). Specifically, for α > 0, we assume that a random generator R α (L) independently selects i k from the following distribution:EQUATIONWe are now ready to introduce a method designed to solve problem (1) utilizing the oracle concept (2).This algorithm falls under the category of coordinate methods and is named random coordinate descent with order oracle (OrderRCD), see Algorithm 1.It should be noted that the inherent "stochasticity" of problem (1) is artificially induced by randomized procedure used to select the i-th coordinate (4).Here, ξ denotes the i-th coordinate, and D represents distribution p α (i) from ( 4).The golden ratio method (GRM) servesAlgorithm 1 Random Coordinate Descent with Order Oracle (OrderRCD) Input: x 0 ∈ R d , random generator R α (L) for k = 0 to N -1 do 1. choose active coordinate i k = R α (L) 2. compute η k = argmin η {f (x k + ηe i k )} via (GRM) 3. x k+1 ← x k + η k e i k endη k = argmin η {f (x k +ηe i k )}).Next, we present our theoretical results, demonstrating through convergence analyses that random coordinate descent with order oracle (OrderRCD) exhibits competitive iteration complexity compared to first-order algorithms when applied to non-convex, convex, or strongly convex functions.Theorem 3.1 (non-convex). Let function f(x) satisfies Assumption 1.1, N is the number of iterations,F 0 = f (x 0 ) -f (x * ),then Algorithm 1 (OrderRCD) with oracle (2) guarantees an error:1 N N -1 k=0 ∥∇f (x k )∥ * [1-α] 2 ≤ O S α F 0 N + S α ϵ + S α Φ∆ ,where ϵ is the accuracy of solving linear search problem by function and Φ = 1+ √ 5 2 is golden ratio.The convergence results of Theorem 3.1 imply the existence of a point k ∈ [N ] where(∥∇f (x k )∥ * [1-α] ) 2 ≤ O SαF0N holds true. Additionally, Theorem 3.1 indicate that, to achieve the desired accuracy ε (according to the gradient norm), Algorithm 1 requires N = O S α F 0 /ε 2 iterations and T = Õ S α F 0 /ε 2 calls to the oracle (2). The maximum admissible noise level ensuring the desired accuracy should not exceed ∼ ε 2 . Notably, the convergence rate of random coordinate descent with the order oracle (OrderRCD), assuming minimal noise (∆ ≤ ε 2 ), is equal to first-order method: random coordinate descent (RCD). It is also characteristic (within the coordinate methods class) to be inferior to gradient descent (Ghadimi and Lan, 2013, under L smoothness assumption) . For instance, in the case when α = 1, the convergence rates O (LF 0 /N ) is better because L ≤ d i=1 L i . Not surprisingly, in terms of oracle complexity, Algorithm (1) is logarithmically inferior to first-order algorithms. This discrepancy reflects the "cost" associated with employing GRM, where the Õ(•) to hide the logarithmic coefficient representing the number of oracle calls in the GRM, contingent upon its accuracy ϵ. A detailed proof of Theorem 3.1 is given in Appendix D.1.We now prove an analogous theorem on the convergence of the algorithm when the function is convex, i.e., additionally assuming that Assumption 1.2 is satisfied with µ 1-α = 0. Theorem 3.2 (convex). Let function f (x) satisfies Assumption 1.1 (L-Smoothness) and Assumption 1.2 (convexity, µ 1-α = 0), then Algorithm 1 (OrderRCD) with oracle (2) guarantees an error:E [f (x N )] -f (x * ) ≤ O S α R 2 [1-α] N + 2S α R 2 [1-α] (ϵ + Φ∆) F N -1 ,where ϵ is an inner problem accuracy,R [1-α] = sup x∈R d :f (x)≤f (x0) ∥x -x * ∥ [1-α] , and Φ = 1+ √ 5 2 .In comparison to Theorem 3.1 (non-convex setting), the convergence results of Algorithm 1 demonstrate improvement under the assumption of function convexity (Assumption 1.2 with µ 1-α = 0). Specifically, according to Theorem 3.2, random coordinate descent with order oracle (OrderRCD) requiresN = O(S α R 2 [1-α] /ε) iterations and T = Õ(S α R 2 [1-α] /ε) oracle calls to achieve the desired accuracy ε (where E [f (x N )] -f (x * ) ≤ ε). However, in cases where ∆ > 0, the condition for maximum noise remains unchanged compared to the non-convex setting. Furthermore, the iteration complexity N aligns with that of the first-order algorithm, (random coordinate descent (RCD) Nesterov, 2012) . Similarly, akin to Theorem 3.2, the convergence rate of gradient descent (Nesterov et al., 2018 , under assuming L smoothness and convexity) outperforms that of Algorithm 1. Moreover, when α = 0 (corresponding to a uniform distribution with probability p α (i) = 1/d), OrderRCD (like all coordinate methods) necessitates d times more iterations than gradient descent. Concerning oracle complexity T , a logarithmic coefficient is evident, correlating with the number of oracle calls per iteration of Algorithm 1, line 2. For a comprehensive proof of Theorem 3.2, refer to Appendix D.2.In this section we consider case when function is strongly convex (see Assumption 1.2, µ 1-α > 0). Theorem 3.3 (strongly convex). Let function f (x) satisfies Assumption 1.1 (L-Smoothness) and Assumption 1.2 (convexity, µ 1-α > 0), then Algorithm 1 with oracle (2) has a linear convergence rate:E [f (x N )] -f (x * ) ≤ 1 - µ 1-α S α N F 0 + 2S α ϵ µ 1-α + 2cS α Φ∆ µ 1-α ,where c is some constant, ϵ is the GRM accuracy (by function) and Φ = 1+ √ 5 2 is golden ratio.As depicted in Theorem 3.3 Algorithm 1 exhibits a linear convergence rate, achieving the desired accuracy ε in N = O S α /µ 1-α log 1 ε iterations and T = Õ S α /µ 1-α log 1 ε oracle calls. Furthermore, there's an enhancement in the maximum noise level ∆, reaching ∼ µ 1-α ε. It's notable that a weaker strong convexity condition was employed in the proof of Theorem 3.3 (see Appendix D.3):∥∇f (x)∥ 2 [1-α] ≥ 2µ 1-α (f (x) -f (x * )), ∀x ∈ R d .(5)This condition (in the case α = 1), also known as the Polyak-Lojasiewicz or Gradient-dominated functions condition Polyak (1963); Lojasiewicz (1963) ; Karimi et al. (2016) ; Belkin (2021) , encompasses a broad class of functions: convex functions, strongly convex functions, sum of squares (e.g. where considering a system of non-linear equations), invex and non-convex functions, as well as over-parameterized systems. Also it is shown in Yue et al. (2023) that non-accelerated algorithms (like Algorithm 1) are optimal for L-smooth problems under the Polyak-Lojasiewicz condition (5).High probability deviations bounds. Given that OrderRCD method in strongly convex setting demonstrates a linear convergence rate and employs a randomization in coordinate selection, we can derive exact estimates of high deviation probabilities using Markov's inequality Anikin et al. (2015) :P f (x N (εσ) ) -f * ≥ ε ≤ σ E f (x N (εσ) -f * εσ ≤ σ. 
accelerated method: 
 Random coordinate descent with order oracle (OrderRCD) demonstrates efficiency in the class of coordinate methods. The number of iterations N required to achieve the desired accuracy ε is fully identical to random coordinate descent (RCD), which is the best among the non-accelerated methods in this class, and are also not inferior to existing competitors with Order Oracle. This fact confirms that our proposed approach to developing a novel optimization algorithm is successful. However, Algorithm 1 is still not optimal because it belongs to non-accelerated algorithms. Nevertheless, Section 3 gives hope for the possibility of acceleration among algorithms using the oracle concept (2).In this section, we demonstrate on the example of the strongly convex (Assumption 1.2 is satisfied with constant µ 1-α > 0) problem (1) that acceleration in the class of optimization algorithms using the Order Oracle (2) exists! For simplicity, we consider the case when ∆ = 0.Our approach to creating an accelerated algorithm closely mirrors the one proposed in Section 3, which involves adapting an existing optimization method (from the class of coordinate algorithms) to the Order Oracle using linear search method (namely, golden ratio method, GRM). Among the accelerated algorithms in the class of coordinate descent, two stand out: (accelerated coordinate descent method (ACDM), Nesterov and Stich, 2017) and (accelerated coordinate descent method with non-uniform sampling (NU-ACDM), Allen-Zhu et al., 2016) . These algorithms boast the same convergence rate and are considered among the best available today. Therefore, we select one of them (specifically, ACDM) as the base algorithm to adapt to our oracle concept (2). At each iteration, the ACDM, given parameters such as α k , β k , a k+1 , A k+1 , B k+1 , Lipschitz coordinate constant L i , strong convexity µ 1-α , distribution p β (i), and a starting point x 0 = z 0 , proceeds as follows:EQUATIONEQUATIONwherew k = (1 -β k )z k + β k y k .Looking at the x k+1 update (6), it seems that it should not be difficult to determine the step size 1/L i k and the value of the gradient coordinate ∇ i k f (y k ) using a linear search, as demonstrated in Algorithm 1. However, substituting the same η k instead of 7) isn't straightforward. The step with linear search is larger than the original step of (1/L i k )∇ i k f (y k ), potentially leading to a paradoxical situation where the step worsens with linear search. This is because there is no guarantee that the function f is monotonically decreasing along the sequences {z k } ∞ k=0 and {x k } ∞ k=0 Nesterov (1983) . Nevertheless, we have successfully addressed this challenge and we are ready to present the first accelerated algorithm utilizing only the Order Oracle: the accelerated coordinate descent method with order oracle.(1/L i k )∇ i k f (y k ) into the z k+1 update (It is evident from Algorithm 2 that the challenge was addressed by incorporating a secondary linear search, ensuring that the update step in z k+1 with linear search is at least as effective as (7). However, unlike Algorithm 1, OrderACDM cannot be deemed fully adaptive as it necessitates knowledge of the strong convexity constant µ 1-α and the Smoothness constant L i (which disappears in the case where α = 0). Despite this, we are ready to present the main advantage Algorithm 2 Accelerated Coordinate Descent Method with Order Oracle (OrderACDM)Input: x 0 = z 0 ∈ R d , R α (L), A 0 = 0, B 0 = 1, β = α 2 for k = 0 to N -1 do 1. choose active coordinate i k = R β (L) 2. find parameter a k+1 from a 2 k+1 S 2 β = A k+1 B k+1 , where A k+1 = A k + a k+1 and B k+1 = B k + µ 1-α a k+1 3. α k ← a k+1 A k+1 4. β k ← µ1-αa k+1 B k+1 5. y k ← (1-α k )x k +α k (1-β k )z k 1-α k β k 6. compute η k = argmin η {f (y k + ηe i k )} via (GRM) 7. x k+1 ← y k + η k e i k 8. w k ← (1 -β k )z k + β k y k + a k+1 L α i k B k+1 p β (i) η k e i k 9. compute ζ k = argmin ζ {f (w k + ζe i k )} via (GRM) 10. z k+1 ← w k + ζ k e i k end for Return: x N of Algorithm: Faster convergence rate of Accelerated Coordinate Descent Method with Order Oracle. Theorem 4.1. Let function f (x) is strongly convex (Assumption 1.2), L-Smoothness (Assumption 1.1) and L [1-α] -Smoothness † , then Algorithm 2 (OrderACDM) with oracle (2) guarantees an error E [f (x N )] -f (x * ) ≤ 1 - √ µ 1-α S α/2 N F 0 ,whereF 0 = f (x 0 ) -f (x * ), S α/2 = d i=1 L α/2 i .Compared to the results of Section 3, the convergence rate demonstrated in Theorem 4.1 is superior, confirming the potential for acceleration in algorithms utilizing the Order Oracle. To achieve the desired accuracy ε, Algorithm 2 (OrderACDM) requiresN = O S α/2 / √ µ 1-α log 1 ε iterations † We assume that for any x, y ∈ R d it holds: f (y) ≤ f (x) + ⟨∇f (x), y -x⟩ + L [1-α] 2 ∥y -x∥ 2 [1-α] .and T = Õ S α/2 / √ µ 1-α log 1 ε oracle calls, significantly outperforming existing competitors that utilize the Order Oracle (see Table 1 ). One notable difference from Algorithm 1 is selection of the active coordinate i = R β (L), where β = α/2. This choice aims to eliminate dimensionality d from the iteration and oracle complexities derived in Lee and Sidford (2013), since S α/2 ≤ √ dS α . A detailed proof of Theorem 4.1 is given in Appendix E. 
stochastic order oracle concept: 
 This section is devoted to an equally important concept of the Order Oracle (2), namely its modification to the stochastic case, where the values of two functions on one realization ξ are compared:EQUATIONFor simplicity, we assume that the oracle ( 8) is not subject to adversarial noise. This oracle concept can also be motivated by the creation of an ideal chocolate only for a group of people on average. That is, in this concept the ξ-th realization of the function can be understood as the ξ-th individual of group.To address the stochastic black-box optimization problem (1) when only the Order Oracle ( 8) is available, we provide the first optimization algorithm that uses exactly the stochastic oracle concept (8):EQUATIONwhere γ k > 0 is a smoothing parameter, e k ∈ S d (1) is a vector uniformly distributed on the Euclidean sphere. In order to proceed to convergence guarantees of this method (9), we use the auxiliary results.Lemma 5.1. Let function f be L-smooth ‡ , γ k = ∥∇f (x k ,ξ k )∥ √ dL, e k ∈ S d (1), then the following holds:ϕ(x k + γ k e k , x k -γ k e k , ξ k )e k = sign [⟨∇f (x k , ξ k ), e k ⟩] e k .Now using Lemma 5.1 we show how our algorithm (9) with oracle ( 8) is related to normalized SGD. Lemma 5.2. Let vector ∇f (x, ξ) ∈ R d and vector e ∈ S d (1), then with some constant c we haveE e [sign [⟨∇f (x, ξ), e⟩] e] = c √ d • ∇f (x, ξ) ∥∇f (x, ξ)∥ .As Lemma 5.2 shows, the direction in which a step is taken in Algorithm ( 9) is the direction of normalized stochastic gradient descent. Given this fact and based on the work of Polyak and Tsypkin (1980) we can provide asymptotic convergence for the first algorithm using the oracle concept (8). Theorem 5.3 (Asymptotic convergence). Let the function f be a L-smooth and e k ∈ S d (1), then for the algorithm (9) with step sizeη k = η/k the value √ N (x k -x * ) is asymptotically normal: √ N (x k -x * ) ∼ N (0, V ),where the matrix V is as follows:V = η 2 d 2η(1 -1/d) c √ d α∇ 2 f (x * ) -I -1 , α = ∥z∥ -1 dP (z) < ∞, 2η(1 -1/d) c √ d α∇ 2 f (x * ) > I (where I is unit matrix).For a detailed proof of Theorem 5.3, including a consideration of auxiliary Lemmas, see Appendix F.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [No] Justification: We believe that the presented experiments contain well-described information that allows us to implement the code on ourselves without difficulty. However, if the Reviewers or Area Chair feel that the information provided is not sufficient for reproducibility of the experiments, we will certainly add a link to an anonymous repository with the code.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussion: 
 In Section 3, we showed that such a multidimensional optimization problem (1) can be solved using Algorithm 1, which utilizes only comparative information. The fact that such an algorithm exists is not surprising, but the fact that it is as good as other methods with this oracle or first-order algorithms (in the class of coordinate algorithms) is positive news that allows us to think about the optimality of the algorithm. In the Subsection 3.3, we showed that when the Polyak-Lojasiewicz condition ‡ We assume that for any x, y ∈ R d it holds:f (y, ξ) ≤ f (x, ξ) + ⟨∇f (x, ξ), y -x⟩ + L 2 ∥y -x∥ 2 .is satisfied, we can perhaps consider that OrderRCD has optimal iteration complexity (see, Yue et al., 2023) . However, when the other conditions are satisfied, this is not the case, since Algorithm 1 belongs to non-accelerated algorithms. Therefore, we believe that Section 4 provides a vector for the development of the question of optimality by showing an OrderACDM, which can perhaps be considered optimal in terms of iteration complexity. However, in the case of a low-dimensional problem, we can take a "Private communication" approach proposed Yurii Nesterov (for a more detailed description, see Appendix G) to create a more efficient algorithm using only oracle (2).Before move to the numerical experiments, it's important to note that accelerated Algorithm 2 employs the golden ratio method (GRM) twice per iteration. This might raise concerns about its computational efficiency. However, in practice, we found that OrderACDM converges efficiently, comparable to the first-order algorithm, even when utilizing the golden ratio method only once. For a detailed analysis of the numerical experiments, refer to next Section 7 and Appendix B.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: In both the main Section 7 and the supplementary Section (Appendix B), we have provided experiments with detailed information including, for example, parameter values, adversarial noise function, etc.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
numerical experiments: 
 In this section, we investigate the performance of the proposed algorithms in the corresponding Sections 3 and 4 on a numerical experiment. We compare OrderRCD (see Algorithm 1) and OrderACDM (see Algorithm 2), which utilize deterministic oracle concept (2) with existing firstorder state-of-the-art algorithms. The goal is to highlight our theoretical results.The optimization problem (1) has a standard quadratic form:min x∈R d f (x) := 1 2 ⟨x, Ax⟩-⟨b, x⟩+c, where A ∈ R d×d , b ∈ R d ,and c ∈ R. We use a uniform distribution (α = 0) to choose the active coordinate, then the distribution (4) has the following form: p 0 (i) = 1/d. For such a problem, the assumptions of L-Coordinate-Lipschitz smoothness (Assumption 1.1) and µ 1-α -strong convexity (Assumption 1.2) are satisfied, where L i = A ii . In all experiments, we employ the golden ratio method (GRM) to solve the linear search problem with a precision of ϵ = 10 -8 . In Figure 2 , we compare the convergence random coordinate descent with order oracle (OrderRCD) and accelerated coordinate descent method with order oracle (OrderACDM) with the SOTA non-accelerated algorithms: random coordinate descent (RCD) from Nesterov (2012) , as well as gradient descent (GD). Non-accelerated coordinate algorithms, both for first-order oracle (RCD) and for our oracle concept (OrderRCD), are observed to lag behind gradient descent, confirming our theoretical derivations in Section 3. Interestingly, the random coordinate descent with order oracle even outperforms its first-order counterpart, despite the limitations associated with oracle usage (only Order Oracle (2) available). This observation can be attributed to the adaptiveness of Algorithm 1, as OrderRCD employs an exact step in the steepest descent direction obtained using the golden ratio method (GRM) at each iteration. Additionally, we can observe perhaps the most significant result demonstrated in Figure 2 : acceleration in our oracle concept (2) exists! We see that accelerated coordinate descent method with order oracle outpaces the convergence speed of all non-accelerated algorithms, including first-order coordinate (RCD) and full-gradient (GD) methods. In this experiment, OrderACDM was implemented using the method described in Algorithm 2 with ζ k = 0 (i.e., with one golden ratio method); RCD and GD used a constant step size, specifically 1/L i and 1/L.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This work does not have a negative social impact Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
conclusion: 
 We proposed a new approach to design optimization algorithms using only the deterministic concept of Order Oracle (2) by providing theoretical guarantees (showing SOTA results up to logarithm factor) for non-accelerated algorithms in non-convex, convex and strongly convex settings. We also discussed under which condition the Algorithm 1 is optimal (under the Polyak-Lojasiewicz condition). Using the proposed approach, we have shown that acceleration in the deterministic concept of the Order Oracle exists, thereby opening up a whole range of potential research. Furthermore, we have shown how the evaluation of the accelerated algorithm (so still convex tuning) can be improved by considering lowdimensional problems. Moreover, we provided first-of-its-kind theoretical guarantees for an algorithm utilizing the stochastic concept of Order Oracle (8). Finally, we demonstrated the effectiveness of the proposed algorithms (OrderRCD and OrderACDM) on numerical experiments, thereby validating the theoretical results. We provided practical recommendations for implementation of these algorithms. In this Section, we would like to emphasize the motivation behind the problem statement discussed in this paper. In particular, we would like to demonstrate the applicability of this work. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Presented research doesn't need safeguards Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All the used assets are cited Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA] Justification: This work provides as new assets unique theoretical results that are verified by numerical experiment. If necessary, we will provide a code license after acceptance of the paper Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used.  
 
 Appendix: As already demonstrated in Section 1 (Introduction) with the example of chocolate, the deterministic concept of the Order Oracle has many potential applications. However, this research was initiated due to a challenge one of the co-authors faced during the realization of a startup: the creation of an ideal coffee machine that can make the perfect drink for each customer. This startup has just started its life cycle. At the moment we have designed a coffee machine that is functioning at the testing stage (see the photo of the machine in Figure 3 and the 3D model in Figure 4 ). Figure 4 : 3D model of a smart coffee machine.Brief description of the coffee machine. A coffee machine that can make the perfect coffee. By varying the proportions of strong Robusta beans, which give a bitter "Starbucks flavor", and mild Arabica beans, we can find the perfect level of bitterness and coffee strength. By varying the amount of milk and cream we can find the right level of milkiness and fat content. We can also adjust the amount of other ingredients such as sugar, ice, lemon juice, chocolate, different syrups to make sure that the customer will definitely like this coffee.A.2 Order Oracle: a zero-order oracle close to realityIn this Subsection, we would like to show that the oracle concept considered in this paper is perhaps the closest to reality. In this paper we consider a concept of zero-order oracle: the Order Oracle (2), which is even closer to reality, where even the function value is not available to us, but only the order between two functions (the possibility to compare). Moreover, we take into account the presence of noise (which seems to be natural in applied realities) in such an oracle.A.3 Why is a convex/concave function being considered?In this Subsection, we would like to emphasize the organicity of considering the convexity/concave assumption of the objective function of the original problem (1)."In terms of the law of diminishing utility, the utility function is a concave function in ordinary coordinates:" In economic science there is a concept of "utility". Usually this term is used when describing a consumer who makes a set of several goods (like a basket in a supermarket). Each such set has some utility for the consumer, and he tries to maximize it. We do not consider a consumer who makes a set of goods, but a consumer who makes the goods themselves from a set of their characteristics. We believe that here the consumer is already maximizing a "preference function" to emphasize the difference with the "utility function". For convenience, we consider all characteristics to be useful (the larger the diagonal of the TV set, the more the consumer likes it). "Harmful" characteristics, such as price, we simply replace with the inverse, because the inverse price 1/p will already be useful (among goods with the same characteristics, it is logical to assume that the consumer will choose the cheaper one). Gossen's first law sounds as follows: "The magnitude [intensity] of pleasure decreases continuously if we continue to satisfy one and the same enjoyment without interruption until satiety is ultimately reached" Kurz (2016). It is more commonly referred to as the law of diminishing marginal utility of goods. The decreasing marginal utility of a good actually means that the derivative or gradient of the utility function decreases as the quantity of the "useful attribute" increases. This leads us to the concavity of the utility function. It is therefore natural to assume that the "preference function" will also be concave.In this Section, we provide additional experiments that solve the problem discussed in Section 7. We also give practical recommendations for implementing the accelerated Algorithm 2 in practice.In Figure 5 , we investigate effect of adversarial noise δ(x, y) from deterministic oracle concept (2) on a random coordinate descent with order oracle (OrderRCD). We used (δ(x, y) = ∆ • cos x • sin y) as the adversarial deterministic noise, where ∆ (s.t. |δ(x, y)| ≤ ∆) is the maximum noise level. In Figure 5 , we see that the adversarial noise justifies its name as it accumulates over iterations. In addition, we observe that the convergence of the non-accelerated coordinate method depends directly on the maximum noise level ∆, namely, the lower the noise level, the more accurately the algorithm converges. And finally we see that our theoretical results from Section 3 are confirmed, which indicate that the asymptote to which the algorithm converges can be controlled by the maximum noise level ∆, for example, in this case, when α = 0, the condition for achieving the desired accuracy ε looks as follows: ∆ ≤ µ 1-α ε/d. Or we can rephrase this condition: the OrderRCD has a linear convergence rate to the asymptote depending on level noise ∆. In Figure 6 , we illustrate the advantage of employing Algorithm 2 with one method of line search (ζ k = 0). We can observe that the method proposed in Section 4, the accelerated coordinate descent with order oracle (OrderACDM with two GRM), indeed qualifies as accelerated (thus affirming the theoretical findings of Section 4) as it outperforms gradient descent (GD), which can be considered a boundary between non-accelerated and accelerated coordinate methods. However, this algorithm significantly lags behind the accelerated coordinate descent method (ACDM, Nesterov and Stich, 2017) . The reason may be the delayed momentum effect caused by using the golden ratio method (GRM) a second time (see line 10 of Algorithm 2). Addressing this may involve utilizing the golden section method only once per iteration in Algorithm 2 (that is, substitute ζ k = 0 into line 10). Indeed, we observe that when using the golden section method once per iteration in Algorithm 2, the OrderACDM enhances convergence rate and does not fall behind its first-order counterpart (ACDM) which confirms our theoretical results. That is why we recommend to utilize in practice accelerated coordinate descent method with order oracle (OrderACDM, see Algorithm 2) with only one the golden ratio method (GRM) per iteration.Technical Information. All experiments were performed on an INTEL CORE i5 2.10 GHz processor. The performance of each Figure depended on the particular algorithm, for example, gradient descent (GD) performed 40000 iterations in 0.1 second, while random coordinate descent (RCD) and accelerated coordinate descent method (ACDM) performed 40000 iterations in 0.2 seconds and 0.4 seconds respectively. But Algorithms 1 and 2 proposed in this paper, by virtue of using linear search at each iteration performed 40000 iterations in 02:02 minutes and 02:13 minutes respectively.In this section we provide auxiliary materials that are used in the proof of Theorems.Basic inequalities. For all a, b ∈ R d (d ≥ 1) the following equality holds:EQUATIONEQUATIONCoordinate-Lipschitz-smoothness. Throughout this paper, we assume that the smoothness condition (Assumption 1.1) is satisfied. This inequality can be represented in the equivalent form:EQUATION)whereL 1 , L 2 , ..., L d > 0 for any i ∈ [d], x ∈ R d and h ∈ R.Lipschitz-smoothness. To prove Theorem 4.1, we additionally assumeEQUATIONC.2 The Golden Ratio Method (GRM)Algorithms 1 and 2, presented in Section 3 and 4, respectively, use the Golden Ratio Method (GRM) at least once per iteration. This method utilizes the oracle concept (2) considered in this paper and has the following form (See Algorithm 3).Algorithm 3 Golden Ratio Method (GRM)1: Input: Interval [a, b] 2: Initialization: Choose constants ϵ > 0 (desired accuracy), put the constant ρ = 1 Φ = √ 5-1 2 3: y ← a + (1 -ρ)(b -a) 4: z ← a + ρ(b -a) 5: while b -a > ϵ do 6: if ϕ(y, z) = -1 then 7: b ← z 8: z ← y 9: y ← a + (1 -ρ)(b -a) 10: else 11: a ← y 12: y ← z 13: z ← a + ρ(b -a) 14:end if 15: end while 16: Return: a+b 2 We utilize the Golden Ratio Method to find a solution to the following one-dimensional problem:η k = arg min η∈R f (x k + ηe i k ).Using the well-known fact about the golden ratio method that GRM is required to do N = O log 1 ϵ (where ϵ is the accuracy of the solution to the linear search problem (by function)), we derive the following corollaries from the solution of this problem:• In Section 4 (Accelerated Algorithms), for simplicity, we consider the scenario when the Order Oracle (2) is not subject to an adversarial noise (∆ = 0) and the golden ratio method solves the inner problem exactly (ϵ ≃ 0). Then we can observe the following:EQUATION)• In Section 3 ("Non-Accelerated Algorithms"), we consider the scenario when the Order Oracle ( 2) is subjected to an adversarial noise (∆ > 0). Then from the convergence results ( by function) of the golden ratio method (GRM) we can observe the following:EQUATION)where c is some constant, ϵ is the GRM accuracy (by function) and Φ = 1+ √ 5 2 is golden ratio.It is worth noting that we consider convergence of the golden ratio in terms of function, because we assume that our Order Oracle may be subject to adversarial noise. If we talk about convergence by argument, there may be no convergence at all with a noisy concept of the Order Oracle. Thus, in the final corollary (15), we consider the scenario where adversarial noise accumulates over iterations, resulting in the following observation: the golden ratio method converges towards the O (∆) asymptote.In this section, we furnish the omitted proofs for the theorems presented in Section 3.From Assumption 1.1 we obtain:EQUATION)where η k = arg min η∈R f (x k + ηe i k ). We use this as follows:E [f (x k+1 )] -f (x k ) = E [f (x k + η k e i k )] -f (x k ) (4) = d i=1 p α (i) (f (x k + η k e i k ) -f (x k )) (16) ≤ - d i=1 p α (i) 1 2L i (∇ i f (x k )) 2 + d i=1 p α (i) (ϵ + cΦ∆) = - 1 2S α ∥∇f (x k )∥ * [1-α] 2 + ϵ + cΦ∆.Rearranging the terms and summing over all k, we haveN -1 k=0 1 2S α ∥∇f (x k )∥ * [1-α] 2 ≤ N -1 k=0 (F k -F k+1 ) + N -1 k=0 ϵ + N -1 k=0 cΦ∆ ≤ F 0 + F N + N ϵ + N cΦ∆ ≤ F 0 + N ϵ + N cΦ∆,whereF k = E [f (x k )] -f (x * ).Dividing both sides by number of iterations N , we obtain the convergence rate for the non-convex case:1 N N -1 k=0 ∥∇f (x k )∥ * [1-α] 2 ≤ 2S α N F 0 + 2S α ϵ + 2S α cΦ∆.This convergence results imply the existence of a point k ∈ [N ] where holds true:∥∇f (x k )∥ * [1-α] 2 ≤ O S α F 0 N + S α ϵ + S α Φ∆ .Then, achieving the desired accuracy ε, where ∥∇f(x k )∥ * [1-α] ≤ ε, requires N = O S α F 0 ε 2 , T = Õ S α F 0 ε 2iterations and oracle calls respectively, provided the maximum noise does not exceed ∆ ≲ ε 2 /S α .From Assumption 1.1 we obtain:EQUATIONwhere η k = arg min η∈R f (x k + ηe i k ). We use this as follows:EQUATION) Denote F k = E [f (x k )] -f (x *). Note that the above calculation can be used to show f (x k+1 ) ≤ f (x k ), then we haveEQUATIONwhere in ① we used Assumption 1.2 with µ 1-α = 0, and a new notation for convenience, which looks as followsR [1-α] = sup x∈R d :f (x)≤f (x0) ∥x -x * ∥ [1-α] .Then substituting ( 19) into ( 18) we obtain:F k+1 ≤ F k - 1 2S α R 2 [1-α] F 2 k + ϵ + cΦ∆.Rewriting this inequality, we obtain:1 2S α R 2 [1-α] F 2 k ≤ F k -F k+1 + ϵ + cΦ∆.Next, we divide both sides by F k+1 F k :1 2S α R 2 [1-α] • F k F k+1 ≤ 1 F k+1 - 1 F k + ϵ + cΦ∆ F k+1 F k .Using the fact that1 2SαR 2 [1-α] ≤ 1 2SαR 2 [1-α]F k F k+1 we obtain the following:1 2S α R 2 [1-α] ≤ 1 F k+1 - 1 F k + ϵ + cΦ∆ F k+1 F k .When summing over all kN -1 k=0 1 2S α R 2 [1-α] ≤ N -1 k=0 1 F k+1 - 1 F k + N -1 k=0 ϵ + cΦ∆ F k+1 F k ,we get:N 1 2S α R 2 [1-α] ≤ 1 F N - 1 F 0 + N (ϵ + cΦ∆) F N F N -1 ≤ 1 F N + N (ϵ + cΦ∆) F N F N -1 .Taking into account the fact that F N -1 = E [f (x N -1 )] -f (x * ) ≥ ε and rewriting the expression we obtain the convergence rate for the convex case:E [f (x N )] -f (x * ) ≤ 2S α R 2 [1-α] N + 2S α R 2 [1-α] ε (ϵ + cΦ∆) .Then, achieving the desired accuracy ε, whereE [f (x N )] -f (x * ) ≤ ε, requires N = O S α R 2 [1-α] ε , T = Õ S α R 2 [1-α]ε iterations and oracle calls respectively, provided the maximum noise does not exceed the following value∆ ≲ ε 2 /(S α R 2 [1-α] ).From Assumption 1.1 we obtain:EQUATIONwhere η k = arg min η∈R f (x k + ηe i k ). We use this as follows:EQUATIONBy strong convexity, we havef (x k ) -f (x * ) ① ≤ ⟨∇f (x k ), x k -x * ⟩ - µ 1-α 2 ∥x k -x * ∥ [1-α] (11) ≤ ∥∇f (x k )∥ * [1-α] • ∥x k -x * ∥ [1-α] - µ 1-α 2 ∥x k -x * ∥ [1-α] ≤ 1 µ 1-α ∥∇f (x k )∥ * [1-α] 2 ,where in ① we used Assumption 1.2 with µ 1-α > 0. Then, using this inequality in (21) we haveE [f (x k+1 )] -f (x * ) ≤ 1 - µ 1-α 2S α (f (x k ) -f (x * )) + ϵ + cΦ∆.Applying recursion we obtain a linear convergence rate:E [f (x N )] -f (x * ) ≤ 1 - µ 1-α 2S α N (f (x 0 ) -f (x * )) + 2S α ϵ µ 1-α + 2cS α Φ∆ µ 1-α .Then, achieving the desired accuracy ε, whereE [f (x N )] -f (x * ) ≤ ε, requires N = O S α µ 1-α log 1 ε , T = Õ S α µ 1-α log 1 εiterations and oracle calls respectively, provided the maximum noise does not exceed the following value ∆ ≲ µ 1-α ε/S α .Denoteω k = (1 -β k )z k + β k y k . Then y k = (1 -α k )x k 1 -α k β k + α k (1 -β k ) 1 -α k β k • ω k -β k y k 1 -β k = (1 -α k )x k + α k ω k 1 -α k β k - α k β k y k 1 -α k β k .Thus, in method we have the following representation:EQUATIONLet the solution of initial problem denote x * = x * = arg min x∈R d f (x), then from Assumption 1.1 we obtain:EQUATIONwhere in ① we used Assumption 1.2 with µ 1-α > 0.2 k = ∥z k -x * ∥ 2 [1-α] and ω k = (1 -β k )z k + β k y k ,then due to convexity of the norm function it follows:EQUATIONSubstituting ( 24) into ( 23) we obtainB k+1 r 2 k+1 (24) ≤ (1 -β k )B k+1 r 2 k + β k B k+1 ∥y k -x * ∥ 2 [1-α] - 2a k+1 p β (i k ) ∇ i k f (y k )e i k , ω i k k -x i k * + 2L α i k a 2 k+1 B k+1 p 2 β (i k ) (f (y k ) -f (x k+1 )) ① ≤ B k r 2 k + β k B k+1 ∥y k -x * ∥ 2 [1-α] - 2a k+1 p β (i k ) ∇ i k f (y k )e i k , ω i k k -x i k * + 2L α i k a 2 k+1 B k+1 p 2 β (i k ) (f (y k ) -f (x k+1 )) (4) ≤ B k r 2 k + β k B k+1 ∥y k -x * ∥ 2 [1-α] - 2a k+1 p β (i k ) ∇ i k f (y k )e i k , ω i k k -x i k * + 2L α i k a 2 k+1 S 2 β B k+1 L 2β i k (f (y k ) -f (x k+1 )) ② = B k r 2 k + β k B k+1 ∥y k -x * ∥ 2 [1-α] - 2a k+1 p β (i k ) ∇ i k f (y k )e i k , ω i k k -x i k * + 2a 2 k+1 S 2 β B k+1 (f (y k ) -f (x k+1 )) ,where in ① we use that (1-β k )B k+1 = B k+1 -σ 1-α a k+1 = B k , and in ② we use that α = 2β. Note that E [f (x k+1 )] = d i=1 p β (i)f (x k+1 ).Therefore, taking expectation we obtain:EQUATIONwhere in ① we use Assumption 1.2 with µ 1-α > 0 and in ② we use that a k+11-α k α k = a k+1 1- a k+1 A k+1 a k+1 A k+1 = A k+1 -a k+1 = A k . E B k+1 r 2 k+1 ≤ B k r 2 k + β k B k+1 ∥y k -x * ∥ 2 [1-α] + 2a k+1 ⟨∇f (y k ), x * -ω k ⟩ + 2a 2 k+1 S 2 β B k+1 (f (y k ) -E [f (x k+1 )]) ① = B k r 2 k + a k+1 σ 1-α ∥y k -x * ∥ 2 [1-α] + 2a k+1 ⟨∇f (y k ), x * -ω k ⟩ + 2a 2 k+1 S 2 β B k+1 (f (y k ) -E [f (x k+1 )]) (25) ≤ B k r 2 k + 2a k+1 f (x * ) -2A k+1 f (y k ) + 2A k f (x k ) ± 2A k f (x * ) + 2a 2 k+1 S 2 β B k+1 (f (y k ) -E [f (x k+1 )]) ② = B k r 2 k + 2a k+1 f (x * ) -2A k+1 f (y k ) + 2A k f (x k ) ± 2A k f (x * ) + 2A k+1 (f (y k ) -E [f (x k+1 )]) = B k r 2 k -2A k+1 (E [f (x k+1 )] -f (x * )) + 2A k (f (x k ) -f (x * )), where in ① we use thatβ k = σ1-αa k+1 B l+1, and in ② we use that a 2 k+1 S 2 β = A k+1 B k+1 . By summing over k we obtain:2 N -1 k=0 A k+1 (E [f (x k+1 )] -f (x * )) ≤ 2 N -1 k=0 A k (f (x k ) -f (x * )) + N -1 k=0 B k r 2 k - N -1 k=0 E B k+1 r 2 k+1 . 2A N (E [f (x N )] -f (x * )) ≤ 2A 0 (f (x 0 ) -f (x * )) + B 0 r 2 0 -E B N r 2 N .Using the known facts from Nesterov and Stich (2017) we can estimate the parameters A N and B N :A N ≥ 1 4µ 1-α (1 + γ) N -(1 -γ) N 2 ≥ 1 4µ 1-α (1 + γ) N -1 2 ≥ 1 8µ 1-α (1 + γ) 2N ≥ 1 8µ 1-α (1 + γ) N , B N ≥ 1 4 (1 + γ) N + (1 -γ) N 2 ,where γ = √ µ1-α 2S α/2 . Then using A 0 = 0 and B 0 = 1 we haveA N (E [f (x N )] -f (x * )) ≤ 2A 0 (f (x 0 ) -f (x * )) + B 0 r 2 0 -B N E r 2 N . ① ≤ 1 µ 1-α (f (x 0 ) -f (x * ) -⟨∇f (x * ), x 0 -x * ⟩) = 1 µ 1-α (f (x 0 ) -f (x * )) .Let's divide both parts by A N , then we have the convergence rate for accelerated methodE [f (x N )] -f (x * ) ≤ 1 µ 1-α A N (f (x 0 ) -f (x * )) ≤ 8(1 + γ) -N (f (x 0 ) -f (x * )) ≤ 8(1 -γ) N (f (x 0 ) -f (x * )) = 8 1 - √ µ 1-α 2S α/2 N (f (x 0 ) -f (x * )) .Then, achieving the desired accuracy ε, whereE [f (x N )] -f (x * ) ≤ ε, requires N = O S α/2 √ µ 1-α log 1 ε , T = Õ S α/2 √ µ 1-α log 1 εiterations and oracle calls respectively.In this Section, we give a proof of Theorem 5.3, which is based on the work of Polyak and Tsypkin (1980) . In order to take advantage of the above work, we need to show that our method ( 9) is a normalized stochastic gradient descent. Therefore, we will first prove two auxiliary Lemmas 5.1 and 5.2 showing that our algorithm is still a normalized stochastic gradient descent, and then proceed to the statement of the Theorem 5.3. Our reasoning in the Proofs of auxiliary Lemmas is similar to the work of Saha et al. (2021) .Lemma F.1. Let the function f be L-smooth (for all x, y ∈ R d it holds:f (y, ξ) ≤ f (x, ξ) + ⟨∇f (x, ξ), y -x⟩ + L 2 ∥y -x∥ 2 ), γ = ∥∇f (x,ξ)∥ √ dLand e ∈ S d (1), then the following holds:ϕ(x + γe, x -γe, ξ)e = sign [⟨∇f (x, ξ), e⟩] e.Proof. From the Assumption of L-smoothness of the function f we have:⟨∇f (x, ξ), γe⟩ - Lγ 2 2 ≤ f (x + γe, ξ) -f (x, ξ) ≤ ⟨∇f (x, ξ), γe⟩ + Lγ 2 2 ; -⟨∇f (x, ξ), γe⟩ - Lγ 2 2 ≤ f (x -γe, ξ) -f (x, ξ) ≤ -⟨∇f (x, ξ), γe⟩ + Lγ 2 2 .Subtracting the inequalities, we obtain|f (x + γe, ξ) -f (x -γe, ξ) -2γ ⟨∇f (x, ξ), e⟩| ≤ Lγ 2 .Consequently, if Lγ 2 ≤ γ| ⟨∇f (x, ξ), e⟩ |, we have that ϕ(x + γe, x -γe, ξ)e = sign [⟨∇f (x, ξ), e⟩] e.Let's analyse P e (Lγ ≤ | ⟨∇f (x, ξ), e⟩ |). It is known that for u ∼ N (0, I), e := u ∥u∥ is a vector uniformly distributed on the unit Euclidean sphere. Then the following is true:P e (| ⟨∇f (x, ξ), e⟩ | ≥ Lγ) = P u (| ⟨∇f (x, ξ), u⟩ | ≥ Lγ∥u∥) ≤ P u | ⟨∇f (x, ξ), u⟩ | ≥ 2Lγ d log 1/ β + P u ∥u∥ ≥ 2 d log 1/ β ≤ P u | ⟨∇f (x, ξ), u⟩ | ≥ 2Lγ d log 1/ β + β,where we used the well-known fact that ∀ β: P u ∥u∥ ≤ 2 d log 1/ β ≥ 1 -β. On the other hand, since ⟨∇f (x, ξ), u⟩ ∼ N 0, ∥∇f (x, ξ)∥ 2 , then for all γ > 0 we obtainP (| ⟨∇f (x, ξ), u⟩ | ≤ γ) ≤ 2γ ∥∇f (x, ξ)∥ √ 2π ≤ γ ∥∇f (x, ξ)∥ .Combining the inequalities, we have that ϕ(x + γe, x -γe, ξ)e = sign [⟨∇f (x, ξ), e⟩] e except with probability at mostinf β>0    β + 2Lγ d log 1/ β ∥∇f (x, ξ)∥    ≤ 3Lγ ∥∇f (x, ξ)∥ d log ∥∇f (x, ξ)∥ √ dLγ ① = 0 = β,where in ① we take γ = ∥∇f (x,ξ)∥ √ dL. Thus, given the condition on the smoothing parameter, the statement of the Lemma is satisfied with probability 1. Lemma F.2. Let vector ∇f (x, ξ) ∈ R d and vector e ∈ S d (1), then we haveE [sign [⟨∇f (x, ξ), e⟩] e] = c √ d • ∇f (x, ξ) ∥∇f (x, ξ)∥ ,where c ∈ [ 1 20 , 1] is some universal constant.Proof. Without loss of generality, we can assume ∥∇f (x, ξ)∥ = 1, as normalizing ∥∇f (x, ξ)∥ does not impact the left-hand side. First, let's demonstrate that E [sign [⟨∇f (x, ξ) , e⟩] e] = ζ∇f (x, ξ) for some ζ ∈ R. Consider the reflection matrix along ∇f (x, ξ) given by:P = 2∇f (x, ξ)∇f (x, ξ) T -I,and examine the random vector ẽ = P e. As you can see that sign [⟨∇f (x, ξ) , ẽ⟩] = sign 2 ∥∇f (x, ξ)∥ 2 ⟨∇f (x, ξ), e⟩ -⟨∇f (x, ξ), e⟩ = sign [⟨∇f (x, ξ), e⟩] .Since ẽ is also a random vector on the unit sphere, we then have E [|e 1 |] ≤ E [e 2 1 ] = 1 √ d .Let us prove a lower bound on ζ. If e were a Gaussian random vector with i.i.d. entries e i ∼ N 0, 1 d , then from the standard properties of the (truncated) Gaussian distribution we would obtain thatE [|e 1 |] = 2 πd. For e uniformly distributed on the unit sphere, e i is distributed like u1 ∥u∥ , where u is Gaussian with i.i.d. entries N 0, 1 d . We then can write:P |e 1 | ≥ v √ d = P |u 1 | ∥u∥ ≥ v √ d ≥ P |u 1 | ≥ 1 √ d and ∥u∥ ≤ 1 v ≥ 1 -P |u 1 | ≥ 1 √ d -P ∥u∥ > 1 v .Since u 1 √ d is a standard Normal, we obtainP |u 1 | ≥ 1 √ d = P -1 < u 1 √ d < 1 ≤ 0.7,and since E ∥u∥ 2 = 1, the application of Markov inequality gives:P ∥u∥ > 1 v = P ∥u∥ 2 > 1 v 2 ≤ v 2 E ∥u∥ 2 = v 2 .For v = 0.25, this means that P |e 1 | ≥ 0.25√ d ≥ 0.2, whence ζ = E [|e 1 |] ≥ 1 20 √ d.Now that we have shown that our method ( 9) is a normalized stochastic gradient descent, then by applying Theorem 2 of Polyak and Tsypkin (1980) , and refining Theorem 2 to the case of normalized SGD, where in our caseR(x) = E [ϕ(x + γe, x -γe, ξ)e] = E [sign [⟨∇f (x, ξ), e⟩] e] ① = c √ d E ξ ∇f (x, ξ) ∥∇f (x, ξ)∥ ② = c √ d φ(∇f (x) + z)dP (z) = c √ d ψ(∇f (x)),where in ① we used the Lemma 5.2, and in ② we defined a function φ(z) = z ∥z∥ and used that ∇f (x, ξ) = ∇f (x) + ξ. Thus, using the followingR ′ (x * ) = c √ d ψ ′ (0)∇ 2 f (x * ) = c √ d ∇φ(z)dP (z)∇ 2 f (x * ) = 1 - 1 d c √ d ∥z∥ -1 dP (z) α ∇ 2 f (x * )and η k = η k , we obtain the sought statement of Theorem 5.3, which guarantees asymptotic convergence. 


Decision: This paper formalizes an 'OrderOracle' model for function optimization where the function values or gradients are not available, and just comparison queries between function values at different points are permitted. The paper presents new optimization algorithms under this model and importantly, gives the first algorithm to achieve acceleration in this model.
The reviewers were split on how surprising the results in the paper are, but I think the model and the results (establishing that one could achieve essentially the convergence rates of randomized coordinate descent, without needed exact function values or gradients) are interesting, and I merit acceptance.

Reviews: review: paper_summary: paper_summary: This paper explores the use of a zero-order oracle called the Order Oracle to solve optimization problems where exact objective function values are unknown. This oracle focuses on comparing the order of objective function values rather than requiring exact values.  The authors propose new non-accelerated algorithm, OrderRCD, that integrate the Order Oracle into coordinate descent algorithm and achieves performance comparable to state-of-the-art methods in non-convex, convex, and strongly convex settings. This involves randomly selecting coordinates and performing linear searches to find optimal step sizes. They also  present an accelerated optimization algorithm called OrderACDM, which uses two linear searches in each iteration to adaptively determine optimal step sizes. They show faster convergence rates and improved efficiency in strongly convex setting. The paper extends the concept to stochastic settings, showing asymptotic convergence. Numerical experiments validate the theoretical results, demonstrating that OrderRCD performs comparably to traditional methods, while OrderACDM converges faster, outperforming other methods.
strength_weakness: strength_weakness: 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.
questions: questions: 1. Could you provide more specifics about the numerical experiments?
2.  Could you show numerical validation in real-world problems and datasets?
3. Are there any experiments being conducted for the stochastic order oracle? Could you show the results in that setting?
limitations: limitations: 1. The theoretical guarantees  rely heavily on the assumptions of strong convexity of the objective function. These assumptions may not hold for all types of optimization problems, limiting the applicability of the proposed methods to broader, less structured scenarios.
2. The paper does not provide practical demonstrations on large-scale, high-dimensional datasets. Additional experiments on a diverse set of objective functions and real-world datasets would provide a more comprehensive validation of the algorithms' performance and robustness
3. The accelerated version requires updating multiple parameters and has multiple steps and iterative processes that potentially increase the computational load.
4. In large-scale problems with high-dimensional data, the computational overhead from linear searches, parameter updates, and coordinate selections can become significant. The scalability of the algorithm is thus a concern, and its performance may degrade as the problem size increases.
paper_summary: paper_summary: The paper considers the “Order Oracle” for optimization, which does not require the function values or gradient information, but only the relative ordering of the function values at different points. This can also be done with some small noise. This model captures the challenges encountered in real-world black box optimization problems and the authors motivate it via the ongoing developments in generative models. The main contributions of the paper are:

 1. The paper provides SOTA convergence results up to log factors for deterministic algorithms with order oracle in the non-convex, convex and strongly convex settings.
2. The paper shows that acceleration in such an oracle is possible by giving an algorithm for strongly convex functions. They further show that the convergence results can be improved when the problem is low dimensional and compare it to the ellipsoid method.
3. The paper gives a stochastic version of the algorithm.

The accelerated and unaccelerated algorithms are inspired by coordinate descent methods. The method is essentially coordinate descent where the step size is chosen via a specific line search procedure (golden ratio method) which is implemented using the order oracle.

For the accelerated algorithm, the authors need to include a secondary line search to ensure that the iterates are always making progress.
strength_weakness: strength_weakness: 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.
questions: questions: 1. When you say adaptive in the text, what does that mean?
2. 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?
3. What is the notation with $\alpha$?
4. Are there examples (even experiments) that can say something about the difference between the order oracle and usual first order oracles?
5. In the accelerated algorithm, are there adversarial examples where the second line search is necessary?
6. What is the barrier in extending the acceleration beyond strongly convex objectives.
limitations: limitations: The paper considers a weaker oracle model than what is usually considered in standard optimization results and gives algorithms under this oracle. It is not clear what the limitations of the oracle are from the paper, but the results match the ones obtained via stronger gradient oracles.
paper_summary: paper_summary: this paper focuses on solving the black-box optimization problem with order oracle method. specifically, the author provided a non-accelerated deterministic optimization algorithm, which relies on weighted sampling of the coordinate and the GRM method to resolve a linear search subproblem. the author provided convergence analysis on non-convex, convex and strongly convex cases and showing a superior iteration complexity. the author further an accelerated method called OrderACDM and proved its linear convergence. the stochastic case is discussed with asymptotic convergence results. Finally, the author provided a very simple numerical experiments to show the advantages of the proposed algorithms.
strength_weakness: strength_weakness: 1. i have some concerns on the novelty of this paper. in the non-accelerated algorithm, the two main techniques (the weighted sampling and the GRM) are not new. and the accelerated algorithm closely follows ( Nesterov and Stich, 2017).
2. both of the proposed algorithms are double loop algorithms as in each iteration, a linear search sub-problem is solved by GRM. as the author mentioned, GRM requires O(log 1/eps) iterations, which should be considered significant especially in the case of strongly convex problem. the author is hiding this factor with \tilde{O} in table 1, which makes the comparison unfair.
3. the numerical experiment is too simple. i understand this is a theoretical paper, but the experiments on a toy example is still below the bar of acception. 
4. in the accelerated case, it's not clear to me how the proposed algorithm is compared with  (ACDM), Nesterov and Stich, 2017) and (NU-ACDM), Allen-Zhu et al., 2016). the proposed algorithm looks slower to me since it is double loop. i would suggest the author to add more discussions on the convergence results.


minor issues:

1. line 77, missing something after "to the inner product as.." ?
2. line 78, L_i appears before it is defined.
3. table 1, many parameters appear before they are defined.
questions: questions: 1. in assumption 1.1, can L-coordinate-Lipschitz suggest L-smooth?
limitations: limitations: see above
paper_summary: paper_summary: This paper addresses challenges in black-box optimization by introducing the concept of an Order Oracle. This oracle compares function values without assuming access to their actual values, allowing for the creation of new optimization algorithms. The paper proposes both deterministic and stochastic approaches, achieving SOTA convergence results and demonstrating the effectiveness of these algorithms through numerical experiments.
strength_weakness: strength_weakness: 1. Elaboration on Motivation: While the setting of the problem is interesting, the motivation for addressing this particular problem could be further elaborated, especially in the introduction. Providing a more detailed context and explanation of the significance and potential impact of solving this problem would help readers better understand its importance.

2. Comprehensive Experimental Validation: The experimental validation appears less comprehensive, as it relies on only one simple function. It would be much more convincing to apply the proposed method to the motivating problem outlined in the introduction. This would demonstrate the method's practical applicability and robustness in a real-world scenario.

3. Performance in High-Dimensional Space: I am curious about the performance of the proposed method in high-dimensional space, as this is often a significant challenge for coordinate descent methods. Could the author provide more insights or experimental results that address this aspect? If there are inherent limitations related to high-dimensional settings, it would be beneficial to discuss and highlight these issues. Providing such information would offer a clearer understanding of the method's strengths and potential limitations.
questions: questions: 1. Technical Challenges compared to Nesterov's 2012 Work: I am curious about the specific technical challenges involved in the proof, especially in relation to extending and building upon Nesterov's 2012 work. Could the author provide more detail on the difficulties encountered and the novel techniques or modifications that were necessary to address these challenges?

2. Dimension-Independent Complexity: I notice that the paper presents a dimension-independent ($d$) complexity in comparison with existing works, as shown in Table 1. This is a significant and surprising result. Could the author elaborate more on this aspect? Specifically, I am interested in understanding the implications of achieving dimension-independent complexity. Or the dependence is manifested in some parameters.
limitations: limitations: The author could discuss the limitations in high-dimensional space if this is indeed a constraint of the proposed method.
paper_summary: paper_summary: In this paper the authors consider the problem of $\min_x f(x)$ with an order oracle that returns $sign (f(x)-f(y)+\delta)$ for some bounded noise $\delta$. The method is based on line search integrated with existing randomized coordinate update algorithms. Convergence rates on non-convex, convex, strongly convex objectives and its accelerated variant in the strongly convex case are provided. These are further extended to the stochastic setup $\min_x E_\zeta[f_\zeta (x)]$ with oracle $sign(f_\zeta(x)-f_\zeta(y))$ where a connection to normalized SGD is drawn and asymptotic convergence is derived. Numerical experiments are presented illustrating the performance of the proposed algorithms.
strength_weakness: strength_weakness: I don't think the analysis result of "the convergence rate of random coordinate descent with the order oracle (OrderRCD), assuming minimal noise, is equal to first-order method random coordinate descent (RCD)" is surprising, given the algorithm is searching for best (1D) stepsize for coordinate update. And in this regard, neither is the acceleration result based on existing algorithmic framework. I've listed my main questions in the section below and here are some minor comments: 

- Line 77 is not finished. Line 78: it would be more clear if one could put in the argument in the norm instead of $\|\cdot\|$, which presumably would be on $x$?

- It would be good to put the GRM in the main text otherwise Algorithm 1 does not make it clear how order oracle is used, which is the main focus of the paper.

- Line 179: I'd suggest using a different letter for line search accuracy instead of $\epsilon$, which was used for denoting desired precision of the final optimization problem elsewhere.

- In (8), it would be better to use the subscript $f_\zeta (x)$, which would make the notation more consistent with (1).
questions: questions: - Why is coordinate descent the best thing to do? To me, it seems like the order oracle is essentially a "noisy normalized gradient oracle". So while I can understand it is one way to incorporate the oracle information into existing method, is there any sense in which this is the optimal way to use this information? I think the paper will benefit from such a justification otherwise it seems rather ad-hoc. For example, why is coordinate update a good idea in this setup? Most zeroth-order methods do not seem to rely heavily on this (note that the oracle information is only used to select the stepsize in Algorithm 1).

- Algorithm 1 as stated works on deterministic objective, i.e., it is not exploiting any finite-sum-type structure. If parts of the result do not concern stochastic objective, the authors should redefine their problem statement in (1).

- The accelerated algorithm 2 has several loops, which makes me wonder how well it would be able to deal with noise in the oracle.

- Similarly in Section 5, these reductions to existing methods are useful for getting some convergence guarantees, but is there a way to see this is how one should use the information optimally?
limitations: limitations: Yes it's adequately addressed.

Comments: title: reply to authors
On the rebuttal
comment: Dear **Reviewer uSy5**,

We are grateful to the Reviewer for checking our responses and for raising the score! However, since there are still concerns about our work, we would like to provide detailed answers:

>**however, my main concern is still the design of the double loop algorithm that leads to an additional log factor**

The number of oracle calls per iteration possibly can be further reduced in log factor... However, **firstly**, such a method (for our oracle) is simply not known. And **secondly**, the total number of oracle calls (Order Oracle calls) may even be better with our approach, because the iterations number may become smaller due to one-dimensional searches. In any case, this is observed for accelerated methods with low-dimensional auxiliary searches (*by the way, note that our oracle could not be integrated into such methods!*): [1] (see experiments and references to other works at the end of the paper), and [2]. Nevertheless, we have shown in Figure 6 (see Appendix B) that using only the first linear search not only reduces computational resources but also improves convergence. Based on our observation, we may well expect as future results an improvement of our estimate by at least one logarithm.

>**and the experiments part. the author mentioned that they could add more practical experiment results. but those results may need another round of review in order to be considered.**

We would like to emphasize that our work is mainly theoretical. Our main results are four new algorithms: an unaccelerated and accelerated algorithm that uses a deterministic Order Oracle (see Section 3 and 4, respectively), the asymptotic convergence of an algorithm that already uses a stochastic Order Oracle (see Section 5), and finally an algorithm that shows how the convergence results of the accelerated algorithm can be improved given a low-dimensional problem (see Appendix G). All these results **individually open directions for future research**, showing an already complete and, more importantly, meaningful paper. However, we realize that our problem statement has many potential applications, so, as we said, we will definitely add experiments on a real-world problem (the smart coffee machine - a startup) but in Appendix (**since our results are fundamental and not limited to a startup**). Nevertheless, *we believe that our current experimental part is fully in the spirit of the theoretical work*.

Finally, we would like to thank the **Reviewer uSy5** once again for taking the time to check our responses. We hope that with this answer we have solved all the remaining concerns of the Reviewer. *However, if you have any further questions, we will be happy to answer them!*

[1] Guminov, S., Gasnikov, A., & Kuruzov, I. (2023). Accelerated methods for weakly-quasi-convex optimization problems. Computational Management Science, 20(1), 36.

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

Best regards, 

Authors
I thank the authors for addressing my questions and concerns. Now i agree that the main contribution in this paper is to deal with a special case where only the order of obj function values can be accessed. I have increased my score to be 5. however, my main concern is still the design of the double loop algorithm that leads to an additional log factor and the experiments part. the author mentioned that they could add more practical experiment results. but those results may need another round of review in order to be considered.
Dear **Reviewer WKzP**,

We thank you for taking the time to check our responses.

With Respect,

Authors
Dear **Reviewer XqbR**,

We thank you for checking our response and for the positive rating.

With Respect,

Authors
Dear **Reviewer K16N**,

We thank you for checking our response and for your very positive evaluation.

With Respect,

Authors
Thanks for the clarifications and answers to my questions! I hope the ones that are missing from the paper end up in the next version!
I appreciate the authors' thorough responses to my questions. After carefully reviewing their answers, I have no further questions at this stage and will provide my feedback to the AC in the next phase.
I thank the authors for their responses to my questions. I have read the responses carefully and I am inclined to retain my original scores. 
And also, it must be interesting to see the algorithm in action real time, all the best to the startup!
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
Thanks for the response and for explaining. 

I remain somewhat neural to the paper / contribution for the following reason: it is straightforward that given any random (i.e., importance-sampling type) coordinate algorithm, such as (3), a line search greedy step can only guarantee more progress, and it is because of the fact the algorithm is built on coordinate update that the 1D binary search is efficient. The same trick, of course, can be applied to coordinate-based accelerated method, which would now require knowledge of $L_i,\mu...$ to implement. 

There seems to be various hidden $d$ dependence in the $S$'s and $L_i$'s: There was a remark about "when the trace of the Hessian matrix has the same order as the largest eigenvalue, this dependence on $d$ is reduced" in which case the problem itself sounds like a 1D-ish problem to me. The methodology feels a bit like a tag-on to existing methods - I think the paper would benefit from a more thorough study of when/why this is the best "gradient estimator" vs. alternatives potentially using full-gradient-like information.