Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values
Authors: Aleksandr Lobanov
Alexander Gasnikov
Andrey Krasnov
Venue: NeurIPS 2024 poster (2024)
Keywords: Black Box Optimization
Order Oracle
Accelerated Algorithms
Asymptotic Convergence
Primary area: optimization

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.

Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values
Aleksandr Lobanov MIPT, Skoltech, ISP RAS lobbsasha@mail..
Alexander Gasnikov Innopolis, MIPT, MI RAS gasnikor@yandex.u ru
Andrei Krasnov MIPT, Innopolis krasnov krasnov. ant.yyeeh.d@yyttthcctu.
Abstract
Frequently, the burgeoning field 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 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-acceles non-accelerated optimization algo- rithms (obtained by integrating Order Oracle into existing optimization "tools") 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 Ora- cle up to logarithm factor. Moreover, using the proposed approach, we provide the first accelerated optimization algorithm using the Order Oracle. And also, using 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.
Introduction
The black box problem has garnered extensive attention in diverse scientific and engineering do- mains, reflecting the challenge of optimizing systems with complex and opaque objective functions, prompting the exploration of innovative solutions Conn al. (2009); Kimiaei and Neumaier (2022)
This paper focuses on solving a standard general optimization problem in the following form:
min (f(x)) == (E)) 2E24
where f dd R is a possibly non-convex. possibly stochastic function. This problem configuration encompasses broad range of applications in ML scenarios, empirical risk minimization, where D denotes distribution across training data points, and (x) represents loss of model on data point &.
When the objective function fx) has exclusive access to zero-order oracle Rosenbrock 1960).
problem (1) falls under the classification of black-box optimization problem. This class of problems actively studied in various application settings, e.g., deep learning Chen et al. (2017) Gao et al.
(2018). federated learning Dai al. 2020);] Alashqar al. (2023): Patel al. (2022), reinforcement
learning Choromanski et al. (2018) : Mania et al. (2018), overparameterizet models Lobanov and
Gasnikov (2023). online optimization (Agarwal et 2010 Bach and Perchet 2016 Akhavan et al.
2022). multi aedd bandits Shamir (2017); Lattimore and Gyorgy (2021). hyperparameter settings
Bergstra and Bengio (2012): Hernández-Lodd et al. (2014); Nguyen and Balasubramanian (2022). and control system performance optimization Bansal et al. (2017); et al. (2022). It is important to highlight that the zero-order oracle presupposes awareness the objective function's ''s value fxx) at specific point zą (which may be inexact), enabling the development of effective gradient-free algorithms tailored to various problem scenarios Gasnikov al. (2022a).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Comparison of oracle complexity for the methods proposed in this work with SOTA methods both in the coordinate descent class and the Order Oracle concept
2 Notation: Fg f(m)) f(x ); R
||x xt"
Ri)-a) Rí Ra-a (Zo) s
||
desired accuracy problem solving.
Reference
Nesterov
2012
Goebunov et al. 2019
Saha et al.
2021
Tang et al. 2023
This paper
Non- Non-convex
7*)
Bafat)
Convex
4ri Mill log
Strongly convex
Sem loy, Pi-n
Bo loy. M
y log.
log
Suiz loy, Vyrte
Order Oracle?
X
Accoleraion!
In this paper, consider concept of zero-order oracle, termed Order Oracle, address problem [ ((x y) = sign (f(x) (v) + 8(2,, v)],
where 18(z, v)1 < A is some bounded noise. The Order Oracle has the capability to compare two functions; however, in contrast to the zero-order oracle, lacks the ability to calculate closely mirrors the challenges encountered in real-world black-box optimization problems. The motivation for the proposed oracle concept becomes when considering the ongoing developments in generative models. Com- panies like Valio and SherAl have already embraced the active involve- ment of Al dessert creation. Notably, Valio, as illustrated in Figure M employed AI to determine the optimal concentration of milk for chocolate bars based on available data. However, envision a scenario where AI cre- ates customized chocolate for an individual by adjusting the concentration of ingredients. In such 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.
utilize the actual value of the objective function. This concept
evident
Figure I: Valio's chocolate
To address the initial deterministic problem (1) with the Order Oracle (2). we propose novel approach to algorithm design that uses class of coordinate descent methods (CD) Bubeck et al.) (2015) 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 ① with the Order Oracle, we propose an approach based on normalized SGD, providing asymptotic convergence.
1.1 Our contributions
More specifically, contributions are the following:
We provide novel approach to design algorithms for solving deterministic optimization problems (I) with Order Oracle (2) that achieves SOTA convergence results up to logarithm factor in the non-conver convex, and strongly convex settings (see Table Algorithm [
By using the approach proposed in this paper to create algorithms for solving deterministic optimization problem (T) with the Order Oracle (2). we have shown, on an example of strongly convex functions, that acceleration in such oracle concept exists (see Algo- rithm 2 and Theorem 4.1). Morcover, 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 I with the stochastic Order Oracle concept, where the order between two functions the same realization 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 (see Algorithm 2
"The picture is taken from the company's Official Website See more motivation in Appendix A

---

1.2 Main assumptions and notations
Before discussing related works, we present the notation and main assumptions we use in our work. Notation. We use (1, == Ei= Jits to denote standard inner product of z R. We denote Euclidean norm TR as || == V x²- In particular, this norm ||>||| := v (z, 2) is related the inner product. We use e; E RRd denote the i-th unit vector. We define the norms || == V a and [|=]|[a]] == VVVV 4. We denote by fz()) the full gradient of function f at point x E R4, and by V.f(a) the i-th coordinate gradient. The sum of constant L; denotes as S. := Σ T.. We use (r) == far Rdd |||]|| = r to denote Euclidean sphere. We use Ö.) to hide the logarithmic coefficients. We denote f := f(x as the solution initial problem. For all our theoretical results, we assume that f(x) is L.-smooth with respect to its i-th coordinate:
Assumption 1.1 (Smoothness). A function I Rd + R is L-coordinate-ippshitt for I1, 12,,. , La 0 if for any E [d], IRd and R the following inequality holds:
V.f(z + he.) v.f(x)) < L.lh).
The smoothness assumption of the function is widely used in the optimization literature (c.g. [oyyd and Vandenberghe 20044, Nesterov et al. 2018). However, Assumption I.Iis specific and frequently uti- lized in the context of optimization via the CD Lin et al. (2014); Zhang and Xiao (2017); Man gold et al. 2023). This assumption means that for every input point if we alter its i-th coordinate by at most h. then the corresponding gradient V. + he;) differs from (if(z) by at most L,, times [h].
Throughout this paper we assume that function fz) can be (strongly) convex w.r.t. the norm [-]]
Assumption 1.2. A function f F + IR is #1-a 2 0 strongly convex w.r.t. the norm Il-I| if for any y Id the following inequality holds:
((v) 2 (
+ (V)(x), x) P1-a 11y x 2
Many works in convex optimization rely on the (strong) convexity assumption, evidenced by references such as Duchi (0166); (Shi et al. (2019); Asi et (02T). Since our work employs norms [1-I|p-a] to derive theoretical estimates, Assumption 1.2 deviates slightly from the standard. However, this assumption of Mi (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 ja (strong) convexity via Euc lidean norm if o This assumption convex provided /4-a 0.
1.3 Paper organization
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 Then in Section[ 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 Section 5 In Section 6, we discuss the current results this work. Through numerical experiments in Section 7 we validate the theoretical results. While Section SaationSeen conocludes the paper.
2 Related Works
The literature in the field of optimization already extensive and continuously expanding, encom- passing various problem formulations and assumptions. In this section, we provide 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 BBergou 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 (dT./ y log 1/e). A little later, the authors Gorbunov et al. (2019) modified the Stochastic Three Points Method to the
3

---

case of importance sampling, improving the oracle complexity estimate in the strongly convex case O (S,//u log 1/E). Already in 2021. 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 (dT. pa log 1/e). The work of Tf[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/="). In this paper, we propose alternative approach for creating optimization algorithms (via line search method), which achieves SOTA convergence results with logarithm accuracy 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. foon-accelerated algorithms lypically converge at rates 1/e and 1/μ convex (μ = 0) and strongly convex (n > 0) cases, respectively, while accelerated algorithms achieve rates 1/vE
and 1/vp p in convex and strongly convex cases, respectively. This classification dates back to 1983 when Nesterov introduced the optimal convergence rates for first-order /letrithnssNestrrv (1983). However, the fundamental difference between coordinate descent and full- full-gradient descent lies 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-gradien descent. However, authors in Nesterov (2012) have shown that considering smoothness along the direction I, can improve the number of iterations
Nesterov
and O (Sa/Un-a log !) in convex and strongly convex cases, respectively, where O (S. RS. Ri--al- = suP ((t) || x= =="1|1 [1-]] for E [0, 1]. In the same paper Nesterov (011)). the authors demonstrated the potential for acceleration in coordinate descent through the scheme proposed in/eestervv (983). Subsequently, in Lee and (adiord((013) they analyzed and presented an accelerated version of coordinate descent (ACDM), along with the corresponding number of required and O ( (VdSa/M1-a log 2) 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-Zhh 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:
O (V
1./3 /S.22. In this paper, we propose a coordinate descent algorithm with an Order Oracle ( 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 Order Oracle, acceleration can be attained, resulting in the most favorable estimates on iteration complexity known to date.
3 Non-Accelerated Methods
In this section, we begin to present our main results, by introducing algorithms tailored to address the initial problem ( 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 crucial question. After careful consideration, determined that the coordinate descent method (CDM) is the most suitable candidate. each iteration, the CDM, given a step size ÇR 0 and starting point Zo Rdd, proceeds follows:
Ik+1
F& Se V., f(xe City
(3)
7/6
where is is the coordinate index drawn from [d]. Note that the coordinate descent method step (3) requires both a step size ÇN and a gradient coordinate value V., f which are scalars. Thus, by employing linear search уソ-- = arg min, ( (ar + ) at each iteration, we can optimally determine both the direction of steepest descent and the step size to traverse along this direction, resulting in fully adaptive algorithm. The next consideration is the strategy for coordinate selection at each itera-
tion. Following the trend initiated by Nesterov (2012). we use more general sampling distribution

---

than the uniform one, obtaining already random coordinate descent (RCD). Specifically, for a > 0, we assume that random generator R,, (L) independently selects ig. from the following distribution:
(i) = L; Sa. i E [d].
(4)
We are ready to introduce a method designed to solve problem utilizing the oracle concept
This algorithm falls under the category
of coordinate methods and is named Algorithm 1 Random Coordinate Descent with Order Ora- random coordinate descent with order cle (OrderRCD) oracle (OrderRCD), see Algorithm [ It should be noted that the inherent "stochasticity" of problem ( is artifi- cially induced by randomized procedure used to select the i-th coordinate (4). Here, ç denotes the i-th coordinate, and DD represents distribution (a.(i) from (
Input: zo E R random generator (L( for k to N 1 do 1. choose active coordinate i Ra
compute 77s argmin, ,, (f(r + tnc )} via (GRM)
3. F++1 + + Ci
end for Return: .N
The golden ratio method (GRM) serves as the linear search algorithm, which is where the Order Oracle is used. is known that GRM (which is described in Appendix C.2) requires N O (log 1/e) iterations to achieve the desired accuracy (in terms of function) of the solution to the linear search problem (namely, 7ı argmin, {.f (ar + })).
Next, present 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, strongly conver functions.
3.1 Non-convex setting
Theorem 3.1 (non-convex). Let function fix) satisfies Assumption 1.1 N is the number of iterations, Fo = f( - f(x"), ), then Algorithm (OdeeRRDD with oracle ② guarantees an error:
Σ (IV)(()))))))) s s So K=
N-1
+ S.E S.E+ S
N
N
where e is the accuracy of solving linear search problem by function and 4 1+55 golden ratio. 2
The convergence results of Theorem 3.1 imply the existence of a point E [N] where (I) (IVVf(=)))
< O Fo holds true. Additionally, Theorem 3.1 indicate that, to achieve the desired accuracy (according the gradient norm), Algorithm requires O Po/E²) iterations and T = Ô (S., Fo calls to the oracle 2 The maximum admissible noise level ensuring the desired accuracy should not exceed ~ e². Notably, the convergence rate of random coordinate descent with the order oracle (OrderRCD) assuming minimal noise (A e²), is equal to first-order method: random coordinate descent (RCD). It is also characteristic (within the coordinate methods class) to be inferior gradient descent (Ghadimi and Lan 2013 under smoothness as- sumption). For instance. in the case when = 1, the convergence rates O (LFo/ //) is better because L LS >' L, Not surprisingly, in terms of oracle complexity, Algorithm [ is logarithmically inferior to first-order algorithms. This discrepancy reflects the "cost" associated with employing GRM, where the Ô(-) to hide the logarithuicc coefficient representing the number of oracle calls in the GRM, contingent upon its accuracy detailed proof of Theorem 3.1 is given in Appendix D.
3.2 Convex setting
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 P1 = 0.
Theorem 3.2 (convex). Let function f(x) satisfies Assumption 1.1 (L-Smoothness) and Assump-
tion 1.2 (convexity, f1-a = 0), then Algorithm (OrderRCD) with oracle (2) guarantees an error:
Sa R2 Rl
25, R2 [-o) (E + +A)
E B[f(xN)] f(x)) so
FN-1
where is inner problem accuracy, R[1-o] sup | x" x²11 1111-a and +b 14v3
5

---

In comparison to Theorem 3.1 (non-convex setting), the convergence results of Algorithm T demon- strate 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 (OrderRCI) -
requires N = (S.. / iterations and T = ŌSS, R /) oracle calls to achieve the desired accuracy (where E. [f(=))) - f(x*) e). However, in cases where A > 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) Nes- terov 2012). Similarly, akin to Theorem 3.22 the convergence rate of gradient descent (Nesterov et al.
2018 under assuming L smoothness and convexity) outperforms that of Algorithm [ Moreover, when a = 0 (corresponding to uniform distribution with probability Pa. (i) 1/d), OrderRCD (like all coordinate methods) necessitates times more iterations than gradient descent. Concerning oracle complexity T, a logarithmic coefficient is evident, correlating with the number of oracle calls per
iteration Algorithm T
line For a comprehensive proof of Theorem 3.2 refer to Appendix D.2
3.3 Strongly convex setting
In this section we consider case when function is strongly convex (see Assumption 1.2
0).
Theorem 3.3 (strongly convex). Let function f(x) satisfies Assumption 1.1 L-Smmothness) and
Assumption 1.2 /convexity, P1-a 0), then Algorithm with oracle (2) has a linear convergence rate:
[[f(ZN)] - f(x))= &
141a Sa
N
Fo +
25.c
+
2cS. $2
P1-a
P1-a
where e is some constant, is the GRM accuracy (by function) and 1+VB is golden ratio.
As depicted in Theorem 3.3 Algorithm I
Texhibits a linear convergence rate, achieving the desired iterations and T = Ô (Sa/M11 111/ log !) oracle calls. Fur- thermore, there's s an enhancement in the maximum noise level A, reaching 111 6. It's notable that
accuracy in N O (Sa/M1a log
a weaker strong convexity condition was employed in the proof of Theorem 3.3 (see Appendix DD33:
|V fV 2 2p1-a(((z)) f(x))((x)))))))))))){)))) Ye Rd.
(5)
This condition (in the case a 1), also known as the
or
functions condition Polyak (1963); Lojasiewicz (1933): Karimi et al. (2016); Belkin (002), encom- passes broad class of functions: convex functions, strongly convex functions, sum of squares (e.g. where considering system of non-lineat equations). invex and non-convex functions. as well as over-parameterized systems. Also is shown in Yue et al. (223) that non-accelerated algorithms (like Algorithm! D are optimal for L-smooth problems under the Polyak-Lojasiewice 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):
E [S(NN(eo)] - S a.
P (f(EN(ee)) - 2 5
60
4 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, non-accelerated algorithms. Nevertheless, [ is still not optimal because it belongs
Algorithm
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 14 0) problem (T) that acceleration in the class of optimization algorithms using the Order Oracle exists! For simplicity, we consider the case when A = 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), AAlen- 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 Otk, Sk, 0k+1, As+1, Bk+1, Lipschitz coordinate constant L,, strong convexity P1-a, distribution pa (t), and a starting point To = 20. proceeds as follows:
V/ = (1 0x + ag.kk
xb+1 = yk (1/ Vin (yx)e
(6)
-k-1 wk 1- Bx))
0x+1
Vie J
(7)
where wik (1 - 3x + BLyE- Looking the 5x+1 update (6). it seems that it should not be difficult to determine the step size 1/Li, and the value of the gradient coordinate ff using linear search, as demonstrated in Algorithm [ However, substituting the same 7/ instead of V., into the 2 update (7) isn't straightforward. The step with linear search is larger than the original step of (1/L,)) J. (1te), potentially leading a paradoxical situation where the
step worsens with linear search. This is because there is guarantee that the function / is monotonically decreas- ing along the sequences (=x and Nesterov [ (198).. Nevertheless, we have successfully addressed this chal- lenge and we are ready to present the first accelerated algorithm utilizing only the Order Oracle: the accelerated coor- dinate descent method with order oracle.
Algorithm Accelerated Coordinate Descent Method with Order Oracle (OrderACDM)
Input: 2o 2g Rd R. (L), Ao 0, 1, o for k = 0 to N 1 do
1. choose active coordinate in (L)
2. find parameter 0x++1 from 1 Ast BR+1. where As+1 = A + ax+1 and BE+1 = B2 + #
3. 0g Akt1
ac+1
evident from Algorithm 2 that the challenge was addressed by incorporat- ing a secondary linear search, ensuring that the update step in 2 with linear
4. Bg < Ba+1
11 M1RR11
5. yk + 12-a)2ztta 86)
1-002
6. compute T7 argmin, 1f (21 no:,)) )} via (GRM)
search is at least as effective as (7). How- ever, unlike Algorithm [ OrderACDM cannot be deemed fully adaptive as ne- cessitates knowledge of the strong con- vexity constant /41-a and the Smooth- ness constant L; (which disappears in the case where a = 0). Despite this, we ready present the main advantage of Algorithm: Faster convergence rate of Accelerated Coordinate Descent Method with Order Oracle.
7. Dk+1 t ykk + Cic
8. Wx + - -Bx)) + Ball + Be41Da(i) TeCi
9. compute G. argmin {f + (ci,)) }} via (GRM)
10. 2k+1 f- W& + Cee
end for Return: IN
Theorem 4.1. Let function f (x) is strongly convex (Assumption 1.2). L-Smoothness (Assumption
1.1 and Lp-aj- -Smoothhess then Algorithm [ (OrderACDM) with oracle (2) guarantees an error
E [[[(x)]] - 5(x)) S (1 (1- V
N
Fo:
Sa,/2
where Fg = f(ro) - f(x*). Sa,2 Σin I2/2
Compared to the results of Section 3, the convergence rate demonstrated in Theorem 4. is superior, confirming the potential for acceleration in algorithms utilizing the Order Oracle. To achieve the
desired accuracy E, Algorithm 2 (OrderACDM) requires N O (Sa/2/ / /Pi-a a log )) iterations
We assume that for any 2, y Red it holds: f()) s f(x) + (Vf(x), y x) 1p-ol l| 2 -
7

---

and T - / a 1 oracle calls, significantly outperforming existing competitors that utilize the Order Oracle (see Table One notable difference from Algorithm iis selection of the active coordinate i RR (T.), where 3 = a/2. This choice aims to eliminate dimensionality d from the iteration and oracle complexities derived in Lee and Sidford (2013), since Sa/2 S vdSa. A detailed proof of Theorem 4.1 is given in Appendix
Stochastic Order Oracle Concept
This section is devoted equally important concept of the Order Oracle (2) namely its modifica- tion to the stochastic case, where the values of two functions on one realization & are compared:
(<z; y, {) = sign (f - fly. E)]
(8)
For simplicity, we assume that the oracle (8) can also be motivated by the creation of an ideal chocolate only for group of people on average. That is, in this concept the ξ-th realization of the function can be understood the ę-th individual of group.
subject adversarial noise. This oracle concept
To address the stochastic black-box optimization problem T when only the Order Oracle (8) is avail- able, provide the first optimization algorithm that uses exactly the stochastic oracle concept
2k+1
Th 7/a (T + 7k. 2x - ew E1 ex
where "/ > 0 is a smoothing parameter, o₁ E (1) is a vector uniformly distributed on the Euclidean the auxiliary results.
sphere. In order proceed convergence guarantees of this method (9)
Lemma 5.1. Let function I be L-smooth
[V VdL
eg
E (1),,, then the following holds:
6(Ik + Ykek Thk Yk Ex)e = sign KVf Ex), ex)l
Now using Lemma 5.1 show how our algorithm with oracle (8) is related normalized SGD.
Lemma 5.2. Let vector ff(z, E Rd and vector c E (1), then with some constant we have
vf(x,{) Eg [sign (V)( Vd [+]x,
As Lemma 5.2 shows, the direction in which a step is taken in Algorithm 99) is the direction of normalized stochastic gradient descent. Given this fact and based the work 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 be a T-smooot and ex Sd((),, then for the algorithm (9) with step size Tix = 4// k the value /N (Ix x²) is asymptotically normal: VN (xt x²) N (0, V), where the matrix V is as follows:
V 1/2
aV ((')(xx)- -1
22 1/d) c
vd
--]| co. 27 - 1/d) a f(x*)
(where is unit matrix).
For a detailed proof of Theorem 5.3
including a consideration of auxiliary Lemmas, see Appendix
Discussion
In Section 3 we showed that such multidimensional optimization problem 4 can be solved using Algorithm which utilizes only comparative information. The fact that such 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 of the algorithm. In the Subsection 3.3 we showed that when the Folyak-Lojasiewil condition
that allows us think about the optimality
We assume that for any æ, y Rd it holds: f(v S f(x,() (Vf(z,),, x) 211

---

is satisfied, we can perhaps consider that OrderRCD has optimal iteration complexity (see, Yue al., ). However, when the other conditions are satisfied, this is not the case, since Algorithm belongs to non-accelerated algorithms. Therefore, we believe that Section provides a vector for the development of the question of optimality by showing an OrderACIM,, 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 more efficient algorithm using only oracle (2).
Before move to the numerical experiments, it's important to note that accelerated Algorithm 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 and Appendix B
7 Numerical Experiments
In this section, we investigate the performance of the proposed algorithms in the corresponding
Sections and on a numerical experiment. We compare OrderRCD (sce Algorithm I and OrderACDM (see Algorithm 2) which utilize deterministic oracle concept (2) with existing first- order state-of- of-e-of-the-aa art algorithms. The goal is to highlight our theoretical results.
The optimization problem (T) has standard quadratic form: min [(x) := (1r, Ax) (b,x)) tc, where A d b E Rd. and E IR. We coordinate, then the distribution (4) has the following form: Po (t) 1/d. For such a problem, the assumptions of L-Coordinate-Lipshhee (Assumption 1.2 are satisfied, where L; = As. In all experiments, we employ the golden ratio method (GRM) solve the linear search problem with a precision = 10-8.
uniform distribution (a 0) to choose the active
smoothness (Assumption 1.1 and pi-o-strong convexity
In Figure 2 we compare the convergence random coordinate de- scent with order oracle (OrderRCD) and accelerated coordinate descent method with order oracle (OrderACDM) with the SOTA non accelerceer algorithms: random coordinate descent (RCD) from Nesterov (2012), 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 In- terestingly. the random coordinate descent with order oracle even outperforms its first-order counterpart, despite the limitations as- sociated with oracle usage (only Order Oracle (2) available). This observation can be attributed to the adaptiveness of Algorithm [] 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 non-accelerated algorithms, including first-order coordinate (RCD) and full aill-gradeent (GD) methods. In this experi- ment, OrderACDM was implemented using the method described in Algorithm 2 with ÇA 0 (i.c., with one golden ratio method); RCD and GD used a constant step size, specifically 1/L; and 1/L
10a
ACD OecanAZD
10:
101
109
10
10-
20000 40000 GO0D0 80000 300000 10-1
Figure 2: Comparison of al- gorithms proposed with accelerated first-order algorithms.
8 Conclusion
We proposed new approach to design optimization algorithms using only the deterministic concept of Order Oracle 2 by providing theoretical guarantees (showing SOTA results up logarithm factor) for non-accelerated algorithms in non-convex, convex and strongly convex settings. We also discussed under which condition the Algorithm 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 low- dimensional 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 ArderACDM) on numerical experiments, thereby validating the theoretical results. We provided practical recommendations for implementation of these algorithms.

---

Authors' Affiliation Clarification
MIPT Moscow Institute of Physics and Technology. Dolgoprudny, Russia,
Skoltech = Skolkovo Institute of Science and Technology, Moscow, Russia;
ISP RAS Ivannikov Institute for System Programming of the Russian Academy of Sciences, Moscow,
Russia:
Innopolis Research Center for Artificial Intelligence, Innopolis University, Innopolis, Russia;
MI RAS- Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia.
10 Acknowledgments and Disclosure of Funding
This research has been financially supported by The Analytical Center for the Government of the Russian Federation (Agreement No. 70-2021-00143 01.11.20211 IGK 000000730334P540002 The authors are grateful to Eduard Gorbunov, Andrey Neznamov, Alexander Vedyakhin.
References
Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky, Alexander Gasnikov, and Martin Takáč. Inexact tensor methods and their application to stochastic convex optimization. Optimization Methods and Software, pages 1-42, 2023.
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi multi-point bandit feedback. In Colt, pages 28-40. Citeseer, 2010.
Ahmad Ajalloeian and Sebastian Stich. On the convergence of sgd with biased gradients. arXiv preprint arXiv:2008. 00055100000000,,...0000000000000 2020.
Arya Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Distributed zero-order optimization under adversarial noise. Advances in Neural Information Processing Systems, 14:10209-00 10209-10220, 2021.
Arya Akhavan, Evgenii Chzhen, Massimiliano Pontil, and Alexandre Tsybakov. A gradient estimator via 1| Irrandomizzaionn for online zero-order optimization with two point foedback. Advances in Neural Information Processing Systems, 35:7685-7696 2022.
BA Alashqar, AV Gasnikov, DM Dvinskikh, and AV Lohanov. Gradient-free federated learning methods with 4 and Iz-randomizaaion for non-smooth convex stochastic optimization problems. Computational Mathematics and Mathematical Physics, 600001366- 2023.
Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In International Conference on Machine Learning, pages 1110-1119. PMLR, 2016.
A Anikin, P Dvurechensky, A Gasnikov. A Golov, A Gornov. Yu Maximov, M Mendel, and V Spokoiny. Modern efficient numerical approaches regularized regression problems in application to traffic demands matrix caleulation from link loads. In Proceedings of International conference ITAS-2015 2015, 2015.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in II geometry. International Conference on Machine Learning, pages 393-403. PMIRR 2021.
Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pages 257-283. PMLR, 2016.
Somil Bansal, Roberto Calandra, Ted Xiao, Sergey Levine, and Claire J Tomlin. Goal-driven dynamics learning via bayesian optimization. In 2017 IEEE 56th Annual Conference Decision and Control (CDC), pages 5168-5173. IEEF, 2017.
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-244 248, 2021.
El Houcine Bergou, Eduard Gorbunov, and Peter Richtárik. Stochastic three points method for unconstrained smooth minimization. SIAM Journal on Optimization, 30(4):7726 27499, 2020.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
10

---

Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trendy in Muchine Learning, 8(3-4):2113357, 2015.
Pin-Yu Yu Chen, Huan Zhang. Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26, 2017.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In International Conference on Machine Learning, pages
PMLR, 2018.
Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to derivative-free optimization. SIAM, 2009.
Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated bayesian optimization via thompson sampling. Advances in Neural Information Processing Systems, 33:9687-9699, 2020.
John Duchi. Lecture notes for statistics 311/electrical engineering 377.
URL: htps://stanford.
I/lccrrsf notes. pdf. Last visited on, 2:23, 2016.
Ji Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi. Black-box generation of adversarial text sequences evade deep learning classifiers. In 2018 IEEE Security and Privacy Workshops (SPW). pages 56. IEEE, 2018.
Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurcchensky, Eduard Gorbunov, Aleksander Beznosikov, and Alexander Lobanov. Randomized gradient-free methods in convex optimization. arXiv preprint arXiv:2211.13366 2022a.
Alexander Gasnikov, Anton Novitskii, Vasilii Novitskii. Farshed Abdukhakimov, Dmitry Kamzolov, Aleksandr Beznosikov, Martin Takac, Pavel Dvurechensky, and Bin Gu. The power of first-order smooth optimization for black-box non-smooth problems. In International Conference Machine Learning, pages 7241-7265. PMIR, 2022b.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341 (24622234--338, 2013.
Margalit Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. In International Conference on Artificial Intelligence and Statistics, pages 9050-9090. PMLR, 2022.
Eduard Gorbunov, Adel Bibi, Ozan Sener, El Houcine Bergou, and Peter Richtarik. A stochastic derivative free optimization method with momentum. In International Conference on Learning Representations, 2019.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov, Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. Advances Neural Information Processing Systems, 33: 13042-3-55 2020.
Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon sgd. In International Conference on Machine Learning, pages 3964-3975. PMIRR, 2021.
José Miguel Hernández-Lobato, Matthew W Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. Advances in neural information processing systems, 27, 2014.
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Accelerated zeroth-order and first-order momentum methods from mini minimax optimization. The Journal of Machine Learning Research, 23(1 1361) 2022.
Bo Jiang, Haoyue Wang, and Shuzhong Zhang. An optimal high-order tensor method for convex optimization. In Conference on Learning Theory, pages 1799- 1801. PMLR, 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. L Linear convergence of gradient and proximal-gradien methods under the tojaak-tjjjsiiwicz. condition. In Machine Learning and Knowledge Discovery in Databases: Eurapean Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pages 795-811. Springer, 2016.
Morteza Kimiaei and Arnold Neumaier. Efficient unconstrained black box optimization. Mathematical Programming Computation, 14(2):365 414, 2022.

---

Nikita Kornilov, Ohad Shamir, Aleksandr Lobanov, Darina Dvinskikh. Alexander Gasnikov, Innokentiy An- dreevich Shibaev, Eduard Gorbunov, and Samuel Horväth. Accelerated zeroth-order method for non-smooth stochastic convex optimization problem with infinite variance. Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Heinz Kurz. Hermann heinrich gossen (1810-1858). In Handbook on the History of Economic Analysis Volume Edward Elgar Publishing, 2016.
Tor Lattimore and Andras Gyorgy. Improved regret for zeroth-order stochastic convex bandits. In Conference on Learning Theory, pages 2938 2964. PMLR, 2021.
Yin Tat Lee and Aaron Sidford. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. 2013 ieee 54th annual symposium on foundations of computer science, pages 147-156. IEEE, 2013.
Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated proximal coordinate gradient method. Advances in Neural Information Processing Systems, 27, 2014.
Aleksandr Lobanov and Alexander Gasnikov. Accelerated zero-order sgd method for solving the black box optimization prohlem under "overrarametrivaatoon" condition. In International Conference on Optimization and Applications, pages 72-83. Springer, 2023.
Stanislaw Lojasiewicz. Une propriété topologique des sous-ensembles analytiques réels. Les équations aux dérivées partielles, 117:87-8 19,9 1963.
Paul Mangold, Aurélien Bellet, Joseph Salmon, and Mare Tommasi. High-dimensional private empirical risk minimization by greedy coordinate descent. International Conference on Artificial Intelligence and Statistics, pages 4894-4916 PMLR, 2023.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341 2012.
Yurii Nesterov. Implementable tensor methods in unconstrained convex optimization. Mathematical Program- ming, 186: 2021.
Yurii Nesterov and Sebastian U Stich. Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM Journal on Optimization, 27(1):110-12) 2017.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Yurii Evgen' evich
evich Nesterov. method solving a convex programming problem with convergence rate of bibigg(k"22) bigrr) In Doklady Akademii Nauk, volume 269, pages 543-547. Russian Academy of Sciences, 1983.
Anthony Nguyen and Krishnakumar Balasubramanian. Stochastic zeroth-order functional constrained optimiza- tion: Oracle complexity and applications. INFORMS Journal on Optimization, 2022.
Kumar Kshitij Patel, Aadirupa Saha, Lingxiao Wang, and Nathan Srebro. Distributed online and bandit convex optimization. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop). 2022.
Boris Polyak. Gradient methods for the minimisation functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864 878, 1963.
Boris Teodorovich Polyak and Yakov Zalmanovich Tsypkin. Optimal pseudogradient adaptation algorithms. Avtomatika Telemekhanika, (8):74844, 88,, 1980.
HoHo Rosenbrock. An automatic method for finding the greatest or least value of function. The computer journal, 3(3):175-188) 1960.
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Ducling convex optimization. In International Conference on Machine Learning, pages 9245 9254, PMLR, 2021.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal Machine Learning Research, 18()):703-11133 2017.
Bin Shi, Simon S Du, Weijie Su, and Michael I Jordan. Acceleration via symplectic discretization of high- resolution differential equations. Advances in Neural Information Processing Systems, 32, 2019.
12

---

Sebastian U Stich and Sai Praneeth Karimireddy. The errorfeedback framework: Better rates for sgd with delayed gradients and compressed updates. The Journal of Machine Learning Research, 21(1):9613-9688 2020.
Zhiwei Tang, Dmitry Rybin, and Tsung- Hui Chang. Zeroth-order optimization meets human feedback: Provable learning ranking oracles. JCML 2023 Workshop Many Facets of Preference- Learning. 2023.
Wenjie Xu, Colin N Jones, Bratislav Svetozarevic, Christopher Laughman, and Ankush Chakrabarty. Vabo: Violation aware bayesian optimization for closed-loop control performance optimization with unmodeled constraints. In 2022 American Control Conference (ACC), pages 5288 5293, IEEE, 2022.
Pengyun Yue, Cong Fang, and Zhouchen Lin. On the lower bound of minimizing volyak-lojasiewin functions. In The Thirty Sixth Annual Conference on Learning Theory, pages 2948-2968. PMLR, 2023.
Yuchen Zhang and Xiao. Stochastic primal-dual coordinate method regularized empirical risk minimiza- tion. Journal of Machine Learning Research, 18(84)1-44 2017.
13

---

APPENDIX
Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values
A A Few More Words on the Motivation Behind the Order Oracle Concept
In this Section, 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.
A.1 Perfect coffee for everyone
As already demonstrated in Section [ (Introduction) with the example of chocolate, the deterministic concept of the Order Oracle has many potential applications. However, this research 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
Figure 3: Smart coffee machine,
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 strong Robusta beans, which give 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 sugar, ice, lemon juice, chocolate, different syrups to make sure that the customer will definitely like this coffee.
A.2 Order Oracle: zero-order oracle close to reality
In this Subsection, we would like to show that the oracle concept considered in this paper perhaps the closest to reality.
One of the key criteria for evaluating optimization algorithms is oracle complexity. Oracles are commonly used in theoretical estimates, where they offer insights into the function's 's behavior. For
14

---

instance, the first-order oracle is prevalent in machine learning literature: the authors of Gorbunov
al. 2020); Gurbuzbalaban et al. (202T): : Huang et al.) (002) use the oracle to obtain the gradient
value V [t of function at a given point Fy. And in Stich and Karimireddy (2020); Ajalloeian and Stich (2020); Glasgow et al. 2022), the authors assume some adversarial environment where the
oracle is inccurrtee, I.e., the oracle produces the gradient of the function at given point with some adversarial noise (adversarial refers to the noise that accumulates over iterations). The authors of Nesterov (2012); Lee and Sidford (2013); Mangold et al. (2023) also refer their oracles that produce only the gradient coordinate of the function (Ir( at a given point 24 to a first-order oracle. mudient-ffree oracle Gasnikov ct al. (022a), since the algorithm does not use the whole gradient. but only the directional derivative.
However, this oracle formally can also be referred to the so-called
The following works Jiang et al. (2019); ; Nesterov (202]); Agafonoy et al. (2023) use a higher-order oracle to obtain information, for example, about the Hesse matrix of a function at a given point. But there are oracle concepts closer reality, for example in Bach and Perchet (0166); [Shamir (2017);
Akhavan et al. (021); Gasnikov et al. (2022b); Kornilov et al. (2023) the authors develop algorithms that use only information about the function value ((x),, possibly with some adversarial noise. Such a concept is very common in the field of black-box optimization. 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 be natural in applied realities) in such an oracle.
A.3 Why is a convex/coneave function being considered?
In this Subsection, we would like to emphasize the organicity of considering the convexitylconcave assumption of the objective function of the original problem (
"In terms of the law of diminishing utility, the utility function is a concave function in ordinary coordinates:" In economic science there concept of "utility". Usually this term is used when describing a consumer who makes a set of several goods (like a basket in supermarket). Each such set has some utility for the consumer, and he tries to maximize it. We do not consider a consumer who makes 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 's first law sounds 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.
B Additional Numerical Experiments
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 6(z, y) from deterministic oracle concept (2) on a random coordinate descent with order oracle (OrderRCD). We used (6(z, y) = A cos x sin y) as the adversarial deterministic noise, where A (s.t. 10(z, v) < A) is the maximum noise level. In Figure [5] we see that the adversarial noise justifies its name as accumulates over iterations. In addition, we observe that the convergence of the non-accelerated coordinate method depends directly on the maximum noise level A, 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 A, for example, in this case, when a 0, the condition for achieving the desired accuracy e looks as
15

---

follows: A S P1-oE/d. Or we can rephrase this condition: the OrderRCD has a linear convergence rate the asymptote depending on level noise A.
10a
OrdentLLD with 0.5
OrderACD =
OrdenACDM with hao (GRM
10a
OrderFCD 6 0.9001
10
OrdenhCCM with one (CRM) ACDM
10"
10.
10"11
10-2
10a
10-1
10-1
10-5
20000 40000 60000 80000 100000
20000 40000 60000 80000 100000
lterations
Iterations
Figure 5: Effects of adversarial noise from Order Oracle 2 on the convergence of random coordinate descent (OrderRCD). Here we optimize f(z) with the parameters: d 100 (dimensional of problem), [0.5, 0.1,, 0.0001} (maximum noise level).
Figure Effect of the second golden ratio method on the convergence of accelerated coordinate descent with order oracle. Here we optimize f(z) with the pa- rameters: d = 100 (dimensional of problem), A = 0 (maximum noise level the Order Oracle).
In Figure [6] we illustrate the advantage of employing Algorithm with one method of line search (CA = O). 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) second time (see line 10 of Algorithm (). Addressing this may involve utilizing the golden section method only once per iteration in Algorithm 2 (that is, substitute Çk = into line 10). Indeed, 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 theoretical results. That is why 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 proces- sor. The performance of each Figure depended the particular algorithm, for example, gradient descent (GD) performed 40000 iterations in 0. 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 and 2 proposed in this paper, by virtue of using linear search each iteration performed 40000 iterations in 02:02 minutes and 02:13 minutes respectively.
[
C Auxiliary Results
In this section we provide auxiliary materials that are used in the proof of Theorems.
C.1 Basic inequalities and assumptions
Basic inequalities. For all a, E Rd (d 2 1) the following equality holds:
||a| + |bbl (a, b) + ||a b11
(10)
(a, b) < ||a|| ||b||-
(11)
Corrdnate-Lipshitt--ooooee Throughout this paper, we assume that the smoothness condi- tion (Assumption I.I satisfied. This inequality can be represented in the equivalent form:
Lhh²
f(x + hc,) S f(x) + fx)
(12)
where L1, L2, ... La > 0 for any i [d] &d and h e R.
16

---

Lipschite-smoothess.
To prove Theorem 4.1 we additionally assume Lp -o) smoothness w.r.t.
the norm 1+ --ll
+ Lp-al 2
f(0)
x x y
(13)
C.2 The Golden Ratio Method (GRM)
Algorithms I [ presented in Section B and 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
Algorithm 3 Golden Ratio Method (GRM)
Input: Interval [a, b]
2: Initialization: Choose constants > 0 (desired accuracy), put the constant
= -5-1
3: y & a (1- p)(b a)
4: f- p(b a)
5: while b a > e do
6: if Φ z) -1 then
7:
b-z
8:
y
9:
y f a + (1 - (b - a)
10:
else
11:
a + y y+z
12:
13:
2 2 a + p(b - a)
end if
15:
end while 16: Return:
We utilize the Golden Ratio Method to find solution to the following one-dimensional problem:
arg min f(x + nyoa))-
nER
Using the well-known fact about the golden ratio method that GRM is required to do 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 this problem:
In Section 4 (Accelerated Algorithms), for simplicity, consider the scenario when the Order Oracle (2 is not subject to an adversarial noise (A = 0) and the golden ratio method solves the inner problem exactly (e ~ 0). Then we can observe the following:
f + e S f(x + met,)
Vn R.
(14)
In Section 3 ("Non-Accelerated Algorithms") "), we consider the scenario when the Order Oracle subjected adversarial noise (Á >> 0). Then from the convergence results ( by function) of the golden ratio method (GRM) we can observe the following:
f(x + ),,) S f( + ne,,) + cbA,
An E R,
(15)
where is constant, the GRM accuracy (by function) and + 1+v5 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. we talk about convergence by ar- gument, there may be no convergence at all with noisy concept of the Order Oracle. Thus, in the final corollary (T5), we consider the scenario where adversarial noise accumulates over iterations, resulting in the following observation: the golden ratio method converges towards the O (A) asymptote.
17

---

D Proof of Convergence for Non-Accelerated Algorithm
!
In this section, we furnish the omitted proofs for the theorems presented in Section
D.1 Proof of Theorem 3.1
From Assumption
we obtain:
(It meci)) ((rk)
Ik
Via f(z))))))))) ((xx)) -ct
Lix
1 (V f(xx))
1
(Vuf(zz))) +c+
Lis
2Li
(Vi,)()))) + cDd
(16)
2T.
where 7/ arg min fa + n);.). ). We use this as follows:
[[ [(xx) E [J (ax me:,)) [(xx)
Pa (1) (S (ox + mew,) - [(xx))
d Pal (i) (V.((T))) + Σ (i) (E+ cDA) (DD)
-=1 2T,
i=1
2
[V
+E+c0A
25
Rearranging the terms and summing over all k, we have
N-1
N-1
N-1
N-1
Σ
25. (IVS(())(iiaa)
)²
S Σ (Fx Fk+1)
Σ k=0
Σ +f
6
k=0
< Fo + FN Ne NeDA
- Fo + Ne+ NoDA,
where F& = [[f(x)) f(x").
Dividing both sides by number of iterations N, we obtain the convergence rate for the non-convex case:
25. N
Σ (V)(())))))))))
Fo + +2. 2S
This convergence results imply the existence of point & [N] where holds true:
SaFo
(IV((())))))))) s 50
+ S.et + (S.+ S
N
Then, achieving the desired accuracy E, where [V [1
I E, requires
N = o Sa Fo g2
Sa Fo
==
82
iterations and oracle calls respectively, provided the maximum noise does not exceed A S 62.
D.2 Proof of Theorem 3.2
From Assumption I.] we obtain:
15
V ((x(e))) ) - f(Ix) + cdA
f (ax + mer)) f(xx)
f
Ib
Lin
18

