A Theoretical Framework for Zeroth-Order Budget Convex Optimization
Authors: François Bachoc
Tommaso Cesari
Roberto Colomboni
Andrea Paudice
Venue: Accepted by TMLR ()

Abstract: This paper studies a natural generalization of the problem of minimizing a convex function $f$ by querying its values sequentially. 
At each time-step $t$, the optimizer selects a query point $X_t$ and invests a budget $b_t$ (chosen by the environment) to obtain a fuzzy evaluation of $f$ at $X_t$ whose accuracy depends on the amount of budget invested in $X_t$ across times.
This setting is motivated by the minimization of objectives whose values can only be determined approximately through lengthy or expensive computations, where it is paramount to recycle past information. 
In the univariate case, we design ReSearch, an anytime parameter-free algorithm for which we prove near-optimal optimization-error guarantees.
Then, we present two applications of our univariate analysis.
First, we show how to use ReSearch for stochastic convex optimization, obtaining theoretical and empirical improvements on state-of-the-art benchmarks.
Second, we handle the $d$-dimensional budget problem by combining ReSearch with a coordinate descent method, presenting theoretical guarantees and experiments.

Published in Transactions on Machine Learning Research (10/2024)
A Theoretical Framework for Zeroth-Order Budget Convex Optimization
François Bachoc
francois francois bachoc@mahhh.cccccooomooooooocc. univ-toulouse.
Institut de Mathématiques de Toulouse Université Paul Sabatier
Institul universitaire de France (IUF)
Tommaso Cesari
tcesari@uolkowva.co
School of Electricol Engineering and Computer Science University of Ottawa
Roberto Colomboni
roberto, colomboni@@nimii.. it
Università degli Studi di Milano Politecnico di Milano
Andrea Paudice
apardice on. dk
Department of Computer Science Aorhus University (AU)
Reviewed on OpenReview: https: openreviee.. net/ forum? bo8uM99330
Abstract
This paper studies a natural generalization of the problem of minimizing a convex function by querying its values sequentially. At each time-step the optimizer selects query point X, and invests budget b, (chosen by the environment) to obtain fuzzy evaluation of at X₁ whose accuracy depends the amount of budget invested in X₁ across times. This setting is motivated by the minimization of objectives whose values can only be determined approximately (hrough lengthy or expensive compulations, where is paramount to recycle past information. In the univariate case, we design ReSearch, an anytime parameter-free algorithm for which we prove near-optimal optimization-erro guarantees. Then, we present two applications of our univariate analysis. First, we show how to use ReSearch for stochastic stafe-of-the-art
convex optimization, obtaining theoretical and empirical improvements benchmarks. Second, we handle the d-dimensional budget problem by combining ReSearch with coordinate descent method, presenting theoretical guarantees and experiments.
1 Introduction
Consider the following fundamental question: given convex real-valued function f, how can we efficiently and sequentially select oracle queries of it in order to recommend point æ such that f(x) is close possible to the infimum of f? This problem is known zeroth order convex optimization and has been studied for more than half century (Roscnbrock) 1960). The field has also recently attracted the interest of the machine learning and statistical community because computing the gradient of a function that depends on a large dataset (e.g., the empirical risk) can be very expensive if not unfeasible (see for example Bubeck ct al. 2202 and references therein). Another significant application arises simulation-basor optimization, where the goal is optimally tune the parameters of system by only observing its output (Conn al.
2009 Spall 2005

---

Published in Transactions on Machine Learning Research (10/2024)
There are several different ways to model this problem. In the deterministic setting, the oracle answers each query x with the exact value f(x). The classic stochastic setting alleviates the restrictiveness of the deterministic oracle by assuming that each query returns a noisy independent estimation of f(x). This oracle model is still not flcxible enough to cover applications where perturbations are not independent or where the optimizer can compute the value [(x) at a query point x with incremental precision. The former is crucial include scenarios where errors have long-range dependence (Lahiri] 2003 Beran 2017]. The latter has several practical applications, e.g., when the values of f are the results of long sums (as in time-series forecasting via weighted empirical risk minimization: Kuznetsov & Mohri 2015 2016) or, crucially, when they can only be computed approximately through lengthy simulations (as it happens ubiquitously in the field of computer experiments; Santner et al. 2003: Sacks et al. 1989).
Contributions.
We make the following contributions:
We design novel zeroth-order budget optimization setting where the oracle answers each query æ with an interval that is guaranteed to contain f(z) and whose length decreases with the amount of budget invested on r so far. In addition to generalizing the deterministic and stochastic settings, our model also captures the aforementioned problems not covered by them. (Section 2
We design ReSearch, an anylime, praclicable, and parameter free algorithu for univariale zeroth-order budget convex optimization that works under minimal convexity assumption on f. (Section 3.1
We prove sharp anytime upper bound the optimization error of ReSearch. Furthermore, our analysis reveals that the optimal dependence on the Lipschitz constant of f is extremely mild, asymptotically negligible, and can be entirely lifted by transitioning to a continuous budget optimization setting, (Section 3.2
We prove a matching (up to constants) lower bound, certifying the optimality of ReSearch. (Sec-
lion 3.3
We apply ReSearch and its analysis to univariate stochastic convex optimization, improving the state-of-the-art guarantees for this problem. (Section 4.1)
We illustrate how to handle the d-dimensional budget setting using ReSearch subroutine of a coordinate-descent algorithm and provide corresponding theoretical guarantees. (Section 4.2)
Finally, we present illustrative experiments supporting our theory in the univariate stochastic and uni/multivariate budget settings. (Section 5
Related Work. Zeroth-order convex optimization is massive field with vast literature. We limit our discussion lo references more closely aligned with the scope of this paper.
The deterministic case is the simplest setting in zeroth-order optimization, where the oracle answers each query x with the exact value the objective fzx) (see Nesterov et al. 2018 and references therein). Although not the core of our work, we highlight that in this setting, our one-dimensional algorithun ReSearch achieves the well-known optimal geometric decay on the optimization error while not requiring the objective to be globally Lipschitz.
To the best of our knowledge, our flexible budget setting with errors decaying as functions of the budget is not addressed theoretically in the convex optimization literature. The more specific stochastic setting, where the oracle answers queries with random independent estimates of the objective, is studied in particular by Agarwal et al. 2013); Jamieson et al. 2012);; Shamir (2013): : Belloni et al. (2015). Our budget setting recovers it as special case when errors decay as O(1/ budget). In the one-dimensional case, an optimization error of Q(//T) is unavoidable in the stochastic setting, even knowing the time-horizon T' in advance and under the additional assumptions of smoothness and strong- convexity (sce Shamir 2013, Theorem 3). This rate is also achieved by Belloni et al. (2015) and Lattimore (2020), with high- bigh-brobability and in in-expectation respectively, up to extra log terms; however, these algorithms are quite involved. Agarwal et al. (2013) and [Jamicson et al. 2012) propose simpler and more practical trisect ion-baed algorithms with similar optimization error guarantees. While these algorithms share some features with ReSearch (e.g., they monitor confidence-interval soparation discard domain portions), our analysis departs substantially from those of Agarwal et al. (2013) and Jamieson et al. (2012), leading to additional theoretical benefits (in particular, a negligible dependence the Lipschitz constant and improved logarithmic dependence on the time horizon T). Finally, in
2

---

Published in Transactions on Machine Learning Research (10/2024)
contrast to the works above, highlight that reduction from the univariate budget to the univariate stochastic setting hold without any additional assumption (such as strong convexity, smoothness, or global Lipschitzness).
2
Setting
Given a bounded convex set c IR", our goal to minimize an unknown conver function f: + IR picked by a possibly adversarial and adaplive enviroument by only requesting fuzzy evaluations of f. At every interaction I, the optimizer selects a query point X, and the environment selects and reveals a budget by- This budget then used reduce the fuzziness on the value of f(X;), modeled by an interval J2 f(X)). In other words, the reader might think of the budget a perishable (must be spent in full at every interaction) and non-divisible (all must be spent in single query point) amount of resources made available by the environment to reduce the fuzziness of the value of the unknown objective at the current query point.
The interactions between the optimizer and the environment are described in Optimization Protocol
Optimization Protocol 1
input:
A non-empty bounded convex set T
Rd (the domain of the unknown objective
f)
for t= 1,2.... do
The optimizer selects query point X₃ I where to invest the next budget
The environment picks and reveals budget b, 0 and an interval Je c R such that f(X,) e J.
4:
The optimizer recommends point R, E
We stress that the enviromment is adaptive. Indeed, the intervals J, that are given as answers to the queries X, can be chosen by the environment as an arbitrary function of the past history, as long as they represent fuzzy evaluations of the convex objective f (i.e., as long as f(X,) Je for all t).
Note that optimization would be impossible without further restrictions on the behavior of the enviromment, since an adversarial convex enviromment could return meaningful information. We limit the power of the environment by relating the amount of budget invested in query point X, with the length of the corresponding fuzzy representation Jj of f(X)), as quantified by the following assumption.
for all / E N, making it impossible to gather any
Assumption 2.1. There exist e and a > 0 such that, for any Le N, if the optimizer invested the budgets bl....,by the query points N1, then
s c/
where [rl] denotes the length of J, and B, E 6,I1(X, X2) is the total budget invested in X, up to time
t.
The performance of recommendation Rr is evaluated with the optimization error f(Rr) - inf f(x).
3 An optimal algorithm for the univariate case
In this section we study the univariate budget convex optimization problem, i.e., the case when the underlying convex set = is a bounded interval. To solve this problem we propose ReSearch, an algorithm exploiting the 1-dimensional nature of the problem by following a query strategy that allows the learner recycle most. of the past queries (Algorithm
3.1 ReSearch
Before presenting its pscudo-code, we introduce some notation. For any positive integer n N we denote by [n] the set [1, (I.....n) of the first integers. Let P = Tmm mar. DD m The blackened parts of the elements of P represent which portions of the active interval maintained by ReSearch the algorithm
3

---

Published in Transactions on Machine Learning Research (10/2024)
Je
J+
J,
J JI
Figure 1: A representation of the delete function. Since Jj s Jr. the points right of r are deleted, ie.,
delete(Js, Je, MTT.
1/1
1/2
3/1
0
1/3 1/2 2/3
Figure The uniform (u) and non-uniform (1) partition functions applied to the interval / [0, 1].
will delete. Additionally, we will consider the element mmm representing the where no parts of the active interval will be deleted. Let J be the set of all intervals, and I c J that of all bownded intervals. Furthermore, for any interval J E JT, let J = inf(J) and J = sup(J). ReSearch relies on four auxiliary functions: the delete function, the uniform partition function u, the non-uniform partition function şl, and the update function. The delete function (sce Figure 1
delete: J + PU (mm)
is defined, for all (J,, J8, by
if Jf J,, else
if 2 Jt, elsc
if min( Jo J²) & J, 2 min(Jf,J3 else
if 2 min( J J²), else
if Jr 2 min (Jt Jz), else
In words, the intervals Jt, Jey Jr will represent the fuzzy evaluations of three points I < <cr in the domain of the unknown objective (left, center, and right). Since we are assuming that the objective is convex, note that whenever an upper bound on the value of the objective at point is lower than the lower bound at another point that is left (resp., right) of z, then, all points that are left (resp., right) of y (y included) are no better than x. Therefore, the function delete returns which part of an interval containing three distinct points I e r should be deleted given the fuzzy evaluations JJ. (E.g., B represents the deletion of all points of the active interval left. of c, ar represents the deletion of all points of the active interval right. of r, emm is returned when the fuzzy evaluations are not sufficient to delete anything, etc.)
The uniform and non-umiform partition functions (see Figure are defined, respectively, by
u: I- R33
T ( 1 1 + +
:: I R3,
1
In words, the uniform (resp., con-uniform) partition function (resp., () returns the three points that are 1/4 1/2, and 3/4 (resp., 1/3, 1/2, and 7/3) of the input interval I.
4

---

Published in Transactions on Machine Learning Research (10/2024)
The update function
update: Ix (u,1) x Ix (u,))
is defined, for all (I, 0, del) &Ix {u, {) x P, by the table:
[ 1 r r [1, I
[ 1
[ !
31++1
rar
25
+21
11 [3r+ (1-,
(
In words, when applicd to an interval I, type of partition 1, and symbol del (representing the subset of I to be deleted), the update function returns as the first component the interval pruned of the subset of I specified by and del, and, as the second component, how the new interval will be partitioned. It can be seen that the types of partitions returned by update are chosen so that our ReSearch algorithm will only query points on (rescaled) dyadic mesh (e.g., if I [0. 1], ReSearch will only query points of the form k/2², for e
For all t e N, if the sequence of budgets picked by the environment up to time t is bi....,bu b,, the se- quence of query points selected by the optimizer is XI....,X, the corresponding feedback is JI....,JJ (see Optimization Protocol D then, for each x E IR, we define the quantities
Ba, Σ bb and
Jz,t
J. se[t],X,.F
with the understanding that Jz,t IR whenever X, x for all E [t]. Purthermore, define Ba.0 for all e R. In words, Ba, is the total budget that has been invested in by the optimizer up to and including time t, while Ja is the best fuzzy evaluation of the unknown objective at x that is available at the end of time t.
The pscudocode of ReSearch is provided in Algorithm 2 ReSearch proceeds in epochs 7 where it maintains an active interval I, and three query points C,, r, Ir. During each epoch t, it repeatedly queries a point in (r,) where it invested the least amount of budget until the function delete has gathered enough information to prune the current active interval. When this happens, first it updates the active interval and the type of partition using the update function. Then, it computes the three query points 4,+1, : of the next epoch 7 1. Notably, among 1r+1, there will be the point among Cr, that has the smallest value of f (or one of them, if there are more than one). Afterwards, the algorithm recommends a point I É {1++1, Tr+1} } with the best known upper bound Jr, on the value of f(x) available at the present time t and concludes the curent epoch. In all rounds in which function delete has not yet gathered enough information to prune the current active interval, the algorithm makes different recommendations depending on whether or not the amount of budget invested in the current epoch is higher than the amount of budget spent in all past epochs combined. See Figure 3 for an illustration of how ReSearch works.
We stress that ReSearch is any-time (it does not need know the time horizon T priorí), any-budget (it does not need to know the total budget B = Σx" by) and does not require the unknown objective to be Lipschitz. Nevertheless, we will show in Theorems 3.1 and 3.2 that its performance is guaranteed to be near-optimal even when compared to algorithms with full knowledge of T' and B, and run on convex Lipschitz functions with known Lipschitz constant.
3.2 Upper bound
We now provide theoretical guarantees for ReSearch.
Under Assumption 2.1 this corresponds to recommending a point Dee (4.,0.,7)) rr) with the best known upper bound J the value of {()) that will "survive" as query point of the next epoch. Indeed, for x e (1e41,0re1:7e rr41) x. (l,,ce ry }, we have J = +00, since has never been evaluated. On the other hand, any z (Jr, cr. Fr) has already been evaluated, hence J co.
5

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm ReSearch
input: A non-emply bounded interval Ic I (the domain of the unknown objective)
initialization: 1 := [[_ [1], 01 =u, (4, = (111), to = 0, Bo = 0, B1,0 = 0
for epochs 5 1,2. do
for 1= 4- 1,4--1 +..... do Query X; arggin Ba,-1
4:
Let del; = delete(Ji,,t Jor Je.
5:
Let B, = B,,t-1+ by and To TT
6:
if del, + mmn then
Let 1,:=,, B, = Br and Bro1ą == Let (1++1, update(Ln (Ly, 0r delı) Let (I.+1, P = 0,.1 (1++1) Recommend RG ar 11: break
7:
10:
J
12:
else if B 2 Σ Br then Recommend R₂ argmin (lore,)))) J
13:
14:
else
15:
Recommend R₂ Rt,-1
f(x)
Figure run of ReSearch. Here, the function piece-wise linear and graph is thick black. The horizontal segments are the active intervals I, of consecutive epochs т. The short vertical segments are the current query points 1,,4,r of epoch t, and the dots (prolonged down vertically) are the recommendations at the end of each epoch, that converge towards z". Note that, from one epoch to the next, two out of three points are kept (together with their guarantees), maximizing the recycling of past information.

---

to Published in Transactions on Machine Learning Research (10/2024)
Theorem 3.1. For any bounded interval I c R, if the optimizer is running ReSearch (Algorithm 2 with inpul in an environment salisfying Assumplion 2.7 for some C 2 0 and a O, then, there cxist 01 & 12 (48/(221 - 1))², 22 s 9/8, c3 2 (ln2)/48 such that, for any time T E N, every sequence of budgets b1.....bu br > O, and every convex function f:I + R, the optimization error f(Rr) - inf f()) is upper bounded by
ΣL by c2 L L1| -C3 [ax by .2.
C1
(1)
b))
where L is the local Lipschilz constant of I on [
The full proof of this result can be found in Appendix A Before presenting sketch of it here, we make few remarks. First, note that the bound is non-trivial even when the function is not globally Lipschitz (as it is the case, e.g., for the function -- -v=)=vvI==" defined on the interval = [-1,1]], since it depends a local Lipschitz constant L (which is always finite) that, informally, as the epochs go by, captures better and better how much the function varies around the points that are close to the minimum Second, note that (up to the constants c1, C22 Ca) the bound consists of two terms.
The first term // c/(2=1 by)% is a consequence of the fuzziness of the evaluations, that is regulated by Assumption 2.1 when Σ.1 by 2 1, decreases when a increases or с decreases. Moreover, when c= and 6, 1 for all t [T], our problem reduces to deterministic convex optimization. In this case, the first term vanishes completely, leaving behind only the known optimal exponentialll-decaying rate e convex optimization.
e -Q(() for deterministic
The second term L| e bx/ maxerry br) is consequence of the discrcte nature of our sctting. Notably, if the optimizer could choose to invest infiniesimaall small budgets b, (i.e., if the discrete optimization protocol became continuous one), the term would vanish completely. Strikingly, when this is the case, the bound becomes completely independent of the Lipschitz constant L. To the best of our knowledge, this is the first result in convex optimization that shows how the dependence on L could be entirely lifted if we transitioned from a discrete to a continuous setting. In other words, our bound gives a parameterization of the dependence on the Lipschitz constant in terms of how close our setting is to a continuous one. The high-level reason for this behavior is that, in a discrete setting, the optimizer might be forced to spend large amount of budget. b, on point X, where significantly smaller investment would have been sufficient to determine whether not that point was suboptimal. In this case, if the function is varying significantly, the number of queries could not be sufficient to get close to a minimizer, and this would yield an optimization error that scales with L. Finally, we note that, naturally, the Lipschitz constant L and the domain length |/] appear as a product. Indeed, shrinking (resp., dilating) the domain of a function f:l + R corresponds an increase (resp., decrease) of the Lipschitz constant.
Proof sketch. We divide the analysis in the cases sketched below, depending on how ReSearch selects Rr-
1. dely LTr. In this case, we partition the number of epochs in several classes and focus our attention on the class where invested the highest fraction of the total budget Σ by. Say that this class contains n epochs. If n is small, we show that in the last epoch of this class there exist two query points that are nctr-optimal and that the recommendation Ry of ReSearch has guarantees that are close to those of these two near-optimal points. II, on the othe hand, n is large, the result follows by the local Lipschitzness of f.
2. dely omm and the majority of the budget was invested in the last epoch. In this case, we split again the analysis in two further cases. If the maximum budget max by is small, we show that all three query points of the last epoch are near-optimal, therefore is the recommendation Ry- II, on the other hand, the maximum budget m by is large, we fall back again to the local Lipschitzness of the objective.
3. dely = ITT and the majority of the budget was invested before the last epoch. Since in this case the recommendation Ry is the same as the recommendation that ended the previous epoch, the result follows by Item [ using half of the total budget.
0
For more on the advantages of adaptive local Lipschitz constant, see Appendix F
7

---

Published in Transactions on Machine Learning Research (10/2024)
3.3 Lower bound
In this section, we show that ReSearch is worst-case optimal: there exist instances where the upper bound of Theorem 3.1 is matched (up to possibly different constants C1, C2, c3). The apparent asymmetry between our upper and lower bounds is due to the fact that, in Theorem 3.2
We gave the optimizer the freedom to select the time horizon T and total budget ahead of time. We restricted the result to convex Lipechitz functions.
Note that both these changes make our results stronger, since ReSearch is able to match the lower bound despite lacking the freedom to select T, B (in fact, being totally oblivious to possibly adversarial choice of both) and Theorem 3.1 holds even for non-Lipschitz functions.
Theorem 3.2. For any nondegenerate bounded interval I IR, if the environment satisfies Assumption 2.1 for some с 2 0 and a > 0, then, there evist 01 2 1/4,22 2 1/2e,, S 1 such that, for any time T e N, every total budget B > O, every Lipschilz conslant. I. O, and every delerministic algorithm run by the optimizer, there erists a sequence of budgets by....,by such that Σi b = B and there erists a max [ - -Lisschtt conver. function f:1 R, for which the optimization error f(Rr) -inf f(x) is lower bounded by
Σt be
+ c2 L exp
-Cs max bt
(2)
(Σ b,)a
We defer the proof of this result to Appendix
B
4
Applications
We present two notable applications of our method. First, we show how to apply ReSearch to the case of univariate stochastic convex optimization, improving on state-of-art bounds; remarkably and in contrast with previous works, the algorithm does not require the Lipschitzness of the objective. Second, we illustrate how to address the multivariate budget case by combining ReSearch with a classic coordinate descent method (see Tseng 2001 and references therein) when the objective is smooth and strongly convex.
4.1 Univariate Stochastic Convex Optimization
In this section, we show how to apply ReSearch to the related problem of univariate stochastic convex optimization (SCO). Typically, in this problem, one assumes that querying a point x returns an i.i.d. subgaussian (noisy) evaluation of the unknown objective f(x). Instead, we will introduce more general setting where the key property is the concentration of the (averages of the) queried evaluations. This way, we recover the classic SCO but also obtain results for more general non-i.i.d settings (see below).
Let I be bounded interval and f:I + R an unknown convex function.
Assumption 4.1. There exist > 0, cs (0, 1) - (0, o0), m: UheN R² R, and family of random variables (Yz,s) safisfying, for all x e and t N,
p P[Im(Y.,...., V..,) -((()( S
(()) ta 2 21-8.
Note that, in classic SCO, where for each x é I, the sequence (YN,))eN is iid. and o-subgaussian, Assumption 4.1 is implied by Hoeffding's inequality for a = 1/2, c(5) == 2 In(/0) (for all & e (0,1)) and m as the empirical average. The case a < 1/2 in Assumption 4.1 relevant to model errors with long-range dependence (Tahiri 2003 Beran 2017). To give simple example, consider that (Ya,) are Gaussian for t, and for fixed [ (0, Then, it can be checked that Assumption 4.1 holds with m as the empirical average, with a= 3/2 and with c(8) = In This is obtained by bounding the variance and then the tail of the (Gaussian) average.
with Cov(Y..a. Y2, (1+((t())
Let T N be the time horizon. The learner interacts with the environment according to Optimization Protocol As before, the goal is to minimize the optimization error after T time steps f(Rr) inf f(x).
8

---

Published in Transactions on Machine Learning Research (10/2024)
Stochastic Optimization Protocol 3
for t= I...., T' do
The optimizer selects query point X₁ I The environment reveals N,,, where N = Exee T(X, = Xx}
4: The optimizer recommends a point Rr E
By running ReSearch with feedback Jr equal to a suitable confidence interval for f(X,) (at each time t), we extend the state-of-the-art for stochastic convex optimization (Agarwal et al. 2013) beyond the globally-Lipschitz case and, even where the previous guarantees held, improve them in two ways: we remove logarithmic factor from the bound and we only pay the Lipschitz constant in the non-dominating term, which decreases exponentially with T.
To lighten the notation, let M2 == m(Yx,, Nx,,N) and consider Algorithm
Algorithm ReSearch for SCO
input: Confidence paramcter d (0,1)
1: for t- 1,.,..., do
2: ReSearch selects the next query point X,
The optimizer feeds ReSearch with the feedback
Jj = M1 1 o(8)
2 No M1 + No
c(8)
ReSearch recommends point RT
Note also that M, is (in general) a biased estimate of f(X.), even in the case when is the empirical average
Theorem 4.2. If the optimizer runs ReSearch for SCO (Algorithm 4, its optimization error is upper bounded by
c(0) T + c2 L|/
C1
on the complement of an event having probability O) where c1, 02, c3, L are as in Theorem 3.1
In particular, in the iidd. subgaussian setting, picking 8 0(1775/2) yields an expected optimization error of order /loTT)/TT improving the state-of-the-art in Agarwal et al. (2013) by log T factor.
We defer the proof of Theorem 4.2 to Appendix
4.2 Multivariate Budget Convex Optimization
We now illustrate how to ReSearch to address the multivariate budget setting (sce Algorithm 5]. where the objective f is defined coordinate descent method in the spirit of Jamieson et al. (2012). Coordinate descent is typically analyzed assuming that the objective f is strongly convex and smooth, which we also assume until the end of the section.
convex bounded subset. I c Rdd We use adaplation to the budget setting of
Algorithm 5 proceeds by performing sequential line searches. During line search k it uses ReSearch along a segment determined by base point Ią and a randomly drawn axis i(k), recommending points based on the recommendations of ReSearch. A line search is concluded as soon the length of the active interval of ReSearch is At the end of each line search, the base point It+1 is updated using the best point found by ReSearch.
Because ReSearch recycles past observations multiple times, even after they have been used to decide which part of the current interval to discard. (At high level, the estimates of the values of the function the points that keep have the tendency to "look better".) This recyeling of information feature, not flaw the algorithm, allows reaching approximate minimizer with smaller number queries (see Section 5.2

---

Published in Transactions on Machine Learning Research (10/2024)
10
10-1
10
10
10a
10-2
100
10-3
10-2
10-2
10
10-1
10-5
10
10-6
100
102
10a
10
10
10c
10
10
10a
10a
10
10a
10a
10
10
10
(a) Univariate budget
(b)
Univariate stochastic
Multivariate budget: error
0.5
0
20
40 60
100
(d) Multivariate budget: runtime
Figure 4: (a) The optimization error of ReSearch (black) is compared with the corresponding upper (red) and lower (blue) bounds. (b) The median optimization error of ReSearch for SCO (black) is compared with Jamicson et al. 2012 (groen) and Agarwal et al. 2013 (orange); shaded arcas are inter-Quartll Ranges. (c) The average optimization error of Algorithm tuned in Theorems 4.3 and D.I (black) is compared with its corresponding upper bound (red) and alternative choices of ry: (blue), 0.1 (purple), 0.01 (orange) see Section 5.3 Plots are in log scale. (d) The average runtime of Algorithm 5 is plotted against the dimension
of the problem -see Section 5.3 All, but (d), plots are in log scale.
Algorithm Budget coordinate descent via ReSearch input: Initial base point zo e 1, threshold length >
for & = 0, do Pick i(k) uniformly at random from [d]
3:
Run ReSearch for time steps 8 = 1,..., TT,,,TT&&e (v) on the interval I == (= R wn Ze((K) E I), recommending Ik R&e,(K) time EE (n) + s, where (n) is the first time step where the length of the active interval maintained by ReSearch is s
4: Set Fk+1 2k (((())
For the sake of simplicity, we present our results in the case where the budgets by are equal to 1, for all t. Theorem 4.3 (Informal statement). Under Assumplion 2. whenever is strongly conver and smooth, for any 17 0, the expected optimization error of Algorithm is upper bounded by
K(T.)) (t) K(T..) zel
+
where K (TT,1) is the total number of line searches performed up to time and the expectation taken with respect the rondom draws of the directions i(0), i()).....
Morcover, appropriate tuning of n yields the bound ((d()TT))) on the expected oplimization error.
10

---

Published in Transactions on Machine Learning Research (10/2024)
For formal statement, the proof of the previous theorem, and more general version holding for arbitrary budgets see Appendix D
We now make the following comments.
First, to put things into perspective, when a = 1/2, we note that our rale d(d/7)3/2 for the budget setting is line with statc-of-the-art bounds in the related classic field of (i.i.d. subgaussian) stochastic convex optimization (Jamieson al., 2012), where confidence intervals shrink at the rate in Assumption 2.1 with a= 1/2.
Second, in convex optimization, strong convexity usually allows for unconstrained optimization (i.c., / == RR;; our method can be extended to this case by adding a pre-processing step before each line search that works by doubling the search space sequentially on the given line until we can guarantee to contain the minimizer. For the sake of conciseness, we leave this standard step out of our presentation.
Third, if one sets a larget optimization error of E, it is consequence of Theorem D.1 that the runtime of Algorithm 5 is of the order of (a"* This is due to the fact that Line 3 takes constant time for each function query and that after I' iterations of Algorithm 5 the optimization error is of the order of d' /Ta (ignoring logarithmic factors). Furthermore, the algorithm, at each iteration, only needs to store three points for ReSearch, the d-dimensional vector with the current direction, and finally the d pairs of interval limits delimiting the coxstonstr.. Thus, the overall space complexity of the order d. We believe that it is unlikely that in this setting one can obtains bounds that are independent from Indeed, in the related stochastic case, (Shamir 2013) shows that at least a linear dependence on d is unavoidable.
Finally, we highlight remarkable benefit of coordinate descent frameworks (in particular, Algorithm 5): they trade off some generality (by requiring strong convexity and smoothness) to gain an easy implementation and obtain efficiency on the two separate fronts of query (by featuring state-of-the-an optimization error bounds) and computational complexity (having low memory requirements and fast execution, irrespectively of the dimension).
5 Experiments
We present a preliminary experimental evaluation in support of our theoretical findings, illustrating the following. First, the performance of ReSearch is in line with the theoretical guarantees and, in practice, closer to the lower (Theorem 3.2) than to the upper bound (Theorem 3.1p. Second, Algorithm 4 significantly outperforms its natural competitors. Third, the role played by the threshold parameter 7) in Algorithm and its performance compared to the upper bound.
5.1 Comparison with upper and lower bounds
This experiment aims at comparing the performance of ReSearch with the corresponding theoretical upper (Theorem 3.1 and lower (Thcorem 3.2 bounds. The oracle is based on the setting described in the first part of the proof of Theorem 3.2 with parameters e 0.1, = 1/2, b. = for all We test the performance of ReSearch on a grid of time horizons T' (10,,103,...
103 ...., 10"} against the objective f constructed in the lower bound. Figure 4(a) shows that ReSearch performs well, appearing significantly (note the log scale) closer to the lower than the upper bound.
5.2 Stochastic Case
This experiment (Figure 4(b) aims at showing the effectiveness of Algorithm 4 when compared to the uni-dimensional algorithms proposed in Agarwal et al. (2013) and Jamicson et al. 2012)) which are state- of-the-art for this setting. To this end, we optimize the function f(x) = 1 over / [0, 1]: notice that f is 1-Lipschitz over I and its minimum value is 0. The stochastic oracle is implemented according to Stochastic Optimization Protocol 3 with independent Gaussian noise with mean 0 and variance o² 0.1. This corresponds having c(6)= 7ou In(16)) In21n(166) and a = 1/2 in Assumption 4.1 We set all the algorithms with the parameters indicated by the theory, so that the overall confidence is 1 1/7 in all cases. Consistently
11

---

Published in Transactions on Machine Learning Research (10/2024)
with the previous section, we evaluate the algorithms grid of time horizons T' {10², 10...... 10 Since we are comparing high probability bounds, we measure the median opt omiimazaiion error and plot it with the corresponding Inter-Quartile Range over 10 repetitions.
5.3 Multivariate case
These experiments illustrate the performance of Assumption in the multivariate budget case. We minimize the function ((x) = over [-1,3d] for d = 10, which has the minimum close to corner, but not exactly there. We implemented the oracle according to Optimization Protocol [ and Assumption 2.1 with c= 1, = and b, = for all t. In addition to using the threshold arr recommended by the tuning in appendix D and the corresponding theoretical upper bound, we also run algorithm 5 using 1/ {1, "000,1003) for T (10", 10 ........ 10%). We repeat each run times and report the average optimization error and the standard deviation (note the high concentration: paths have little to no variance). Figure [[c] shows the results (in logarithmic scale), highlighting that the tuning of the threshold mr dictated by the theory can be little more conservative ive in some cases than some ad hoc choices of 1), but it is still far better than the upper bound (which is on par with state-of-the-art bounds for analogous settings) and random guess of 17.
In a second experiment, we considered the same problem setting and measured the runtime of the algorithm against the dimension, varying the dimension in the interval [10, 100] with a step of 10. We set target optimization error 0.1 and run the algorithm until reaches In Figure [[d) we reported the average runtime across 10 repetitions. As predicted by the theory, the runtime follows the predicted d2 behavior and remarkably the execution for d = 100 takes less than second.
6
Conclusions
We designed and studied flexible zeroth-order convex optimization setting, where the accuracy of the queries improves with the invested budget (Assumption 2.1 This framework grants additional modeling power (sce Section D compared to standard stochastic Lengs In dimension one, we designed an any-time, any-budget, parameter-fres algorithm, called ReSearch (Algorithm 2 that does not require the a priori knowledge of the (local) Lipschitz constant of the objective and works even in an adversarial and adaptive environment. We provided upper and lower bounds on the optimization error that match up to constants. We provided a natural adaptation of ReSearch the stochastic setting together with a corresponding upper bound featuring the same mild dependence on the Lipschitz constant, and further improved the state-of-the-art for this setting by logarithmic (erm. Finally, in the multivariate budget setting, we illustrated the benefits of using ReSearch a line search procedure in coordinate descent method: this results in numerically efficient and practicable budget optimizer that can run even in high-dinensional spaces.
References
Alckh Agarwal, Dean P. Foster, Danicl J. Hsu, Sham M. Kakade, and Alexander Rakhlin. Stochastic convex oplimization with bandit leedback. SIAM J. Oplim., 23(1):213 240, 2013.
Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Conference on Learning Theory, pp. 240 265. PMLR, 2015.
Jan Beran. Statistics for long-memory processes. Routledge, 2017.
Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex optimization. Journal of the ACM (JACM), 68(4):1 35, 2021.
Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to derivative-free optimization. SIAM, 2009.
Kevin G Jamieson, Robert Nowak, and Ben Recht. Query complexity of derivative-free optimization. In A Advances in Neural Information Processing Systems, volume 25, 2012.
12

---

Published in Transactions on Machine Learning Research (10/2024)
Vitaly Kuznetsov and Mehryar Mohri. Learning theory and algorithms for forecasting non-stationary time series. Advances in neural information processing systems, 28, 2015.
Vitaly Kuznetsov and Mehryar Mohri. Time series prediction and online learning. In Conference on Learning Theory, pp. 1190-1213. PMLR, 2016.
SN Lahiri. Central limit theorems for weighted sums of a spatial process under a class of stochastic and fixed designs. Sankhya: The Indian Journal of Statistics, pp. 356 388, 2003.
Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Mathematical Statistics and Learning, 2(3):311 334, 2020.
Yurii Nesterov al. Lectures on conver optimization, volume 137. Springer, 2018.
HoHo Rosenbrock. An automatic method for finding the greatest or least value of a function. The computer journal, 3(3):175 184, 1960.
Jerome Sacks, William J Welch, Toby J Mitchell, and Henry P. Wynn. Design and analysis of computer experiments. Statistical science, 4(4):409-423, 1989.
Thomas J Santner, Brian J Williams, William Notz, and Brain J Williams. The design and analysis of computer ezperiments, volume 1. Springer, 2003.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. In Conference on Learning Theory, pp. 3 24. PMLR, 2013.
James C Spall. Introduction to stochastic search and oplimization: eslimalion, simulatioo, and control. John Wiley & Sons, 2005.
Paul Tseng. Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of optimization theory and applications, 109(3):475, 2001.
13

---

Published in Transactions on Machine Learning Research (10/2024)
A Full proof of Theorem 3.1
In this section, we give a detailed proof of Theorem 3.1
Proof of Theorem 3.1 Fix any bounded interval I2, time T' E N, and a convex function f:1 R. Without loss of generality, we can (and do!) assume that / contains at least two distinct points Moreover, without loss of generality, interval T- of any epoch r e [Tr] (defined in the initialization and updated at Line S always contains at least a minimizer, because the first active interval I is the entire domain and, by the unimodality of and the definition of the delete and update functions, ReSearch deletes a fraction of the active interval (Line S only if it certain that the value of f at one the remaining points is no bigger than all of the deleted points. Thus, there exists (and we fix for the rest of the proof) an [(=)= min(s). Recall that, for all & e N, 7. is the epoch of round (Line 5 of Algorithm 2 Also, for the sake of convenience, redefine tog = T and B = Br.,T-
can also (and do!) assume that attains its minimum in I 1 Then, note that the active
such that x' é IT .... c I1 and
define to = 0 and, if the last epoch is not concluded exactly at the end of time T, we
To prove the result, we analyze separately the performance of the recommendation Rr of ReSearch in the three cases Lines 10
13
and 15 in Algorithm 2
(i.c., the condition on Line true and we recommend RT as in Line 10). We partition the epochs é [Tr] into four sets, depending on whether or not the epoch uniform and whether not x' S c,. More preciscly, for any Ç {u, o' and {s,>), ). we let Aç,- be the set of all epochs T [TT] such that 0, Ç and x" (or, equivalently stated, that there exist at least two distinct elements 2, y (4.,c,,r7 such that x² + xx Now fix A = Açt,, where
Assume first that dely
(Sit)
Br (E)))) reA
argmax EB.
In words, A is the set of epochs A where ReSearch spent the highest budget. Define, for each T A, the points F, Yr the closest and second-closest points in (7,r), to x" such that x² xx yr (they always exist by definition of A). More precisely,
Fr == argmin an (.
Ix x"1
Vr = argmin x=-x"1
2s (I (r
Let be the number of elements of A and Kj. Ken be the elements of A increasing order. Then, for any N, we have
|Taa| S 1/2
2
(3)
1y,, In, 5 1m INNiil /2
if 2 if if 2
(4)
1xx x² S lyn, IInal= -2
(5)
Mi; x²1 S | - xx"
(6)
1ye, - 211 1yas 1 x01
2
Here, equation follows directly by the definition of the update function, noting that there are never two uniform or two non non-uniform epochs in a row, unless half of the current interval is eliminated in one single call
of the update function. Inequality equation | follows directly from equation 3 Inequality equation 5 is a
consequence of the definitions of the partition functions u and ş.. To prove equation 6 note first that the claim
'Otherwise; the optimization error is trivially zero.
Lndded, if it does not, then there cxists x" < (I",1*) such that lim wel f(z) = infaxt f(x) (this can only happen if / is not closed or f is discontinuous at s"; in the latter case, note that by convexity, f(x") > lim sel f(x) - inf f())). Thus, replace with J. where f(x) f(x) all a and f(x") ) inf f()). This way, up extending (or redefining) f x". are left with convex function such that f(X1) Ji...., .......((X f(Xr) ) e Jr, attains minimum at x² (in domain), and satisfies f( (Rr)) infaet f(x) = f(Rr) f(x').
noting that ReSearch never queries nor recommends the endpoints (") of
14

---

Published in Transactions on Machine Learning Research (10/2024)
holds trivially when 2x, E (lx TK, J. When this is not the case, since ReSearch discarded 2x; at the end of some previous epoch, it either holds that Ire [-o0, Tx,-1] In. C [x 00). If x² 1 dx.-1 (meaning that h=s), it follows from x' Ix, that la₃ (-o0, Tn..1J; which implies x" IN,, < <Imm-1 Analogously, if x > En
(meaning that -=>), it follows from x² e Ix, that Ix. c [ 00), which implics x² 2x, > I This proves
equation Moreover, as a direct consequence of equation and equation 6 we oblain equation 7
By construction, we have that
4 ΣΣ
B 2
Σ rE[rr]
B,
Σ 1=1
be
(8)
Now, we show that for any 7 [Ty] and & e {O....,
t we have
B, - 1222(222 k) max b
min
B B2,t,-k2
(9)
2e ( (1)7))))
3
i.e. that the total budget Bx,4,- spent on any query point I E (7, (kk) m(x))))) by) than the budget B, spent (on all query points) only during epoch т. Indeed, for any r [ry] and & (0,...,67) 1, letting Tiin argmin (llr.....r.. Bz, be query point where the algorithm spent the least amount of budget to time t, - k and M = {I (r, BB,,t-k- #mi.dr- S m b be the set of all query points in which the algorithm spent a budget close to that of Emins we have
Cr, r, up to time - k is no smaller (up to
3. min ze (r)
2 Bz
Σ
B2,t,
2 max b tc[7]
ZEM
b-
2 Σ
Σ
biT(X, X2 = x}
2 max by se[2]
2 (=tr-1+1
Br
b 2 max b. tE(T]
t=t,-k+1
2 Br (2+ + k) max br.
te[T]
with the understanding that any sum E. 2 equal to zero whenever i> j, and where in (+) we used the fact that, if a (1, is such that Bz,t, B Bzmins -k > max bi, then ReSearch never queried x epoch 7 up to time t, k, i.e.
k
Σ
This proves equation g
Thus, for any T A, if B, maxxar bi, since J + Jy (this follows from the definition of the delete function and can be proved by exhaustion), it holds that
f(v+) f(x,) J+ - Ja
J 24 J Jyr,t--1
J Jr Jr. Jz
J |Jacerr
Ba t.,t.-1
B
2,,t,-1
2.c
< (minge((r.crrvr (,,,)-11
equation <
..
(10)
(Br 3axx4(77] by)
Assume now that f(y..) -f 0. Then, for any 7 é A, by convexity and inequalities equation 6
(xx.)
equation 7 have that f(x+) f(x+) 0 is also true. By equation 10 it follows that, for any i n
15

---

Published in Transactions on Machine Learning Research (10/2024)
regardless of the fact that the inequality Bx, 3 [a iy holds not,
3- c2 1/a
Bx, s maxb; 10[7]
(11)
(f(w)) - (2xx;) 1/a
Summing equation 11
over i [a], we obtain
equation
bt
S
Σ
B,
Bx.
TeA
i-1
equation
3 (2 c)
S
Σ
3 maa by 65|T1
- -f(xx) 1/c
1-1
12. (2
12 max by [[[]]
(12)
(f(wx.) (2xx)) 1/00
Now, using equation 0
equation 7 together with the fact that difference quotients of convex function are non-decreasing in both variables, and since for each ie [n]] it holds that (yx,. Ix..) (yr, Fxz;) ) 0, we have
(f(W).) (x 1/a
1/a
f(yma) f(xx.)
1/a
(J(Un)) (x)x))
f(yn.) f(xxm))
1/a
1/a
-tan (1nm))f((an))
Yknm
Ina
Yn: In.
equation G equation
1/a
equation
1
1/a
S
5
(13)
2
1-2-1/a
Yiu
Putting equation 12 and equation
13 together, we obtain the inequality
12- (2- 1/a
be s 12 max Σ
1-9-1/0
te[T]
(f((ke)) f(I 1/0
that can be rearranged, whenever Σt be 2 24 max by n, to oblain the inequality
24 21/a
f(xn.) f(I $4
(14)
(E b,)aa
Then, relying again on the fact that difference quotients of convex function are non-decreasing in both variables, and that (yk.. vkk.) (IK,, x= whenever Σt b, 24 max b, and Fx. x", have that
f(xm)) (0x,, x²)
[(xn)) f(xx))
2x. x
{1)mm ) (
(Ir.. xx)
INn Inn
equation
14
24
Fna x²"
S
21/a -
(I b.)a
Vx. Ix
equation
24
(15)
21/a
E bz)
16

---

Published in Transactions on Machine Learning Research (10/2024)
(note that equation 15 is trivially true also when xxn. = =x" and
Myx... -0=x((())))))))) = (y (I (3xx)) - ((x')
equation 14 equation 15
12
24
c
(16)
21/a
(Ei=ib))
Recall that the derivations for equation 15 and equation [6 were carried out under the assumption that f(yr.) ) f(xx.)) 0. If this assumption does not hold, by convexity, f(yx.) f(xxx)) = f(x"), therefore equation 15 and equation 16 are still (trivially) true.
Now, we will prove that the recommendation Rr is approximately at least as good as Ix., and ye., Since under the assumption that Σiz be 2 24-n max b we showed in equation 15 and equation 16 that Ix, and Ux.. are both ncar-minimizors, this will yield under the same assumption that Ry is also a ncar-minimizer
Recalling that we are currently assuming delr # [لиo, we have that Ry (et which (as can be checked directly) implics in turn that Rr e (op Jn and, whenever ΣT by 2 24 n max be:
If Ry {Irm Nn. }, then equation [ follows by equation and equation 16
2. If Ri & {Ix,, In. } such that f f(Rr) s JR,T S Jar $ fz)); therefore, equation [ follows by equation 15 and
} and (Ti, Mnn J c Uor CrrsTrr then there exists x e Hlr Cry Trr) }
[[T)
equation T6
If Ry é (Iixa: (bn)) and (Fnn:yRen & (1rr,err: ] then, since at least one between Txa and yea does not belong to the set of active query points {lrg Crya at time T, there exist past time t E [T] and past query point E (hr Tr. such that J S max((J (a. .t Jt..,)): therefore, noting that the sequence minsre(h,, J a is non-increasing, we have f(RT) S JR S J S max(J=mme Jy... < max( (f (xx.), f(Y..) and equation follows by equation 15 and equation 16
On the other hand, if ET. b, < 24.n n max br. then
3 ((Rr) f(x')
9
T T
T.
T..
16
equation
g
9
(4/2)
1-
9
L (1122))
Ef. b1
16
In2
ΣT be
exp
24
max
where is the smallest between the Lipschitz constants of ff on [brr Try] and [br+1 Try+1] indeed, by convexity, is a Lipschitz constant for on the convex hull of {x" Trr) (resp., (e"i }) if and only if is Lipschitz constant [1z [Tr] (resp., (rrra Tr..)). Putting everything together yields equation I when dely # m...
Assume now that dely t and B 2 EPE B (i.e., the condition on Line 12 is true and we recommend Ry as in Line 13 This implies that the three intervals JI,,, Jo,y TT Jr.y." T have non-empty intersection, which in turn implies that
max w'e Seppbey--egy""r
Jt
min zellle txp)
Jør 22
max JWr.Tl
(17)
d'E(leg.Cry..rr)
Now, define f2, far fa the four functions whose graphs are straight lines such that fi passes through the points (ry .) and (Frzy f2 passes through the points (E.r)) and (in,) Sa passes through the points (brr, Jt and (Crr and fa passes through the points (loys and JF,,. (Figure 5).
17

---

Published in Transactions on Machine Learning Research (10/2024)
Fig
Jery iT
Ir Jtep if
Jirp.
Joy T
OerT T
f4
f2
log
CTp
Frr
f3
Figure representation of the four lines fi...., fa. By convexity, f is lower bounded by the blue solid segments. Note that, since M..,TnnJ. Jen....nnn,. T Ø; then /1 are nondecreasing and Ja. nonincreasing. Therefore, the minimum of the y coordinates of the red dots is lower bound on the value of the function, which in turn implies equation 18
By the convexity of f, for each a [T |r we have ((x) (1(),, for each x [1r,, Cry] we have f(x) 2 f2(x), for each x E [Crr,Trz] we have f(x) 2 fa(x), and for each I E ([ry,,Ty)) we have f(x) 2 fa(x). Writing down explicitly these four incqualities and upper bounding, we conchude that
f(x')
min
2
max w'ellop Cop Prp)
J2
min w wellry Erp
J2
(18)
Then, if B,, 2 max] bi, for all (Tyr: (rr ) we have
f(x) f(x"((())))))))))))
s J J2 - f(x")
equation
5
J
min z'ellr Roz Ner)
Ju
max x'c (op
Ju
min
z'e 2
equation
S
max z' d'e(lopiCoy (oay
J
max
c
s'e s'e(l frg
B3 2
equation
g
S 36
Brp 2 b
(Bz,
C
48
a
S 6 12a
S 12
(Σ bi)a
21/a -1
(Et bz)aa
If, on the other hand, Bry 4 44mxx by since Bry 2 2 Et bi, then for all x E flay Crp we have
4 27 bs 12 m
f(x) (111(3)) L111
Ber Pemncaa (4/22
EF bq [1n
LM (1/2)
ln2 Σx b
=|4 exp
24 max by
where L the Lipschitz constant of f on [T,, J. Thus, adding together the two bounds for B 2 max{ by and Byp 4 max by yields equation when delp mто and B Σ7 B,,.
Finally, assume that dely mre and Byy En By (i.c., the condition on Line true and we recommend Ry in Line 15 Then the recommendation Rr is the point with the best upper bound at the
18

---

Published in Transactions on Machine Learning Research (10/2024)
end of the -ossstt epoch.
Thus, proceeding in the first part of the proof (case dely (m37), we get
((RT) f(x')
(Berr f(x))
24
12
21/a
(E/-r-1
9 T. l exp
In2 Σ
f by
24 max bt
48
< 12
2//0 -1
(Ei=1 (E)
In2 Σ/- b
+
L 11| exp
8
48
[ 6
where L the Lipschitz constant of f on [rr] Being the interval the time T and the convex function, f arbitrarily chosen, the proof is complete.
B Full proof of Theorem 3.2
In this section, we give a detailed proof of Theorem 3.2
Proof. Fix nondegenerate bounded interval Tc IR. Fix also an horizon T e N, total budget B 0, and a Lipschitz constant L > O. For each t [T], define by := B/T. We divide the proof in two cases, depending on which of the two addends in equation is the dominant term.
Assume first (EL,,
L exp
ΣT, by
For all > 0, define J(b) = c(c((2))).((()8)))
max.erjbb Consider the two alternative objective functions f. and f-, defined for all E I, by
32c
{+x)= = (1 2(x (1-)==11-(0-777 (-)((=1))
2Ba
At each time e [T], if the algorithm chosen by the optimizer queried XI...., Xr, the enviromment returns the fuzzy evaluation J, J(Bxx.)) where we recall that Br., defined, for any Note that the environment satisfies Assumption 2.1 and that both functions fa are 7 - Moreover, the algorithm provides the same queries and recommendations for both f and ft, as it receives the same JI,...,Jy Jr. Furthermore, if the algorithm rocommends Ri (I+I+)/2 then (-rr -infzr f- (x) 2 c/(2"), while if the algorithm recommends Rr (I" /²2 then (+(r)) inf (+)x) 2 c2BB)). Thus, in both cases there exists e Lipschitt convex function f {f- for which:
by Σ b, TxT,X, x).
f(Rr)
inf [(x)(( sel
c
+ L
(Eth b,)a
32c
In this case, at each time t [T], the environment returns == (x.))) Note that, this instance, our problem reduces to deterministic convex optimization. By classic lower bound for deterministic convex optimization (see, e.g., Nesterov al. 2018 Theorem 3.2.8), then, there exists T-Lipschitz convex function f: I IR for which
Assume now 1 b.
32E 7 exp
Σ & maxesfrj by
1
1 16c
Σ maxe
f(Rr) inf f(x)
L e
L
sel
16c
1
E/ &
2
L
4
(
32e
Being the interval I, the horizon T, the budget B, and the Lipschitz constant arbitrarily chosen, the theorem follows.
19

---

Published in Transactions on Machine Learning Research (10/2024)
C Full proof of Theorem 4.2
In this section, we give a detailed proof of Theorem 4.2
Proof. For the sake of simplicity, we assume that 7= [0, I], f is continuous and admits unique minimizer
x' [0,1] (the other cases can be treated similarly). For each E N, let Dn = 2k-2- 2 k E Z}, let
D = (In.1....,, In.10) c Dn such that
Fn,1 <... 2n,5 Sx $ 2n,6 ... In,10
and In.j+1 - Fnnj Wnis2" for all je [9]. Define D= Una[T] DA (0,1). Consider the "good event."
Yengs) - f( ((nns)s c(0) 1a
8 =
n,te [T] ]c[10]
and note that Mear (s(x)) e Ji) C. By De Morgan's laws, union bound, and Assumption 4.1
we have
P[E*] 10 Now, we are in the good event &, then Assumption 2.1 holds for all & [T), with e c(d) and b1 =..- by 1, since ReSearch queries points only in D. To prove the last claim, consider the budget version of ReSearch. Recall the observation (at the beginning of the proof in Appendix A that the minimizer x² of f belongs to all active intervals of ReSearch at all epochs. Assume by contradiction that there exists an epoch 7 é [Tr] such that flr, r+) is not included in D. Then, the set of query points {4,,c,, is not included in DA n (0, 1) when n - logg (r, 422. Consider the case where r, & D n (0, and ry 2n,10 (the other cases can be analyzed analogously). Since the leftmost point I of the active interval of epoch t is always bigger than or equal to rr 4 4.22 then
2 1, 2r, 4. 2 In, 2 4. =xn,7 Fn.6 x²
which yields contradiction. It follows that, in the good event & (hence, with probability at least 1 107 we can apply Theorem 3.1 obtaining the result.
D Missing details on Section 4.2
We now consider the minimization of multivariate objective over a convex bounded subset I c Rd, where Optimization Prolocol [ has be = 1 for each and Assumption 2.1 holds. In this section, we refer to this setting as Multivariate Budget Convex Optimization (MBCO) for the sake of emphasis. We assume the objective to be y strongly convex and f-smooth with 0 y 3 i.c., Va, xip Rdd
f(x) / (VS( x- -2o) r xo
8 2
f(x) s f(r) (VI(x)), -
r xo
where the first equation corresponds to the strong convexity and the second to the smoothness. For simplicity, we further assume the existence of a unique minimizer x e int(T). As it will be apparent later, it is not necessary to assume that x" the interior of the entire analysis that follows holds the objective is Lipschitz, a condition that implied by the strong convexity and smoothness. This cosmetic choice allows to replace the local Lipschitz constant appcaring in equation I with B.
Before providing the detailed version of Theorem 4.3 there. Given some budget T for line search subroutine, the bound of equation scales roughly as 1/T", which implics that the point recommended by ReSearch is at distance at most 1/T from I" due to strong
let. provide some intuition on the bounds appearing
convexity. We denote with T(n) = deg "01 the maximum number of iterations needed by ReSearch to find
6Te existence of unique minimizer is an easy consequence of the strong convexity
20

---

Published in Transactions on Machine Learning Research (10/2024)
1yminimiier in given epoch and by k(T,n) = [I/T(n) the corresponding minimum number of epochs made by the algorithm with an overall budget of T (we have approximately K(T,n) R(T,n) with the notation of Theorem 4.3
Now, we state the detailed version of Theorem
Theorem D.1. Let A f(zo)= f(x"x, x" be the unique minimizer, K B/P | be the condition number of f, and @ = max Recall c1, C2 C3 from Theorem 3.1 Suppose that a 2
la2 and 48
te[d]
T2 max (2dr:3) log (1
a C3
2
Ca (2)(0diam(())
In
2
In
Adr
C3
C3
C1
If the optimizer runs ReSearch for MBCO (Algorithm bounded by
then, ils expected oplimization error upper
[1
1
K(T.)
Do 2dx
(19)
4dk
Thus by setting upper bounded by
log
2dk T
with caa) = (r=((4c1)) the expected optimization ervor is
c(a)) 1og(1log(11-00
2dkB
Do
((co) log (1
1
2dx,8 To
log
(20)
To
(1 - -1da
Adre
Proof of Theorem D.1. Take a, 8,K and Q defined in Theorem D.1 Let g be univariate function obtained by considering on segment I' of I. We upper bound the Lipschitz constant of the function g using the global Lipschitz constant L of J, which, given that are assuming that x" e 1 can be further upper bounded by B diam(!). We start noticing that, assuming b, for all t and c = 1, the bound of equation can be bounded from above by 201/Taa whenever
- In C3
2
C2 L
T2 max
In
2 C3
In
(21)
C3
C3
C3
Indeed,
c
2 2 (x00xxp-eg3)
(22)
To
is equivalent to
C1 T exp (-c3 T)
L0
Taking logs both sides and re-arranging this is equivalent to
In Le
T _ In(T) C3
Now consider the case when e2 c2 2 C1, so that the second term on the right hand side is positive. Notice that by hypothesis we have that a/e3 2 1, so by Lemma A.2 from Appendix A Shalev-SShwart Ben- Ben-David (2014). by taking
2
L2
T 4 In
2 _
In
C3
C3
C3
C1
21

---

Published in Transactions on Machine Learning Research (10/2024)
equation 22 holds. On the other hand, if cgL < c1, then the second term on the right hand side is negative and we can solve the stronger inequality
T2 (T).
using Lemma A.1 from Appendix A of
& Ben- BaviD 2014). Thus by taking
T 2-2-1 a
C3
equation 22 holds.
Now let T" any integer satisfying equation 21 and let denote with Ty the output of ReSearch after T' iterations. Notice that for any function as described above, by the strong convexity of g it holds that
pr 201
2 / I s V
s2
ci ///
uToa
1. then it follows that the point 2T found by ReSearch satisfies |ay - x"| m Now let f be multi-variate function satisfying the assumption of Theorem D.I. Notice that any restriction f of f along coordinate line will also satisfies the same assumptions over the interval Is (see line of Algorithm 50.
Let < 17 θ (f) =
4cg pay"
The analysis of Jamieson et al. 2012) applies to our case and they show that after & epochs of coordinate descend, the expected optimization error of the current iterate is bounded above by
[1- 1
Ao + 2dk
4dr:
Recalling that T(π) is the worst-case number of itcrations required by ReSearch to find an n-optimizer, and if we are given total budget of T, the number of epochs made by equation is at least K(T,n) = (T/T(n)) From this we get the bound of equation 19 Now we set
2 n= log (1 4dw
2dkB
log
Ta
whit c(a) = (1u((cc))) and notice that if T > max{1/(log (1 11((4))))) (2dr3) V*3, then T(n) s ((4cI/(u77)) 1/2. Thus, the following holds
T
T
K(T (T/(() T/T(() 122
17
toj ump
40
1
2dxx33
log
1.
log (1
To
4dx
Replacing this into equation 19
R(T..)
Do 2dxx3m
4dk
2dc38
1
2dk;
Ta
Ao 2dk3
log
c(a)TTog (1-
11
7a
Adx
1dk
2dkB
Ao
2dkr
log
Ta
(1
c((a) log
(1-
1 Zdw
Ta
Idw
22

---

Published in Transactions on Machine Learning Research (10/2024)
obtain equation 20
In the following we also present generalization of the above theorem to arbitrary budgets b,, 0 and In the context of the next theorem B()) (defined in the proof) is meant to be the worst case total budget required to find an ppoptimizer at a given epoch, Br is the total budget and n) BBr/B(n)] (Br//))(BBBB(())
Theorem D.2. Let Ao = f(zo) f(="), x² be the unique minimizer, x== B/P be the condition namber of f, and e = m Recall c1, 022 C3 from Theorem 3.1 Let by max be and Br Σ.= b₁_ Suppose that ie|d]
Br max (2ake))
abi ln C3
(bbi
Jabi C3
1)
In 2 max (abr 11)
+ bT In
C2 (
}
max
C1C
If the optimizer runs ReSearch for MBCO (Algorithm 5 then, its expected optimization ervor is upper bounded by
1 K(T.))
(1-
Ao + 2dx
(23)
4dk
Thus by setting
2dk3
7
log
B7
c(() BT log
(1
F3 2wrrdd
BT
Adk
with c(a) (u/(4cic)) //1>
the expected oplimization error is upper bounded by
Ao
1
2drz3 Bo.
+
log
(24)
B7
Idm
c(a) log
(1
B 2rc3d
ddx
Proof of Theorem D.2. Take a, a, B, and obtained by considering on segment. I' of T. We upper bound the Lipschitz constant of the function g using the global Lipschitz constant L of f, which, given that are assuming that x E 1 can be further upper bounded by B- diam(I). We start noticing that, using by. = max b, the bound of equation can be bounded from above by 20/c/(Eir b.)a whenever
defined in Theorem D.2 Let g be univariate function
T Σ h max 1
(2 abú
abb
[abi C3
. }.m max
( abbi
11) + 2 by In
(22L0)
}
In
4 max
(25)
C3
c3
C3
C3
C₁C
Indeed,
Eisbbe bi by
C10
2 c2L0pxp
-C3
(26)
(E b))a
T
is equivalent to
T
a
ΣT be
C
bi
exp
Le
by
7 At. high level, that 7 whenever total hudget By large compared to Dy
23

---

Published in Transactions on Machine Learning Research (10/2024)
Taking logs both sides and re-arranging this is equivalent to
abi
by
02
Σ E1
by
In
Σ
bi
In
ciC
Now consider the case when e2 LO e₁C, so that the second term on the right hand side is positive. So by Lemma A.2 from Appendix A Shalev--hhee Shwwrrz & Ben-David 2014), by taking
Σ b. 2 max { 1) max
jabi
Labi
by
(22L)
In
C3
C3
equation 26 holds. On the other hand, if c2 cic, then the second term on the right hand side negative and we can solve the stronger inequality
abi
T
Σ
b
In
bt
using Lemma A.1 from Appendix A of Shalev-Shwarde & Ben-David (2014). Thus by taking
T
abT
aby
Σ 1=1
by
2
In
C3
C3
equation 26 holds.
Now let (b,)T_ any sequence satisfying equation 25 and let denote with 2y the output of ReSearch after T iterations. Notice that for any function g as described above, by the strong convexity of holds that
PT x²1s|
/ (o(xT) - 9*) 2
C1C # (ET, by)
Let 0 < S O, and define Bnn) TT()) b. with T(n) the first natural number s.t. ΣT(1) b, follows that the point vr found by ReSearch satisfies |eT - x=1 1 $ 1). Now let f be multi-variate function satisfying the assumption of Theorem D.2 Notice that any restriction fx of along a coordinate line k, will also satisfies the same assumptions over the interval (sce line of Algorithm 5).
1cre
then it
pnp
The analysis of Jamieson al. 2012) applies to our and they show that after & epochs of coordinate descend, the expected optimization error of the current iterate is bounded above by
(1 (1-21) 1-110 4dk
Do + 2dx
Recalling that B(n) is the worst-case number budget required by ReSearch to find an n-optimizer, and if we given total budget of Br, the number of epochs made by Line [ of Algorithm 5 is at least K(T.n) (r)) From this we get the bound of equation 23 Now notice that
(Acee) t (
( (ccc)) 1 + bT
B(n)
and that
2dr38
77
log
Ai Try
B3
daa log
(1
Bo
4dx
24

---

Published in Transactions on Machine Learning Research (10/2024)
with c(a) (HH(4ccc)) 1/2 implies the following
Br
M(T,1) = (Br/B())> Br/B(r) - 1
bq
nepp
2dk/B3
log
-.
log (1
B
Adw
Replacing this into equation 23
R(T,n)
[
Do + 2dk:Bn)
4dk
2dw,8
2dk,3
Do 2dlx
log
b/
BTg.
1dx
c(a) By log
(1 idm)
By
2nddd
2dx3
An
2dh..B3
by log
B
(1
B
4dx
c(ar) log
(1
Be 2repid
zetes
we obtain equation
24 Notice finally that to make the above bound valid, has be Br (2dr;3 1/a
E Adaptive Lipschitz constants
This experiment aims to show the advantages of featuring the local Lipschitz constant, as given in Theorem
3.1 over bound that uses the global constant. To this end, we optimize the function f(=)= =-1)==-/>> + over the interval (a, 1) with the maximum value is smaller than 1, thus any meaningful upper bound on the optimization error should be smaller than 1. In the experiment set 0.001, 0.1, 1 (Assumption 2.1b, b, I (for all 1), and we let the intervals Jr to be symmetric around f(x) for query at at time t. We run ReSearch for T = 1000 iterations.
O. The Lipschitz constant of f grows roughly 1/va. Moreover, f(x") ) 0 and
Figure shows that the upper bound featuring the local Lipschitz constants (local) is much tighter than that featuring the global constant (global). In particular, as denoted by the vertical lines, the former falls below after 84 iterations, while the latter becomes non-trivial only at iteration 339.
25

---

Published in Transactions on Machine Learning Research (10/2024)
local global
10a
(85,33.16)
101
bound
10a
(8,1.0)
(339,1.0)
339,0.18)
100
200
300
400
500
600
700
800
900
1000
Figure The vertical green line raises at the first point where the local curve falls below 1; the red line raises at the first point where the global curve falls below 1.
26


Reviews:
[{"review_id": "lq71ZrHzo8", "reviewer": "Reviewer_ka7u", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This is a general framework that covers stochastic convex optimization as a special case, but can have other applications.\n2. The proposed algorithm is natural and easy to implement, and it's nice that it has a theoretical guarantee that is worst-case optimal.\n3. The paper is very well-written, full of proof sketches and ideas, useful pictures, and has enough details for a reader to understand and reproduce the results.\n4. The experiments validate the robustness of the algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a framework for black-box optimization of a convex function f, in which the algorithm can query the value of the function at any point x and the environment responds by announcing an interval I, which is guaranteed to contain f(x). Moreover, as the optimizer queries the same point again and again, the length of the returned interval gets smaller and smaller (see Optimization Protocol 1 and Assumption 2.1). In a way, this is like getting noisy estimates for the value of the function, where the noise decreases as you query that point more and more.\n\nThe paper proposes an algorithm ReSearch (see Algorithm 2) for the 1-dimensional case and proves a theoretical upper bound for the optimization error (see Theorem 3.1), and proves that there are cases where you cannot achieve a better bound (that is, the bound is optimal in the worst-case, see Theorem 3.2).\n\nThe authors explain how the algorithm can be deployed for stochastic convex optimization and that it improves the state-of-the-art bounds for the stochastic framework (Algorithm 4 and Theorem 4.2). They also extend the algorithm to the multidimensional case, using coordinate descent, and prove a theoretical upper bound for this case (Algorithm 5 and Theorem 4.3). They also run some experiments showing the algorithm is practical.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is acceptable, but I have some clarification requests.\n\n1. The way previous work is cited is weird; e.g., \"The former is crucial to include scenarios where errors have long-range dependence Lahiri (2003); Beran (2017)\" does not grammatically make sense.\n\n2. Please avoid using abbreviations if possible: (a) what is DCO on page 6? (b) what is IQR in the caption of Figure 4? Please define it or give a reference. \n\n3. In Theorem 3.2, when you write \"every algorithm\", does that mean \"every deterministic algorithm\"? Please clarify whether the bound holds for randomized algorithms as well.\n\n4. For Theorem 4.3, you assume budgets equal 1 ... what happens if the budgets are not 1? Can you prove a guarantee in that case?\n\n5. Footnote 3 is quite awkward and hard to understand; consider finding a way to embed it in the text (and in general, avoid footnotes as much as possible).", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qrdHfeEdO8", "reviewer": "Reviewer_LTy2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n1. The paper is well-written and easy to follow.\n\n2. Both theoretical and empirical results are provided. In particular, theoretical results contain both upper and lower bounds with near-optimal guarantees.\n\n\n\n## Weaknesses\n\n1. The proposed methods, particularly for multidimensional problems, may be complex to implement in practice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a method for zeroth-order budget convex optimization, named ReSearch. The optimizer can invest a budget at each query point to obtain a fuzzy evaluation of the function, where the length depends on the invested budget. \n\nThe authors provide near-optimal optimization error guarantees with both upper bounds and matching lower bounds. \n\nApplications include stochastic convex optimization and a coordinate descent method for d-dimensional budget problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be better if the authors could discuss more about the actual cost of the algorithms compared to existing ones in experiments.", "broader_impact_concerns": "Zeroth-order optimization is a fundamental problem in machine learning with black box models. So it would be of interest to the community.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VnezMYCgB1", "reviewer": "Reviewer_vNNQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n1) They designed a new setting. On the traditional Zeroth order optimization, they added a budget constraint so that the learner can observe better results when he spends more budget on that observation.\n\n2) For this problem, they designed an algorithm called ReSearch which works under minimal convexity assumptions on the target function $f$. (the environment could be adversarial)\n\n3) They also provide a matching lower bound, even with the Lipschitz condition and prior knowledge of T and B. \n\n4) They provide two examples to support their new setting and algorithm's practicality. \n\n5) The algorithm is also quite straightforward - close to a binary search approach, and easy to understand. \n\nWeakness\n\n1) The setting that 'budget is given by environment' is not that straightforward, and some settings regarding the budget are not very convincing. \n\n1-1) First, since there's no limitation on budget, obviously using all the budget possible is always the best strategy. Usually budget works as an overall constraint that prevents the optimizer from spending too much on one try (or observations). However, in this paper, spending less budget does not give any additional bonus, so optimizer should simply spend all their given budget for each time, which makes the problem less interesting.\n1-2) Also, the width of the confidence relies on the budget spent on a 'certain point', so it naturally encourages the optimizer to choose the same point multiple times. Intuitively in practice, when someone invests a budget on a point $X_2$ close to the previous point $X_1$, then naturally we expect that the investment on $X_1$ affects the accuracy on $X_2$ too. I feel this setting is quite tailored for their algorithm ReSearch. It makes the lower bound result less surprising. \n\nThough I know they proved a lower bound even with Lipschitz condition and known T and B, I should say the result is different from what I expected.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "At each time-step $t$, the optimizer can invest a budget $b_t$ in a query point $X_t$ of their choice to obtain a fuzzy evaluation of $f$ at $X_t$ whose accuracy depends on the amount of budget invested in $X_t$ across times. In the univariate case, the authors design ReSearch, an anytime parameter-free algorithm for which they argue near-optimal optimization-error guarantees. \n\nThey also present two applications of this univariate analysis. First, they used ReSearch for stochastic convex optimization. Second, they applied the d-dimensional budget problem by combining ReSearch with a coordinate descent method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "- Perhaps use a different word instead of 'budget'? It is quite misleading. I think ML people use the word 'budget' as 'the amount of money available for a purpose.'\n\n- The setting itself is not super interesting, forcing the optimizer to sample a certain spot repeatedly. I hope authors justify this setting more \n\n    - such as papers with the same budget assumption, \n    - or an example in practice (maybe univariate SCO is an interesting example, but I am not an expert in this direction and am not sure whether Agarwal et al. (2013) is really the SOTA algorithm in this field - it is more than 10 years old).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a new setting for zero-order convex optimization where the oracle answers each query x with an interval that is guaranteed to contain f(x) and whose length decreases with the amount of budget invested on x so far. The authors propose an anytime parameter free algorithm for the univariate case and prove both an upper bound and matching (up to constants) lower bound on the optimization error. They apply their algorithm to the special case of univariate stochastic convex optimization, where they improve on existing theoretical guarantees.  They also extend the algorithm and its theoretical guarantees to the multidimensional case using coordinate descent. Some toy experiments are presented to support the theoretical claims.

Below is a summary of the strengths and weaknesses highlighted by reviewers and based on my own assessment.

Strengths:
- The proposed setting is general and includes stochastic convex optimization as special case
- The proposed algorithm is simple and easy to implement
- Theoretical guarantees are near-optimal and yield improvements on existing results in the special case of stochastic convex optimization
- Paper is well written. Results are clearly presented.

Weaknesses:
- Experiments are only done on toy synthetic problems, with small dimension d in the multivariate case.

The official recommendations from the reviewers were mixed, with two reviewers recommending to accept and one leaning to reject. The authors have addressed in their responses most reviewers' concerns. The rejection recommendation is based on the reviewer not being convinced that the setting introduced is interesting. I agree that the paper would have benefitted from more concrete examples where this setting arises. Nonetheless, I think the setting considered is reasonable, it already includes the interesting special case of stochastic convex optimization, and it is likely to have other applications. So I recommend to accept this paper with minor revision.

I request the following revisions to be made:
- Clarify if the budget is revealed before the optimizer selects a query point or after. The description given at the beginning of Section 2 seems to imply that the budget is revealed before, while the pseudocode in "Optimization Protocol 1" shows that the budget is revealed after. 
- fix formatting of citations and define or remove acronyms 
- clarify in Theorem 3.2 that only deterministic algorithms are considered.
- Add a comment on how Theorem 4.3 can be extended to arbitrary budget in the main text, and include the proof of this general case in the appendix.
- Include the discussion about time and space complexity of the proposed algorithm, from the response to Reviewer LTy2. 
- Include the discussion clarifying the meaning of budget in the proposed setting from the response to Reviewer vNNQ.

I also recommend running experiments with larger d.
Decision: Accept (poster)