Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
Authors: Yuya Hikima
Hiroshi Sawada
Akinori Fujino
Venue: ICML 2025 poster (2025)
Keywords: Zeroth-order method
performative prediction
decision-dependent distribution
guided evolutionary strategy
Primary area: optimization->zeroorder_and_blackbox_optimization
TL;DR: Improved zeroth-order methods for stochastic non-convex optimization problems with decision-dependent distributions

Abstract: In this study, we tackle an optimization problem with a known function and an unknown decision-dependent distribution, which arises in a variety of applications and is often referred to as a performative prediction problem.
To solve the problem, several zeroth-order methods have been developed because the gradient of the objective function cannot be obtained explicitly due to the unknown distribution.
Although these methods have theoretical convergence, they cannot utilize the information on the known function, which limits their efficiency in reducing the objective value.
To overcome this issue, we propose new zeroth-order methods that generate effective update directions by utilizing information on the known function.
As theoretical results, we show the convergence of our methods to stationary points and provide the worst-case sample complexity analysis.
Our simulation experiments on multiple applications show that our methods output solutions with lower objective values than the existing zeroth-order methods do.

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
Yuya Hikima' Hiroshi Sawada
Akinori Fujino
Abstract
distribution ((x) depends on decision vector and is un- known. This problem appears in wide range of applica- tions. For example, in pricing applications, seller aims to optimize the prices x of products and services for their revenue, considering the price-dependent distribution ((æ)) of stochastic demand (Ray al., 2022; Hikima & Takeda, 2025b). In strategic classification in financial practices, lender aims to train the parameter of a classifier for finding good customers, considering the parameler-depencee distribution D(x), which is caused by customers who may react to the deployed classifier (Levanon & Rosenfeld, 2021; Liu et al., 2024a). Various studies (Perdomo et al., 2020; Mendler-Dünned et al., 2020; Chen et al., 2024) have ad- dressed problem (I). because of its importance in practical applications.
In this study, we tackle an optimization problem with a known function and an unknown decision- dependent distribution, which arises in a variety of applications and is often referred to as a perfor- mative prediction problem. To solve the problem, several zeroth-order methods have been devel- oped because the gradient of the objective func- tion cannot be obtained explicitly due to the un- known distribution. Although these methods have theoretical convergence, they cannot utilize the information on the known function, which limits their efficiency in reducing the objective value. To overcome this issue, we propose new zeroth-order methods that generate effective update directions by utilizing information on the known function. As theoretical results, we show the convergence of our methods to stationary points and provide the worst-case sample complexity analysis. Our simulation experiments on multiple applications show that methods output solutions with lower objective values than the existing zeroth-order methods do.
data
Since the gradient of the objective function is inaccessible as a result of the distribution D(x) being unknown, various zeroth-order methods have been proposed, which update the decision vector by some estimated gradient on the basis of function evaluation(s). For example, (Chen al., 2024; Hikima & Takeda, 2025b) proposed zeroth-order methods based on the following gradient estimator:
g 24 (f + wun, f(x pm. (2)) u.
where μ E RR20 is constant, Id is sampled from some distribution (e.g., the standard Gaussian distribution), & D(x pus) and g² D(x -uu). Not limited to the above, various studies (Ray et al., 2022: Liu et al., 2024a) proposed zeroth-order methods using different gradient estimators.
1. Introduction
In this study, we consider the following problem:
min 2ER4
F(x)= = (E- (f(x.
(1)
Although these existing zeroth-order methods are theoreti- cally valid for solving problem (1), they treat the function f as a black box and do not leverage its gradient informa- tion, which limits optimization efficiency. Specifically, an unbiased stochastic gradient of the objective function F in (I) can be written as follows (Liu et al., 2024b; Hikima & Takeda, 2025a):
where F: Rd R generally non-convex, / a given differentiable function, and ((x) an unknown distribu- tion of random variables & This formulation known as the performance prediction problem (Perdomo et al., 2020). The main feature of this problem is that the probability
'Communication Science Laboratories, NTT Corpora- tion. Kyoto, Japan. Correspondence to: Yuya Hikima www.ahiiinn@ntt.co....
Vaf f(z, E) log Pr(E x)) & ~~ D(z). (3)
Here, although we cannot obtain the second term since Pr(E x)) is unknown, we can calculate the first term, that is. f {). since is known. Thus, we can access partial information on the gradient of objective function F.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Depender Distributions
The fact that existing methods do not fully utilize the infor- mation leads slow convergence and increases the number of samples & ~ D(x)). Such an increase is undesirable in practice because a decision (x) must be deployed in real-world to obtain a sample & ~ (ax). For example, a decision maker must sell some products at prices æ to obtain sample demand & ~ ((z)).
the set of natural numbers. The gradient for a real-valued function f(x) w.E.I æ is denoted by V (ar) We let Ia be d-dimensional identity matrix and let .V Σ) be a Gaus- sian distribution with co-variance matrix E. We denote the set of x d positive definite matrices by Sd be the set {1, NN..
4++- Let [N]
In this work, we propose guided zeroth-order methods that integrate partial gradient information derived from the known structure of S. Inspired by (Maheswaranathan et al., 2019), our methods use the gradient estimator (2) with u ~ (O, Σ), where (0, Σ) is a normal distribution with a auriance-covariang matrix E E Rdxd The key to our methods is to incorporate partial gradient information in E in order to generate an updating direction u that tends de- crease the objective value. We design two interchangeable methods for obtaining partial gradient information. One
2. Related Work
2.1. Zeroth-Order Optimization Methods
Zeroth-order optimization methods have been proposed for solving optimization problems where gradient and Hessian information are either unavailable or computationally ex- pensive to calculate (Powell, 2006; Ghadimi & Lan, 2013;
Nesterov & Spokoiny, 2017; Ragonneau & Zhang, 2024). Recently, various studies have proposed zeroth-order meth- ods for solving problems with decision-dependent distri- butions (Ray et al., 2022; Liu et al., 2024a; Chen al., 2024; Hikima & Takeda, 2025b). (Chen et al., 2024) de- rived the conditions under which (1) can be reduced to a convex optimization problem and solved the reduced con- vex problem by using a zeroth-order method. (Hikima & Takeda, 2025b) proposed zeroth-order methods with one- point and two-point gradient estimators and derived the iteration and sample complexities for reaching stationary points. (Ray al., 2022: Liu et al., 2024a) proposed zeroth- order methods for (1) with time-varying decision dependent distributions. Although these studies effectively develop zeroth-order methods within their settings, they fail to lever- age the known structure of the function f. In this study, we propose new zeroth-order methods by using the information on f to generate updating directions.
method computes, as the information, the first term of (3) from new sample(s) 5 ~ D(æx) at the current iteration k. The other method approximates it from historical sample(s) E, ~ (ax)) in past iteration(s) i.
Our theoretical analysis shows that our methods converge to stationary points and provides the worst-case sample complexity, which represents the number of samples & D(x) needed to obtain a stationary point & such that BIIVF(()] e². In particular, we show that the worst- case sample complexity of our methods is 0(a%d4e-9) -9), where ((FDD()](((aa))
{) S o² for any æ e Rdd. Since the sample complexities of the existing methods are O(o2dãc-9) (Hikima& & Takeda, 2025b) and (G (Liu et al., 2024a), where G = suPz.c [f, E)), our meth- ods outperform them when G = w(d+) or G is unbounded. Note that even if f is a simple loss function such as squared error, G is unbounded. This improved order is achieved by employing tighter convergence analysis compared to (Hikima & Takeda, 2025b), which involves tuning algo- rithmic parameters such as mini-batch size and step size. Furthermore, the proposed zeroth-order methods incorpo- rate partial gradient information without making any as- sumptions about its correlation with the true gradient, and crucially, without deteriorating the convergence rate.
2.2. Other Methods of Solving Stochastic Problems with Decision- Distributions
Here, we list methods other than zeroth-order ones for (1).
Retraining methods (Perdomo et al., 2020; Mendler- Dünner et al., 2020; Roy et al., 2022; Mofakhami et al., 2023; Li & Wai, 2024; Khorsandi et al., 2024). Re- training methods update the decision vector without ac- counting for the distribution shift at each iteration. Specif- ically. repeated gradient descent (Perdomo et al., 2020) updates the decision vector such that xx+1 := pro mi (V (=x,, where is the feasible region and proje the Euclidean projection operator onto C. This method makes the decision vector converge a perfor- matively stable point Eps arg ming Eg-D( [f(x E) Subsequent studies have explored several directions, in- cluding variants of the above approach Siendler-Dünnee et al., 2020), a setting where the data distribution follows a Markov chain with a stpendee transition kernel (Roy et al., 2022), relaxed assumptions on the objective function
We conducted simulation experiments on multiple products pricing and strategic classification applications. The results show that our methods output solutions with lower objective values than the existing zeroth-order methods do.
Notation. Bold lowercase symbols (e.g.. x, y) denote vec- tors, and ||عا|| denotes the Euclidean norm of vector æ. Bold uppercase symbols (e.g., Σ) denote matrices, and || |Σ|| denotes the spectral norm of a matrix Σ. The inner product of the vectors x, y is denoted by x T y. Let Ry (R>u) be the set of positive (non-negative) real numbers. Let N be
2

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
(Mofakhami et al., 2023; Li & Wai, 2024), and improved convergence analyses (Khorsandi et al., 2024). However, these methods focus on obtaining performatively stable solu- tions and do not aim to (nor is capable of) finding stationary points, which may result in worse function values.
3. Proposed Method
Here, we describe our new gradient estimator in Section 3.1 and the algorithm using the gradient estimator in Section 3.2. Moreover, we describe an advanced algorithm that utilizes historical samples from past iterations in Section 3.3.
Stochastic first-order methods (Liu et al., 2024b; Hikima & Takeda, 2025a). These methods assume that Pr( 2) and V. Pr(( æ) are known and update the decision vector by using the unbiased stochastic gradient (3) of the objective function. However, these methods cannot be used for solving (1) with an unknown distribution (zx).
3.1. Our Gradient Estimator
We propose the following gradient estimator:
g u. u 5², == f(x + pu, ,u, - f(x pu,, ,,),
u.
2/1
(4)
where u ~ NO, Σ), 5 ~ D(x + ju)), E² D( r- and μ E Rzo- Here, we utilize partial information on the gradient set Σ, inspired by (Maheswaranathan et al., 2019). Specifically, we regard the following vector partial gradient information:
Performative gradient descent (Izzo et al., 2021). This method updates the iterates using an approximate gradient obtained by estimating V log Pr(E x) in the second term of (3). While this approach can find an optimal point rather than a performative stable point, it relies on several restric- tive assumptions. For example, they assume that the distri- bution can be written Pr(E x) p(g(a)), E), where the function is known and the intermediate parameter q can be approximately obtained through samples. They also assume that the objective function F' is convex. In contrast, our study suppose looser assumptions: the distribution ((x) is completely unknown and the objective function is generally nonconvex.
Σ 1=1
8
where 5 ~ D(x) for i 21, n). & approximates the expectation of the first term of the un- biased stochastic gradient (3) for the objective function F. ||]
This is because
Let h be the normalized vector of s, that is, h a if s # 0 and h = otherwise. Accordingly, we define Σ as follows:
α Σ = y la (1-
(6)
Distribution approximating approaches (Miller et al., 2021; Lin & Zrnic, 2024). These approaches estimate models of the distribution map D(-) and optimize prob- lem (1) by using the estimated distribution. While these approaches perform well when the distribution is approxi- mated accurately, they assume specific distributions or func- tions. For example, (Miller et al., 2021) assume that the distribution map is included in location-scale families, i.e., D(x) needs to satisfy & ~ D(x))= + & == Eo + Ax, where Eo is random variable independent of x and matrix A is constant. Moreover, they assume that is strongly con- vex. In this paper, we tackle the design of (more) generic methods for solving (I) without such specific assumptions.
where a E (0. 1]. Here, a is balance parameter that adjusts the weight of the partial gradient information.
Next, we present the property of our gradient estimator. First, let us define an important function, which is closely related to our gradient estimator.
Definition 3.1. We call the following function the aug- mented Gaussian smoothed function of F.
FT, == (u)N(( [F(x + ju))..
The function FE, serves as a smooth approximation of F. This is an extension of the Gaussian smoothed func- tion (Nesterov & Spokoiny, 2017; Iwakiri et al., 2022): if Σ la. function FN, is consistent with it. Throughout the paper, we assume that F, FT.)(()) is well-defined, that is, Eu-A(o, [| + [ru)]] < oo for any given E 12 deffiiee matrix Σ E S4 and x E Te..
Search optimization (Bergstra & Bengio, 2012; Frazier, 2018; Xue & Shen, 2020). Search optimization tech- niques, such as Bayesian optimization (Frazier, 2018), ran- dom search (Bergstra& & Bengio, 2012), and sparrow search algorithm (Xue& & Shen, 2020), aim find a global solution by iteratively evaluating objective values across the search space. When these methods are applied to our problem, they require a large number of samples& & ~ D(x) to obtain the objective values. Having to take such a large number of samples is undesirable from the perspective of the sample complexity, as noted in the introduction.
Next, we show that our gradient estimator is correlated with the gradient of F,, by the following lemma.
Lemma 3.2. Suppose that F is Lipschitz continuous. Then, for any x. E RRd and μ E Ry we have
E Eu-N(0,E) (()) DD [g(x, u, u. u {
= EV VV Pa.)(
3

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
Algorithm 1 Guided zeroth-order method with new samples
Algorithm 2 Guided zeroth-order method with historical samples
input 2o E R& T E N, Eo E $4_ Mi Rzo. Mmin E Rxo. E (0.1], 1], ao (0, 7 E 10.1). 3 E Ry0, 17 {mx A E N, [nRJR= E N, and distribution DR for [T].
In Algorithm 1, add p N to the input and replace lines
6 and 7 as follows:
(aat( +))) Va (
1: Sample R ~ (T)
2m
where ④ min min(k.)) p).
2: for k 0, ....,..... R do
3: Sample us from (0, Ex), 15% 1. J==1 from D(#s
(x2x)), and (5x (52.),m Ji=1 from D( - p.uus))
4: gk + 1 Ei=1
Merttu -h1") (ww - p. uk.
3.2. Guided Zeroth-Order Method
mn
2Pk
5: Ik+1 x Tg. 3gk
We propose Algorithm 1. It begins by probabilistically deter- mining the maximum number R of iterations on Line 1. This stochastic operation is necessary to guarantee the conver- gence for our method, but practically, the maximum iteration number can be set as R. Lines 2-15 are the operations of repeatedly updating the decision vector. Lines 3-5 update the decision vector 3gg by using the (mini-batch) gradient es- timator (4). Lines 6-12 calculate Σx+1 by using (5) and (6). Line 13 adjusts the smoothing parameter pu: Algorithm I starts with sufficiently large μo and gradually reduces 14k- It is known that a better local solution can be potentially obtained by making such adjustments to μu (Hazan et al., 2016; Iwakiri et al., 2022). Line 14 adjusts the balance pa- rameter or.. It is updated so that 1 1-10-1 1 = 7(1 7(-00)), with Og approaching 1 toward the end. As noted in Section 3.1, this setting promotes faster decrease in the objective value initially and reduces the bias of the gradient estimate g in later iterations.
6:
Sample {Ex mm from 1(#++1)
Ji=1
7:
Sk + E Vaf 3.1)
8:
if 8k: + 0 then
9:
Ex+1 + d Ia (1 ax Matte where h4
Tekl
else
11:
Σx+1 ok Ia
12:
end if
13:
Mk++1 + max0m//4a Pmiin)
14:
01++1 + - 7(1 )
15:
end for
return FR
Note that the proofs of all our lemmas and theorems can be found in Appendix D. Moreover, the Lipschitz condition for F in Lemma 3.2 holds under later Assumptions 4.2 and 4.3 (See Lemma D.2).
From Lemma 3.2, when Σ A La, the gradient estimator in (4) is biased gradient estimator for the augmented Gaus- sian smoothed function Fx When Σ La. it is an unbiased gradient estimator for F2
3.3. Guided Zeroth-Order Method with Historical Samples
Although Algorithm 1 generates efficient random directions, it requires new samples, (E) n.,
J==1 on line 6 to set E. In order to prevent this increase in sample size, we propose an advanced algorithm that utilizes past samples. Specifically, change the partial gradient information of (5) as follows.
Effect of balance parameter a. From Lemma 3.2 and (6),
parameter a adjusts the trade-off between the biasedness of our gradient estimator and the weight of the partial gradient information: if a = 1, then Σ = LL and g is an (scaled) unbiased gradient estimator for F, if a is close to O, the distribution (0, Σ) emphasizes the partial gradient information. Our methods (proposed later) initially set to small value to promote faster decrease in the objective value, while in the latter iterations, they make a closer to gradually to obtain a gradient estimator with a small bias.
k-1
my
Σ j=k-p
2m
(8)
where (5)-)) and (5, Jm are historical samples from the past j-th iteration. Here, my is the batch size of the j-th iteration and E N the window size that determines how far back the past samples are.
The way of sampling u. Samples of u ~ NN(0 Σ) can be generated efficiently as
In Algorithm 2, the partial gradient information is obtained using samples from past iterations. This allows us to set Σ without requiring a new sample.
u
a V
w V1 - Vaau d
(7)
However, this adjustment is not necessary to guarantee the convergence of method, and theoretically, can also fixed pik-
where w ~ NN(0, I2) and 1 ~ NN,0, 1). This fact is shown in (Maheswaranathan et al., 2019, Section 3.2).

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
4. Theoretical Analysis
As noted in the introduction, sample complexity is an impor- tant metric in evaluating algorithms for solving problem (1). This is because, to obtain sample & ~ D(x) in practice, decision (œ) must be deployed in the real world.
4.1. Assumptions and Definitions
For the theoretical analysis of our method, we make the following assumptions.
Assumption 4.1. For any æ E Rd, there exists E Rg0 satisfying
No assumptions about partial gradient information. In our analysis, we do not assume any correlation between partial gradient information (i.c., (5) and (8)) and the true gradient. Therefore, we consider the worst-case scenario for the partial gradient information. Even under this worst-case scenario, our analysis establishes improved sample com- plexity for our methods compared to the existing method (Hikima & Takeda, 2025b). This improvement is achieved through (i) a reduction in sample complexity by tuning algo- rithmic parameters such as mini-batch size and step size, and (ii) the incorporation of partial gradient information without increasing the sample complexity, even in the worst-case scenario.
- {( so?
(9)
Assumption 4.2. For any E IRL, fax, E) is Le -Liischch continuous with respect to f. Moreover, for any &, f(x, E)
is Li-Lsscciizz continuous with respect to æ.
Assumption 4.3. For any æ E RR,, there exists A E Rg satisfying
W(D(z), < <f| x'Il.
where W represents the W distance.
Assumption 4.4. F(x) = BE E)] is Hy- smooth.
4.2. Sample Complexities of Our Methods
Assumption 4.1 is required for approximating F(x) by Ex,,E) with sample Ç. Since the objective function involves random variables, such an assumption is needed to evaluate the objective value by its sample. The purpose of Assump- tions 4.2 and 4.3 is to guarantee the Lipschitz continuity of the objective function (Lemma D.2). is used to derive the properties of the Gaussian smoothing function (Lemma D.8). Assumption 4.4 is standard in convergence analysis, ensuring the accuracy of the first-order approximation via Taylor expansion. This is because descent methods with (estimated) gradients can be seen as optimizing a first-order approximation of the objective function at each iteration.
First, we provide a lemma, which indicates a theoretical property of our gradient estimator.
Lemma 4.6. Suppose that Assumptions 4. 4.144.4 hold. For any x E Rd, the following holds.
T Bu
FEELi
Σ g p4 n. Sth {.))
24a²
d² (d+
+ 24(1- a) 23a / FF())]
+5188(1 - 1 a)²) 160 (6o0
30
+ + 11?
+ 2u²
d
where { nrm).
Ji=1 ~ D(x + pu) and ( ~ D(æ
Comparison with assumptions in existing studies. Our assumptions are looser than or equal to existing stud- ies (Ray et al., 2022; Hikima & Takeda, 2025b). First, our assumptions are less restrictive than those of (Ray et al., 2022). Assumption 5 in (Ray et al., 2022) im- plics that (g=-D(>)(((()>> f(x, <)) & (2G)² for G == sup=.e (f E) which yields our Assumption 4.1. As- sumptions and in (Ray et al., 2022) yield our Assump- tions 4.2, 4.3, and 4.4. Conversely, we do not require As- sumption 1(c) Assumption 2 in (Ray et al., 2022). More- over, our assumptions are equivalent to those of (Hikima & Takeda, 2025b). Regarding Assumption 4.4, the existing study (Ray et al., 2022) gives a sufficient condition. It can be found in Appendix C.
Lemma 4.6 gives an upper bound on the second moment of our gradient estimator.? ?
Below, we use Lemmas 3.2 and 4.6 to derive the sample complexity of Algorithm 1.
Theorem 4.7. Suppose that Assumptions 4.1- 4.4 hold. Lei {œL) be the sequence gener- ated by Algorithm I with Pmin = O(ed-
'An existing study (Maheswaranathan et al., 2019) showed the upper-bound of the (normalized) variance of their gradient [F estimator for given correlation p; == [[V["]]] between partial gradient information (U,'s) and the true gradient (VF(w)). In our study, we derived an upper bound on the second moment of our gradient estimator (Lemma 4.6) without such p., Icading to a guarantee of convergence for the proposed method. While (Maheswaranathan et al., 2019) demonstrated a trade-off between the unbiasedness and the variance of their gradient estimator by considering Pt, our study does consider Pi, and therefore, theoretically, no such trade-off exists in our setting.
Moreover, we define an indicator to evaluate our method, Definition 4.5 (Sample complexity for e-stationary point). We define the sample complexity for an e-stationary point to be the number of samples & ~ D(x) to obtain [[[[=F(@)|(" S e,, where è is the output of a target algo- rithm.
5

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
140
( such that Ho 2 Muinn B :=
GZO-NS. This means the Guided-Zeroth Order method
min
(8H=((d-11)2225B)) T T-3d dd 3) and Pr(R = k) :=
aod
with New Samples, which corresponds to Algorithm 1.
GZO-HS. This means the Guided-Zeroth Order method with Historical Samples, which corresponds to Algorithm 2. ZO-TG. This is Zeroth- method with a Two-point Gradient estimator. It is consistent with Algorithm I where Σx = 4 for all k E {o..... ........ T) and lines 6-12 and line 14 are not executed. It is analogous to the zeroth-order method used in the existing studies (HHikima & Takeda, 2025b, Al- gorithm 2) and (Liu et al., 2024a, DFO(0) with 92pt-11)). Z0-OG. This is a Zeroth-Order method with One-point Gradient estimator. It is analogous to the zeroth-order method used in the existing studies (Ray et al., 2022: Liu et al., 2024a).
Bazd 24H 9 L [Bard-1 -21H 5 (- 21H (1 (1- 23cr)) -0--0
for distribution DR- Then, for any Zo E Rd, Eg E $ " (0, ag 1), 7 E [0, ni 0(1) for k T, my = O(1) for k- = 0,...T, T, the sample complexity required to obtain B[][V((aR)]+] s 6² is c )*))
Moreover, we can derive the sample complexity for Algo- rithm2 2.
Theorem 4.8. Suppose that Assumptions 4.1 1.4 hold. Let the inputs of Algorithm other than p be as in Theorem 4.7. Then, for any p E N. Algorithm 2 achieves the same sample complexity in Theorem 4.7.
ZO-OGVR. This is Zeroth-Order method with One- point Gradient estimator with a Variance Reduction parame- ter (Hikima & Takeda, 2025b, Algorithm 1).
The O(a"d'e sample complexity of our methods has advantages over those of existing methods (Liu et al., 2024a; Hikima & Takeda, 2025b). The sample complexity of the method of (L.iu et al., 2024a) (f 9)) where G = s (x, 4) Therefore, our methods outperform them when G is large or unbounded.* 4 Moreover, the iteration complexity of our method is O(d+) smaller than that of (Hikima & Takeda, 2025b).
5.1. Multiproduct pricing application
We conducted experiments on the same problem as (Hikima & Takeda, 2025b). Specifically, it is the following problem:
min [f E)], =ER10
where and & denote the price vector and the demand vec- tor for 10 products, respectively. Function f is defined by (ax E) = - s(x,, {) + c(E), where s(x. {) and c(E) repre- sent the sales and production costs of products, respectively. Distribution ((x)) represents the (price-dependent) prob- ability distribution that & follows. This experiments were semi-synthetic, and some of the parameters were set us- ing real retail data from a supermarket service provider in Japan. Details of how to set each function and distribution are given in Appendix A.
Remark 4.9. To set the inputs of Algorithm according to Theorem 4.7, it is necessary to know the value of F in Assumption 4.4. While the existing methods (Ray et al., 2022; Hikima& & Takeda, 2025b) also need such information (e.g.. 7 in (Ray et al., 2022) and a in (Hikima & Takeda, 2025b)), it may not be known in advance in practice. In such cases, one can begin with a sufficiently large value and refine it using information gathered during the iterations.
5. Experiments
SETTING AND METRIC
We conducted two experiments on applications of multiprod- uct pricing (Hikima & Takeda, 2025b) and strategic clas- sification (Levanon& & Rosenfeld, 2021) to show that Algo- rithms and 2 output solutions with lower objective values compared with the existing methods for the same number of samples. All experiments were conducted on a com- puter with Intel(R) Xeon(R) CPU E5-2697A v4 (2.60GHz) x2 and 512GB of memory RAM. The program code was implemented in Python 3.12.2.
We performed our experiments under the following settings. Initial points. For all methods, we set the initial points as
Zg == 0.5 1, where 1 := (1,..., 1) E "O
Metric. To evaluate the output ã we computed obj ==
10a Eye f(t, {*()),, where (#)) D(t).
1
Termination criteria. We terminated each method once it
had taken 5000 samples from D(x) for some x.
EXPERIMENTAL RESULTS
Compared methods. We implemented the following methods. Details of the parameters can be found in Ap- pendix A.1.2 and 1.2.1.
Table shows the results of the experiments using real data from different weeks. Our methods (GZO-NS and GZO- HS) were superior to the baselines for all weeks of data.
'Note that (Liu et al., 2024a) considers setting which the sample/data distribution evalves according to controlled Markoy chain, and addresses a more general problem than ours.
Figure 1 illustrates the objective value (ob)) obtained with
'The data, "New Product Sales Ranking", has been made pub- licly available by KSP-SP Co., Ltd, http://www.ksp-pp.comm Last accessed on Jamuary 28, 2025.
"Note that even if f is a simple loss function such as squared error, G unbounded.
6

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependentt Distributions
Table Experimental results for multiple product pricing in randomly generated problem instances. The obj (sd) column represents the average (standard deviation) of the obj. The best value of the average obj for each experiment is in bold. In all experiments except for 7/18- 7/24, the differences in obj between our methods (GZO-NS and GZO-HS) the baselines were statistically significant (two-sided I-test: p < 0.05). For 7/18-7/24, the difference between GZO-HS and ZO-TG was not statistically significant, while the difference between GZO-NS and the baselines remained significant.
date
GZO-NS
GZO-HS
ZO-TG
ZO-OG
ZO-OGVR
obj
sd
obj
sd
obj
sd
obj
sd
obj
sd
2/21-2/27
-12.53
0.99
-12.85
0.70
10092
1.21
5.10
10.33
-6.30
1.75
3/21-3/27
-12.52
1.29
-12.58
1.09
10.52
1,45
1.56
3.38
-6.41
1.64
5/23-5/29
-15.70
1.04
-15.41
1.17
-10.11
2.29
-0.06
1.59
-5.60
2.07
6/20-6/26
-9.06
1.30
-9.52
0.69
-8.81
0.82
10.15
17.28
-5.65
1.96
7/18-7/24
-8.43
0.99
-8.38
1.29
-7.98
1.42
10.38
19.72
-3.47
2.43
8/08 8/14
-14998
1.01
-14.93
1.28
-10.30
2.41
-0.53
1.87
-6.11
1.55
5.0
GZO,N5
C20 HS
G20_HS
620_HS
0.0
70_16
20 TG
20 TG
20_06
-5
20.0G
20 08VR
-5-
-10
-755
-10.0
10
-12.5
3000
1000
3000
sample number
sample number
sample number
(a) 02/21-02/27
(b) 03/21-03/27
(c) 05/23-05/29
2,5
0.0
GZD_NS
H5
20
15
G20 H5
G2O_NS
-2.
620_MS
GZO HS
ZD_0G
20.06
5.00
20_96
obj
2.5
20_06VR
10
20, 00.
20_DGVR
-5.0
10.0
7.5
-12.5
-10.0
-5
-15.0
10
1000
2000
3000
4000
5000
1000
2000
3000
4000
3000
1000
2000
3000
4000
5000
sample number
sample number
sample number
(d) 06/20-06/26
(e) 07/18-07/24
(f)
08/08-08/14
Figure 1. Change in obj in the experiments on multiproduct pricing. Each graph shows the result for one problem instance for each week. The horizontal axis indicates the cumulative number of samples from D(x), and the vertical axis indicates obj.
each method against the cumulative number of samples from (xx) in its optimization process. The figure implies that our methods reduce the objective value more stably than the baselines. This is due to the following reasons: (i) ZO-TG and ZO-OGVR could not efficiently decrease the objective value because they determined the updating direction u4 according the standard Gaussian distribution without using information on the function f; (ii) ZO-OG could not stably decrease the objective value because of the large variance of its gradient e
5.2. Strategic Classification with Unknown Agents' Cost Functions
We conducted experiments on the application of strategic classification with a real dataset from (Ych & hui Lien, 2009).? We considered a variant of (Levanon & Rosenfeld, 2021, Section 4) where the decision maker wants to opti- mize the parameter æe of the classifier to decide whether to provide loan financing for strategic agent with feature Er R and label L E {0, 1}. Here, &r includes credit- card spending patterns, while L, indicates whether the agent
'The large variance of the one-point gradient estimator used by 70-OG is also noted in (Hikima& & Takeda, 2025b).
"As with (Levanon & Rosenfeld, 2021), used processed version of the data from (Ustun et al., 2019).
7

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
defaults on payment. Since the agent can vary their own features according to the parameter æ. (Er, L.) follows
Zo == 1, where 1 == (1, (1....,
, 1) R
Metrics. For the output of each method, we used the train- ing loss, the test loss, the test AUC, and the test accuracy as metrics.
decision-dependen distribution D(x). Here, we used the following loss function:
Termination criteria. We terminated each method once it had taken 10000 samples from ((x) for some æ.
f(Er, L:x Log
1te (111))tt)1)))
1
EXPERIMENTAL RESULTS
+ (1- - Log 1
1 1 (0
Table shows the results of the experiments with different 7.9 Note that 7 E R50 is a constant that controls the magni- tude of the cost. If T E Rx is small, distribution (xx) is more likely to vary with decision vector æ. The results show that our methods (GZO-NS and GZO-HS) were superior to the baselines for all т. Moreover, the performance of our methods is less affected by changes in T than existing methods, which indicates our methods are less sensitive to the changeability of distribution D ((x).
where 2(11]= ;= (I1, 22.............................. T11).
The mos-miniimization problem is as follows:
min 22
D(gr) [f(EF, L;
Settings of unknown D(x). We assumed that each agent has the true feature Strue ~ Derue but may change its fea- tures according to the parameter z of the classifier and the cost associated with altering its feature. Specifically, each agent modifies its features by using the following response mapping:
6. Conclusion
We proposed two zeroth-order methods for solving non- convex stochastic problems with decision-dependent dis- tributions; they utilize partial gradient information derived from the known structure of f. The first method obtains partial gradient information from samples at the current iteration, and the second one obtains partial gradient infor- mation from historical samples. Our theoretical analysis showed that they converged to stationary points and pro- vided the worst-case sample complexity. Our experimental results showed that our methods outperformed the conven- tional zeroth-order methods.
Er arg maxe r(E, 2)) - c(S. Etrue, T),
where
$ + x12 2 0, 0, if a Sil $ + x12 < O,
2, if x T
rE,, a²
c(E, Struey 7) == - - Etruell
Here, r(E, .) represents the profit for each agent: if x0 Tun + F12 2 then the agent receives positive classification and is rewarded. 8 Function represents the cost of modifying their features: changing one's own features incurs a cost based on the distance of the modified feature vector from the true feature vector. Here, = E R> is constant that controls the magnitude of the cost. We consider the set of real data to be the set of (Etrue: L)) and set D(x) with the above settings. Note that the information on (xx) was not used by any of the methods.
Future work includes exploring efficient methods for ad- justing the balance parameter o, which controls the weight of the partial gradient information. We used the first term in (3) as partial gradient information, whose importance is affected by the size of the second term. Therefore, we can adjust a according to the size of the second term. Similarly, it is expected that method for determining the range p of past samples to be referenced in Algorithm 2 can also be derived. If the reliability of past samples can be theoretically established, the value of can be accordingly set.
Remark 5.1. This setting does not satisfy the smoothness in Assumption 4.3. This is because the data distribution changes discontinuously at the point where the cost exceeds the gain for some agents. Despite this unfavorable setting for our methods, the experimental results described later show that they still perform well numerically.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
SETTING AND METRIC
We performed our experiments under the following settings. Initial points. For all methods, we set the initial points as
"Note that the performance of each method in our experiments is lower than that in typical experiments without strategic agents because the strategic agent manipulates its own features to cheat the classifier.
The reward value of 2 is set based on the existing study (Leev- anon& & Rosenfeld, 2)2
8

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
Table Results of experiments on strategic classification for randomly generated problem instances. The metric (sd) column represents its average value (standard deviation). The best value of each metric for each experiment is in bold. In all experiments, the differences in each metric between our methods (GZO-NS GZO-HS) and baselines are significant (two-sided t-test: 0.05).
GZO-NS
GZO-HS
7O-TG
Z0-OG
ZO-OGVR
train loss
sd
train loss
sd
train loss
sd
train loss
train loss
sd
0.5
0.87
0.04
0.83
0.03
1.21
0.08
2.75
1.80
1.51
0.62
1.0
0.88
0.05
0.84
0.03
1.27
0.08
2.98
1.83
1.63
0.63
2.0
0,86
0.05
0.81
0,03
1.34
0.10
3.44
1.92
1,83
0.73
4.0
0.84
0.05
0.79
0.03
1.35
0.12
3.96
2.09
2.06
0.93
8.0
0.83
0.04
0.78
0.03
1.35
0.12
4.39
2.27
2.24
1.09
GZO-NS
GZO-HS
ZO-TG
ZO-OG
ZO-OGVR
test loss
sd
loss
sd
test loss
sd
test loss
test loss
sd
0.5
0.93
0.04
0.89
0.03
1.31
0.09
2.89
1.91
1.63
0.67
1.0
0.96
0.05
0.91
0.04
1.38
0.09
3.12
1.94
1.75
0.69
2.0
0.93
0.06
0.87
0.04
1.43
0.11
3.55
2.03
1.96
0.79
4.0
0.90
0.05
0.84
0.04
1.45
0.13
4.04
2.20
2.20
1.01
8.0
0.88
0.05
0.83
0.04
1.45
0.14
4.44
2.39
2.38
1.18
GZO-NS
GZO-HS
ZO-TG
ZO-OG
ZO-OGVR
test AUC
sd
test AUC
sd
test AUC
sd
test AUC
sd
test AUC
sd
0.5
0.62
0.03
0.62
0.02
0.46
0.03
0.48
0.12
0.44
0.08
1.0
0.62
0.03
0.62
0.02
0.47
0.03
0.49
0.13
0.45
0.09
2.0
0.66
0.03
0.66
0.02
0.48
0.04
0.50
0.14
0.46
0.10
4.0
0.67
0.03
0.68
0.02
0.49
0.04
0.50
0.15
0.46
0.11
8.0
0.68
0.02
0.69
0.02
0.50
0.05
0.51
0.15
0.46
0.12
T
GZO-NS
GZO-HS
ZO-TG
ZO-OG
ZO-OGVR
test acc
sd
test acc
sd
test acc
sd
test
sd
test acc
sd
0.5
0.55
0.03
0.53
0.03
0.47
0.02
0.49
0.06
0.47
0.04
1.0
0.57
0.03
0.56
0.03
0.47
0.03
0.51
0.08
0.47
0.05
2.0
0.60
0.03
0.59
0.03
0.48
0.02
0.51
0.10
0.48
0.06
4.0
0.62
0.03
0.62
0.03
0.47
0.03
0.51
0.10
0.48
0.07
8.0
0.63
0.03
0.63
0.02
0.49
0.03
0.52
0.11
0.48
0.08
References
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-ore order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
Bergstra, J. and Bengio, Random search for hyper- parameter optimization. Journal of Machine Learning Research, 13(2). 2012.
Hazan, E., Levy, Y., and Chalev-Shwartz S. On grad- uated optimization for stochastic non-convex problems. In International Conference Machine Learning, pp. 1843-1841, 2016.
Chen, Y., Tang, W., Ho, C.-J,, and Liu, Y. Performative prediction with bandit feedback: learning through repa- rameterization. International Conference on Machine Learning, pp. 7298 7324, 2024.
Hikima, Y. and Takeda, A. Stochastic approach for price optimization problems with decision-dependee uncer- tainty. European Journal of Operational Research, 322 (2):541-553, 2025a.
Frazier, P. I. A tutorial on bayesian optimization. arXiv preprint arXiv: arxivv/807.028//1 2018.
Freund, E. and Walpole, R. E. Mathematical Statistics. Prentice-Hail Hall, Inc., 1986.
Hikima, Y. and Takeda, A. Zeroth-order methods for non- convex stochastic problems with decision-dependent dis-

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
tributions. In AAAI Conference on Artificial Intelligence, volume 39, pp- 17195-17203, 2025b.
Miller, J. P., Perdomo, J. C., and Zmnc, T. Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning, pp. 7710- 7720, 2021.
Iwakiri, H., Wang, Y., Ito, S., and Takeda, A. Single loop gaussian homotopy method for non-convex optimization. In Advances in Neural Information Processing Systems, 2022.
Mofakhami, M., Mitliagkas, I., and Gidel, G. Performa- tive prediction with neural networks. In International Conference Artificial Intelligence and Statistics, pp. 11079-11093, 2023.
volume 35, pp.
Izzo, Z., Ying, L., and Zou, J. How to learn when data reacts to your model: performative gradient descent. In International Conference on Machine Learning, pp. 4641- 4650, 2021.
Nesterov, Y. and Spokoiny, V. Random gradient-free mini- mization of convex functions. Foundations of Compula- tional Mathematics, 17(2)527-566, 2017.
Jagadeesan, M., Zrnic, T., and Mendler-Dünner, C. Regret minimization with performative feedback. In Interna- tional Conference on Machine Learning, pp. 9760-9785, 2022.
Perdomo, J., Zrnic, T., Mendler-Dünnner, C.,, and Hardt, M.
Performative prediction. In International Conference on Machine Learning, pp. 7599-7609, 2020.
Petersen, K. B.., Pedersen, M. S., et al. The matrix cookbook.
Khorsandi, P., Gupta, R., Mofakhami, M., Lacoste-Julics S., and Gidel, G. Tight lower bounds and improved convergence in performative prediction. In OPT 2024: Optimization for Machine Learning, 2024.
Technical University of Denmark, 7(15):510, 2008
Powell, J. D. The NEWUOA software for unconstrained optimization without derivatives. In Large-Scale Nonlin- ear Optimization, pp. 255-297, Springer US, 2006.
Levanon, S. and Rosenfeld, N. Strategic classification made practical. In International Conference on Machine Learn- ing, pp. 6243-6245550 6253,, 2021.
Ragonneau, T. M. and Zhang, Z. PDFO: cross- cross-platform package for powell's s derivative-fres optimization solvers. Mathematical Programming Computation, 16(4):535- 559, 2024.
Li, Q and Wai, H.-T. Stochastic optimization schemes for performative prediction with nonconvex loss. In Ad- vances in Neural Information Processing Systems, vol- ume 37, pp. 8673-8697, 2024.
Ray, M., Ratliff, L. J., Drusvyatskiy, D., and Fazel, M. Decision-dependeen risk minimization in geometrically decaying dynamic environments. In AAAI Conference on Artificial Intelligence, volume 36, pp. 8081-8088 2022.
Lin, L. and Zmnie T. Plug-in performative optimization. In International Conference on Machine Learning, pp. 30546 30565, 2024.
Roy, A., Balasubramanian, K., and Ghadimi, S. Constrained stochastic nonconvex optimization with state-dependent markov data. In Advances in neural information process- ing systems, volume 35, pp. 23256-23270, 2022.
Liu, H., Li, Q. and Wai, H.-T. Two-timescale derivative free optimization for performative prediction with markovian data. In International Conference on Machine Learning, pp. 11425-31450, 2024a.
Ustun, B., Spangher, A., and Liu, Y. Actionable recourse in linear classification. In Conference Fairness, Account- ability, and Transparency, pp. 10-19, 2019.
Liu, T., Lin, Y., and Zhou, E. Bayesian stochastic gradient descent for stochastic optimization with streaming input data. SIAM Journal on Optimization, 34(1):389-418, 2024b.
Xue, J. and Shen, B. novel swarm intelligence optimiza- tion approach: sparrow search algorithm. Systems Science & Control Engineering, 8(1):22-34, 2020.
Maheswaranathan, N., Metz, L., Tucker, G., Choi, D., and Sihll-ickstten, J. Guided evolutionary strategies: Aug- menting random search with surrogate gradients. In In- ternational Conference on Machine Learning, pp. 4264- 2019.
Ych, I.-C. and hui Lien, C. The comparisons of data min- ing techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2, Part 1):2473-2480. 2009.
Mendler-Dtinned C., Perdomo, J., Zrnic, T., and Hardt, M. Stochastic optimization for performative prediction. In Advances in Neural Information Processing Systems, volume 33, pp. 4929-4939 2020.
10

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependeee Distributions
A. Details of Our Experiments
A.1. Experiments on multiproduct pricing
A.1.1. PROBLEM SETTING
We performed semi-synthetic experiments based on (Hikima & Takeda, 2025b). Here, some of the parameters were set using real retail data from a supermarket service provider Japan." 10 The experiments simulated a scenario in which a seller determines the prices of multiple products (n 10) for multiple buyers (m = 40). Each buyer purchases at most one unit of any product. Let
(x1, .........,...................... (10) E R be the price vector (decision vector) for the products. Let & E {0, 1..... .... m3" denote the stochastic demand vector of the products, where & for i = ...... 10 is the number of sales of each product, and {ι is the number of buyers who do not purchase any product.
Then, the objective is to solve the following revenue-maximization problem:
min D(n [f E)], æERIC
where f(xxE) := -=x + c(E) and (ax) the probability distribution of demand &. Here, s(x, E) and c(E) are the sales and production cost function, respectively. They are defined as:
s(x, E)
Σ
c(E)
where
EwiE.
E, S li
cc.))) == wi 1,) + 2wrls;
I: < & S Ui
3w: (E: - u.) wi(u. (u: 1.) + 2wdh,
& > u.
Here, we set 4 : 0.5m U, == 1.5m and wi == p;O,, where Pt is random variable generated from a uniform distribution of [0.25, 0.5] and 0g the normalized recorded average selling price for each product i. The function o; reflects the scenario where the production cost rate varies based on the number of units sold.
Settings of unknown D(x). We assume that buyers choose one product stochastically. Each buyer chooses product -710%==x))
i = [I....,n] n with probability pi(x)) ao -. -=5 does not choose any product with probability
(o()) ag BO+E" e., T,T- Here, we let 7/2 ==
2n and let ag == 0.1m. Then, Pr(E: x) (%. (x))5 Note that the
v6a;
information on (1x) was not used by any of the methods.
A.1.2. PARAMETERS METHODS.
GZO-NS. This is Algorithm 1 with 1i 0.2, Mmii 0.0001, og 0, Bk 0.01 0.95*, 7 0.95, 7 0.98,
ma 30 + 2k, and := 30 + 2k, where & is the current iteration number.
GZO-HS. This is Algorithm 2 with p = 1; the other parameters are the same as in GZO-NS.
ZO-TG. This is consistent with Algorithm where Σ₁ = I for all l: E (O....,T) T) and lines 6-12 and line 14 are not executed. The other parameters are the same as in GZO-NS.
ZO-OG. This is consistent with Algorithm where Σn = Id, gh 1 ΣTt f( f( un for k E {o...., T).
and lines 6-12 and line 14 are not executed. We let == 10 and μn == 0.001; the other parameters are the same as in GZO-NS.!! !I
ZO-OGVR. This is consistent with (Hikima & Takeda, 2025b, Algorithm 1). We let 8 = 0.001 0.95%, co = Σラn f(xo, (' Smax := 10, and M 0.1; the other parameters are the same as in GZO-NS.
10The data, "New Product Sales Ranking", has been made publicly available by KSP-SP Co., Ltd, htt::/www.ksp-sp.com Last accessed on January 28, 2025.
1Teee step size of ZO-OG is small compared with those of other methods. This is hecause the variance of the one-point gradient estimator is large, which causes the objective values to diverge.

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependeee Distributions
A. 1.3. DATA DETAILS.
The experimental data, "New Product Sales Ranking", provided by KSP-SP Co., Ltd, includes confectionery price data. We used the actual prices of confectionery in the buyer's probability function for purchase. We also determined the cost of each product based the actual prices.
A.2. Experiments on Strategic Classification
A.2.1. PARAMETERS METHODS.
GZO-NS. This is Algorithm 1 with μo 10, Mmmnn 0.1, 0g 0, 0.95* 0.95, 7 0.98, my 30 +k,
and n4 := 100 + 2k, where & is the current iteration number.
GZO-HS. This is Algorithm 2 with p 1; the other parameters are the same in GZO-NS.
ZO-TG. This is consistent with Algorithm where Σg := l for all k E {O,.... T) the other parameters are the same as
in GZO-NS.
Eme flam P for all l E (0...., .......T, T).
Z0-0G. This is consistent with Algorithm where Σg = Ia and g ma We let / == 0.05 and μ4 == 0.1; the other parameters are the same as in GZO-NS.
Mk
ZO-OGVR. This is consistent with (Hikima Takeda, 2025b, Algorithm 1). We let B = d 0.95*, cp =
j=1 fxv. e (zo)), Smax == 10, and 0.1; the other parameters are the same as in GZO-NS.
A.2.2. DATA DETAILS.
The experimental dataset (Yeh & hui Lien, 2009) includes features describing credit-card spending patterns, along with labels indicating default payment. As with (Levanon & Rosenfeld, 2021), we used the preprocessed version of the data by (Ustun et al., 2019). The dataset includes 11 features. We divided 13272 data samples into 12272-sample training set and 1000-sample test set in our experiments.
B. Additional Experiments
B.I. Statistical information on objective values during iteration
Since Tables and 2 show the statistical results the final iteration, we give the figures to show averaged curves and error bars across multiple instances. Figure 2 shows the average and standard deviation of the objective values across iterations, obtained from experiments using data from each week in the multi-product pricing application. These results indicate that our methods are superior to existing methods even during iterations.
B.2. Statistical information on gradient norms during iteration
Figure 3 shows the mean and standard deviation of the gradient norm in the application of multi-produe product pricing. This graph shows that the proposed method reduces the gradient norm with fewer samples than existing methods.
C. Sufficient condition for Assumption 4.4
Lemma C.1. (Ray et al., 2022, Lemma 1) Suppose that there exist a matrix A and distribution D' such that
~~ +
where v D'. Moreover, suppose that f(x, E) is p-smooth with respect to both x and &. Then, Assumption 4.4 holds with
Hr =F== 02 + max(1, 1(,))
where App is the operator norm of A, that is, A| sup ,x00
|Aw
[
12

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
GZO_HS HS
GZO_HS
GZO HS
0.0
GZO NS
G2O NS
G20 NS
-2.5
zO_0G
Z0_0G
0G
Zo OGVR
ZO OGVR
ZO OGVR
09)
ZO_TG
8
20 TG
7.5
20_1 TG
-5
10.0
1255
-10
-10
-50.0
-15
17.5
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5006
sample number
sample number
sample number
(a) -22/27
(b) 03/21-0330 00/27
(c) 15/23-05/29
GZO HS
GZO_Hz
0.0
GZO HS
15
GZO NS
GZO GZO_NS
-2.5
GZO_N5 NS_
10
-5.0
ZO OG
OGVR
OGVR
Z0, OGVR
00)
zo_ TG
TG_TG
-7.5
20_TG
0
-10.0
-125
-5
15.0
-10
-175
2000 sample number
3000
sample
sample number
(d) 06/20-06/26
(e) 07/18-07/24
(f) 08/08-08/14
Figure 2. Changes in the and standard deviation of obj for 20 problem instances relative the number of samples in the experiments on multiproduct pricing. Each graph shows the result for each week.
50
GZO
G20, HS
35
GZO
GZO, NS
norm norm
40
ZO_0G
40
20 20
30
RGVR
2G_GGVR
gradlent.oo
30
ZO_TG
gradient
30
ZO_TG
gradient
20
20
15
10
10
1000
3000
5000
1000
3000
5000
1000
3000
5000
sample number
sample
sample number
(a) 02/21 02/21-02/27
(b) 03/21-03/27
(c) 05/23-000100 05/29
G20 HS
G2O HS
GZO HS
50
GZO G2O_NS NS
GZO NS
GZO NS
gradient nom
20_0G
ZO OG
gradient norm
20_0G
ZO OGVR
60
ZO OGVR
ZO. OGVR
30
ZO TG
gradient
2G
20
20_TG
20
10
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
sample number
sample number
sample number
(d) 06/20-06/26
07/18-07/2
08/08 0088-08/14
Figure Changes mean standard deviation the approximated gradient norm the objective function (calculated by (3) with 1000 samples) for 20 problem instances relative to the number of samples in the experiments multiproduct pricing. Fach graph shows the result for each week.
13

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependentt Distributions
D. Proofs
D.I. Technical lemmas
Here, we provide technical lemmas that are needed to prove the lemmas and theorems in our paper. Technical Lemmas D.I-D.4 are from existing research, while Technical Lemmas D.5-D.12 are newly proved by us.
Technical Lemma D.1. (Nesterov & Spokoiny, 2017, Lemma 1)
For prrpe E [0,2] 2).
E ( [| [] dē,
(10)
For p 2 2,
Ew [||=||*]] S (d + p)
(11)
Technical Lemma D.2. (Jagadeesan et al., 2022, Lemma 2.1)
Under Assumptions 4.2 and 4.3, function Fxx) = (f {)] is Lipsscchh,,,, where LF = Le + O
Technical Lemma D.3. (Freund & Walpole, 1986, p183)
For any x E Rd
((())
Σ f(z, E¹) E() E)]
S EewD [lf(x, E') - (1=1
Technical Lemma D.4. (Maheswaranathan et al., 2019, Section 3.2)
Σ> = 4 + (1 - hh T for E N. h E R4, and a E (0, 1]. Let u = Fw + vI- adv, where w ~ NO Ia) and (0, E).
NO, 1). Then, the distribution
Technical Lemma D.5. Let E == at + (1 ohhhh' T for E N, E Rd such that | = 1 or = 0, and a E (0, 1). Then,
Σ
a,
d
where [ is the spectral norm of Σ. Moreover,
d
Σ
Proof. Since E is a positive semi-definit, matrix, its spectral norm is equal to its largest eigenvalue. Let À be an eigenvalue of Σ. Then, there exists an eigenvector x: + O that satisfies
a j + (1 (1-a) wh.
Ax = Ex
From the above equation, À = å when = 1. When = 0, x satisfies x = ch for some constant e E R or satisfies
ATa x = 0. In the case that æ = ch,, we have h * O since æ + 0. Then, we have = a + (1 a:) since |hl]l = 1 from the assumption. In the case that h x = 0, we have À = a- Therefore, from the fact that a E (0, 1], we have 3 <
Next, have that |-1 Emm. where Emin the smallest singular value of the matrix Σ. Since the eigenvalues of the positive-definite matrix Σ are equal to its singular values, we have that ||-1|| Xmin where Amin is the smallest eigenvalue of Σ. From the previous discussion, Amin 2. Therefore, |
Technical Lemma D.6. For any N, x Rd, and y E Rd
I + yll" 2- + 2n |1
14

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-eepeneett Distributions
Proof. Lemma D.6 holds if
2 +
y
| | +
|
2
2
Due to the symmetry between æ and y, we can assume that | | 1. Moreover,
||
2
|
without loss of generality. Let 2 ==
Tall
2
Then,
+ y
2
+
||vll
y
| ll I
|| +
| 101
|| +
11
2
2
Therefore, Lemma D.6 holds if
+
| "
||=l|*+|1111 +|v1"" that is,
++|++1
+1 for || 2 1. Here, let
f(s) = =1
2 (2 Then, for 2 1,
ns=-1
12(s + 1)n-1
s s 1
n-
f'(s) 2
8-
2 0.
2
2
Since ((1) = 0, we have f(s) 2 f(1) = 0 for 2 1. Therefore,
|
<
| 1 for | 2 1.
Technical Lemma D.7. Let E = 4 + (1 aahhh for N, E Rd such that |/]]| = 1 or = 0, and a E (0, 1].
Then,
1
(12)
32a (d + 6)3
E. Eu [|]
10976(1-a))
(13)
d3
Proof.
Since ||aa|22 = tr(uuT) from (Petersen al., 2008, (17)), we obtain that
E. = BunNN (o,)/(o, [r((um J] Lr(Bun-Woo.))uuu J) Lr(00 + Σ) ir (
X
where X, is are the eigenvalues of E. Therefore, (12) holds if Σd -i=1 A < 1. Let + be eigenvector of E. Then,
A = Σx 7 x + (1 - h xh.
(14)
Here, we consider the three cases as follows.
(i) the case where a = From (14), A = 1/ for all i 1,..., ....... Then, Σi= 11
(ii) the case where a (0,1) and || From (14), æ satisfies æ ch for some constant E RR satisfies h "x In the that ch, we have
3 + - a).. In all other cases that h. Tx 0, we have 3. Then,
A a ((
(iii) the case where a E (0, 1) and h 0. From (14), we have dx
g x. Then,
Σ d 1.
From the above discussion, (12) holds.
15

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
Regarding (13),
E (0,))))))l (+)
||
w + v1 ahe
d
(+o)
32
+ vI ahv
d
(s.a)
32ax
S
N (||00191 + 32(1 - a
E
E V0.101)))
db
(*.**)
32a (d + 6)3
32(1 - -7)87
d3
32a 3 (d + 6)3
+ 10976(1 - ox)3
d3
where (*) comes from Lemma D.4, (**) follows from Lemma D.6, (***) is due to the fact that ||A]| = 1 or ||/|] (****) holds from (11) in Lemma D.1.
0, and
Technical Lemma D.8. Suppose that Assumptions 4.2-4.4 hold. Then, F,,x: is Hy--mooth for any l Ry and any positive-definite matrix E E 84
Proof.
[V,x((()
Vo. [ [m]] VE V pu)]
Eu~N VF(x+ - Eo VVFly + pw)]
Bu>.V VF(z + nm)
VF(U pa)]
Eu-,((o.)) VF pm)
FF +m))
pr)1l
Eu~N(o, HF -
ylll
Hr yl
where (*) holds since Lemma D.2 enables to exchange the order of differentiation and integration. Moreover, (**) comes from Assumption 4.4.
Technical Lemma D.9. Suppose that Assumptions 4.2 and 4.3 hold. Let
E, = @1 Ia + - h2) Eg = d
022 Ia + (1 - h22)222
where d N, 01 E (0, 1], 02 = 7(1 a1) for E (0,1), b E Rd such that |h1l| h 0. and b E Rd such
that |22] = or h2 0. Then,
FF x, (x) - F So Ny (x)) S 22L min - H2l + LepelVan - Vo2l + LFp2(1 + --V1-
Proof. We have
F PP E, (x) (x) Fp2.E,
(z) -e))-Pa
FF,, M, (x) F Fu (x) Eu (x) Fp2. E. (x))
< Pm, E, (x) Fug E, (x) Fry (x) F Es (z)
(15)
16

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
Here,
(x)) - 22 (2)1 Eu [( + [ru]] Po..) + p22ill
Bu~~((.E [((x + pru) F(x + [22)]|
x Eu [ + (11)) F(x: + [22
Eu-N(o,E,)) [L M pI
LF |M1 122 E VO, ||
(+)) LF 111 Wio
V a w + vI arhiv
d
(.)n)
I LF 111 - M2l (V Em
+ v1 - ai a.
(*)**)
S LF 111 uel (vai + vI-ai)
(
S V2LF |m u2l:
(16)
where (*) holds from Lemma D.2, (**) comes from Lemma D.4, (***) is due to the fact that ||hı|| = 1 or h1 0, (****)
follows from Lemma D.I, and (*****) holds since SuPae(o, (Va + vI a) = 22.
Moreover,
FA E, (x) F2z M, (x))
Eu-N (x Lf + [z2u]]
- -E [F(x + p2lil|
x + u2
w + /2 - an11
w + u2vl - az 022 )
02
Euw.Wo...),, F x Man d
aa w + -2v1- agh1o - F pay d
log + p2v1 - - || (17)
F
x ped
d
where (*t comes from Lemma D.4. Here, from Lemma D.2,
F
x
+ 12
a w
#2V1 -
-
x + M2v a2 w + u2v1 - 02/24
<
LF
12
01
w
12211
- M22
w uav1 a2h2v
a2
< LF
P2
w
Aan
LF |2 - a2h20
LFP2
-
v |||| + LF12
V1-aa - -1- lol.
(18)
Moreover,
(x) S VI ai VI-
WI-aahy - VI-
(14) v1 an + V>(1-
= = vīv[ an.
(19)
where (*) is due to the fact that ||عح|| = or h and the fact that h2 || = 1 or h2 = 0. Moreover, (**) comes from the definition of or2.
17

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependeen Distributions
From (18) and (19),
a1
1221 1awi--ahip ashiv) - - H2y 02 + p2v1 a212y
F
x + Hov
LF U2
Iai
v02l |||| + LFF2(1+ a//ol
(20)
From (17) and (20), have
F Ei (x) - 22 2o (x)
LF
Vai
|1 LF + v7)11 a, ((..ll(.
Vd
Lr yai 002 1.pp2(1 + --v1-mm
(21)
where (+) follows from Lemma D.I. From (15), (16), and (21), we have
1F, (2) - Fg (x)) S V2Lr I - 121 + Lepalyai - vo2l + LFp2(1 + v-VVT -
Technical Lemma D.10. Suppose that F is Lipschitz continuous. For any Rd, μ Rso, and E E S the following holds.
F(x + p())
F(x - pm)
F(w pr)
FFmx(x)=>> =
E-'BuNNi0. -E
E "-'EE Eun
11
2/1
Proof. First, we show that, when f [F(y]e 2n (v-
dy < 00,
lim F(y)e zia (v (w-r) x/ "(y-a) 0, y (oC,...)))))
F(y)e zue (v-m)) ((y-x) 0.
lim y (0)
Assuming that the above does not hold, we derive a contradiction. Since
F(y)e a/a (V-= (y--) 2) # 0.
lim (c0.....))))))
there exist C1 E Ry & E RR and {yn ) such that yy - yn+ill 2 q and [F(yn)le -يي (v) =)E (2y, mm)
2 Ci for n
1, 1,..., 0o. Then, since F is Lipschitz continuous, there exist 0g E TR and 5 < such that FF(y)e e +/f =) (リ- 2
8 E + 8. 1. Then, 1 (F(y)ee - 2/ (v =j ((y-a) dy 2 En c2(26) = oc. It contradicts
C2 for
the fact that f (())e z ( '(y w) dy < co. Therefore,
lim F(y)e zi DJ -y =0. (00
(22)
Similarly,
F(y)e 2 (w- ((y- 0.
lim リ px
(23)
18

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
Let v (2 and y = we. Then, have
(+) k ʃ
V FF,,5())
V a puje 3=" "du
A Vyl(y)e ( "1 ((v-x)dy dy
1
Fly)e -
/ 1dt2k Fly)e 10 x/ (v-z) (-E ( (3 x)dy
(2)
1
F(y) Vy (e (リ- ( (リ-))/) ((v-0) dy
ud22k
3 (00,,,,,,
(!.*)
1ut2k
Σ-1
F(x + muje fuε "wuuddu
1 -
F(x + nm)
ue - juu='uud du
F(x + pm)
(24)
where (*) comes from the fact that F is Lipschitz continuous, (*#) is due to integration by parts, and (***) follows from (22)
and (23).
Moreover, since (1,,)(
p(x+uu)
(un-)((,.)))
F(a-uu) (-u)]
1 (
F(x uri)
(F))(()) -E E-EEE N(.
(25)
1
Then,
VFES(())
VF + F.F.,(())
2
F(w + pu)
F(x - ww)
E E Eu~)(
E
E
u
1
2
11
F(x (u)) - F(x mm)
= B-LB
2/
where (*) comes from (24) and (25).
Technical Lemma D.11. Suppose that Assumption 4.4 holds. Let Σ == 7 + (1 - hi for d E E Rd such that
La
|h|| = 1 or h = 0, and E (0, 1]. Then, for any a E Rd and E R
|V < 221
16a (d 6)s
5488(1 - -a)))
a²
d3
Proof. First, we show that (F(x) B [F(x)] u Σ ull...
Let = fg e J e
tudu. Since k
V E and Σ = -
In (fe-tu'ss'u uuuu du (2())
In(
2
Differentiating this identity in E-1 it follows from (Petersen al., 2008, (57)) that
2x Jz uu TuTe
1 Ta-Te-ju""
Ju ''
1 =
1
Σ,
2
2
where (+) holds since E is symmetric matrix. Thus, multiplying by VF(x)) from the right yields
uu TVF(xe J 'udu = EVF(x),
R
19

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
that is,
2 VF(x)= - - - / (F(a)) (u use u uau-uu udu (o. 1 uE-+u.
Then,
|V Bu (FF(x) u "ull"
Euu (F uu)- - F(x)) - (F(x + pm) (VF()) M M
Bun [F(x + uu) F(xx)) uu]
S
1 Eu-A((o.))
+ 2
(F(x + um) F(x) (VF(x) -u== u2]
#
0 2 /
1 E E. + mm) - F(x) vV u) '4]
+2
2
2 [F
Eu-Nio,))(F(
F(x) LVF(z) - 12
112
(m))
2
H3
3 21 (x))]
+ BunAN1..2)
|
|
11a
d2 H
21|VF
Eu-NNo,,)
E
2a²
(.)
Hp.
32a
6d
2/
1097661 a)3²) -a))3
2a²
d3
d 112
(d
6)3 d3
5488 aa)3
where (+) comes from Lemma D.10 and the fact that N [F(x) F(x)) - ((, [u] 0, (**) is
due to the fact that fx + pu) S F(x) + F(()) (wu) + 1 | 2 from Assumption 4.4, (**8) follows from Lemma D.5, and (****) comes from Lemma D.7.
Technical Lemma D.12. Suppose that Assumptions 4.2-4.4 44 holds. Let Σ := L + (1 hh T for E N, h E Idd such that ||l| h 0, and a E (0, 1]. Then, for any æ E Rd and μ > 0, the following holds.
F(x + pu) F(x nu)
E E,~,(
2p
8a² (d+ 4) 8(1 (11-a))233 a)(25 -23))223300)1111) / +2²
16a (d + 6)
5488 -0)))
S
d2
d3
Proof. Since F is -mmoohh from Assumption 4.4.
1
F(x + ym) < F(x) VF()) (mrU) + Hr ||
2
1
F(x (r)) > F(x) VF(x) (nU) ((u))
H || 2
Then, we have
F(x + pui) - F(x pm) = [F(x + pra)= - F(x)] + [F(x))
- F(x - [wn)
< (NV((z) u 422
+ [NVF(1)) u + /2 2
2 HF |ul2
H [||
2x) Tu u 1² 2211 HF 22l
(26)
20

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Depender Distributions
Similarly, since
1
F(x: + jul) F(a:) VF(x)
Hr p
2
F - S F(x) V=xx) ((r)) + Fr |ueel
2
we have
F(x + we)) - F(x - -ua) 2 22VF((x) u -rr
(27)
From (26) and (27).
(F(x + pm) F(x -mu))² S (2pVF((z) u+
T 1rrlHllll (2nVF(2)'uu u- -r 112333
-8y²(VF((x))
=)² (o)rF((()TT>>>>0000000> 2y H13 /u/1
(28)
Let p: = ( h. Then,
F(x wr) F(x ur)
(un
2/4
1 BunN( [[F(x + pu) - F(x -mx))² [|]]]
1112
(
( 22111 + 24 11(11111
4p²
(**)
Em--N10.1)).-110001)
2
(VP()) (V2 + v1 anv) 1) |V
21
a
w v1 -hh
ahv
+ +Eu-N(0.E)
4 H2
F
2
6
d
2
(***)
(22
(22(VF(0)) (VF(z) w) + 2(1 a)p²r?
( (20
|wol 12 2(1 a)1²²) 11
1e H3
32a 3)3
+ 10976(1-a))
2
d3
4a(1 a)) (VF(x) w0) 4(1 a)a 1 2 (VF(x) 22)
2 N(..T)),
d
16a (d+ + 5488(1-
+ + a))p'p
+ H²
d3
a
8a(1 - (((1aa)|VF(())
E B
d²
d
8(1 a)a
d
16a (d (488(1-a)})
+8(1 a)²p² Eu H
d3
(m0.e) 2
5
(d + http:///000--0o0100//////0/01100
Sa
d2
16a² (d + 6)3
+ 112 H2
+ 5488 -a))²
d
+ 8(1 31155)22 23a) V + 2 16a (d+ 6)3
+ 5488 a)3 a)²))
de (d 2)
V
F
1
2
d3
where (*) comes from (28), (**) is due to Lemma D.4, (***) follows from Lemma D.7 and the fact that || < 1, and (****) comes from Lemma D.1 and the fact that p = V (x)) (x) Th < [[F())]][ s [x))].
21

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Deeisien-eependent Distributions
D.2. Proofs of main lemmas and theorems in paper
Here, we prove the main lemmas and theorems in our paper by using the technical lemmas prepared in Section D.
D.2.1. PROOF OF LEMMA 3.2
Proof. From Lemma D.10,
P(x pw) - F(x we)
(x)) = E 10,
u
2p1
RelnDletwulss + pan,, {²)
D(e - pan, E2)
E ((.
2/
E E N(0
uI, u, [ ( M,,
,<)]]]
D.2.2. PROOF OF LEMMA 4.6
Proof. First, show that || + y + =12 < 3||21||
+ 31ul2 + 3|
The inequality of arithmetic and geometric means
yields, for any E Rd, y E Rdd and E Rdd
| + |
|
1 +
||
|| + ||00|
-< ||y/||
y |=|||=|| <
2 |
2
Then,
x + y + =|
||>||| | + |1 + 12=
2x
y
+ 2y
2 + 2x Tx
< || + |11l + || + ||| + 21 + 2||x||||
3 |
3 b11 + 3|
(29)
Here,
E.))((,)))
u. 1,,,221 221)
J=1
En f(x + +pu, (1.)
Σm f(x
mml g2.5) g
Eu
mm
2/
F(x + uu)
-F uu)
En f(x + nm, m.
F( + pA)))
u
2/1
21
1 Eg= f(x um, 22d) + F(x pm)
2p
(4)
F(x + um)
F(w
pm))
1 - f(x um E1.5)
F(x pr
Eu
3
u
BB ~
2p
Em f(x nmn, (2:)
F(x puu)
+3 -
u
2/
(4a)
F(x + pm)
F(x - -juus
3
30 4p2m [io
3E
u
Bu-N 1|u1
24
4p2m
($08)
F(xr + pm) - F(xx= - juZ))
12
30"
3E, <
2p²m²
(s000) 24n²
d
24(1 (6l1-)a1 a2) 23a)
( [F(x)| +322 H
16a (d 6)
d
5488 a)*)
+
22p2m'
3
22

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependent Distributions
where (*) follows from (29), (*#) follows from Assumption 4.1 and Lemma D.3, (***) is due to (12) in Lemma D.7, and (****) comes from Lemma D.12.
D.2.3. PROOF OF THEBRRM 4.7
Proof. From Lemma D.8, function Ppe. E. is H--ooothh. Then,
HF
E, (IX+1) S FR,, (ark) + V Pp E. (It)) (ax+1 -mk) +
a - =0
Fu (ook) 3V F,..E, (ork) " Hp
19
Here, let Ço := (ux, ) 162 رーرر (5k to the random vectors Ç(o.a). we obtain
1 1 )o=1) and Sio. = (So. Si,... , Taking the expectation with respect
E Ee (20++1)
Hrg
S 13sp Fr (mtk) FL.. (Txx) gt 2 ||
Hr
-EGooe-11 (x(x) - Fu, (Ix) TEc, [gx 11) +
Egg ||]9||] ((ox-11]
2
(2) EG Fr BV Hr. (Iba) Σ (ook) +
12H 1
FV.
(d + 4) FV
d²
[a 6)3
3
+ (1-) 230
+3
2744(1 - 0x6)3
d3
4
(30)
where (*) comes from Lemmas 3.2 and 4.6. Here, when 8% + 0, we have
V FF (ax) T E E. (ax) = and VF V...... (xx)
+
ah V E. (ax))l
2 and V V (2x)
When 83 = 0, we have
VF V
(xx)
Ev. V. E.
(xx) ond-11 VI E, (xx)
Therefore, from (30) and the fact that my 2 1,
Eco.. [F Ei (Ix+1))
12Hr3 a
E F Ee (2x) 3/ (xx)]]²+
(d 1)
d²
12H (1- 230, 230z
88 (a 32
6)3
+ 2774(1 - -cx)²)
3H 3Hr 4
d3
23

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
Rearranging the terms in the above inequality leads the following.
Band
E
VF (2x)
E c [F
En (xx)] - cp [F Hr. En (Ix++)]
(31)
1 a
4)² + 12/1 F 3 - c2) 23cux)
de
+ 3/ 3 3
(d + +6)
+ 2744(1 - oxs)*
d3
411
10, -11 [F Er Dz [x+)] + co. m| - Wr (x+++) + EpEtL (#+++1) - F Fu De41 (2 (xx++))
(d 12 ai
2)² + 12H F onx (2n))252300))) 230rx)
12
80 6)$
+ 2744(1-14 - o2a))) (1x))))a)))))))))))))))) 33p
33
d
411
$ Ec | En [xx)] + Bc || - P.E.I, (I+++1) - FFurI Ex11 (#k+1)] - Fu Exs (xx++)]
12
(d + 4)²+ + 12H 8 - (25 -030x)))
d2
[8 + 6)3 2744(1 axn + H2
r3r3202
d3
4
(4)
Eço 11 [F Ee (xxx) - (i |F E24i (Ix+1)] + ++V22 (2LF(uu mK+11) + LFHb+I(VaRH - vax)
+ LF + v9VV1 ag +
12H
ak (d 4)² +
a25 - 230x)) E E [[(x))
d2
2 +63
+ 2744 10l--ayp en)²) +
3Hp320²
(32)
d3
4
where (*) holds from Lemma 1.9 and the facts that uıu 2 Mk+1 and Og S 0x+1 for all k: O,...,T. T.
Here, since it follows from Lemma D.11 that
? S 2 E. (xx)]1 +
H2
(160 6)3
+ 5488(1 -ax)))
a
we have
3dp
(16xz 6)3
Bond ( [VF()))) < 23ord
+ 5488(1 (1 - ana)3)
d3
Taking the expectation with respect to the random vectors (jo,k-1), we obtain
Bopd
'B ca. [F(x)))
H3
(16a)(d+6)
< 23aad BBandd'ESon 11 V... (2x)
+ 5488(1
ax)3) -ax)))
ag
d3
< 2Bçax-11 (F (xxe) -2E
FREEI (x 1)] + 2 222LL(1 mc+1) + 2T (Vou+1 - Vas)
24HpB oZ (d 4)2
22F + 14vI-aa +
+ 24H 3² -ax)(2) 23aa)
Ecio. [1[VF(2)))11
&
88 (d 32
+ 2744(1 on)²))
3H 8o2
Hdp / /16af(d 6)3
d3 5488(1 oz)²
d3
24
ai
24

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Depender Distributions
where (*) follows from (32). Rearrange the terms in the above inequality, the following holds.
(Band-1 24H1 (d + 4)2
21Hr - (25 (1125-234m)) 233xz) [cpo.-1] [[VF(())11))
d2
S Gp.te ( Pur, (xx)] 21.00 [ Pet1.Ee11
(Ix+1)] +2/2Tr Mk+1) + 2IrMett vax)
80 [0 6)8 2744(1 - -ax)²
+ 22FF/K+111+ + vT)vI
ak + H3
d3
32p
H3 16a (d + 6)$
+ 2
5488(1 - ox)²)
(33)
O4k
d3
Here,
(4) T
2L vT)11 - ak 2
Σ
2LF + //1 (1-)0)
k=0
-1I + /7)VV 00 - 72
7
2LF + v7)vI-cn
(34)
1- 7
where (+) comes from the updating rule of og and the fact that μk S Mo for k 1....,T. T.
Let F mER F(x). Then, summing up (33) for 0 I k s T, we have
Σ Band 24Hr:Paa + 4)2
- 23cx)) (25
BGG..- [[V](
d²
k=0
2F no. Eo (m)) -2B Spm F
WTT Ertr (IT+1)) (T1(()+))) +
+2V2(10
11++1) + 88 [af 6)a
voo
2LF (1 + vJVV ag
+
6pg 3 B2
+ 2744(1 - -3x)))
1 g-
d3
T
022
Hd
16a (d + 6)3 + 5488(1 ax)²
+
+
2ph
Okk
d3
k=0
k=0
(*4)
Io (2o) 2F 2V/2(pp - MT+1) + 2L CooruooVaT-... VVr-i Vao) + 2L + vJ)1I-
2F
1-72
(8(d+ + 6)3
+ 2741 + +T++1) 311 + (T + 3dp 1)dpfdd 2p
16(d + 6)3
+ 6(T + H3
+ 5488) (35)
d3
d3
where (+) comes from (34) and Mu 2 ps for all k = 0........ T. The inequality (**) is due to that ummn S m4 for all l
1, T, 0 < Og I 0g < 1 for all k- == 0, ,,....,,, T, and (x)) = E. (F(x + pou)] 2 Eu- [F = F
for any x Rd. 1 2 0, and desitive-defimit matrix Σ E Rdd x Rd.
Here, we have 3 < 78E ( 2 for k- = 0, ,,...,T, T,
and
and 0 S og S o4 1 from the assumptions on B and the updating rule of og. Then,
Bon -
- a25 23ax)
2 Bood 1 24H (d 32
= BBod
2552)
and
2 Band 24H 2( (2)+++4+++ 25d²)
48H ((d + 4)2 + 25d2)
B0x
(36)
2d
25

---

Guided Zeroth-Order Methods for Stochastic Non-convex Problems with Decision-Dependee Distributions
Therefore, from the definition of wn.
ER. [= - -1 ) [[+))())
-110 -AHp: a2) 23(xr)))
2d I - 11t-://0000t01222//00444-331-111
- 23 B) V V[
13+00
4d Fno.Io(00)) Fa + V2I.(100 - WT+1) + (VTT-1 von) - LFHO(1 - (1 (1-72)
(+0)
(T + (1+1)3800
H3 8(d+ 6)3
+ 3d
+ H
116(d + 6)3
+
+ 2744
+ 5488
00
d3
1 0g
aB
d
O((1 (((1+M))1 1) (1
( 2 + (dd Mi),
where (*) comes from (36) and (**) follows from (35). Here, Mo (cdd-l,, Mmin @(cd=!) from the assumption. Moreover, since 3 min
18H 4250- 3d T we have
and
B = O(T (d and
5- 48Hr((d + 4)2 + 25d²)
+ +T O(d
and
Therefore,
En.Go. [
=0 ((1 ed -t( -
By setting = ( -6d4,, obtain
E [ E
Here, the sample complexity is 0(a"e-6d since ΣT (2m; + na) En 0(1) = O(T) = 0003e-6d4) where
2mg + ng is the number samples at the k-th iteration.
D.2.4. PROOF OF THEOREM 4.8
Proof. Since the proof Theorem 4.7 does not depend on the value of s Algorithm 1, the same iteration complexity holds for Algorithm 2. That is, by setting 0(a3e-0d')) we obtain ER.ço. F(x)(())) S 22 Then, the sample
complexity of Algorithm 2 is 0 since Σk-0mm 2mH Σt 0(1) = O(T) = e -dd)), where 2m, is the number of samples at the k-th iteration.
26


Reviews:
[{"review_id": "XcbF7419VC", "reviewer": "Reviewer_e6Wm", "summary": "This paper studies zeroth-order methods with partial gradient guidance for solving the performative prediction problem. Specifically, the proposed algorithm leverages the gradient information of the known function $f(x, \\xi)$ to refine the update direction. The authors establish a rigorous worst-case convergence bound and analyze the sample complexity. Simulation results are provided to validate the theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive suggestion.\nWe answer each of the questions in the ''Weaknesses'' and ''Experimental Designs Or Analyses'' sections.\n### Weaknesses.\n1. Motivation.\n\nThe motivation for our study is clear, and we clarify the positioning of our methods in relation to existing methods.\nFirst, as already mentioned in Section 2.2, the motivation of our method for the two-stage method by [Miller et al., 2021] is to find a stationary point without making strong assumptions about the distribution or loss function.\nSpecifically, in section 4.2 of [Miller et al., 2021], they assume that the distribution $D(x)$ (denoted $D(\\theta)$ in their paper) is included in the location-scale family, i.e. $D(x)$ needs to satisfy\n$$\\xi \\sim D(x)  \\Leftrightarrow \\xi := \\xi_0 + A x,$$\nwhere $\\xi_0$ is a random variable independent of $x$ and matrix $A$ is constant.\nThis implies that the randomness is **decision-independent**, which limits practical applications.\nFor example, in the multiproduct pricing (strategic classification) application in Section 5 of our paper, the demand (data) distribution does not satisfy this assumption.\nMoreover, [Miller et al., 2021] assumes that the function $f$ is strongly convex (see (A.3a) and (A.3b) in their paper).\nHowever, in the context of price optimization (machine learning), non-convex revenue (loss) functions are widely used.\nIn contrast, we develop our method under milder assumptions;\nour assumptions do not require strong convexity of $f$ or any specific form of the distribution $D(x)$.\nIn response to your comments, we will add these detailed explanations to Section 2.2.\n\nNext, the motivation for our method in relation to existing zeroth-order methods lies in leveraging the gradient information of $f$, as mentioned in the introduction section.\nIn existing methods,  $f$ is treated as a black box, and the gradient information is not used.\nHowever, in many applications, $f$ is a known function.\nThis study speeds up the existing zeroth-order methods by using the gradient information of $f$.\n\n2. Algorithm.\n\n**Definition of $D_R$.**\nIt is a probability distribution over \\{$1,2,\\dots,T$\\}.\nIn Algorithms 1 and 2, the iteration to terminate is determined probabilistically using this distribution.\nAs shown in Theorem 4.7, the convergence of our method can be guaranteed by setting $D_R$ as in the theorem.\nSuch termination schemes are common in stochastic optimization to ensure convergence guarantees.\nFor example, see (Ghadimi \\& Lan, 2013; Theorem 3.2).\n\n**Guidance for $\\hat{p}$.**\nTheoretically, the constant $\\hat{p}$ can be any natural number.\nThis is because we have derived the sample complexities of our methods in the worst-case for $h$, and $\\hat{p}$ only affects the partial gradient information $h$.\n(Details are in the response to reviewer 2's question (1).)\nOn the other hand, a future issue is to provide appropriate guidance for $\\hat{p}$ depending on the distance between the past and current iterates.\nThis is because as the distance increases, the past distribution may deviate significantly from the current one.\nIn response to your comment, we will add this content to the conclusion section as a future issue.\n\n3. Gradient Estimator.\n\nAs shown in line 14 of Algorithm 1, we proposed a rule that updates $\\alpha_{k+1} := 1-\\gamma (1- \\alpha_k)$.\nAs noted in lines 195-199 in the left column, this updating rule promotes a faster decrease in the objective value initially and reduces the bias of the gradient estimate $g_k$ in later iterations. The updating rule of $\\alpha_k$ is important to guarantee the theoretical convergence of our methods. (Details are in the response to question (1) of reviewer 2.) For the empirical setting of $\\gamma$ and $\\alpha_0$, if $\\alpha_0$ is near 1 or $\\gamma$ is too small, $\\alpha$ rapidly converges to 1, resulting in behavior similar to existing methods. We set $\\gamma=0.98$ and $\\alpha_0:=0$ to prevent this.\n\n### Experimental Designs Or Analyses.\n1. Evaluation of the gradient norm in the experiment.\n\nIn response to your comment, we will add figures that show the norm of the gradient. However, since we believe the function value better reflects the goal of the application, we will retain  Fig. 1 as it is.\n\n2. Response function of agents in strategic classification.\n\nWe calculated the optimal response of the agent by the following procedure: (i) calculate the cost required for each agent to be judged as positive (the cost is $0$ for agents that have already been judged as positive), and (ii) if the cost is less than the gain from being judged as positive, the agent will change its own feature values so that it is judged to be positive.\n\nThis setting does not satisfy the smoothness in Assumption 4.3. This is because the data distribution changes discontinuously at the point where the cost exceeds the gain for some agents. Despite this unfavorable setting for our methods, the experimental results show that they still perform well numerically.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the methods used in this paper are appropriate for the performative prediction problem, but the motivation is unclear, see Weakness part.", "theoretical_claims": "Yes, I have checked the proof of Theorem 4.7, and it looks fine to me.", "experimental_designs_or_analyses": "1. For the multiproduct pricing application:  In Fig. 1, the author plots the loss function as a metric. However, in Theorem 4.7, the convergence metric is the expectation of gradient. From the current figure, we cannot observe the convergence speed information.  \n\n2. For strategic classification with an unknown agents' cost function:  Regarding the setting with unknown $D(x)$, according to the best response function shown in line 301, right column, I wonder how to get $\\xi_F$ in closed-form solution in simulation and whether this settings satisfy smoothness assumption A4.3.", "relation_to_broader_scientific_literature": "In the zeroth-order methods literature for performative prediction, [Miller et al., 2021] and [Zrinc, 2024] consider the two-stage approaches, i.e., first estimate the shifted distribution and then optimize it. But neither of them use partial gradient information.", "essential_references_not_discussed": "All realted works are well discussed.", "other_strengths_and_weaknesses": "### Strengths:\n\n1. This paper is well written and easy to follow. Meanwhile, the proof is clearly presented.  \n\n2. Simulations are conducted to support the theorem.  \n\n### Weaknesses:\n\n\n1. **Motivation**: Could the authors clarify the positioning of Algorithm 1 and Algorithm 2 within the existing literature on performative prediction? Specifically, how do these algorithms compare to prior approaches?  If one only has access to the stochastic loss function $f(x,\\xi)$ and seeks to quickly find the performative optimal solution, the two-stage method in [Miller et al., 2021] may be a more natural choice. On the other hand, if only loss values are available, existing zeroth-order methods such as [Roy et al., 2022] could be used. Given these alternatives, what specific problem setting or advantages motivate the development of the proposed algorithms?  \n\n2. **Algorithm**: Could you explain the definition of the distribution $D_{R}$? For Algorithm 2, is there any theoretical guidance on the historical sample size $\\hat{p}$ to achieve better performance?  \n\n3. **Gradient Estimator**: In equation (6), the gradient estimator is affected by an important factor $\\alpha$. How should it be chosen properly in practice? Additionally, we would like to see its effect on convergence behavior.", "other_comments_or_suggestions": "I listed some typos in this paper:\n\n1. Line 298, 299: \"Table 2\" should be \"Table 1.\"  \n\n2. Line 1125, 1126: The expectation notation $E$ should be $\\mathbb{E}$.", "questions_for_authors": "See the weakness part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5b8FMAcCJp", "reviewer": "Reviewer_homv", "summary": "The authors explore zeroth-order methods to solve stochastic problems where the distribution of stochastic variables depends on the decision x. By incorporating partial information in the construction of gradient estimators, they demonstrate improved convergence rates compared to existing works.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable and constructive feedback.\n### Weakness.\n\n> The presentation of Assumptions in section 4.1 is dense and difficult to follow, and the purpose of Assumption 4.3 needs clarification since it appears only in the appendix. \n\nIn response to your comment, we will add the following explanations for each assumption:\n- Assumption 4.1 is required for approximating $F(x)$ by $f(x,\\xi)$ with sample $\\xi$.\nSince the objective function  involves random variables, such an assumption is essential to evaluate the objective value by its sample.\n- The purpose of Assumptions 4.2 and 4.3 is to guarantee the Lipschitz continuity of the objective function.\nIt is used to derive the properties of the Gaussian smoothing function. (See Lemma C.8.)\n- Assumption 4.4 is standard in convergence analysis, ensuring the accuracy of the first-order approximation via Taylor expansion.\nThis is because descent methods with (estimated) gradients can be seen as optimizing a first-order approximation of the objective function at each iteration.\n\n> Moreover, the paper heavily relies on the boundedness variance assumption 4.1. While this assumption relates to the $G$ constant in line (204), the constant sigma is not explicitly included in the complexity bound. This makes it difficult to compare the guided zeroth-order method with Liu et al.'s work, which depends on $G$.\n \nIn response to your comment, we will include $\\sigma$ in the expression of the sample complexities.\nWhile some studies (Iwakiri et al., 2022; Hikima \\& Takeda, 2024b) omit constants other than error tolerance $\\epsilon$ and dimension $d$ in their theorems, several studies (Perdomo et al., 2020; Mendler-Dunner et al., 2020; Ray et al., 2022) include such constants, and we agree that your suggestion is valid.\nIn this paper, including $\\sigma$ leads to a sample complexity of $O(\\sigma^2 \\epsilon^{-6} d^4)$.\n\nHowever, we argue that Assumption 4.1 is much looser than the assumption of constant\n$G:=\\sup_{x,\\xi}|f(x,\\xi)|$ in existing studies (Ray et al., 2022; Liu et al., 2024a).\nAssuming the existence of $G$, we cannot handle even a simple loss function.\nFor example, $G$ is unbounded even if $f$ is the squared error $f(x,(A,b)):=||A x-b||^2$, where $\\xi=(A,b)$.\nThis fact is a weakness in the one-point gradient estimator, which is also pointed out in (Hikima \\& Takeda, 2024b).\nIn contrast, Assumption 4.1 requires only that $F$ can be approximated by samples, which is a fundamental and minimal requirement; if $\\sigma=\\infty$, the objective value cannot be estimated by sampling, making such assumptions unavoidable.\n\n### Claims And Evidence and Essential References Not Discussed.\n> Compared to [1], the main improvement stems from replacing Assumption 3.2 with Assumption 4.1 and using two-point zeroth-order estimation. The authors should provide a clearer explanation of how partial information improves convergence compared to [1].\n\n> More discussion and comparison with Hikima \\& Takeda, 2024b is needed, such as which part of the algorithm contributes to the improved rate?\n\nCompared to (Liu et al., 2024a), the reason why $G$ does not appear in the sample complexities of our methods is that our methods use a two-point gradient estimator.\nThis improvement has already been made in (Hikima \\& Takeda, 2024b) and is therefore not the main contribution of this paper.\nThe main contribution is the difference from Algorithm 2 in (Hikima \\& Takeda, 2024b).\n\nOur contribution is two-fold: \n- We achieved a tighter convergence analysis compared to (Hikima \\& Takeda, 2024b) by modifying settings such as mini-batch size and step size.\n- We proposed zeroth-order methods incorporating the partial gradient information, without making any assumptions on the information or worsening the convergence rate.\n\nRegarding the second contribution, please see our responses to reviewer Vnz2's question (1) for more information.\n\n### Theoretical Claims.\n\n>  According to the proof from lines 1284 to 1303, when $\\alpha_0=1$ (meaning no partial information is used), there is no negative impact on the theoretical results.\n\nYou are right. \nSince we consider the worst case for the partial gradient information $h$, the same sample complexity can be achieved with $\\alpha_0=1$.\nPlease see our responses to reviewer Vnz2's questions (1) and (8) for more information.\n\n### Experimental Designs Or Analyses.\n\n> For the experimental validation, it would be valuable to include an experiment running Algorithm 1 with scaled gradient (setting \n in ZO-TG) to demonstrate the effectiveness of incorporating partial information in gradient estimation.\n\nIn the experiments, we already used scaled gradients in ZO-TG by adjusting the step size $\\beta$. \nSee lines 532–536 for details.\nCompared to GZO-NS and GZO-HS, the updating distance in ZO-TG is scaled by reducing the step size by $d^{-1/2}$.\nSorry for the confusion. \nWe will clearly state in the experimental section that the scale of each method is aligned.", "claims_and_evidence": "Compared to [1], the main improvement stems from replacing Assumption 3.2 with Assumption 4.1 and using two-point zeroth-order estimation. The authors should provide a clearer explanation of how partial information improves convergence compared to [1].\n\n\n[1] Haitong L I U, Qiang L I, Wai H T. Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data[C]//Forty-first International Conference on Machine Learning.", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "I briefly go over the proof of main result in the last section. According to the proof from lines 1284 to 1303, when $\\alpha_0 = 1$ (meaning no partial information is used), there is no negative impact on the theoretical results. In fact, the results are slightly better since both the first and last terms in line 1290 decrease.", "experimental_designs_or_analyses": "For the experimental validation, it would be valuable to include an experiment running Algorithm 1 with scaled gradient (setting $\\Sigma_k=I_d/d$ in ZO-TG) to demonstrate the effectiveness of incorporating partial information in gradient estimation.\n\n\nThe legend box obscures a significant portion of the figure, making it difficult to verify the authors' claim that a small $\\alpha$ promotes a faster initial decrease in the objective value. Please relocate the legend box outside the figure.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "More discusssion and comparison with Hikima & Takeda, 2024b is needed, such as which part of the algorithm contributes to the improved rate? This should be clarified in the main file", "other_strengths_and_weaknesses": "**Strength:**\n\nThe paper constructs a central difference type gradient estimator, which proves superior to the result in previous work (Hikima & Takeda, 2024b), with better complexity dependence on $d$. Additionally, incorporating partial information into the covariance matrix is an innovative approach that shows promising results in the experiments.\n\n\n**Weakness**\n\nThe presentation of Assumptions in section 4.1 is dense and difficult to follow, and the purpose of Assumption 4.3 needs clarification since it appears only in the appendix. Moreover, the paper heavily relies on the boundedness variance assumption 4.1. While this assumption relates to the $G$ constant in line (204), the constant sigma is not explicitly included in the complexity bound. This makes it difficult to compare the guided zeroth-order method with Liu et al.'s work, which depends on G.\n\n\nMinor:\n\n- The range of $\\alpha_0$ is incorrect in both Algorithm 1 and Theorem 4.7. According to the proof, $\\alpha_0$ should be in (0,1] rather than [0,1).", "other_comments_or_suggestions": "NA", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jsB3MZ4I4Z", "reviewer": "Reviewer_Vnz2", "summary": "This work proposes new zero-th order methods for nonconvex performative prediction problem (i.e. optimization with decision-dependent distribution) which improve the theoretical sample complexity of the state of the arts when the function variation $G=\\sup_{x,\\xi}|f(x,\\xi)|$ is large compared with the dimensionality of the decision variable. The experimental results also demonstrate faster convergence of these new methods.\n\n## update after rebuttal\nReviewer Vnz2 is satisfied with the authors' responses and keeps rating 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for positive comments and constructive suggestions.\n\n### Questions For Authors.\n\n**(1):** Since we make no assumptions on $h$ except that it is normalized, \nthe sample complexities of our methods are derived in the worst-case scenario for $h$.\nIn this case, by letting $\\alpha_k \\to 1$, as in our Algorithms 1 and 2, the effect of $h$ (, which is adverse in the worst-case scenario) is reduced, allowing us to achieve the stated sample complexity.\nFor Lemma 4.6, note that $L_f \\ge ||\\nabla F(x)||$; the upper bound is smaller when $\\alpha=1$, unless $d$ is very small.\nTherefore, there is no trade-off in the worst-case scenario.\n\nAs noted in ``Claims And Evidence and Essential References Not Discussed'' in the response to reviewer homv, our contributions are: (i) an improved sample complexity over (Hikima \\& Takeda, 2024b) through tighter convergence analysis, and (ii)\nthe introduction of partial gradient information $h$ without degrading the sample complexity, even in the worst-case scenario for $h$.\nRegarding (ii), (Maheswaranathan et al.,2019) assumes a confidence level for the partial gradient information ($\\rho$ in Section 3.3 in their paper) and establishes a trade-off between the unbiasedness and variance of the gradient estimator.\nIn contrast, we make no such assumptions on $h$, yet successfully construct methods that preserve sample complexity.\n\nWe deliberately avoid assuming any correlation between \n$h$ and the true gradient because we adhere to the existing problem setting (Perdomo et al., 2020; Mendler-Dunner et al., 2020) where $D(x)$ is unknown for application requirements.\nIf we assumed such correlation, the weight of first term in (3) would have to be known, which requires information on $D(x)$.\nMoreover, to the best of our knowledge, our paper is the first study to apply the concept of guided evolutionary strategy to problem (P). \nThus, our goal is to first establish a highly general method under minimal assumptions.\nWe believe our convergence analysis lays a foundation for future work that makes additional assumptions tailored to specific applications.\n\n**(2):**  You are correct that the scales differ between Eqs. (2) and (6).\nIn Eq. (2), when $u$ is sampled from the unit sphere, it is common to include $d$ in the numerator;\nwhen $u$ is sampled from a Gaussian distribution, $d$ is typically not included.\nThis is done to align the scale of the gradient estimator with that of the true gradient (see [1], Eqs. (2.14) and (2.33)).\nAlthough we did not explicitly specify the distribution of $u$ in Eq. (2), we will remove $d$ from the numerator since we use a standard Gaussian distribution as an example.\n\nIn Eq. (6), the scale is aligned with that of the existing study (Maheswaranathan et al., 2019).\nAlthough multiplying the right-hand side of (6) by $d$ would match the scale in (2), we used this scale to facilitate comparison with the previous study.\n\n**(3):** $\\mathbb{R}^d$ is correct. Thank you for the comment.\nWe set $d=10$ to match (Hikima \\& Takeda, 2024b).\n\n**(4):** Tables 1 and 2 show the mean and standard deviation of the metric at the final iteration across 20 problem instances. \nTherefore, each value in the table does not represent the result of a single problem instance.\nIn Section 5.1, ''Table 2'' should be ''Table 1.''\nWe apologize for the typo.\nIn Table 1, the data ID corresponds to the week of data used.\nTherefore, ``data ID`` and ``date`` in Table 1 represent the same information.\nTo avoid confusion, we will remove the ``data ID`` column from Table 1. \n\n**(5), (6), and (7):**\nYou are correct in all comments. Thank you.\n\n**(8):** The same sample complexity can be derived when $\\alpha_k=1$ for all $k$.\nIn other words, the results of Theorems 4.7 and 4.8 hold for any $s$ (and normalized $h$).\nThis is because we performed worst-case analysis on $s$ (and $h$), as described in our response to (1).\n\n**(9):** \nThank you for the valuable suggestion.\nIn the proof of Lemma C.12, replacing $L_F$ with $||\\nabla F(x)||$ does not yield tighter result.\nHowever, we realized that it simplifies the proof.\nSpecifically, the left side of equation (29) becomes \n$$\\left(\\beta \\alpha_k d^{-1} -\\frac{24 H_F\\beta^2 \\alpha_k^2 (d+4)^2}{d^2}-24H_F\\beta^2(1-\\alpha_k)(25-23\\alpha_k) \\right) E_{\\zeta_{[0,k-1]}} \\left[||\\nabla F(x_k)||^2\\right],$$ \nand the sixth term on the right side (i.e., $24H_F\\beta^2(1-\\alpha_k)(25-23\\alpha_k) L_F^2$) is eliminated.\nThis shortens the right-hand side of (29), and also makes (31) unnecessary.\nThen, if we set \n$$\\beta:= \\min \\left(\\frac{\\alpha_0 d}{48H_F( (d+4)^2 + 25d^2)},T^{-\\frac{2}{3}} d^{-\\frac{1}{3}} \\right),$$ \nTheorems 1 and 2 hold.\n\n### Essential References Not Discussed.\n\nWe will add these references in Section 2 and clarify the differences from our study.\n\n[1] Berahas, Albert S., et al. ``A theoretical and empirical comparison of gradient approximations in derivative-free optimization.\" Foundations of Computational Mathematics 22.2 (2022): 507-560.", "claims_and_evidence": "The claims above are well supported by theorems and experimental results.", "methods_and_evaluation_criteria": "The proposed zero-th method looks reasonable but the advantage of using guidance is still not intuitive and clear, as will be elaborated later. In the theoretical results, using the gradient norm as the evaluation metric is standard and reasonable. In the experiments, the evaluation metrics including objective function value, classification accuracy and AUC are also standard and reasonable. The experiment scenarios are good since they fit the studied performative prediction problem and directly come from applications.", "theoretical_claims": "I checked the proof of Lemmas C.2, C.4, C.5, C.7, C.10, C.11, C.12, 3.2, 4.6 and the general proof logic of Theorems 4.7 and 4.8, and did not find any mistakes.", "experimental_designs_or_analyses": "The experiment scenarios are good since they fit the studied performative prediction problem and directly come from applications. The evaluation metrics including objective function value, classification accuracy and AUC are standard and reasonable. The basic information for reproducibility is clear to me, including the objective function, data distribution, algorithms and their hyperparamter choices. The results also demonstrate the faster convergence of the proposed methods than that of the existing methods.", "relation_to_broader_scientific_literature": "This work is among the very few papers on theoretical complexities to converge to a stationary point of the objective function (instead of the performative stable point as an approximation), and improves these complexities using a new zero-th order gradient estimator when the function variation $G=\\sup_{x,\\xi}|f(x,\\xi)|$ is large compared with the dimensionality of the decision variable.", "essential_references_not_discussed": "[1-5] on convergence results of performative prediction are not cited. \n\n[1] Li, Qiang, and Hoi-To Wai. \"Stochastic optimization schemes for performative prediction with nonconvex loss.\" Advances in Neural Information Processing Systems (2024): 8673-8697.\n\n[2] Khorsandi, Pedram, et al. \"Tight Lower Bounds and Improved Convergence in Performative Prediction.\" OPT 2024: Optimization for Machine Learning. \n\n[3] Izzo, Z., Ying, L., and Zou, J. How to learn when data reacts to your model: Performative gradient de- scent. In Meila, M. and Zhang, T. (eds.), Proceed- ings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 4641–4650. PMLR, 18–24 Jul 2021\n\n[4] Roy, A., Balasubramanian, K., and Ghadimi, S. Projection- free constrained stochastic nonconvex optimization with state-dependent markov data. In Advances in neural information processing systems, 2022.\n\n[5] Mehrnaz Mofakhami, Ioannis Mitliagkas, and Gauthier Gidel. Performative prediction with neural networks. In International Conference on Artificial Intelligence and Statistics, pages 11079–11093. PMLR, 2023.", "other_strengths_and_weaknesses": "Strengths: This work studies an emerging and significant problem called nonconvex performative prediction (i.e., optimization with decision-dependent distribution), with important applications. There are only few existing works on theoretical complexities to converge to a stationary point of the objective function (instead of the performative stable point as an approximation), and this work improves these complexities using a new zero-th order gradient estimator in the case of large function variation $G=\\sup_{x,\\xi}|f(x,\\xi)|$ compared with the dimensionality of the decision variable. The experiments are application-driven, clear, reproducible and demonstrate the faster convergence of the proposed algorithms. I can understand the clear presentation well. \n\nWeaknesses: The major weakness is that the intuition and benefits of using the gradient guidance $hh^{\\top}$ in Eq. (6) are not clear, especially given that the proof of Theorem 4.7 does not depend on $s$ and thus $h$. This major weakness corresponds to my questions (1) and (8) in \"Questions For Authors\". Some works on performative prediction are not cited as listed above. Some other details are to be clarified as listed below.", "other_comments_or_suggestions": "(1) You could stress your contribution in the abstract that your theoretical sample complexity improves the state of the arts in the case of large function variation $G=\\sup_{x,\\xi}|f(x,\\xi)|$ compared with the dimensionality of the decision variable. \n\n(2) You could cite the works listed in \"Essential References Not Discussed\" above, and compare (Liu et al., 2024a) with yours in terms of setting and complexity.  \n\n(3) You may mention the name \"performative prediction\" of this optimization problem. \n\n(4) You could use \"an unbiased\" instead of \"the unbiased\" right before Eq. (3).", "questions_for_authors": "(1) Could you provide intuition why using the guidance $hh^{\\top}$ in Eq. (6), and the benefit of using $\\alpha_k\\to 1$ in Algorithm 1? For example, can Lemma 4.6 imply that the variance of the stochastic gradient is small if $\\alpha\\approx 0$ for large $||\\nabla F(x)||$, and $\\alpha\\approx 1$ for small $||\\nabla F(x)||$ (usually near the final iterates)? In this way we balance bias-variance trade-off? \n\n(2) The gradient estimator (2) has Gaussian variable $d{\\bf u}$ with covariance $d^2I_d$, while in Eq. (6), the first part is $\\frac{I_d}{d}$. Why is there a such scale difference in $d$? \n\n(3) At the beginning of Section 5.1, should $x\\in\\mathbb{R}^d$ instead of $x\\in\\mathbb{R}^n$? What is the value of the dimensionality $d$ and $\\theta_i$ for the price experiment? \n\n(4) Do Tables 1 and 2 involve only the final iterate of each problem instance? You could explain that in the caption. Near the final of Section 5.1, should \"Table 2\" be changed to \"Table 1\"? In Table 1, does each data ID correspond to a problem instance? If yes, why not using data IDs 1-20? \n\n(5) In Lemma C.2, should it be $L_F=L_x+\\theta L_{\\xi}$? \n\n(6) In the proof of Lemma C.10, what does $n$ mean? Should it be changed to the dimensionality $d$? Also, (21) can directly imply (22) by replacing $u$ with $-u$ as they follow the same distribution $\\mathcal{N}(0,\\Sigma)$. \n\n(7) In the proof of Lemma 3.2, the second $x+\\mu u$ in the second row could be changed to $x-\\mu u$. \n\n(8) In the proof of Theorem 4.7, what will be the complexity result if $\\alpha_k=1$? Since the proof does not depend on $s$, what if we use arbitrary $s$? \n\n(9) In the proof of Lemma C.12, if we replace all $L_F$ with $||\\nabla F(x)||$, will this yield tighter result? It is fine if there is not enough time to explore this question in the discussion period.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "osgiP6I2NY", "reviewer": "Reviewer_DqGa", "summary": "This paper a new zero-order optimization algorithm for a new algorithm for a special optimization problem. The theoretical results show the proposed method converge to the stationary point and the step of steps to converge is also provided. The covariant matrix as estimated is a type of CMA-ES method (Eq. 6).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the general appreciation of our work as well as constructive comments.\n\n### Questions For Authors.\n\n**1:** If the distribution $D(x)$ does not change significantly with respect to $x$, GZO-HS, which uses samples from past iterations, is likely to perform better.\nThis is because the distribution $D(x_i \\pm \\mu_i u_i)$ at past iteration $i$ is similar to the current distribution $D(x_k)$, improving the reliability of past samples.\nConversely, when $D(x)$ varies greatly with $x$, GZO-NS, which leverages current partial gradient information, tends to outperform due to its increased accuracy in reflecting the current distribution.\n\n**2:** Since we were unable to ascertain the exact subject of your Lipschitz constant, we interpreted your question as follows. \nPlease let us know if our understanding is incorrect:\n\n``Is it easy to compute a constant that bounds $\\theta$ in Assumption 4.3?\nIt is better to calculate this constant directly rather than relying on the assumption on the Wasserstein distance.\"\n\nTo find such a constant ($\\theta$ or higher) that makes Assumption 4.3 valid, we must obtain samples from $D(x)$ at all $x$ since $D(x)$ is unknown, which is impractical.\nMoreover, without Assumption 4.3, such a constant may not exist.\nFor example, consider a discrete distribution $D(x)$ over $\\xi \\in$ {$0,1$}, where $\\xi=0$ with probability $1$ if $x > y,$ and $\\xi=1$ with probability $1$ if $x \\le y$.\n(This setting corresponds to the situation where the seller determines the price $x$ of one product and the buyer buys it ($\\xi=1$)  with probability 1 if the price $x$ is less than $y$.)\nIn this case, for any $\\theta>0$, there exists $\\epsilon>0$ such that $W(D(y), D(y+ \\epsilon)) > \\theta \\|\\epsilon\\|$.\nTherefore, $\\theta$ in Assumption 4.3 does not exist.\nThis is due to the discontinuity of the probability distribution $D(x)$.\nHence, Assumption 4.3, which imposes continuity on $D(x)$, is necessary.\n\n**3:** Since Fig. 1 shows convergence in a single instance, we did not include error bars.\nTo add error bars to Fig. 1, we would need to show results averaged over multiple instances.\nHowever, when describing averaged results, it becomes difficult to understand how the methods converge.\nFor example, even a method that decreases the function value **non-monotonically** may appear to decrease it **monotonically** when averaged values are presented.\nFor this reason, we have included the convergence of each method for one instance in the figures and summarized the statistical information in tables.\nNote that Tables 1 and 2 include that not only single-dimensional results of performance (i.e., average) but also measures of variation (i.e., standard deviation).\n\nOn the other hand, since each table shows the statistical results at the final iteration, it is currently not possible to see the statistical results during the iterations.\nTherefore, we will add the figures that include averaged curves and error bars across multiple instances to the appendix.\n\n**4:** Although our baselines are based on recent studies (Ray et al., 2022), (Hikima & Takeda, 2024), and (Liu et al., 2024a), they fail to converge for different reasons: \n- **ZO-OG** suffers from high variance and instability at each iteration. While increasing the number of samples $m_k$ may improve stability, it would also increase total sample size.\n- **ZO-OGVR** and **ZO-TG** do not include partial gradient information in the update direction $u$, which delays convergence.\n\nIf you have other baselines, we would be happy to add them.\n\n**5:** We adopted the loss function used in (Levanon \\& Rosenfeld,\n2021, Section 4)) in order to align our experimental setup with that of the existing study.\nMoreover, cross-entropy is a widely used and standard loss function for binary classification.\nWe could have tried other loss functions in our numerical experiments, but we preferred to vary the coefficient $\\gamma$ of the agent's cost function to see the performance of the proposed method for different probability distributions (which depends on $\\gamma$).\nHowever, our method is applicable to other loss functions if they are differentiable.\n\n### Other Comments Or Suggestions.\n\n**1:**\nWe consider 5488 to be an appropriate coefficient.\nThis large number arises from the sixth power of the expected value of $u$ in Eq. (12) of Lemma C.7.\nLook at the equation transformation in lines 697 to 708.\nIn the first inequality, the norm is decomposed, where number 32 occurs in the coefficients.\nFurthermore, in the third inequality, from (Nesterov \\& Spokoiny, 2017, Lemma 1), i.e., Eq. (10) in our appendix, number $7^3$ appears in the coefficients.\nThese transformations  account for the magnitude of this constant.\n\n**2, 3, and 4:**\nThank you for the multiple suggestions about the description. \nWe will correct them accordingly.\n\n### Essential References Not Discussed.\nWe will cite these references and clarify the differences from our study.\nThank you for the suggestion.", "claims_and_evidence": "This paper proposed two methods in zero-order optimization with decision-dependent distributions. All results are well validated by theoretical proofs and simulations.", "methods_and_evaluation_criteria": "The using evaluation criteria are training loss, testing loss and AUC. All are all pretty standard criteria.", "theoretical_claims": "This paper proposed two main theorems, .", "experimental_designs_or_analyses": "1. The testing problems multiproduct pricing and strategic classification are a bit simple. Consider using more complex realworld problem. \n\n2. Why the other three methods perform so poorly. Are these methods fair benchmarks?\n\n3. Where the the error bar in Figure 1?", "relation_to_broader_scientific_literature": "This paper is related to zero-order optimization method as proposed by Powell.", "essential_references_not_discussed": "1. Z. Zhang, Scalable Derivative-Free Optimization Algorithms With Low-Dimensional Subspace Techniques, arXiv:2501.04536, 2025 [pdf]\n\n2. T. M. Ragonneau and Z. Zhang, PDFO: A Cross-Platform Package for Powell’s Derivative-Free Optimization Solvers, Math. Program. Comput., 16:535–559, 2024 [pdf]. Consider compare with some zero-order methods in this lib.", "other_strengths_and_weaknesses": "1. The theoretical results in this paper are strong. \n\n2. The notation section is clear, which is admirable.\n\n3. The related work regarding to Decision-Dependent Distributions is very informative.", "other_comments_or_suggestions": "1. Lemma 4.4, the constant 5488 is strange. Is 5488 too large?\n\n2. Is using **e** as an all vector standard? It is usually used as **1** in previous literature.\n\n3. The notation $\\gamma \\in R_{>0}$ is a bit too complex. Consider using $\\gamma > 0$.\n\n4. In Table 1, the data information is not necessary and takes too much space.", "questions_for_authors": "1. For some tasks, GZO-NS performs better and some tasks GZO-HS perform better. Why? Is there a statement which algorithm will be better under certain condition?\n\n2. Is assumption  4.3 proper? I think for Wasserstein distance, it is easy to bound the lipschize constant. So it is better to calculate this constant directly rather than using an assumption. \n\n3. Consider adding an error bar in experiments.\n\n4. The testing problems are too simple and the benchmarks methods have not converged. What is the main reason?\n\n5. Line 282 right. Why only this loss function f is considered, will other functions also work?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_flag": "Flag this paper for an ethics review.", "ethics_expertise_needed": ["Discrimination / Bias / Fairness Concerns", "Other expertise"], "ethical_review_concerns": "NA."}}]

Author rebuttal:

Meta-review: This paper studies a stochastic optimization problem with decision dependent distribution and proposes a guided 0-th order algorithm for it. By extending the idea from [Mahewaranathan et al., 2019], this paper suggests to guide the 0-th order estimate of gradient by designing the covariance matrix of the random perturbation vector to accelerate convergence. Both theoretical rates and numerical experiments support the efficacy of this approach. 

In the intial reviews, most of the reviewers found the technical contributions to be solid and provides valid improvements over prior works such as (Hikima & Takeda, 2024b) and (Liu et al., 2024a). Some of the concerns on the motivation and comparison to prior works have been resolved during the author-reviewer discussion phase. As such, the reviewers are in consensus that the paper can be accepted. 

In the final version, the authors are suggested to implement the promised changes in their rebuttal.
Decision: Accept (poster)