---

(vx,((x))) 1 (Vu)(Ex)) +c+
Li
2L12
2 (Vinf(zx)) + cDA
(17)
where Th - arg min sxx + rjei.). ). We use this as follows:
[[((+++1]] - [(xx) = E [f (ax me:; )) - f(xx)
Pa(t) (f (ox + mee,)) f(zx))
Pa (i)
(V.[(Tx)) Σ (e
2h,
(IVS(T>))((aa)) c
(18)
2Sa
Denote Fg. = E [f(a)] - f(x*).
Note that the above calculation can be used to show
f(14+1) S f(xx), then have
FB
(zx)) 2t x²)
| x= [-- Vf(zv)lfi-a
$ RRpaa [
(19)
where in ① we used Assumption
1.2 with Mi-a = 0, and a new notation for convenience, which looks follows Rii-a] suPpes> || x² -|
Then substituting
I99 into
18
obtain:
FR+1 Fx
F + + cbA.
2S, 12
Rewriting this inequality, we obtain:
F S FR +c-
2S R2
[1-a]
Next, we divide both sides by Fk:
Fg
1
1
+
2S R2 [-)
Fk+1
F
Fb
FRtIFs
Using the fact that 28, RC -n)
F
obtain the following:
25. R ii
F4-1
6 CDA
2S, R2 [1o]
Fk+1
Ft
FR
When summing all k
e cD
+
28 R2 [-o]
F
Fk
F
k=0
k=
we get:
1
N(C+
N
+ FNFN-1
25, R2 1
FN Fo
1
N (c+CDD)
+
F'
FxFx-1
19

---

Taking into account the fact that FN-1 = E [f(xN-11]) - ff(x) 2 and rewriting the expression we
obtain the convergence rate for the convex case:
2 [1-a] + 25 (1-a) (e + cPA). -((x")))-(x' S
Then, achieving the desired accuracy E, where E [f[(xN]] - -f(x²) S E, requires
Ra
S R1 [-
N 0
T=
iterations and oracle calls respectively, provided the maximum noise does exceed the following value A S e² /S, R2 )
D.3 Proof of Theorem 33
From Assumption 1.] we obtain:
f (xx + m.r,)) f(xx)
Ib
Vuf(zz)e f(xx) + +c+ cPA
Liv
1 +et
(V f(xx)) +
+et co
Lix
2Li
(Vi,)(ms))) + cfA,
(20)
2
where min (xx + njei)) We use this as follows:
[[f(x*+1) - f(*x) E [f (ax + mew, - f(xx)
Pa (a( (S (xx + men)) - [(xx)
d
Pal (i)
1
(Vif(x))) + +Σ (1) (e cBA)
2L,
i=1
i=1
(IV (1Vf(o)))i
2 +c+o0A
(21)
2Sa
By strong convexity, we have
( [(x*)
(VS(*)), Fx xx) 41-a
|| -x" =3"1[1-o]
2
[V]())) II [1-a]] ||,ra - xx x0(l1-a)=
M1-a
||
x 20][[=o]
2
[V 2
P1-o
where in we used Assumption 1.2 with Pi-a > 0. Then, using this inequality in 21 we have
E (((())))-- - < (1 (1- 25.
M1-a (f(xx) f(x")) - - coA
Applying recursion we obtain a linear convergence rate:
E [f(xx) - -(x=)) < (1 M1-a (f(2r) - f(x")) (+=²))++ + 25,E 2cS AA
N
25.
11-a
P1-a
Then, achieving the desired accuracy s, where E E[f(xN] f(x*) E, requires
N S. (5550)))))) log !)
T= Ô Sa ! log &
M1-a E
P1-a
iterations and oracle calls respectively, provided the maximum noise does exceed the following value A < M1-a=/Sa S/a.
20

---

E Proof of Convergence for Accelerated Algorithm 2
Denote wk (1 =k + BkyK. Then
yk (1 ax ax -B6)
Wk BLyK
(1 Ork )=k + aguik
a 04
3x
Thus, in method we have the following representation:
(1 axk) + ayikk
(22)
Let the solution of initial problem denote x² I. arg min f(x), then from Assumption I.] we obtain:
2 aK+1
2 a a
(5 (5(B
1
f(y:: + +me,))))))))))))))))))))))))++ - - f(yn)
V (Vvkeei)) f(ya))
B 12
B 1 (ix)
Lip
k++
(Vi, ((ke)) + llwe x. 22112-al
1
B k+ (ik)
27
(w (ba) - x2
12) +
ax+1
(in((
Σ L - 20)
1
I1-a
B Bk+1Pp8 (ix)
if
+ |lwx
x+ 3211(1-01
10
1-a
(1te
(6x)
ag+1
Vins(ue))
24
(tx) x (6u))
bi
W
26
Bk+
I
_1 (1
L: 1 [
(2)
xxx (1)) + ||wr
Wk
ak+1
Viv Fuufeee - 2x
+ 1 - =211(1-a)
1-aaj
BR+IDo(iN)
[1-a]
2ak-1
V (irk())) 2x
(Ww) )
(1x)
+
2
(Vf(x)). 2x+11 xx,)
Ba+1pa(ix)
M1-a
Wk
ak+1
Via (YNc)e - Et
+llw> - 2x =2.1(1-0 +
BR+IPa(ik)
[1-0]
20k-1
( (Vn.f( ((N) - ((iu)) - 1|2441 xx212 12111al + 2
(f(2*41) f(xx))
B8+1pa(1x)
P1-a
||++11 - x.al x011i--a1 + +|wwk xx
10.12-aa
20s+1
(Vun) (64) - ((i)))
Bx+1pa(1k)
V V (us)es) ]
+
2
- [[(()))
+
2
f(xx)
Wk
a&+1
P1-a
Ii-a
D
Bkt1pg(in)
2
Vf(zz), -1-a 1--BBttie (po(i))
ax+1
Vin fink)on
Li-a
S - ||++1
Nall
Balli1oo] + Ilwe x. [1]1-o)
2ax+1
(Vin( (4k) -x((t)
BR+1Pa(1K)
+ 01-a
f(zx41) - f(x.) + f(xx)) -f Wk
ah+1
V (yuseen
11-BBetPPll
20x41
|| - 2..1 + ||w x 1-
(23)
Bu+iPa(1a)
21

---

where in ① we used Assumption 1.2 with p1-o > 0.
Denote r = || - I [|a) and wk (1 - -x + BLyK. then due to convexity of the norm
function it follows:
Wk x. [1 aaj S (1 - Bx) ||Ex - zolli-a + 3e llve - x- x=-lit-0)
(24)
Substituting (24) into
(23 we obtain
BK+17 k+1
(1 B + Bx+1 Ilye - In 1(2-aj
2ak+1 ps(ik)
(Viy (1 )ei, wht adt) + B 12
2L a
(f(vE) - ( (Ix++1)
2ax+1
2L 0k41
Bark + Bx+1 11y.k - xz 2011(1-0
Vii (y::)e with - -x+t) BE+1D
(J(ya) ((x++1)
(ikk
Bar + Bx 1lyk - xz 2a1p1-0 4
2ak+1
2L 1
V f (2x (0. w -xa²) +
(f(yk) - f(xx+1))
pa(it)
B L
@ Bark + Bx+1 118k x. 1011
20k+1
V fyk wtth -2
24 S
(f(yk) f(xx+1)),
(1k
Bx+1
where in 1 that (1 (1-Bx, Bx+ Bx+1 0k+1 Bg, and in @ that a 2,3
Note that E [[ = Ei (((()(((R+))) Therefore, taking expectation we obtain:
2ax+1 (ix)
[[e41 Bar + Br Bx+1 11 2..1i 2011(--) -E
(Vir (yx)) - =x//)
2 52 (f(yk) E [f((x1)))
Bb+1
Bar 2 + By Bx+1 1lyx wwn-a0 -2.1(1-0 Σ
pa(i)
2ax+1 (f
pr(i)
24 S3 (f(w)) - ( [f((x+1)))
+
B
20 (f(N)) B[f(xx+11))
B + BB Bx+1 1ly x. 2-112-a1 + 2ak (Vf()),, wx)
Bx+1
Since Wk
2k + 1-ak (yk - ok), we obtain
1 Okk (xx yk
-0k 1 (Vf())), I. wa) 2ax+1 (Vf(y)), 1/k
a3s
① < 20x+1 (f(x.) - [(n)) 04+101-a ||.0. 31112-o1
1 - (f(#*) f(yk))
+ 20k+1
as
@ 2f (x.) 2f + 2Ax 11+101-a ||r,
Ve Mel(i-a]
(25)
where in ① we use Assumption 1.2 with P1-o 0 and in @ we use that ax+1
1-sse
ax
a&+1
Ak+1
AR41 0x+1 Ak
1
2a $2
[B411 & Berk + BB Bx+1 1l xx112-aa + 2ak-1 (Vf())), x. - we) +
(f(yk) - E [f((xx+1))
B
22

---

2a 2a 1
BLTK + -1-+101-alla -x.lli-ai + 2ak+1 (Vf(y=), - -Wk) +
(f(ye) E [f(
Bx+1
25
21 53
BETK + 2ax+1f(xx) +4,
+
(f(yk) E [f(x==)))
Bx+1
Bar + (ax+1f(z.)
22 + 2 (f()k) - E [f(+++))))
Bar 2Ax+1 (E (Zx+1 )] - f(x.)) + 2A (f(z)) - f(x,))
where in 1 we use that 3x
"1 -1-0 and in 2 we use that o S = A B B
By summing over k we obtain:
N-1
2 Σ
Akt1 [B[[( f(x.))))))(())))))) 2 Σ As (f(#k) f(x)))
Σ k=0
B
Σ
E
[B+1
k=0
2AN (E[f(IN) - f(x.)) 2Ao (f(z)) - f(x.)) Borg
JE [NT
Using the known facts from Nesterov and Stich (017) can estimate the parameters AN and By:
AN 2
- (1-7)
4p -a
(1+7))~11)
(1 7)2
1 (1+7)
4/11-a
8u1
8p1-a
1
BN 2 4
71+ + 7 7)
where y
V/i-= 28,/2
Then using Ag = 0 and Bo = 1 we have
AN (B| - f(x))) S 2Ao (f(z)) - -(xx)) + Bor - Bx [r2]
@
1
(f(zo) - -f(x.) fvx(()),, xo - xx))
Pi-a
(f(zo) f((x)).
P1-a
Let's divide both parts by AN. then we have the convergence rate for accelerated method
B[f(xx)] f(x))
A1-AAN (f(zo) - f(x.))
$ 81 + 7) - (f(zo) - f(x.))
- 8(1 - ~) (f(ao) - f(x.))
= 8 (1 VuI-a N
(f(20) - f(x.)).
28a/2
Then, achieving the desired accuracy e, where B[f(xN]]
f(x') S requires
(==(55p log ) iterations and oracle calls respectively.
N N N=O( | V
T= Ô Sa/2 log
V41aa E
F Scheme of the Proof of Asymptotic Convergence of the Algorithm with the Stochastic Order Oracle Concept
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 normalized stochastic gradient descent. Therefore, we will first prove two auxiliary Lemmas 5. and
5.2 showing that our algorithm is still normalized stochastic gradient descent, and then proceed to
the statement of the Theorem 5.3 Our reasoning in the Proofs of auxiliary Lemmas similar the
work of (aha al. (2021).
23

---

Lemma E.1 Let the function f be L-smooth (for all z.y E f(v,E) S (xx + (v, 2) lly =11²). ? | and the following holds:
R it holds: (1), then
val.
6(x + 70, y0, sign
e)
Proof. From the Assumption of L-smoothness of the function f we have:
In² 2
Tnp
(V) I f(x + -0, (
2
In² -VVf(z,5), & - - (V 2
In²
Subtracting the inequalities, we obtain
[s + ye. f(x (0, - 27 (VI(z, (). s LT2.
Consequently, if if <
(V) ( |, we have that
<(x ye, e)e sign (Vf((,()))
Let's analyse Pe (In - (Vf (). It is known that for ~ N (0, I),
ju] is vector
uniformly distributed on the unit Euclidean sphere. Then the following is true:
Pe (c 2 Ln) = P. P. (1 (v)(z.)) u) L
P.
[VVf(x,)) (), u) 2 21m dloog 1/B
+ Pu
[lul] 2 2 d'og 1/3
P. ((V)((x))) u > 2 dlog 1/B
+ +
where used the well-known fact that v/: Pu ||n|| - 2 dloo 1/3
2 1
1 B. On the other hand,
since (Vf(z,)), u) / (0. 11. then for all y obtain
P((VS(Z,E)
2y
7
Vf E) 2
[V((,.))
Combining the inequalities, we have that o(x + 7e, 7e, E)e - = sign (VV except with probability most
2 V dlog 1/3
3Ly [f((,
Ví(,, E)
inf 3>0
3 +
d
3,
V fx, E
Vdl.
where in ① take 7
Thus, given the condition on the smoothing parameter, the statement of the Lemma satisfied with probability
VaL
Lemma F2. Let vector (z) E Rd and vector e (1), then we have
c vf(a,()
E jign (Vf(z.
Va [V
where [1] 1) is some universal constant.
Proof. Without loss of generality, we can assume ff , | = 1, as normalizing fz. [ does impact the left-hand side. First, let's demonstrate that E ssign (Vf(z, E), e\ [2, for some Ç E R. Consider the reflection matrix along V f(x { given by:
P= 2/
24

---

and examine the random vector é = Pe. As you can see that
sign (V (z, e)] = sign 2 V (x, e)l (V)(z,)), - (VS(z, (), sign {),
Since is also random vector on the unit sphere, we then have
Ee [sign Sigg((V/e ())
2 Es [sign (V/n, + L.
{
Ee sign (Vf((,)
2
| 1)
+ 2
E. [V
Thus, Eh (sign (v, E) et] e] = (v)( where E. (z e) ||. It remains to restrict
S. which by virtue of rotation invariance is equal to Ç E [ For an upper bound, observe that by
symmetry E [ef]] 2 E
à and consequently:
1 Vd
E [|ell]
V B
Let prove lower bound on Ç. If Gaussian random vector with i.i.d. entries eq / (0, 2). then from the standard properties of the (truncated) Gaussian distribution we would obtain that
[[ea]]= - V nd- For e uniformly distributed on the unit sphere, e; is distributed like us Tlu]
where u is
Gaussian with i.i.d. entries N (0, 2)- We then can write:
P |ea
((ea)
2
" P
|u
2 v
2 p
|u1| 2
1 and ||l| - !
vd
|u||
Vd
Vd
1
1
2 1 P
|
2
P
||u||
Val
Since #1 v is standard Normal, we obtain
P
[m
Vd P
<1 s 0.7.
and since E. [|u||]] 1, the application of Markov inequality gives:
P |u||
P -P(ll13
S D 10 v².
1
82
For = 0.25, this means that P
(e1l 2 0.25vd) 2 0.2, whence Ç = E
[| | 2 1 20
vd.
Now that we have shown that our method (9) is 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 case
Vs(r,) E) (x){
R(x) E [p(x + 70,2 g)c E [sign [/sggn((/[(aaaa (2)
vd Eg
c /
+ = Vd (Vf(z)),
Va
where ① we used the Lemma 5.2 and @ we defined a function (p()) = x
and used that
(f(x, vf(x) +.. Thus, using the following
c (²'x') Va (')())²2(())) v.a V=(2)dP(2)V21(0>> (1 (1
-1-
c ||||| dP(2)
d Va
and ? R. we obtain the sought statement of Theorem 5.3 which guarantees asymptotic conver- gence.
25

---

G Description of the "Private Communication" Approach
In this section, describe an approach privately communicated us by Yurii Nesterov create more efficient algorithm for low-dimensional problems, compared to the gradient-based methods proposed in this paper, using only the Order Oracle (2)
Consider the following method for solving the problem of minimiz- ing convex Lipschitz function (with Lipschitz constant L) square in R² with side R. A horizontal line (blue line) is drawn through the center of the square. On the interval carved from the square of this line, with accuracy e/ log(LR/a (by functiio) we solve the one-dimensional optimization (line search) problem. At the found point (blue point), the direction of the function gradient (which determined via the Order Oracle) is calculated and it determined in which of the two rectangles it "looks"; ; this rectangle "discarded". vertical line (red line) is drawn through the center of the remaining rectangle, and on the segment carved by this line in the rectangle, also with accuracy ~ e/ Log(LR/e) (by function) solves the problem of one-dimensional optimization (line search) problem. At the found point (red point), the direction the function gradient (which is determined via the Order Oracle) is calculated and it is determined which of the two rectangles it "looks"; this rectangle is "discarded". As result of this procedure, the linear size of the original square is halved (green square). The schematic the performance of the algorithm is shown in Figure 7
Figure Schematic of algorithm
Corollary G.1. not difficult to show that after log(LR] [R/ee) repetitions of such a procedure we can find with accuracy (by function) the solution of the original problem.
26

---

NeurIPS Paper Checklist
1. Claims
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 [ (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 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 other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section I (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 move away from the assumptions under consideration, e.g., the gradient dominance assumption (Polyak-Lojaseevicz condition). Guidelines:
The answer NA means that the paper has 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 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 few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
The main assumptions and notations can be found Section (Introduction). Each theoretical statement contains conditions (assumptions) under which a particular result is guaranteed. And also after each theoretical result (discussion) there a link to the Appendix section with detailed proof.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 7 (Experiments) presents particular problem formulation ( which demonstrates the performance of the proposed algorithms with counterparts a nu- merical experiment. Also, both in the main Section 7 and in the additional Numerical Experiments Section (Appendix) [B), detailed information on the hyperparameters used and other information necessary to reproduce the experiments is provided.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
28

---

(d)
reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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 to implement the code ourselves without difficulty. However, if the Re- viewers or Area Chair feel that the information provided is not sufficient for reproducibility of the experiments, will certainly add link to anonymous repository with the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niip.cc/
Suuiides/CodeSumissse
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
huips..c/publiccguuu.ees/ Cwte//ooeeeeeeiieeeeeeeeee cessiinnPoccyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, 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 the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
29

---

Unfortunately running experiments several times to calculate statistics and error bars would be too computationally expensive
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Detailed information is provided in the section with additional experiments (see Appendix B Technical Information)
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Fthics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpp:://euur
Answer: [Yes]
Justification: Research conforms with NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
30

---

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 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 tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that 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 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.
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).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Presented research doesn't 't need safeguards
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and 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 existing assets.
31

---

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 URL.
The name of the license ge.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.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, (paperswithcode coltde..coo/oo datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pase 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 s creators.
13. New Assets
Question: Are 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.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
32

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
33


Reviews:
[{"review_id": "hBtk1jrpqX", "reviewer": "Reviewer_XqbR", "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.", "questions": "1. Could you provide more specifics about the numerical experiments?\n2.  Could you show numerical validation in real-world problems and datasets?\n3. Are there any experiments being conducted for the stochastic order oracle? Could you show the results in that setting?", "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.\n2. 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\n3. The accelerated version requires updating multiple parameters and has multiple steps and iterative processes that potentially increase the computational load.\n4. 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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper formalizes a novel concept called Order Oracle, which enables optimization without requiring exact function values.  Building on this concept, the authors develop two new algorithms, OrderRCD and OrderACDM, which integrate the Order Oracle into the coordinate descent framework. The paper provides a  comprehensive theoretical analysis demonstrating the effectiveness of OrderRCD across non-convex, convex, and strongly convex settings and showing faster convergence rate of OrderACDM in strongly convex setting.  The convergence proofs of both the algorithms are detailed. Additionally, this paper also introduce the first algorithm using the stochastic Order Oracle with asymptotic convergence guarantees. They also show practical effectiveness of OrderRCD and OrderACDM compared to traditional methods through their numerical experiments.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear **Reviewer XqbR**, \n\nWe would like to thank you for your time for preparing the review.\n\n> **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.**\n\nSince 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.**\n\n> **Could you provide more specifics about the numerical experiments?**\n\nFirst, 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.\n\n> **Could you show numerical validation in real-world problems and datasets?**\n\nAs 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.\n\n>**Are there any experiments being conducted for the stochastic order oracle? Could you show the results in that setting?**\n\nOf 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.\n\n>**Limitations.**\n\nThank you, we will be sure to add a \"Limitations\" section to the main part of the paper.\n\n# **Significance and novelty of our results**\nIn 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.\n\n[1] Zhang, C., & Li, T. (2024). Comparisons Are All You Need for Optimizing Smooth Functions. arXiv preprint arXiv:2405.11454.\n\n[2] Drori, Y., & Taylor, A. B. (2020). Efficient first-order methods for convex minimization: a constructive approach. Mathematical Programming, 184(1), 183-220.\n\n[3] Narkiss, G., & Zibulevsky, M. (2005). SESOP: Sequential Subspace Optimization Method.\n\n[4] Hager, W. W., & Zhang, H. (2006). A survey of nonlinear conjugate gradient methods. Pacific journal of Optimization, 2(1), 35-58.\n\nWith Respect,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xf1wc7MiO6", "reviewer": "Reviewer_K16N", "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:\n\n 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.\n2. 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.\n3. The paper gives a stochastic version of the algorithm.\n\nThe 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.\n\nFor the accelerated algorithm, the authors need to include a secondary line search to ensure that the iterates are always making progress.", "questions": "1. When you say adaptive in the text, what does that mean?\n2. 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?\n3. What is the notation with $\\alpha$?\n4. Are there examples (even experiments) that can say something about the difference between the order oracle and usual first order oracles?\n5. In the accelerated algorithm, are there adversarial examples where the second line search is necessary?\n6. What is the barrier in extending the acceleration beyond strongly convex objectives.", "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.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper demonstrates that using a very weak oracle such as order oracle is sufficient to get rates of convergence that match the rates of the optimal gradient methods via first order oracles. The algorithms are quite simple and work well in practice as shown in the experiments. The ideas are original and the results are presented clearly.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear **Reviewer K16N**,\n\nWe thank you for your positive evaluation of our work! Below we provide detailed answers to all comments and questions that arose in the review.\n\n> **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.**\n\nWith 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. \n\n> **When you say adaptive in the text, what does that mean?**\n\nThis 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.\n\n> **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?**\n\nIndeed, 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.\n\n> **What is the notation with $\\alpha$?**\n\nBy $\\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]. \n\n> **Are there examples (even experiments) that can say something about the difference between the order oracle and usual first order oracles?**\n\nYes, 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.\n\n> **In the accelerated algorithm, are there adversarial examples where the second line search is necessary?**\n\nAt 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).\n\n> **What is the barrier in extending the acceleration beyond strongly convex objectives?**\n\nAs 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.\n\n[1] Bubeck, S. (2015). Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning.\n\n[2] Nesterov, Y. (2012). Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization.\n\n[3] Nesterov, Y., & Stich, S. U. (2017). Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM Journal on Optimization.\n\n[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.\n\nWith Respect,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1mMzqtvE8N", "reviewer": "Reviewer_uSy5", "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.", "questions": "1. in assumption 1.1, can L-coordinate-Lipschitz suggest L-smooth?", "limitations": "see above", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. overall, the paper is clear and easy to follow.\n2. the author provided solid analysis to the convergence of the proposed algorithms and the results look correct to me.\n3. the proposed algorithm looks clean and simple.", "weaknesses": "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).\n2. 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.\n3. 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. \n4. 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.\n\n\nminor issues:\n\n1. line 77, missing something after \"to the inner product as..\" ?\n2. line 78, L_i appears before it is defined.\n3. table 1, many parameters appear before they are defined.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear **Reviewer uSy5**,\n\nWe thank you for your interest in our work. We attach below detailed responses to the comments and questions raised in the review.\n\n> **i have some concerns on the novelty of this paper...**\n\nWe 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)*.\n\nPerhaps 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:\n- The approach proposed in our paper is perhaps the only feasible scenario at the moment. \n- 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. \n- 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.\n\nHowever, 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.\n\n> **both of the proposed algorithms are...**\n\nWe 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.\n\n> **the numerical experiment is too simple...**\n\nAs 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.\n\n> **in the accelerated case, it's not clear to me...**\n\nWe 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.\n\n> **minor issues.**\n\nThank you, we will correct those typos.\n\n> **in assumption 1.1, can...**\n\nAssumption 1.1 is standard for the class of coordintate algorithms and implies some L-smooth over each coordinates.\n\n[1] Zhang, C. et al. (2024). Comparisons Are All You Need for Optimizing Smooth Functions.\n\n[2] Drori, Y. et al. (2020). Efficient first-order methods for convex minimization: a constructive approach. \n\n[3] Narkiss, G. et al. (2005). SESOP: Sequential Subspace Optimization Method.\n\n[4] Hager, W. W. et al. (2006). A survey of nonlinear conjugate gradient methods. \n\n[5] Nesterov, Y. et al. (2017). Efficiency of the accelerated coordinate descent method on structured optimization problems.\n\nWith Respect,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AXdNKSEjGa", "reviewer": "Reviewer_WKzP", "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.", "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?\n\n2. 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": "The author could discuss the limitations in high-dimensional space if this is indeed a constraint of the proposed method.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The order oracle setting is new.\n2. The theoretical analysis seems solid.", "weaknesses": "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.\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear **Reviewer WKzP**,\n\nWe thank you for your feedback on our work. We provide detailed answers to the comments and questions raised in the review below.\n\n> **Elaboration on Motivation.**\n\nDespite 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. \n\n> **Comprehensive Experimental Validation.**\n\nIndeed, 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.\n\n> **Performance in High-Dimensional Space.**\n\nThe 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.\n\n> **Technical Challenges compared to Nesterov's 2012 Work.**\n\nTo 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*:\n- The approach proposed in our paper is perhaps the only feasible scenario at the moment. \n- 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.\n- 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.\n\nHowever, 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.\n\n> **Dimension-Independent Complexity.**\n\nThis 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}}$.\n\n[1] Nesterov, Y. (2012). Efficiency of coordinate descent methods on huge-scale optimization problems.\n\n[2] Zhang, C. et al. (2024). Comparisons Are All You Need for Optimizing Smooth Functions. \n\n[3] Drori, Y. et al. (2020). Efficient first-order methods for convex minimization: a constructive approach. \n\n[4] Narkiss, G. et al. (2005). SESOP: Sequential Subspace Optimization Method.\n\n[5] Hager, W. et al. (2006). A survey of nonlinear conjugate gradient methods.\n\n\nWith Respect,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PsUpDxrlO6", "reviewer": "Reviewer_ErqJ", "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.", "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).\n\n- 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).\n\n- The accelerated algorithm 2 has several loops, which makes me wonder how well it would be able to deal with noise in the oracle.\n\n- 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": "Yes it's adequately addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper has clear exposition and adequately surveys the related literature. The problem under study is of great interest to the machine learning community and has many interesting applications. The technical claims are sound and presented ideas are conceptually simple with demonstrated good performance in several setting.", "weaknesses": "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: \n\n- 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$?\n\n- 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.\n\n- 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.\n\n- In (8), it would be better to use the subscript $f_\\zeta (x)$, which would make the notation more consistent with (1).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear **Reviewer ErqJ**,\n\nWe thank you for your feedback on our work.\n\n> **I don't think the analysis result of...**\n\nWe provide detailed answers to all questions below, including concerns about the significance and novelty of our results.\n\n> **Line 77 is not finished. Line 78...**\n\nThank you, we will correct those typos.\n\n> **It would be good to put the GRM...**\n\nDue 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.\n\n> **Line 179: I'd suggest using...**\n\nIn 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.\n\n> **In (8), it would be better...**\n\nThank you for this comment, we will correct this typo.\n\n> **Why is coordinate descent the best thing to do? To me...**\n\nFirst 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. \n\nRegarding 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.\n\nMoreover, 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.\n\n> **Algorithm 1 as stated works...**\n\nAs 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.\n\n> **The accelerated algorithm 2 has several loops...**\n\nRegarding 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.\n\n> **Similarly in Section 5, these reductions to existing methods...**\n\nIn 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.\n\n[1] Zhang, C., & Li, T. (2024). Comparisons Are All You Need for Optimizing Smooth Functions. arXiv preprint arXiv:2405.11454.\n\n[2] Drori, Y., & Taylor, A. B. (2020). Efficient first-order methods for convex minimization: a constructive approach. Mathematical Programming, 184(1), 183-220.\n\n[3] Narkiss, G., & Zibulevsky, M. (2005). SESOP: Sequential Subspace Optimization Method.\n\n[4] Hager, W. W., & Zhang, H. (2006). A survey of nonlinear conjugate gradient methods. Pacific journal of Optimization, 2(1), 35-58.\n\n\nWith Respect,\n\nAuthors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear **Reviewers**, we thank you for taking the time to prepare reviews of our work. We have prepared detailed answers to the comments and questions that arose in the reviews. Our responses will be found under the official review. However, we would like to emphasize the highlights from your reviews. 

- For example, **Reviewers XqbR** and **uSy5** advised to add experiments closer to reality. We would like to point out that our work was initiated due to a challenge faced by one of the co-authors in the realization of a startup (a smart coffee machine, see Appendix A1). 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.

- Whereas **Reviewer K16N** emphasized in the Summary section all the key points of our work that demonstrate the significance and novelty of the results. *We would like to describe them in more detail*: This work was motivated by a specific application problem (startup: smart coffee machine), but the presented results are not limited to it! The oracle concept under consideration has a number of applications, including perhaps the most popular setting, namely *Reinforcement learning with Human Feedback (RLHF)*. It is also worth noting that all previous works (see Section 2 and Table 1) have only achieved unaccelerated estimates under various convexity assumptions. 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 [1-3]. 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 already 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.

- Finally, **Reviewers WKzP** and **ErqJ** drew attention to the proposed additional advantages of our approach. Namely, the advantage in the case of a high-dimensional problem, which is typical for the class of coordinate algorithms. Since we are based on the coordinate descent 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. 

We would like to thank **all Reviewers** once again for their interest in our work. We really appreciate it!

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

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

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


Best regards, 

Authors

Meta-review: 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.
Decision: Accept (poster)