Stochastic Direct Search Methods for Blind Resource Allocation
Authors: Juliette Achddou
Olivier Cappé
Aurélien Garivier
Venue: Accepted by TMLR ()

Abstract: Motivated by programmatic advertising optimization, we consider the task of sequentially allocating budget across a set of resources. At every time step, a feasible allocation is chosen and only a corresponding random return is observed. The goal is to maximize the cumulative expected sum of returns. This is a realistic model for budget allocation across subdivisions of marketing campaigns, with the objective of maximizing the number of conversions.  We study direct search (also known as pattern search) methods for linearly constrained and derivative-free optimization in the presence of noise, which apply in particular  to sequential budget allocation. These algorithms, which do not rely on hierarchical partitioning of the resource space, are easy to implement; they respect the operational constraints of resource allocation by avoiding evaluation outside of the feasible domain; and, they are also compatible with warm start by being (approximate) descent algorithms. However, they have not yet been analyzed from the perspective of cumulative regret. We show that direct search methods achieves finite regret in the deterministic and unconstrained case. In the presence of evaluation noise and linear constraints, we propose a simple extension of direct search that achieves a regret upper-bound of the order of $T^{2/3}$. We also propose an accelerated version of the algorithm, relying on repeated sequential testing, that significantly improves the practical behavior of the approach.

Published in Transactions on Machine Learning Research (04/2024)
Stochastic Direct Search Methods for Blind Resource Allocation
Juliette Achddou Deportment of Computer Science Universitd degli Studi di Milano
juliette.achdou@gmal..
Olivier Cappé
olivier.com Cenpier.coppeeenrss...
Department Computer Science ENS Paris
Aurélien Garivier
curcllen.portieeddeen---...p
Department of Mathematics
ENS Lyoon
Reviewed on OpenReview: https: // openreview. net/ forum? 9 #10XBLOdd
Abstract
Motivated by programmatic advertising optimization, consider the task of sequentially allocating budget across set of resources. At every time step, feasible allocation is chosen and only a corresponding random relurn is observed. The goal is to maximize the cumulative expected sum of returns. This is a realistic model for budget allocation across subdivisions of marketing campaigns, with the objective study direct search (also known as pattern search) methods for lincarly constrained and derivative-free optimization in the presence of noise, which apply in particular to sequential budget allocation. These algorithms, which do not rely on hierarchical partitioning of the resource space, are easy to implement; they respect the operational constraints of resource allocation by avoiding evaluation outside of the feasible domain; and they are also compat- ible with warm start by being (approximate) descent algorithms. However, they have not yet been analyzed from the perspective of cumulative regret. We show that direct search methods achieves finite regret in the deterministic and unconstrained case. the presence of evaluation noise and linear constraints, we propose simple extension of direct search that achieves regret upper-bound of the order of 22/3 We also propose accelerated version of the algorithm, relying repeated sequential testing, that significantly improves the practical behavior of the approach.
maximizing the number of conversions. We
1 Introduction
1.1 Motivation: Blind Resource Allocation
In the field of programmatic marketing, advertisers are given daily budgets that they are required to entirely distribute across number of predefined subdivisions of campaign. Their goal is to maximize some notion of cumulative reward during the lifetime of the campaign, corresponding to the number of clicks or purchases generated by the campaign. The expected reward generated by each subdivision every day is an unknown function of the daily budget allocated to that campaign. We focus on the context in which, when choosing a specific allocation, the advertiser only observes a noisy version of the total reward. The optimization task faced by the advertiser can thus be formalized as a continuous resource allocation problem, under zeroth order and noisy feedback. Indeed, key operational constraint is the impossibility directly access higher-order (derivative) information. Furthermore, every noisy evaluation of the objective function has

---

Published in Transactions on Machine Learning Research (04/2024)
cost related to the value of the function, that needs to be accounted for in the performance criterion. The cumulative reward is thus more relevant than alternative traditional measures of performance based, for instance, on the distance to the optimum or the norm of the gradient of the objective function reached after some iterations. Note that the resource allocation task that we consider is different from that in which the resource constraints are cumulative, i.e. where the budget spans the whole period instead of one day or time-step. Cumulative and step-level constraints lead to distinct optimization problems, none of which being a reduction of the other.
The blind resource allocation task may be seen specific instance of the more general model of zeroth-order lincarly constrained optimization considered in this paper. For resource allocation, we assume that the learner has access to d + 1 & N different resources. To keep up with the dominant convention in optimization, we consider a minimization problem for which the costs may be thought of as minus the rewards. At each round E (1.... 7): the learner is allowed to choose her level of consumption of each resource, on a continuous scale from to (corresponding to the constraint of spending all the daily budget in the advertising context). The use of resource i E {1....,d .d + 1} to a level of xt generates an expected marginal cost wx(x))). Overall, the expected one-step cost of the learner is given by E wx(ax.), where the set of all possible consumption levels (z 2 ( corresponds to the d dimensional simplex. The goal of the learner is to sequentially minimize the expected cumulative cost over evaluations of the function, having access only to a noisy version of the expected cost associated to the allocation tried at step Not only are the cost functions w1 to 1 unknown, but one cannot observe their individual outputs.
1. We impose that the consumption levels of all the resources sum
1.2 Model
While the main application of interest to us is resource allocation, our results are valid for more general linearly constrained optimization problems. We consider a generic optimization domain D that is a subset of Id defined by linear constraints: D = {a E Rd, Ayr S u} with m E N, Ar E Rmmxd, and u E R". At each round & E (1....T, T), the learner selects It E 'D and incurs a cost f(x)) + ct, where & is assumed to be a centered o-subgaussian noise, with a known to the learner.
The goal of the learner is to minimize the cumulative cost over T evaluations of the function, or equivalently to minimize the cumulative regref
T RT f(x))
[=1
denoting by x, = arg mingep f(x) the optimal allocation. We make the following regularity assumption on f. Assumption 1. f is continuously differentiable, 8-smooth and a-strongly convez DD.
Note that under Assumption M. f has a unique minimum and is bounded from below. Assumption is com-
mon in online optimization due to the difficulty of controlling the cumulative cost without this assumption.
In programmatic advertising and economics, it is common to observe marginal returns that decrease the level of a resource increases (following the so-called law of diminishing returns). Assuming convexity of f on is therefore reasonable, since Assumption implics that when f has the form f(x ....... ,... ".....(()))
EL. w.(ax()) + wa+1 (1-
x; " the marginal cost functions wT wa+1 are also convex and hence satisfy the law of diminishing return (viewing ww, the marginal utility associated to the i-th resource).
1.3 Related Works
The discrete counterpart of the resource allocation model in which the resources can only be used up to discrete consumption levels, is a celebrated model of operations research with multiple applications. Its properties have first been discussed by [oopman (IH6%) who proposed the first algorithmic solution for this problem. Koopman's works have further been extended by Gross (1955); Katoh of all ((иие) who propose more efficient algorithms under specific assumptions on the number of resources and the total consumption
2

---

Published in Transactions on Machine Learning Research (04/2024)
budget. The range of applications is wide, including experimental design, load management in an industrial context, computer scheduling and, more recently, the adwords problem introduced by Mehia et all (2m07). Recently, Agrawal & Devanur (2 studied online and offline resource allocation, motivated by the latter task. With the same motivation, Fontaine of all (2020) focus on the online and continuous version of resource allocation in which the learner accesses the derivatives. The method studied by Fontaine el all (2020) extends the bisection mothod in dimension >> 1.
The broader problem of derivative-free optimization in noisy environments has been considered by re- searchers coming from different horizons. A relevant stream of works originates from the bandit community, which considered this task as an extension of the more traditional multi-armed bandit problem (sce c.g Auer el all, 2012). The class of X'armedd bandits models focuses on the case where a learner can select actions in a generic measurable space and the mean--ayoff function is regular. In (Bnnbeck et all, 2011), for example, the mean payoff function is supposed to be locally Lipschitz with respect to some dissimilarity measure. Bubeck et all (Z and Mumos (2UTE) adopt the approach of hicrarchical optimization, in which the optimization domain is iteratively partitioned, resulting in finer and finer partitions, that are required to be balanced in some sense. The learner maintains an upper confidence bound of the goal function that is constant on each cell defined by the finest partition. The algorithm proposed by Bubeeck et all (20TT) achieves a regret of the order of vT when the learner knows the exact order of the smoothness at the optimum. However, partitioning the domain in a hierarchical and balanced way is relatively easy when the domain is an hypercube, but is a computational problem in itself when the domain has a more complex form. We also mention that knowing the smoothness is considered a challenge most of the time in black-box optimization, so that several methods have been introduced that are adaptive to the smoothness (Locatelli & Carpentier (2018); Valko ct all (201); Shang Ct. all (201)) We mention that concurrently to HOO based on hierarchical partitioning, Agarwal el al. (2 has also proposed different strategy for X'-armed bandits, but this time convex, with ellipsoid methods, that also result in O(VT) regret.
The extension of more traditional first-order optimization methods has also beon considered. When the function evaluation is not perturbed by any noise, Nesterov & Spokoiny (2017) consider random gradient descent based on finite differences to estimate the gradient. Mlxxman et al (210)) consider a version of stochastic gradient descent with one-point estimate of the gradient for the adversarial sctting introduced
by Kevichich (20IK) in which at each time step, new goal function is chosen by an adversary, making it
impossible to rely on a two-point estimate of the gradient. In this setting, Flaxman et all (2018) show an
adversarial regret bound of the order of 15/6, Later on, Hazan & Levy (2ME). Hazan &r Li (21T6T Bubeek
al (2017) propose new methods for the same setting, but with adversarial convex or strongly-conve
functions, showing improved regret bounds, as low as vT. In a stochastic setting that is closer to ours,
Akhavan of all (202)); ; Bach & Perchei (20T)) consider a version of stochastic gradient descent with unbiasod estimates of the gradient, obtained by finite differences. While they provide an analysis in term of the regret, they focus on restricted notion of regret that is different from the one considered in this work. The algorithms that they propose rely on number of samples used to estimate the gradient at each iteration of the gradient descent algorithm. But the regret only accounts for the cost incurred by the iterates of the gradient descent algorithin and ignores the regret incurred by the samples used for the estimation of the gradient. Moreover, the constraints also do not apply to those samples, meaning that the algorithm is allowed to get samples outside of the feasible domain order to estimate the gradient. The authors prove an upper bound on their version of the regret, which is of the order of VT when Assumption II is satisfied. In Section and below we will see how evaluations outside of the feasible domain can be avoided, using for instance ideas of Bravo et all (2ITS), at the price of an increased regret rate.
1.4 Contribution
In this paper, we focus instoad on a class of simple but mathematically well grounded algorithms known as direct or pallern search methods. Direct search (Kolda el all, 2008) makes use of the well-known fact that if the objective function is continuously differentiable, then at least one of the directions of any positive spanning set (a set that spans the space with non-negative coefficients, abbreviated as PSS in what follows) is a descent direction. It explores the space by evaluating the function at new points that are located in a number of predefined search-directions from the current. iterate, at distance from that iterate that varies
3

---

Published in Transactions on Machine Learning Research (04/2024)
with time. The algorithm moves to a new iterate only if this iterate yields a sufficient improvement of the value of the function (there exist. other versions of the algorithm where the sufficient decrease condition is replaced with a constraint on the choice of the trial directions). The sample-complexity of such an algorithm has been analyzed in (Viceett, 20r) in the deterministic and unconstrained setting. Lewis & Torezor (20m)) study direct search in linearly constrained domains. Handling the const raints in direct search is quite simple, as it consists in testing only the directions in the set of scarch-direction that are feasible. Gratton cf all (2015 analyzed direct search with random sets of search-directions instead of predefined ones and later extended the analysis to the case of conetra-conntraineee domains (Gratton et al, 2019). Dzahini (2022) extended their work by analyzing a similar algorithm in the presence of noise, but without constraints. Dzahin (2022) relies on an assumption on the decrease of the noise. In this paper, we will study direct search algorithms that rely on a number of samples at each point to build tight estimates of the function
at the trial points, which can be understood as a way to decrease the noise. Dzaum (2122) analyzes some notion of sample complexity of direct scarch, which only takes the itcrates into account rather than the number of function evaluations needed, which is not appropriate in our setting.
Our purpose is to study these methods that are suitable for the blind resource allocation model, i.. in particular, compatible with zeroth-order feedback, computationally tractable and that do not require to sample points outside of the feasible domain. Besides satisfying the above requirements, these algorithms have the advantage of being approximate descent algorithms with high probability, a guarantee that is useful in practice, allowing, for instance, warm start from previously tested allocations. The adaptation of direct search to the noisy case is achieved by performing enough sampling to ensure that the algorithm moves to a new iterate only if it results in a sufficient improvement, with high probability. We propose two ways of doing so: the first method (termed FDS-Plan) simply computes the number of necessary evaluations ahead of time, whereas the second one, FDS-Seq, uses sequential lesting strategy to interrupt sampling early as possible. The algorithms are specified in Section B. An illustration of the behavior of the proposed algorithms can be found in this same section, alongside an illustration of other baseline strategies, which allows for understanding the specifics of direct search. We analyze the cumulative regret of these algorithms in Section 3 providing an upper bound of their regret of the order of T2/3 (up to logarithmic factors), when the optimum in the interior of the feasible domain. A significant technical challenge for the analysis in terms of regrct is that, while in traditional analyses of dircct-scarch, the number of rounds is fixed and the analysis proceeds by looking at the distance to the optimum al each round, here, the number of rounds is random (the indexing of the regret is the actual number of function evaluations instead of the number of rounds). We start Section B by the simpler case in which there is neither noise nor constraints, showing that in this basic setup the regret of direct search is bounded by a constant.
2 Algorithms
2.1 Description of the Algorithms
In Algorithm M below, we start by describing the most common version of the direct search method used for deterministic and unconstrained optimization. It requires the setting of an initial point zo and an initial parameter ag- The learner also specifies a PSS DD that is, a set of directions that spans Rd with nen-negative coefficients. At each iteration, the algorithm sequentially tests points at a distance 0g from the current iterate and in the directions defined by D. If none of the test points results in a sufficient decrease of the function's value, the iteration is declared unsuccessful and the trial radius os shrinks by a factor 0 < 1, otherwise, the iteration is declared successful and the iterate 2g is moved to the first trial point that results in a sufficient improvement. A decrease is considered to be sufficient if it is larger than some predefined forcing function of ak, that we take here to be quadratic, with a coefficient that can be set by the learner.
The analysis can also be adapted to the presence of a growth factor o 2 1 by which the trial radius eg expands at successful iterations. For simplicity, we choose to focus on the case where ø 1, as this parameter does descent algorithm with
not modify the regret rates obtained in Section Bl Also note that Algorithm respect to the iterates Fk, Le., the sequence (fxx))) is decreasing.
4

---

Published in Transactions on Machine Learning Research (04/2024)
Choose zo E R2 ap > 0, < c> p(u) = cu² and a PSS D
for O...K K do
Set Unsuccessuulearcch + True
for v E D do Evaluate (Ix agu)
if -(Ix)- f(xx + aqu) 2 p(ax) then
Set F++1 3ek + 0g and 01+1 t- og
Set Unsuco Break
False
end end if UnsuccessfulSearch then
Set Tk+1 t Iy and 0x+1 t 6ok
end
end
Algorithm 1: Direct Search with sufficient decrease
Obviously, different choices of PSS result in different trajectories of the algorithm. Setting D as the set of 2d vectors of the positive and negative coordinate directions results in the algorithm known as coordinate or compass search. Other frequently considered choices include random directions, as in (Gratton et all,
2015 2011 Dzahin. 2022).
Choose Tu E Rdd on > 0, <
p(u) cu²
Choose 2g p(u) = cu² Set Unssucessffuleercch +- True for k = 0... K do
Rd dg > 0, 0,
for k = O...K K do Set UnsuccessfulSearch +- True
Select a set of directions D3;
Set N₂ 32n -222210((2 loR(2/6)
Select a set of directions Di for in Da such that Fæ oggo E D do while Condition Q is not satisfied do if na.k S Ro, then
plan)²
Estimate f(xx) by making NA samples at 2t and setting f(xx) = 1 N. Ei (xx) + Ey for E Da such that + a&e E D do Estimate f(0* + agy) by making N₃ samples at Ik + agg and setting f(Iu+ +aa)) = No Een f(r + agu) +e/
Sample 2y + agv and update ne, and the empirical mean fn., (xx + agu).
end else
if f(xx) f agu) p(ax) then Set Ik+1 t 2b + ag and a1+1 + ax. Sct UnsuccessfulSearch False Break
Sample at and update no.k and the empirical mean fno, (Ix)
end end if UnsuccessfulSearch then
end end if fno.( - fno, (xx + agv) 2 p(ax) then
Set T4+1 +- Ib and 0:+1 +- Oak end
Set Db+1 Ib + age, and ax+1 + ag. UnsuccesfuuSearch False Break.
end
Algorithm 2: Pla-
end end if UnsuccessfulSearch then Set Tk+1 f- Fy. and 0x++1 Oox
end
end
Algorithm 3: FDS-Seq
We apply three sorts of modifications to Algorithm in order adapt to the more general model introduced in Section 12 The first. consists in sampling trial point only if it is feasible. The second consists in
5

---

Published in Transactions on Machine Learning Research (04/2024)
allowing changes in the set of directions De considered. This is to account for the fact that the change in search-radius at every round impacts the set of admissible directions, denoted An. We thus only need to sample directions that span A& positively, and not the whole optimization domain D. The third modification consists in introducing cstimation stages that allow building reliable estimates of f at the trial points. We propose two ways of doing so, that result in two different algorithins The first. algorithm that we study is a plug-in version of Algorithm D which we replace f*x* and f + agv) with their empirical estimates, consisting of means computed from N₂- 1og2//) samples. This mumber of samples guarantees that plax)²
with high probability, the estimation gap is smaller than p(ax)/4, which in turn ensures that an iteration is declared successful only when it leads to decrease of f(xx by at least p(ax)/2 and that an unsuccessful iteration cannot occur if there exists direction u in D& such that the decrease achieved by moving to Tx +og is larger than 3p(az)/2. The resulting algorithm is termed Feasible Direct Search with a planned number of samples (FDS-Plan) and described in Algorithm & We also propose a faster algorithm, Feasible Direct Search with Sequential Tests (FDS-Seq) described in Algorithm & For any v E Dy, instead of planning the number of samples at I& + a ahead of time, it samples at Ik + aayu and Iy until cither
[non (dxe) - Sn (Irk + owo) - p((a)) s 20 2002) mo.k
s
(
I +
(1)
or (mo,k 2 N& and ne. 2 N1)
Ro.k and &y denoting the number of samples at aq and zy + age and fno. (xx) and fn..t (æx + agg)) the rosulting empirical means. Successful and unsuccessful iterations are defined as in FDS-Plan and trigger the same actions.
The sequential stopping rule is designed to achieve early detection of sufficient decrease, but also to detect as carly as possible the cases in which the trial point cannot lcad to a sufficient docrease. The first test in Condition M is a consequence of the fact that the estimation gap at 2y (respectively 23 + agu) is o² //no. subgaussian (respectively /2/nn, subgaussian). The second test of Condition corresponds to a safeguard preventing from waiting too long when the decrease induced by the trial point is very close to the sufficiency threshold. At worst, the mumber of evaluations needed is the same as in Algorithm D Essentially, the sequential stopping rule reduces the number of evaluations needed for each iteration but maintains the desirable property that with high probability, an iteration is declared successful only if it lcads to decrcase of at least p(ax)/2 and that an ileration cannot be declared unsuccessful if there exists a direction v in Dr such that the decrease achieved by moving to I + agy is larger than 3p(ax)/2.
2.2 Illustration
their trajectorics in the case where there are 3 resources (d = 2) and the loss functions associated to cach resource log( ++ with 7 2, T = 1, 72 0.45, and T3- 0.95. We set the horizon to T 100, 000 and use Gaussian noise with standard deviation budget allocation problems. In the symmetric representation of Figure M, the three vertices correspond to the points where one of the resource is fully saturated (equal to 1) and the edges correspond to linear paths along which one of the resources is set to O. The contour lines of the target function are materialized by orange lines and the location of the minimum is marked by a black cross. The size of each point is a logarithmically growing function of the number of samples made at this point, and its color is a function of the index of the first round at which has been sampled. Finally, points at which a succossful itcration of FDS-Plan (and FDS-Seq) occurred are circled in blue. The parameters of both versions of feasible direct search are ao 0.2, = 5 and 0 == 0.7, and the initial point corresponds to the allocation x0) (1/3, 1/3, 1/3) (center of the simplex). To make the figure more interpretable, we choose to set fixed D. The set of directions chosen for these algorithms are the 6 directions that support the edges of the simplex (in both directions).
In order to illustrate graphically the behavior of the proposed methods, we show on Figure [(a] and [dd
i E (1....,d d + }} are of the form wx(x)) = Ti log(1+>)
0.1, realistic value for
In a first phase, the algorithm proceeds rapidly by testing directions until a sufficient descent direction is found. Afterwards, when the itcrates get closer to the minimizer, the search area iteratively shrinks as finding descent directions becomes harder. In the first phase, the trajectory is similar to a descent path that would result. from a gradient descent algorithm while the second phase is closer to the behavior of
6

---

Published in Transactions on Machine Learning Research (04/2024)
10
10a
10
10"
10P
10a
10P
102
104
(a) FDS-Plan
(b) HOO
(c) Gradient Descent with
two-points estimate
10"
10a
(d) FDS-Seq
(e) UCB
(f) Cradient Descent with
one-point estimate
Figure 1: Single trajectories
bandit algorithms based on hicrarchical partitions, like HOO (Bubeck call 201 order to illustrate the differences with such algorithms, we also plot the trajectories of baseline methods, either related to gradient descent or bandits with hierarchical partitioning. Before turning to these other algorithms, it important to note the difference between FDS-Plan and FDS-Seq. Figure [d]] shows that FDS-Seq faster than FDS- Plan, it spends less time the first iterations, in which it is casy to determine whether the trial points lead to sulficient decrease. The FDS-Seq algorithm can thus perform more ilerations than FDS-Plan. A common point of these two algorithms that is illustrated on the figure is that they are approximate-dessent algorithms with high probability, an interesting quality for practitioners intorested in interpretability.
Let us now comment on Figure [b] that represents the trajectory of version of HOO. is not straight- forward to apply algorithms for X arareed bandits like HOO on the simplex, because it implies constructing balanced hicrarchical partitions of the simplex. We thus explain implementation of HOO in Appendix EL On Figure [[b], observe that this algorithm explores the partition tree in way that favors the cells close to the optimum while persistently visiting cells that are clearly far from the minimizer. The behavior of algorithms based on direct search can thus be preferred because it makes warm-start possible, in the sense that prior belief on the location of the minimizer can be used for setting the initial point, which is not possible for HOO. The fact. that suboptimal points will keep being sampled until the end of the experiment can also be difficult to accept for practitioners such as advertiscrs for example.
We also illustrate the behavior of UCB discretization of the space, which is an interesting strategy, especially in dimension 2. The discretization used for UCB consists of points arranged in regular grid of 1]2, from which the points lying outside of the feasible domain have been removed. The step parameter of the grid is taken as 7-1/4 as suggested by Combes & Prouliers (211).. Although simpler than HOO, this algorithm results in similar sampling patterns, as shown on Figure [[e], and hence shares some of its drawbacks. The performance of UCB good in dimension 2, as the regret can be proved be of the order of VT with this choice of step-size (see Combes Pronfierd (2mT)) but it will worsen higher dimension due to the difficulty of simultaneously controlling the distance between grid points and the overall number of

---

Published in Transactions on Machine Learning Research (04/2024)
points in the grid. In fact, the optimal step in this case is of the order of T-1((4+2) and the resulting regret is of the order of 7d/d+2, which only works in favor of UCB for small values of d. Note that while Combes & Pronfierd [) also provide weaker regret guarantees under more general assumptions, the assumptions required to obtain this order of regret are similar to Assumption M. They are only less constraining than Assumption D that they require a quadratic upper and lower bound on the function locally near the optimum, whereas Assumption M1 should hold uniformly on the domain.
Lastly, we illustrate the behavior of two methods related to stochastic gradient descent. The first method is related to that proposed by Akhaaan et all (2022). Without constraints, this method would estimate the gradient of the function at Lt. by evaluating the function at y, = + Z and y, = - 2 where Z is a random vector of the sphere of radius 1, and use (i,")=((v7 Ze as an estimation of the gradient. The h: method in itself does not take constraints into account, but a slight modification results in an algorithm that is feasible in the presence of constraints. This modification consists in performing a homothetic perturbation (Bravo all,, 2 on the evaluation points yi and yr : instead of using these points, the algorithm evaluates the function at y.- y/+ + he/r(c-- xz), where is a point in the interior of the simplex such that B(c, r) D. We use y/ = Dt + lhhh//(ee
244) and Di yr he/r(e- - vt), where e is point in the interior of the simplex such that B(c, r) c. D. This ensures that the evaluation point belongs to the constrained domain, provided that Ie E D, but adds a bias which is proportional to he, under suitable regularity assumptions on f. To ensure that 2y E 'D, we also project the result of the gradient descent step on D. We use an estimation step h equal to (t/2)-1/² and a learning rate decreasing as 1/(2.5)). This choice is justified by the following reasoning: with this choice of value for the learning rate and hg set to t-1/4, f(=1 f(z)) - f(x*) would be bounded by O(T!/2), thanks to the analysis of Akhavan el all (212)); but we have to add a term related to the sum of evaluation steps ETZ + [ ) 2f(xx))) to bound the actual regret, which under suitable assumptions is of order Ei= he; so that setting he to (t/2)-1/3 allows to bound both terms by O(T2/3). On Figure IC we see one trajectory of this method when the starting iterate on the center of the simplex. The convergence speed is rather fast at the beginning but the speed is limited by the homothetic perturbation.
The sccond method is inspired by Elaxman ct all (201E)) This paper proposes to use gradient descent with one-point gradient estimation. In order to evaluate the gradient of the function at Fe, the algorithm evaluates the function at = Iz + h,Z,, where Z, is a random vector of the sphere of radius 1, and uses flu)/haa, as an estimation of the gradient. As for the previous method, we apply an homothetic perturbation to ye- We use an estimation step he equal to t-1/3 and a learning rate decreasing as 1/(2.5t). The trajectory that we see on Figure [T] is not very indicative of the average performance of the a algorithm, since this method comes with very high variance. We see that the algorithm generates a trajectory that roughly gets closer to the minimizer, but that is far from being a descent path because of the poor estimation of the gradient. This method, which has been designed for adversarially evolving objective functions, is clearly not advisable for static objectives with stochastic perturbations.
3 Regret Analysis
As discussed in the introduction, the regret criterion takes into account the number T' of function evaluations instead of focusing on the number K of iterations, as in the more traditional analysis. In the noiseless case of Algorithm M. T and K differ by a factor of at most. [T|+1 and this is not an issue. However, in the case of Algorithms 2 and B, the situation is very different as the number of function evaluations per itcration is stochastic and typically increases as the algorithm converges. In this case, it is not possible to predict in advance the evolution of T as function of K because it depends on the function and starting point. A significant part of the analysis is indeed devoted to quantifying this phenomenon. In practice, it means that in order to comply with a number T of function evaluations set in advance, the algorithms are run without a fixed number of rounds K, instead they are run until the number of function evaluations reaches T.
In the following, we analyze the proposed algorithms and show that in the constrained and noisy sct-up of interest, PDS- and FDS-Seq have a regret of the order of (log T)3333/22//3 under some further assumptions I and the chosen direction set DD;, provided that the optimal point lies in the interior of the feasible do-
8

---

Published in Transactions on Machine Learning Research (04/2024)
main. To provide some intuition on the proofs, we start with the analysis of Algorithm @I in the unconstrinned and deterministic setting, thereby providing the first regret bound of any direct search algorithm.
3.1 Warm-up: the Unconstrained and Deterministic Setting
The choice of D is decisive for the performance of both FDS-Plan and FDS-Seq. In the sequel, make the following assumption on D.
Assumption 2. The vectors of ID have wnit norm and the cosine meosure of ID is lower-bounded, i.e, there ewists > 0 such that
u 1 |
cm (TD)
min max wERd ,000 DED
Assumption 2 common in direct search's 's literature, guarantees that at each iteration k, the cosine similarity between least one direction in D and f is larger than K. If D is a PSS there exists K satisfying it. Theorem 1. Under Assumplions and B, the cumulaaiie regret of Algoritie satisfies
DI+1 c
(1-02 (F(xz) [xx) plan)) ((1+)) B)
RT
( [[V a00
(f(20) f(x.))
(c + () where == $ k0
This result shows that under Assumption M. the asymptotic behavior of the regret of direct search can be compared to that the more traditional gradient descent algorithm, whose regret also bounded under this assumption (sce Thcorem 3.6 of [Bubeck ct all, 2000).
3.1.1 Elements of Proof
The proof of Theorem D combines two well-known properties of direct search and the following lemma holding for any descent algorithm.
8 a
Lemma 1. If] f satisfies Assumption M. then Vk' > k, [V]( ||
[V
In the proof of Theorem D, Lemma. M is used in conjunction with the following well-known property (see e.g Vicente, (UK) of direct search.
Lemma 2. If satisfies Assumptions W and and iteration k corresponds to unsuccessful iteration, then 9
p(as) =
[[](()))| O
+ ax. os.
Okk
The above lemma follows from the definition of the cosine measure of ID that results a bound of of (=)()))))), where Uk is the direction in D maximizing the gap f( + tage), and from the smooth- ness assumption f. Thanks to Lemma this lemma also means that when iteration is unsuccessful, can bound all subsequent gradients by A ( + c)ag. We can deduce that for any k' following the first unsuccessful iteration, [[V I|S yar' where r) = 2 J (c+ 8) Indeed, if k' is the index an unsuccessful iteration, Lemma suffices prove [[V naa In contrast, when k' the index of successful iteration, one should consider the last unsuccessful iteration k. Since or 2 Aag, there has been at most roduction of the step-size since iteration k and
3 ka0
(1 +
(6+c)
aw noW.
(2)
The following general argument on direct search the final key element of the proof of Theorem MI that links the sum of the squared search-radius to the initial sub-optimality gap f(xo) f(x.).
9

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 3. If f satisfies Assumptions M and B.
80
Σ
p(ax))
Σ S 1 8- k=0
cat
82 g2 (f(r)) f(x)) + p(aa))
Lemma 0 can be explained by the fact that p(a²) decreases geometrically by a ratio 0 between two successive successful iterations, so that the contribution to the sum of these ilerations boils down to multiplying the remainder of the sum by a factor of - The sum on successful iterations cannot be too large, because by definition of successful iterations, f(xx) - f(x)) is lower bounded by this sum plus the initial sub-optimality gap [(=a)_ Bringing Lemma R and the bound of Equalion @ logether results in bound on the squared norm of the gradients [ after the first unsuccessful iteration. Using the regularity conditions of Assumption @ suffices to relate the regret to the squared norm of the gradients, which in turn yields Theorem m. The complete proof can be found in Appendix [..
3.2 The Constrained and Noisy Setting
We now turn to the noisy and constrained case described in Section assumptions on the domain.
We further impose the following
Assumption 3. 'D is contained in a ball of radius b.
This assumption, together with assumption M. implies that f(x) - f(x.) is bounded. It also follows from these two assumptions that Vf is bounded in norm by a constant, denoted by B, on the feasible set D.
While in the unconstrained case, the chosen PSS only needed to satisfy Assumption D, a stronger as- sumption is required in the presence of linear constraints. Indeed, Assumption was way to ensure that there was at least one trial direction e in D satisfying ]< 2 K. This property is not sufficient in the constrained case, because in this case, the directions of interest at iteration k in D2 are those that are feasible. A problem that might arise for example, is that a sufficient descent direction is not detected even in a situation where IY= ag V fZx)) is feasible, because the set of feasible directions in D1 does not positively span the feasible region. To avoid such cases, we impose a constraint on D2 that involves the notion of approximate tangent cones. Approximate tangent cones at a point x are the polar cones of the cones that are generated by the a-binding constraints at x as defined by Kolda of all (2mmn) (see particular Figure 2.1 of Kolda all (2ImT) for an illustration of the notion of approximate tangent cones).
-Vf(s))²
Let af be the i-th row of the constraint matrix At and let C, {y, s.t afy ) denote the sets where the i-th constraint are binding. If there exists point of C, at distance smaller than a from then the i-th constraint is said to be a-binding. The indices of a-binding constraints at x are denoted /(x,, a) = {ú, dist(r,C)) C.) & a), where dist is induced by the Euclidian distance. We define the approximate normal cone N(, a) to be the cone generated by the set {a;, s.t. i E [(x, [(x,a)) U {0}. The approximate tangent cone T(z, a) is the polar of N(x, a) which means that T(z, = {o to:y"" S O, Vy E (zz.))). Informally aa is the cone inside of the boundaries generated by the a-binding constraints at æ. We highlight that since the number of constraints m is finite, there can only be finite number, smaller than 2mm of tangent cones. Consequently, Assumption 9 is rather mild.
Assumption 4. For k E K). B. contains set Gk of positively generating directions of T(x, a) included in T(x, a), for any I E D and a E Rt.
In the following, we denote by Gr such set. Assumption @ was already necessary in (Kolda et all 2003) and Lewis & Torczon (201), while in (Gratton et all, 2m19), the descent set at iteration & is assumed to be contained in T(x, a:) and to generate it. We explain the purpose of this assumption in the following. While the purpose of Assumption was to ensure that the maximal cosine similarity of a vector in Dy with (fx( was bounded away from 0, we focus on a different kind of mcasure of similarity to - fxx) defined as
- VT max (Pronn](V//(a))) if otherwise.
# 0.
10

---

Published in Transactions on Machine Learning Research (04/2024)
If Pr(z.a)( (-V gets close to 0, this measure of similarity to fZx(2)) does not necessarily become small, although - (zx))) is small for any v in GR- In order to bound this measure of similarity between a vector of Gy and - (xx away from O, we define the following approximate cosine measure:
uTo
inf am) (9k) := MER* Prag agg (0 vE
max P (w)l
As proved by Lewis & Torczon (2000) and recalled by Gratton el all (2I1)), if C is a set of cones ej that are respectively positively generated from a set of vectors G(cy), then
u |P (w) [I]
X(C) = min ejEc
inf "ERA, Pe, uEC(es))
max
>0,
which guarantees that cmT an) (Gk) is bounded by some constant Kmin > 0, under Assumption R.. Under the above assumptions, we can bound the regret of FDS-Plan when the optimum lies in the interior of the feasible set. Note that assuming optimal allocation in the interior of the feasible set crucial for analysis, but we believe the opposite would not be harmful in practice, as supported by simulations (sce Appendix E)) Theorem 2. Under Assumptions D, D. and d if ax E inl(D) and if [D&] is bounded by a constant Se, the cumulative regret RT of PDDS-lan (respectively FDS-Seq) after the first T evaluations of f satisfies
E [[[T] = O (1og(T)3/ápar3)
for the choice 8 3= TT/3 (respectively 8 10/3 for FDS-Seg).
In the absence of a lower bound, the optimality of such a regret rate is unsure. It is difficult to compare it to other known bounds, as the performance of related algorithms often not evaluated in the same way. In particular, the performance of the version of stochastic gradient descent proposed by Akhavan all (2020) is analyzed with respect to different notion of regret, Rr, that does not take into account the samples needed for the estimation of each gradient. Their analysis yields Ry O(VT). It is important to note that the algorithm by AAkhavan ct all (2020) takes advantage of the fact that in the setting of the latter paper, sampling points outside of the feasible domain is possible. When using homothetic perturbatinn as we did for the illustration in Figure [[c], the regret of such a method is of the order of T2/3 as explained in Section 2M
Black-box algorithms such as HOO or StoOO (Bubeeck all, 2011: Munos, 201! are other possible baselines. When given a balanced hierarchical partition of X, and the smoothness of the function around its optimum, these algorithms would incur regret of the order of VT. The regret rate of FDS-Plan appcars to be larger than that of HOO instantiated with the right parameters. However, HOO relies partition of the feasible domain that is computationally difficult to achieve with arbitrary linearly constrained domains.
The assumption that [D&| be bounded by a constant Sp is actually not constraining at all, since one way of satislying Assumption M is to set D2 to the constant set of vectors corresponding lo edges of optimization domains, which amounts to 2m(m- - 1) directions, where m the number of constraints. Depending on the optimization domains, there may be smarter ways of choosing [IDx| that lead to smaller constants Sp. The motivational case of resource allocation, where the feasible domain is the simplex, is an example of that.
In that case, the above method for choosing Dh yields Sp = 2d(d + whereas recomputing the direction set at every round can spare us a factor d. An intuitive way to understand this is to consider the simplex of dimension d = 2. When the iterate in the interior of the simplex, and the step-size ag is such that the admissible directions When T( aq) smaller, then minimal sets G are formed by even fewer voctors. An efficient method for recomputing the set of directions at every round is described in Grillin el. all (2008). It is possible to verify that for the simplex, this method provides less than 2d directions each round.
T( og) form RR, we only need +
vectors (an angle of 2 2n/3 apart).
This is particularly important, because the regret bound is proportional to the number of directions contained in Dy (see the proof of Theorem 2. in Appendix D22),, so that the dependence of the regret with respect to d is linear, For the sake of comparison, the regret of the algorithm by Alahaaan et all (2122) is quadratic in d, whereas, when HOO is perfectly parameterized, the dependence on d of the regret of HOO disappears. Recall however, that on arbitrary linearly constrained domain, or even on the simplex in high dimension, HOO might be computationally intractable.
11

---

Published in Transactions on Machine Learning Research (04/2024)
3.2.1 Elements of Proof
After some finite number of iterations that depends on A := mi..m (ist(z,,C)) the boundaries of DD is smaller than A/4 with high probability, thanks the analysis of Gralton el all (201). Waiting for another number of iterations, ag gets small enough for the approximate tangent cone TTk aq)) to describe the whole space R.. Then, the trajectory of the algorithm is the same in the unconstrained setting. In the unconstrained setting, the following elements provide intuition of why the regret is of the order of 22/3, With similar arguments to those of the proof of Theorem M. i. Lemmaa M. 2 and B. it is easy to see that the instantaneous regret incurred at iteration k of the algorithm is proportional to the sum of o (up to logarithmic factors), whereas was proportional to oj in the deterministic case: indeed, iteration k now involves N₂ times more evaluations than the noiseless case and N₂g proportional to o (up logarithmic factors). Thanks to Lemma 3 we know that a summable. Then, thanks Hölder's inequality applied to the sum of 0g written as (ax)2/0 (ax) 2/3-2 evaluations to the power of 2/3, up to logarithmic factors. The complete proof can be found in Appendix D
the distance from øg to
(ax3)2/3-2
the regret is proportional to the total number of
4 Experiments
our experiments, we focus on the case in which there are seven resources (d= = 6), and the loss functions log(1+>=) are of the same form as in Section 2n2 and wx(x)) - Tog 1+7) with =2,, 71
= 0.75, Ts 0.89, and To 57 0.95. On Figure B. compare FDS-Seq and FDS-Plan to UCB on discretization of the space, and gradient descent with an homothetic perturbation. Both methods are explained in Section eme The comparison with HOO is made impossible by the numerical complexity of HOO. We set the horizon to T = 500, 000 and use Gaussian noise with standard deviation o = 0.1. The set of directions used in FDS-Seq and PDS-Plan are chosen with the method of Griftin all (2008).. The step parameter of the grid of UCB set as 7-1/(d42) 7-1/8.
=
140000
UCB
FDS-Seq
120000
2-points GD
FDS-Plan
100000
80000
60000
40000
20000
100000
200000 300000
400000
500000
Time
Figure 2: Regret plots of various strategies for resource allocation
The regrets of the algorithms strongly depend on the chosen function. In the case of UCB, the position of the maximizer with respect to the grid that it relies on is important. To alleviate this issue, we plot the mean regret of all the algorithms, when randomly shifting the loss function by random vector whose coordinates are in [0.05, 0.05). We use 1200 Monte Carlo repetitions. The shaded area represents the region wetw the first and third quartile.
Clearly, FDS-Seq. by reducing the number of samples needed the beginning of the run (when moves cor- responds to significant drops of the target function), dominates FDS-Plan. The unsatisfying performance of
12

---

Published in Transactions on Machine Learning Research (04/2024)
the gradient descent algorithm can be explained both by the homothetic perturbation that harms the conver- gence to the optimizer, and by the bad dependence of this algorithm on the dimension. FDS-Seq also clearly outperforms UCB. Note that the performance of UCB will worsen in higher dimension due to the difficulty of simultancously controlling the distance between grid points and the overall number of points the grid.
5 Conclusion
We have studied extensions of direct search algorithms designed for linearly constrained zeroth-order opti- mization in the stochastic setting. We have shown that these algorithms, though being fairly simple, suffer regret of the order of T2/3, which quite satisfactory when compared to other options with comparable implementation cost, like those inspired by finitely-armed bandit algorithms or by gradient descent schemes, There is still performance gap, in terms of regret rate, when compared to some continuously-armet bandit approaches that are however computationally much more heavy, even in low-dimensional instances of the resource allocation model, such as the one considered in Section !! We do not believe that the analysis of the algorithms proposed in this paper can be refined so as to obtain the vT regret rate. However, an interesting open question for future work is to know whether this bound could be achieved by other sampling allocation schemes.
13

---

Published in Transactions on Machine Learning Research (04/2024)
References
Alckh Agarwal, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. Advances in Newral Information Processing Systems, 24, 2011.
Shipra Agrawal and Nikhil R. Devanur. Fast algorithms for online stochastic convex programming. In Proceedings of the Twenly-sirth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, 2015.
Arya. Akhavan, Massimiliano Pontil, and Alexandre Tsybakov. Exploiting higher order smoothness derivative-free optimization and continuous bandits. Advances in Neural Information Processing Systems, 33:9017 9027, 2020.
Peter Auer, Nicolo Cesa- Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-2 2002.
Francis Bach and Vianney Perchet. Highly-smooth zero-th order online optimization. In Conference on Learning Theory, pp. 257-283. PMLR, 2016.
Mario Bravo, David Leslic, and Panayotis Mertikopoulos, Bandit learning in concave n-person games. Advances in Neural Information Processing Systems, 31, 2018.
Sébastien Bubeck, Gilles Stoltz, Csaba Szepesvári, and Rémi Munos. Online optimization in x-armed bandits. Advances in Newral Information Processing Systems, 21, 2008.
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimization. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 72-85, 2017.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(vv), 2011.
Richard Combes and Alexandre Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms. In International Conference on Machine Learning, pp. 521 529. PMLR, 2014.
Kwassi Joseph Dzahini. Expected complexity analysis of stochastic direct-scarch. Computational Optimiza- lion and Applicalions, 81(1):179 200, 2022.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit sotting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
Xavier Fontaine, Shie Mannor, and Vianney Perchet. An adaptive stochastic optimization algorithm for resource allocation. In Algorithmic Learning Theory, pp. 319-363. PMLR, 2020.
Serge Gratton, Clément W Royer, Luis Nunes Vicente, and Zaikun Zhang. Direct search based on proba- bilistic descent. SIAM Journal on Optimization, 25(3):1515-1544 2015.
Serge Gratton, Clément W Royer, Luis Nunes Vicente, and Zaikun Zhang, Direct search based on prob- abilistic feasible descent for bound and lincarly constraincd problems. Computational Optimization and Applications, 72(3):525-550) 2019.
Joshua D Griffin, Tamara G Kolda, and Robert Michael Lewis. Asynchronous parallel generating set search for linearly constrained optimization. STAM Journal on Scientific. Computing, 1144:189221924 2008.
O Gross. A class of discrete-type minimization problems. Technical report, 1956.
Elad Hazan and Kfr Levy. Bandit convex optimization: Towards tight bounds. Advances in Newral Infor- mation Processing Systems, 27, 2014.
Elad Hazan and Yuanzhi Li. An optimal algorithm for bandit convex optimization. arv preprint arXiv:1603.0400 2016.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Naoki Katoh, Toshihide Ibaraki, and Hisashi Mine. A polynomial time algorithm for the resource allocation problem with convex objective function. Journal of the Operational Research Sociely, 30(5):449 455, 1979.
Tamara G Kolda, Robert Michael Lewis, and Virginia Torczon. Optimization by direct search: New per-
spectives
classical and modern methods. SIAM revieu, 45(3):385-4822 2003.
Tamara G Kolda, Robert Michael Lewis, and Virginia Torczon. Stationarity results for generating set search for lincarly constrained optimization. SIAM Journal on Optimization, 17(4):943-968, 2007.
Bernard O Koopman. The optimum distribution of effort. Journal of the Operations Research Society of America, 1(2):52-66) 63, 1953.
Robert Michael Lewis and Virginia Torczon. Pattern search methods for lincarly constrained minimization. STAM Journal on Oplimization, 10(3):917-941, 2000.
Andrea Locatelli and Alexandra Carpentier. Adaptivity to smoothness in x-armed bandits. In Conference on Learning Theory, pp. 1463 1492. PMLR, 2018.
Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online match- ing. Journal of the ACM (JACM), 54(5):22, 2007.
Rémi Munos. From bandits to monte-carlo tree search: The optimistic principle applied to optimization and plamning. 2014.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
Xucdong Shang, Emilic Kaufmann, and Michal Valko. General parallel optimization a without metric. Algorillmmic Learning Theory, pp. 762 788. PMLR, 2019.
Michal Valko, Alexandra Carpentier, and Rémi Munos. Stochastic simultancous optimistic optimization. In International Conference on Machine Learning, pp. 19-27. PMLR, 2013.
Luís Nunes Vicente. Worst case complexity of direct search. EURO Journal on Compulational Oplimization, 1(1):143-10) 103,, 2013.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. -28-9324 2003.
15

---

Published in Transactions on Machine Learning Research (04/2024)
Supplementary Material
Outline. Appendix Bl contains general considerations about the potential repercutions of this (method- ological) work. We prove in Appendix E all the results pertaining to the noiseless, unconstrained case. In Appendix I we provide an additional result for the noisy but unconstrained case. The analysis of direct search in the latter case paves the way for the proof of Theorem @ whose proof is deferred to Appendix Di Appendix contains further explanations about simulations Section 22 and Appendix D contains additional experiments.
A Broader Impact Statement
This paper mostly a methodological paper that is unlikely have direct socictal impact.
However, il explores the idea that direct search algorithms, akin to approximate descent algorithms, can provide explicability in the context of budget allocation for advertising. Advertising practitioners who these algorithms can explain their actions to their clients by guarantecing that with high probability, the latter result in an increase of the desired performance indicator. This work is thus part of a collective effort to reach explicability in machine learning, which is crucial as it allows for more transparency.
From an even broader perspective, sctting budgets for advertising campaigns still manual task in many companies, which could be replaced by algorithms such as those we propose here. Note that this would still leave the task of setting the scope of the campaign (which users to target, which inventories, etc.) to marketing professionals. It is not clear which impact employment the automation of budget allocation could have. However, for now, digital marketing is flourishing sector where employment seems to have increased steadily in the last few years.
B Deterministic and unconstrained set-up
B.1 Preliminary Results
Lemma II. If sotisfies Assumption M.
Ak' k. V/ 2 [+}()
Proof. First observe that because of strong convexity,
(f(x))-V((r. (=x==2,) 2 al|=x xz, =2.12
and
- = |V (x)) || || x1
which implies that
- 211 -
ffxx))
(3)
Hence,
[V S 8|| - x.All
< / ff(xx) f(xx) S 3 [f((a) f(r.)
3
Va
8
v
( x²) 5 Va¹
V ( [
Va
[][[<x)]11
16

---

Published in Transactions on Machine Learning Research (04/2024)
where the first incquality comes from the smoothness (in fact [f((=)]] [ -1,1)= the second inequality is a result of the song convexity, the third one ensues from the fact that the algorithm is a descent algorithm, the fourth one arises as a resut of convexity and the fifth one comes from the strong convexity property of Equation B.
Lemma 2. f solisfies Assumplion M and ileration k. corresponds to an unsuccessful ileralion then
[V 1 (
g 2 + plax) 1
2 + as.
04k
This lemma is already well-known (see e.g.
Vicente 2mR)) only prove it here for completeness.
Proof. Since cm( min Rd, und maXvED,
a² || |||e|| K, there exists D2 such that
-Vf(xx) 2 x|| V+(=))]
Since the iteration is an unsuccessful iteration, we have f(*x) - f(r* + axı) & p(ax) = caf. Then
kay vowlV((z))1-paaa s - Vf(()) 4 f(** + avv) - f(mx)
a Vf(zz - ut) T v V fz(z)) T vdu
$
[ + uv) - v
$ 3 I udu S 3 a
which yields [[Vf(>))]> 1 aa + plas))
) (fas + cas)
ax
Lemma B.
Σ p(an) v 0- (f(x1) - f(xx) + p(aa)) k=0
This lemma is also common element of the analysis of direct search algorithms (see e.g. Gratton et all, 2019), we only prove it here for completeness.
We assume that there are infinitely many successful iterations as it is trivial to adapt the argument otherwise. Let k; be the index of the ith successful iteration 2 1). Define Ko -1 and a-1 ou for convenience. Let us rewrite E p(ax) as E Exid+ p(ax) and study first k11 Ek=k+1 p(ax). Thanks to the definition of the update on a successful iteration and on unsuccessful iterations,
A Σ
k
p(ax)=
Σ km2
(()))))
Σ +1
20 p(ax) 15 02 plan))
Rim
Since on successes p(ax.) S f(xx)) - f(xx; + +ak,) = = (11111))
Σ paan)) 1 f(x)) - -(x..)
Hence
Σ p(a)) < 1 1 -2 (f(rr) - f(x.) + p(au))
k=
17

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 4. The inder ky of the first unsuccessful iteration satisfies:
hi S f(xu) f(x))
p(ao)
Another version of this lemma is due to Gratton et at (2011)
Proof. Before the first unsuccessful iteration, 04 a0-
So by definition of a successful iteration,
yk, such that << k < k
f(Ik-1) - -((x)) 2 p(ao).
By summing,
f f(xx)) 2 kyp(ao).
The left hand-side of this incquality is upper-bounded by f(xo) f(x.), which suffices to conclude the proof.
]
B.2 Regret Bound
In this section, prove in Theorem & below result involving the regret at iteration K of the algorithm instead of the regret after T function evaluations. As T S K(Dp 1), Theorem B directly implies Theorem
M.
Consider
K Σ f(zx)- k=
RK
f(x))
Σ f(ax + agv) f(x-)) vEDx
which is an upper bound of the cumulative regret suffered by the algorithm at iteration K, since it accounts for all directions in D each round k, while necessarily all of them will be tested. Rg can be bounded as follows.
Theorem 3. Under Assumptions and B
Rx S (Sp + 110++1[[ ã 1 go (f(xo) - (xxx) + plav)) (1++ + 3)
(1xo) f(x,)
(VV saB Bob)]
B a
p(ao)
where 1) := f a nD (c G)
Proof.
We decompose the regret as
K
Rk =
Σ
f(xx) =(xx) + Σ f(x + +xv) f(xxa)
0=0
VED
[(xx) -((x)) + Σ
f(rk + axv) f(xx) + f(xx) - (sxw)
VED
K
K
(D)+1)((((*)) - ((x+)))
+
f(z + +..0) ((x))
==
WED
ky
k
(DI+1)(((Ix) - f(x.))) +
Σ
f(x + axv) f(xx)
k=0
FED
(LI+1)(f((z) f(z.)))
Σ
Σ weD
f(x + axv) f((x)
(4)
k=ky
k=
18

---

Published in Transactions on Machine Learning Research (04/2024)
where ky is the iteration of the first unsuccessful iteration. The third incquality provides decomposition of the regret in a first term that involves the suboptimality of the iterate, and second term that involves the difference between values of f at the iterate and at the trial points. As is usual for direct search algorithm, the behavior of the algorithm before the first unsuccessful iteration has to be studied separately, which explains the use of the decomposition of the fourth inequality. We bound the regret due to the rounds preceding ky by:
Lemma 5. The regret due to the rounds preceding 2 is bounded by
Ky
Σ (()++))f(ax)-f(a))
Σ
E + axe) f(xx)) S Sr
where we denote by ky is the index of the first unsuccessful iteration and by C f(zo)-f(m.) (If(zo) fxx.) + V f + saa) cogg
Proof. As until k [(xx) S (20) and ar ao. it holds that
ky
by
(ID++)(f((z)) - f(z)))) +
Σ f(æx + aa.)) - f(zx)
k=
k=
ky
(1)+))(f(2))- -
V [V(()x)laa + +Ba
k=n
WED
L Vf(xx)) lao + +Bad)
by ((F)+1((f(z)) +
8 f(xo) f(x+) (D)+1)(f(E)) f(x.) ffxx))
v [f(z))llao Bag))
cag
C1,
where Lemma M is used for the second incquality and the third inequality comes from Lomma The first inequality results from the following property of convex and 3-smooth functions: f(y) - (())) S (x() v) S (=)) (x +/l++ yl? applied iy + ag and Fk.
Lemma 6. After ky,
K Σ k=
f(xx + app) - f(xx) S C2
where ky is the index of the first unsuccessful iteration and C2 = = B) (5(z)) f(x.) + p(ao))
Proof. We take k > ky. Using the property of convex and f-smooth functions that f(v)-f(x)) s ()) v) +) - v/l?, applied to og + age and Øk, as in Lemma 5, we get
f(r agu) f(æx) < au / [[([[
We note that is the index of an unsuccessful iteration,
[Vf( 1 3 az = 0k
c 2
L
by Lemma 2, if as < 1. If k is the index of successful iteration, we come back to the last unsuccessful iteration N', since
31 B av S
31
3
[V < [f(xx) 1s
k 2
K
2
19

---

Published in Transactions on Machine Learning Research (04/2024)
where the first incquality comes from Lemma M, and the third from the fact that a 2 Bay. Hence for any k > ky,
V nak.
nak
and
(1 - [(xx) S (1 + Blos.
Hence
K
K
fix + taxe)= - f(xx)= - Σ
(n + a)
k=
k=0
Consoquently,
K
Σ
f (æx + axd) - f((x)) S (m+ 8)= (3)
Σ plas)
k=
1
1 - 02 (f(zo) - f(xx)()))))))))){)))) + plao))
(1 + 8)
Lemma 7.
K
n? Σ (f(#x) (f(x)) f(x))) S ac 02 k=ky
(1- (f(x1) - f(x.) + +((w))) = C3
Proof. Take ky. Thanks the convexity of f,
f(xx) - f(x.)= S (f(xx) (xx (xx- xx)
where the second incquality stems from Equation which itself come from strong convexity. As in the proof of Lemma F we have for any k > ky,
[f(=n)]s nas
so that for any ky,
f(x)) S (n)² (am)²
(n)²
Thanks to Lemma B, we have 2k=o af < (f - f(x)) + plan))
uallt
f(xx) - f(xx) < 1 (1 (:1-) 02 (f(11) f(x,) + f(xx)+ Cs.
a
Using the regret decomposition of Equation together with Lemmas E. R and completes the proof of Theorem 3
20

---

Published in Transactions on Machine Learning Research (04/2024)
C Noisy and unconstrained set-up
Before considering the constrained sctting, we analyze the algorithms described in Scction Ø (Algorithms 2 and f when there are no constraints, that is, D IRd.
C.1 Presentation of the main Result
Theorem 4. Assume that is lower bounded and upper bounded on R so that there exits U, f(x)-((x.) I U, Va R Also assume that the region X' = {z E R² f(x) < f(zo)} is convex and that f is a-strongly convex and 3-smooth on X. Let Ry be the cumulative regret on the first evaluations of f made by FDS- Plan. Set å = -/333 Then
E[RT] (1og(())2/31213))
This regret bound is also valid for FDS-Seq under the same Assumptions, with å T-10/T/2. In the following, we give proof of the regret bound for FDS-Plan. Note that Sections CK and C. refer to FDS- Plan, and Section t deals with FDS-Seq.
The regularity assumption Theorem E1 requuies that f bounded and satisfies local version of Assumption D. The initial point in should not be chosen too far from x², nor should ag be too large. This assumption is not unreasonable, since for every zg and ag, it is naturally satisfied by bounded and strictly convex functions in 8² for some choice of a and B. We stress that under the alternative assumption the same kind of regret bound could still be proved, but with a smaller choice of 8, resulting in higher confidence bonuses and the multiplication of the regret by some constant factor. Indeed, in this case, estimating f incorrectly at each round can lead to a trajectory that always deviates from x", which highly detrimental to the regret rate; meanwhile, under the assumption required by Theorem H. is bounded by U, so that deviating from x contributes to the regret by at most UT.
In the following, we will use the following additional notation.
Notation. We define uk to be
arg max,eD, f(*)) f(x - agv) agp) iteration l is unsuccessful the chosen direction otherwise.
Uk: =
C.2
Intermediate results
Lemma 8. We call & the event.
Ex = flf(xx + axv) f(* c/uoa/ss/4(au)) Vo e Da U (0)).
The probability of &x is lower bounded by
P 1( 8(SD + 1)
where Fk-1 the a-field representing the history.
Proof. Let u e ID [0) f(xx + akv) -
- f(xx+avu) = ENie ej with e, independent Gaussian variables with
variance o² and we have
N Σ
1og(2/8)
20 log(2/5)
- plax)
S
20
32o²
with probability 1-6 8, when knowing N₁.- By union bound, IP (E 2- ((18((++1) where FR-1 the o-field representing the history.
The following lemma characterizes unsuccessful iterations and successes when &x occurs.
21

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 9. On Ek, if k is unsuccessful iteration then f(xx) f(r + ayou) 3c/2(ax)) and if is successful ileralion then f(xx)) f(r + 0g.4) 2 c/2(ax))
Lemma g implies that if E occurs for all k, then each iteration of the algorithm results in descent. Lemma 10. On T the algorithm is descent algorithm. In particular, F& E X, Wk {1... K). Lemma 11. If f satisfies the assumptions of Theorem and on DESKER then,
Ak' > k. Vf(aw)l [Vf(x
Proof. The proof of Lemma M applies verbatim thanks to Lemma M.
Lemma 12. If satisfies the assumptions of Theorem D and the iteration corresponds to an unsuccessful itcration then Ek:
[f((*)]ls 1 (5. (2ax + 3p(ax) = (3ax + +3aaa)
20x
2x
Proof. We reproduce the proof of Lemma by using Lemma
Since cDD) = mil max,en Tel|ea|| > there exists v E D such that
-s(m)) x: [++())]
Since the iteration is unsuccessful iteration, have (xxx [ ous0) ppp(a)) Gea thanks to Lemma g. Then
ka [ 1 2 a
exactly as in the proof of Lemma 2 which yields [V/(m>)]| 1 a + 2 plan)) = (fax + 3
Lemma 13. f satisfies the assumptions of Theorem and on E
K
plas) & 0z -xx.)+
Assume that EASK&R holds. Let k; be the index of the i-th successful iteration (i 1). Define ko --1 and a-1 ou, and aę 0, vk K for convenience. Define K, the number of successes until K. We rewrite 1 as E p(ax) and study first A 2 p(ox).
Thanks to the definition of the update on successful iteration and on unsuccessful ilerations,
Σ plas) < 1 0z p(ave)
1
exactly in the proof of Lemma g Since successes,
2 p(an) & f(xx)) f(ok, + aax) =((k)) - f (Ikk4)
we have
p(an.) S ((x)) (((xx).
2 i=1
Hence
K₁
Σ
p(ax) < - 02 (f(x1) - f(x.) + p(au))
k=
22

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 14. On & the first iteration that results in unsuccessful iteration occurs at round ky. salisfying:
k - f(20) - f(xx)
p(ao)
Before the first unsuccossful iteration, os = ao. So by Lemma
04 < ho - ky
- 2 =2" pp(ao).
By summing,
f( - f(xx,) 2 2 ksp(ao)
The left hand-side of this inequality is upper-bounded by f(z)) f(xx),, which suffices to conclude the proof. Lemma 15. If f satisfies the assumptions of Theorem f and on E for any after the first unsuccessful itcration,
[f(()>]] 7oak.
where we denote by 2ax (3c + 3).
Proof. For unsuccessful iterations,
[
(3c + 3)
2k
thanks to Lemma 12 If k is the index of a successful iteration, we can come back to the last unsuccessful
iteration N', since
2 |
8 (3c + May S (3c + () (aa) a 2n
$ 1
[
a
a 2k
where the first inequality comes from Lemma D. the second from Lemma that 0% 2 8ag.
P and the third from the fact
C.3 Regret Analysis of FDS-Plan
Lemma 16. If f satisfies the assumptions of Theorem and on n
2/3
K
Rx - Calog(2/6) + C. log(2/8)
Σ
No
C₁ 22 Clap C (Sp 11
where
1/3
Cr = (Sp
(f()))
( + 1/2 + +)
Proof. In the following we study the case where & holds true. As in the deterministic case, decompose the regret
kr
Rx
f(xx) No. f(zx)) - (xx)+ + Σ f(zx + axv) - ((xa)
k=0
VED
f(Ix) - f(z.) Σ f(xx awv) f(x.))
+
No
k=ky
23

---

Published in Transactions on Machine Learning Research (04/2024)
We start by dealing with the cumulative regret before ky. We write
by
(((x)) ((x,)+ + Σ
No
f(x + ta.u) - f(xx))
k=
RED
hr
No
f(xx)- - -f(x,) ((x+)++ + Σ
f(zz + axx) - f((x))
k=
DED
ky
32
6² 40
'log(2/6)
Σ
f(xx) - f(x,)= + E S(s + axx)) - f(xx))
kmm
EEB
32
-4 'log(2/8) x 2C1
S 22
90
C. log(2/6),
where the last inequality obtained exactly as in the proof of Lemma E with the help of Lemma instead of Lemma H. By using the above incquality and the decomposition of the regret, we get
Rx - C4 log(2/0)
K
Σ
No
f(xx)) ((xx)-f(x.)) + Σ f(xx + tav) - f(z.))
k k=ky
NED
K
<
N
- f(xx)) (fxx) + Σ
f((xx)
f(Xx + awv) - f(zn) + f(zx) f(x.)
k k=ky
MED
K
<
N
(5++1)(f(ze)) - f(xx))(++))))))){())))))))))ff + Σ
f(xx + a f((x))
k=kı
VED
K
Σ No (1IVF((Es)) + BO
$ (Sp + 1)
where C4 32 a + 1). The fourth inequality comes from the regularity assumptions required for
Theorem 2 together with Lemma I. We use Lemma IR to get that for any lo > ky,
[f 7/0k
Then
[(aaa) + But
-2 + n2a Bax
a
We get
K Σ
K
No
1 (1
S Co log(2/8)
Σ k=ky
(an) -2
k=ky
S Co log(2/8)
(ar))
where Co = (3:12 + + B) 22. Consoquently
Rx S log(6/0) log(((20)
Σ (ax)
The number of function evaluations is defined as
K 32 log(//2))
N
Σ
k
k=0
24

---

Published in Transactions on Machine Learning Research (04/2024)
Thanks to Lemma IK
2 Σ (ax)² S d(1 - 02)
(f(x1) - f(x+) + p(oo))
k=0
By Hölder's inequality, we get
K
(ak)
2
(ax)
22/3
(ark)
-2/3-2
k=
k=0
1/3
K
2/3
Σ (ook
2/3x3
Σ
(ax)
8/3x3/2
1/3
K
2/3
(ox))
Σ
(ax))
k=0
k=
And thus
Rx C4 (2g(2/6)
1/3
K
2/3
(f(x)) - ffx.)) + plao)
$ C. (og(1/))
N
c(1 - 02)
8log(2/8)
k=1
K
2/3
$ CC
Nk:
log (2/))
k=1
2/3
Cs (og(2//1))
Σ
Nk
where C3 = (Sp + 1)C6
32 (I- (f(x1) - f(x.) + p(ao)))
c
Proof. of Theorem We note Kr the last round reached by the algorithm with T evaluations. Lemma Itr proves that on &
2/3
RKr (ggg + Css
log (
(8D 1)
Thanks to Lemma S
P K
cC
P (E < (Sp + 11) Σ
T T-4/33 1/3 12 S (Sp + 1/7
(5)
when taking 8 = T 4/3, since Kr < T. Hence,
E[RT] < 4 3
C4 log(27) + 3 (Sb +1)
4
2/3
Cs 2/3 + (Sn + 1)UT2/3
= O(log 2/33)
25

---

Published in Transactions on Machine Learning Research (04/2024)
C.4 Regret Analysis of FDS-Seq
Instead of considering & as in the previous section, need to consider & = {(((x)) s(x + cn.Tk) V MM M 3c/2(ax) and is an unsuccessful iteration) or (k is a suecessful iteration and f(xx) - f(æx + ox.uk) c/2(ax) }). Instead of Lemma we prove the following result.
Lemma 17. The probability of &g is lower bounded by
P(E))F-1)21 8 N (II|+1),
where FR-1 the a-field representing the history.
Proof. Fix V D. First assume that f(*x) fox + axv) + 3322p(ox). In particular, f(zz) > f(rx aga) + p(ax). We denote no,x and n the values of no, and ne,k at the end of the while loop of FDS-Seq. Observe that
TP (EL FR-1, 1. = nT No)
21 5% (ID++1).
Hence only need to focus the case when the first part of Condition 0 is first satisfied. In this case, knowing " Ni the probability that fig. (xx) < fmg, (xx + agv) + p(ax) when the first row of Condition
M is first satisfied is bounded follows. We have
P f(xx) -Sug (Ixx) (f(xx aau) Sug, (otk aku))
v 20 log(1/6)
FRs no S..
Since ((*x > (1v + agu) p(ac);
f(xx) - fog, (xx) (f(x + axp) Fuz, (Ix + ayvl)
2 -p(a)) Sug, (xx)) + fnz, + axv)
So that the above deviation bound results in:
PP
Jng, (Ix) - fnz,e (xx + axx) - p((aw) S
2222 log(1/0)
Frs nō. no
nT,w
Finally, we apply a union bound. Since no.a and nh both belong to [0, N&) and cannol be simultaneously equal to N&:
P Jnj (IN) Ini, (ox + (av) plau)
20 log(1/5) -V00)1
Fk. not(no, = = No)) < < - 1)8.
no,K
n
This amounts to bound of the probability of k being unsuccessful iteration and thus of E when the first part of condition M is satisfied. Summing with the probability of & in the other case, we obtain P (()())) 2 N25.
26

---

Published in Transactions on Machine Learning Research (04/2024)
The case f(xx) > f( + agu) + 3322p(as) can be treated in the exact same way.
To adapt the proof of Theorem to FDS-Seq (with different choice of TT-10//) it suffices replace Equation by
T
Kr
S (SD + 1)
Σ
P
S (Sb +1) Σ
N
NēT-10/3
A=1
k=1
T
S (Sp + 1)
Σ
T 2 10/3 12 < (Sp + 1/7
k=1
The regret is hence
B - 3
10
C4 log(2T)
+
10
(Sp + 1
1
2/3
Cs (g + (Sp 13UT2/3
3
((log 2/2333)33)
D Noisy and Constrained Set-Up
In this section analyze the behavior of the algorithms in the presence of linear constraints. The complexity of feasible direct search with linear constraints in the noiseless case has been studied by Gratton et al (2019). In this paper, instead of studying the speed at which the gradient converges to 0 as is usual in the unconstrained case, the authors study the convergence of lower bound of the gradient x(x) := max || - V to Indeed, the convergence of the gradient to might be unachievable when the optimum lies on the boundaries, but X(x) is equal to if and only if æ is optimal. The paper proves that the first iteration K, which X(xx) is smaller than is of the order of c=2 like in the unconstrained case.
In the following, we denote by U the global upper bound of [xx J (xx) the domain.
D.1 Intermediate Results
We recall that & denotes the event
& = (If + axp) - f(x + anv)ls )/4(au)²), Ve e (U)
Lemmas
g III are left unchanged by the transition to constrained domains. A version of Lemma 3.4. of reads
Gratioon all 201
Lemma 18. On E and if f satisfies Assumption D. then the following holds: if the k-th iteration is unsuccessful, then
[5+1 Bg
B
os + 3p(ax)
x(xx) <
= L2aRs
2k
Mhuin
280
where Timin == X(N) where N is the set of all possible upprocimale normal cones N(I,a), VED, a Ed.
Proof. It straightforward to prove
Pr(s (-V((x))) 1 (goz 3p(ax) 200
2x (Bax 3ca
with the same elements in the proof Lemma II by noticing that ID contains GE, that generates T(æk, ak). To prove the bound x(xx); we the Moreau decompasitionnssttiing that any vector IRd can be
27

---

Published in Transactions on Machine Learning Research (04/2024)
decomposed as Pr.lu] + PNulo] with N₁ (Ix, as) and Pr, PN₂ [t] 0, and write
X(xx)=
max a+VED, S1
(Pr.- - + (Pn.
PN. PMl-
(v" T ( + PN. [0] -
max
max 24 1M
[ Pm [-V
(6)
The first term of the right hand side of Equation is bounded in the following way
1 (Bax. + 3ca
PT( (-V
2x
consequently.
Lemma 19 (Proposition B.1 of (Lewis &r Torczon, 2000 ) Let x E D and a > 0. Then, for any vector v such that a + u D, one has
[ /u]ls
Mnii
This in lurn provides bound of the second term of the right hand side of Equation E
|| PNx, Px.((V((>))
By.
quin
which suffices to conclude the proof.
Lemma 20. Assume that E holds, and satisfies Assumption M. Set O. Let h denote the mapping from to
22L3
log( (002)
2U EiE
M(e) = O01
E2,
log 1/0)
oo
0g
where E₁ =(2 (2L.U
and Eg log( 20022
Denote by k(c) the first iteration of the algorithm where
col
log(1/0)
x(xx) Se. e. h(e) < K, then
k(e) < h(e).
The proof is mere adaptation of the proof of Theorem 1 of (Gratton at. 20R with different constants (we use Lemma I8 and [3]
Lemma 21. If f satisfies Assumption
allox - x.115 x(xx).
Proof.
allra x.l1s f(x) f(xx) | x.
-V((x) - Ixx) x(xx), 1|r xall
<
by definition of x(
Lemma 22. Tf f satisfies Assumplion M and if xx is in the interior of D and the algorithm achicves descent at each iteration, then
(
3/2
Vk' k. (x(
Ix(xx)]l-
Proof. Like in the proof of Lemma M. we get
a al| 1|5
[xx))
28

---

Published in Transactions on Machine Learning Research (04/2024)
Hence,
B x. s
B
B|
V((kk) f(x+)
(s(xk) (xx+)
va
Va
B
g
x((x)²
BiK -rx)²
Va
Va
2 3/2
x(*x),
where the first incquality comes from the strong convexity, and the second comes from the fact that the algorithm is descent, the third one comes from Lemma 21
Now let = arg maX++ ||l|| - - f(xx).
- -- VV(ww - v + to (V( vf(aa)) 0| z.ll,
because vf(x.) = O. This concludes the proof.
D.2 Regret Analysis when the Optimum in the interior of
Let us assume that 2+ is in the interior of D. Let us denote by A the distance from 2, to the closest boundary, and by r A/4.
Lemma 23. If x(x)= S ar then || x.115r. r.
Tf |a x. 221121 then xx(x) thanks to Lemma 21
Lemma 24. For any k 2 k (a/3)8/2 ar). | -x.11...
Thanks to Lemma I1 after (1a/3)5/2rr) iterations, x(xx) S ar. And thanks to the previous lemma, we thus have || r.
Lemma 25. Set ki the inder of the first successful iteration following ((a/8))/2 ar) where a S A/2. After iteration k,, T(z,, 04) spons all directions in Rd so that the instantaneous regret is the same as that of the algoritlom in the unconstruined case with inétial point In, and initial step-size ak,- The iteration of this first successful iteration comes before k; :=:= k (aa/3)3/ 3/2 ar) + l)
log 1/0
Proof. If k is successful iteration 2r A/(2), since || - r and || - -x.1< r. And if & is an unsuccessful iteration, it comes after one of those successes and a sequence of unsuccossful itcrations, which yields a < (2)..
Lemma 26. On E
K
2/3
Rx < Cy 1o + 1ogg
N
where C7 = (Sp + 1)U 32
clgg (1/0)-1
and
a
log( On/ A)
BA2
C = Ej
3
ar
+ E2 +
log 1/0
+
29

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. In the proof of Lemma Itd. isolated the steps preceding the first unsuccessful iteration. Similarly here, we treat the iterations before the first unsuccessful iteration after ki, denoted by Ky, separately from other iterations.
Rx
- (xx))) -
+
N₂
Σ vEDx
[ar + taso) - [(x.))
k=
A=U
(Na(BB))))(f(e)) -f fxx)))) +
Σ N&
Σ ADED
f(zx + +auu) s(oa))
k=
Because f(x) f(x.) is bounded by U,
4 (x(x(x)) - f(x))) +
Kj
Nk Σ f(z + awe) ((x.))
(iDgl+))NuU.
k=
By rewriting Nk.
N2 (D& +1)NNU
KG
32 log (1/() c²ar
Σ k=
(DD +1)U
A=
32 log( /8) [D+|+1)U
c² CagaaR
k=
32 log (1/ 1/6) (1/0)-48; < (Sp + 1)U
2ad
(1/6) 1
Also on E
Kg S ki + f(x,,) f(xx)
B4 on
a
3/2
log(oo/A A) +
BA2
k; +
k
ar
+
00
log 1/0
where the first inequality comes from the same argument used to prove Lemma B. the second inequality comes from the smoothness of f and the third one comes from the definition of kj
On E
(
3/2 a
3/2
-2
a
ar <
Ei
ar
+ Eg.
with E1, Eg defined in (Gration of all 201). Kg. On &
Finally, we focus on the part of the regret accumulated before
Σ
Σ No Σ
[(x + ano) - S (xxx)
km
k k-
WEDD
K
2/3
- Cs log(2/8)
N₂.
by following exactly the same steps as those needed to bound the regret in the unconstrained case.
30

---

Published in Transactions on Machine Learning Research (04/2024)
Theorem 2. Under Assumptions D. and B and if 2, int(DD), the cumulative regret Ry of FDS-Plan (respectively FDS-Seg) ofter the first T evaluations of J, satisfies
[[ O (11g(())3/8711))
for the choice 8 = T (respectively = T-10/3 for FDS-Seg).
Proof. for FDS-Plan. We denote by Kr the last round reached by the algorithm with T evaluations.. Lemma Mi proves that on the event &kgK,
K
Rx S Cy (og(20)(1/))) 40s + Cs Co
N₂
Thanks to Lemma E
T
P (UKn oc) S (Sp + 1)P (U s (1x]+1)
Σ 1=1
T
4/3 1/18/25 (Sb + 1/3
since Kr & T. Hence,
4 B[Rr] C1(100) log(2T) +
4
2/3
Os (ogg
3
([Dx|+1)
((Sb + +1))UT2/3
= =(((ooT)))/31)
Adaptation of the proof for FDS-Seq The way of adapting the proof of FDS-Plan to the case of FDS-Seq of Section Cdd applies verbatim.
E Details on the implementation of HOO in Section 2.2
To implement HOO in the simulations of Section 202. the tree of partitions that we used is built. in the following way. We set the parameter of HOO as suggested by Bubbek al (20IT) to 2-2/d, A binary tree of depth H log(1/T) of partitions of [0, 1jd obtained by recursively halving the cells at each depth h of 2 llgile
the tree along dimension h (mod 2). At depth h, this approach yields a partition formod by rectangular colls represented by their lower left corner b., Then, in order remove unwanted cells, we traverse the tree, starting from the leaves, and remove every cell having an empty intersection with the domain. Due to the geometry of the simplex, knowing if a cell intersects the domain boils down to checking if its representation la, b.] belongs to it. When the algorithm selects cell (h, i) at time t, the representation of that cell is chosen sampling point. In the simulation, the smoothness parameter Vn of HOO is set to 16.
F Additional Experiments
Here, as in Section 2 focus the case in which there are three resources (d = 2). The loss functions log(1+72) for resources and are of the same form as in Section 20 and wy wx(x)) - Tog[I+>] with ? = 2, t = 1, = 0.3, but now the second resource is associated to wz(x) = 0.1 æ. This choice of reward functions results in an optimal choice whose second component is zero. We set. the horizon to T = 100, 000 and use Gaussian noise with standard deviation a = 0.1.
We show the trajectories of FDS-Plan and FDS-Seq in Figure R. Notice that the trajectories do not change drastically compared to those of Section 2 which seems to indicate that the location of the optimal
31

---

Published in Transactions on Machine Learning Research (04/2024)
allocation the border of the feasible set is not problem in practice. We complement these plots with regret plots (Figure El of all the algorithms detailed in Section 2a run first the environment described in this same section and second on the environment described above with the optimum on the border of the simplex. Once again, this seems to show that the optimum lying in the border not an issue practice. Incidentally, this last. plot also shows that, as expected, UCB should be the preferred algorithm dimension d 2, as simpler and gives excellent results.
10"
10a
10a
10a
102
10*
(a) FDS-Plan
(b)
FDS-Seq
Figure 3: Single trajectories with the optimum on the border
20000
PDS-Plun
PDS-PPas
FDS-Skg
FMS-8eg
17500
B100
[OO
UCB
CCB
GD
GD
poluts
Begies
10000
10000
7600
5000
5000
2500
100000
Time
Time
Optimum the interior
(b) Optimum the border
Figure 4: Regret plots in dimension d =
32


Reviews:
[{"review_id": "3grZO2Odi4", "reviewer": "Reviewer_GNrJ", "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:\nThe paper is study an interesting problem providing efficient solutions. Moreover, the paper shows that other algorithms (that were designed for similar problems) are less effective also from a practical point of view.\n\nWeakness: \nThe work is rather incremental, and it relies heavily on techniques introduced by previous work.\nThe setting under study is not clearly presented. While the motivating application is budget allocation, the setting is quite more general and should be introduced in its generality.", "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 studies direct search methods for blind resource allocation. In particular, the authors study a repeated problem in which at each time step an agent chooses a feasible allocation and then observe a stochastic reward. This framework models the problem of allocating budget to advertising campaigns, but it is applicable to more general problems. The paper provides a direct search method that provides regret $T^{2/3}$ under linear constraint. Finally, the paper provides a more practical algorithm with better empirical performances.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I suggest to better clarify the generality of the model and that budget allocation is only an (interesting and important) application.", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LJkokeyjM1", "reviewer": "Reviewer_7z8h", "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": "The paper investigates an interesting problem, which is of high relevant to TMLR. I believe it renders attractive to audience from both optimization and (bandit) learning communities. Further, as the studied resource allocation problem admits a generic form, despite its framing for the setting of programmatic advertising optimization, I believe the algorithms presented in the paper will find use in other application areas in engineering where similar resource allocation problems would naturally emerge. \n\nThe paper is written very well, despite the typos I spotted and some places that could be further improved; see below. Further, it has a clear presentation and is overall a nice read. A positive aspect here is to have included in the introduction a well-elaborated motivating example, which fits well the importance of the setting and the gap in the literature. \n\nIn terms of technical strengths, one, in my view, is to have considered a regret definition in terms of function evaluations, as opposed to the classical ones in the literature. Also, another one is the consideration that only feasible points could be queried. These make the presented algorithms more faithful to practical scenarios. \n\nThe two proposed algorithms are designed and analyzed under a set of assumptions on the objective function (Assumption 1) commonly considered in the most of literature on bandit convex optimization. A positive aspect of them is that the assumptions, unless I miss something, are only there to ensure the reported regret bounds, and the algorithms do not rely on the knowledge of strong convexity or smoothness moduli. This might be worth highlighting. Further, it appears that the algorithms could be still used even if some of assumptions (e.g., strong convexity) are violated; namely, even if the analysis could be open under such relaxations, the empirical performance could nonetheless be sound. However, this is neither investigated nor discussed in the paper. \n\nOne drawback here is that when comparing to the regret bounds of approaches such as UCB + discretization, it is not highlighted that they may not rely on such assumptions. It appears to me that the proposal by Combes and Proutiere (2014), although suffering from a larger regret when the dimension $d$ grows, would rely on arguably milder assumptions of (mostly) implying unimodality of the decision space. I urge the authors to precisely discuss this matter in the paper. \n\nOther major drawbacks and comments are listed below: \n\n1. It is assumed that the optimal allocation resides in the interior of the feasible sets. To what extent is this assumption restrictive in practice? I wonder whether relaxing this assumption would lead to bad empirical performance or maybe it is there merely for the regret analysis. \n\n2. The reported regret bounds do not elaborate well on the dependence of the bound on relevant parameters of interest, especially $a$, $\\beta$, $\\sigma$ etc. Also, I found it difficult to get these from the more detailed bounds in the appendix. I urge the authors to further elaborate on this and potentially discuss such dependence. I understand that the final bound could be rather ugly, as a function of all involved quantities. Yet, discussing such dependencies would be very helpful. \n\n3. Continuing the previous point, a reader might be curious on how the derived regret bounds stand with respect to other bounds in terms of dependence on $\\beta$ and $a$ (of course to the extent that comparison would make sense). \n\n4. I appreciate the comparison made with UCB in some respects. However, in the end, it is not clear for the cases of small $d$ (say, at most 4) which of UCB or FDS-Seq is advised theoretically and empirically. In the case of $d=2$, UCB achieves a better regret bound than FDS variants. Also, the experimental result reported in Section 4 suggests that it could be a viable solution in small $d$. \n\n5. While most of the paper is written very well, the author(s) have been less careful in writing Subsection 3.2. I spotted many notation inconsistencies there and some typos. Below I listed what I spotted, but I’d strongly recommend the authors to carefully revise this part. \n\n6. Some details of “Illustration” (Section 2.2) could be moved to the appendix (e.g., the long paragraph on how HOO is adapted). This could be more relevant if some space in the main text is needed to accommodate the requested revisions. \n\nFurther detailed comments:\n\n- In algorithms it is mentioned $\\theta \\leq 1$ whereas in the text $\\theta<1$ required.  \n\n- p. 5: $D_k$ must be $\\mathbb D_k$\n\n- p. 6: $\\gamma$ is used both as a parameter in $w_i(x)$ and to denote a growth factor. Although clear, consider using different symbols. \n\n- p. 6: The statement “and the edges to linear paths along which …” appears which unclear to me. Could you revise it and ensure, e.g., a verb is not missing?\n\n- p. 8: FDS-Test => FDS-Seq\n\n- p. 8: In Theorem 1, it appears that a right parenthesis is missing in the first term. Please check it carefully. Also, it looks like plugging-in the definition of $\\rho$ (and some simplification) could make the bound more interpretable. \n\n- p. 9: In “the gap $f(x_k) – f(x_k - \\alpha_k v)$”, did you mean $f(x_k) – f(x_k +\\alpha_k v)$?\n\n- Assumption 4: In view of the $\\beta$-smooth assumption, assuming a bound on $\\nabla f$ appears redundant to me, if we have a bounded set $\\mathcal D$. \n\n- p. 10: In “This property is not sufficient in the unconstrained case”, did you mean “the constrained case”?\n\n- Why “FDS-Plan and gradient descent show roughly the same regret”?\n\n- Some details appear missing in relation to the experimental results. E.g., what is it the error bars indicate. \n\n- Theorem 4 in appendix: You assume that the region where $f(x) < f(x_0)$ is convex. But isn’t it simply an implication of convexity of $f$? I am referring to the property that all $c$-level sets of a convex function $f$ are convex sets. \n\nPotential Typos/Grammar Mistakes: \n\n- p. 3: of and increased regret rate => … an increased …\n \n- p. 3: The algorithm that they propose relies on => The algorithms they propose rely on (Note: you are referring to two works, hence algorithms.)\n\n- p. 3: Flaxman et al. (2004) later considers => Remove “later” as the preceding sentence cites a work from 2017. \n\n- p. 4: allows to understand => allows for understanding OR allows us to understand\n\n- p. 5: we replace … by => … with\n\n- p. 6: In “Finally, … of FDS-Plan (respectively FDS-Seq) occurred are …”, it seems that “and” could be used in lieu of “respectively”. \n\n- p. 6: two algorithm => two algorithms \n\n- p. 9, Lemma 2: Assumption 1 and 2 => Assumptions \n\n- p. 9, Lemma 2: a unsuccessful iteration then => an unsuccessful iteration, then\n\n- p. 10: i-th => $i$-th\n\n- p. 10: “… are $x$ are denoted …”: Please carefully check the sentence. \n\n- p. 10, Assumption 5, Lemma 10 (and potentially elsewhere): “{” and “}” are missing.\n\n- p. 10: in the following, => in the following. \n\n- p. 9 (and elsewhere): $x_*$ => $x_\\star$ (to be consistent with earlier definitions). \n\n- p. 11: $R^2$ => $\\mathbb R^2$\n\n- p. 11: $\\mathbb R_d$ => $\\mathbb R^d$\n\n- p. 11: What is $G_k$? What is $\\Pi$ when you wrote “($2\\Pi/3$ apart)”?\n\n- p. 12: … they rely on => it relies on\n\n- p. 20: Make correction to $\\hat f(x_k\\alpha_kv)$.  \n\n- p. 18, Lemma 5: extra parentheses in the definition of $C_1$.\n\n- p. 22, Lemma 16: $log$ => $\\log$\n\n- p. 24: Carefully check the exponent $-32/3\\times 3/2$", "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 studies a problem called blind resource allocation problem, which is an instance of convex optimization with linear constraints under bandit feedback and with noisy function evaluations. Specifically, this a sequential decision-making problem where the learner receives the function value corresponding to the queried point but corrupted by a zero-mean sub-gaussian noise (under the conditional independence assumption commonly considered in the literature), where for concreteness the noise is taken to by Gaussian. The learner has prior knowledge on the variance of the noise, but no access to the gradient information. The performance measure is a notion of regret that is defined in terms of function evaluations, unlike those of existing literature which is defined in terms of decision rounds. The paper presents two algorithms for this problem, FDS-Plan and FDS-Seq. These algorithms are variants of the direct search method, which are derivative-free methods from the optimization literature for similar problems. The first algorithm relies on pre-computed numbers of evaluations whereas the second decides these numbers adaptively. Both algorithms are analyzed under the assumption of strong-convexity and smoothness of the underlying objective function, and are shown to enjoy a regret growing as $T^{2/3}$ (in order, and ignoring logarithmic factors) after $T$ many evaluation rounds. The efficacy of the two algorithms over existing approaches (e.g., Gradient Descent with one/two-point feedback, HOO, and UCB) are demonstrated using numerical experiments as well as some illustrations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the comments above.", "broader_impact_concerns": "I believe there is no concern associated to the developments and results reported in the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iyOrmXbnns", "reviewer": "Reviewer_CKgM", "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": "The formulation considered in the paper seems to be new and different from the existing ones in the literature. Yet I have the following concerns:\n\n1. The formulation seems niche in that there is a rich literature for both online bandit convex optimization and online resource allocation. The paper considers a formulation combining the two settings. I am not quite clearly motivated as to why this formulation matters: \n\n- Resource constraints are imposed individually for each time step. This is equivalent to restricting each $x_t$ to belong to some set $\\mathcal{S}$ for all the $t$. First, I don't know how much this changes the nature of the online bandit convex optimization problem, and more specifically, why the existing online bandit convex optimization algorithms cannot be applied here. Second, the more common resource constraints seem to be $x_1+....+x_T\\le B$, and this type of cumulative constraint will significantly differentiate from the online bandits optimization literature. To me, the cumulative budget constraint more naturally reflects the ads problem where the budget is the bidding budget for each advertiser. \n\n- There is a lack of justification for why the cost function $f$ has this additive form. \n\n2. The technical contribution. The analysis seems very standard to me. I wonder what are the technical challenges of the analysis. And as mentioned in the paper, \"in the absence of a lower bound, the optimality of such a regret rate is unsure.\" It is hard to appreciate the optimality of the algorithm.\n\n3. The scalability with the dimension $d$. Assumption 2 may result in an undesirable dependence for the PSS set $D$ on the dimension $d$. Authors should consider to derive some bound on the relationship between the cardinality of $D$, the parameter $\\kappa$, and the dimension $d$. For the numerical experiments, it is more of within a low-dimensional regime. \n\nMinor comments:\n\n- Seems no definition for the abbreviation PSS.\n- $\\theta<1$ instead of $\\theta\\le1$  in Algorithm 1.", "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 considers the problem of online bandits/zeroth order optimization under resource constraints. It develops three natural algorithms and derives the regret bound accordingly.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above for questions.", "broader_impact_concerns": "NaN.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission delves into the domain of programmatic advertising optimization, focusing on the sequential budget allocation across various resources under linear constraints and noisy evaluations. The paper proposes novel direct search algorithms that are analyzed for regret in both deterministic and noisy conditions. It presents an extensive theoretical analysis along with empirical evaluations to demonstrate the efficacy of the proposed methods.

The paper's strengths include its innovative algorithmic solutions for resource allocation challenges, thorough theoretical insights, and convincing empirical evidence. On the other hand, two of the reviewers have both questioned the originality of the algorithm design and its analytical aspects. Additionally, the reviewers have noted the lack of convincing motivation behind some modeling choices and questioned the scalability and practical applicability of the proposed methods. Therefore, I suggest that the authors revise their paper to highlight the novelty of their algorithms and their practical value.
Decision: Accept (poster)