Zeroth-Order Gradient Estimators under Decision-Dependent Noise

arXiv:2510.24929 · math.OC · Submitted 2025-10-28 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: We're looking at the paper: "Zeroth-Order Gradient Estimators under Decision-Dependent Noise".

Emmy: Here's the gist of the paper. Zeroth-order gradient estimators that average over multiple directions achieve the lowest sample complexity for stochastic optimization problems with unknown decision-dependent distributions The attained sample complexities improve those of existing zeroth-order methods in the problem setting that allows nonconvexity and unboundedness of the objective function Problem Formulation and Context The paper studies a stochastic optimization problem with unknown decision-dependent distributions, formulated as min x∈Rd F(x):= Eξ∼D(x)

f(x, ξ): This problem is the generalized problem for the classical stochastic problem min x∈Rd Eξ∼D

f(x, ξ): The formulation (1) is also referred to as the performative prediction problem emphasizing that the data-generating process adapts to the deployed decision This setting is important in applications such as pricing and strategic classification where demand or agent features depend on the chosen decision x Gradient Estimator Comparison The authors investigate various gradient estimators, including one-point, two-point, coordinate-wise directions, directions sampled uniformly from the unit sphere, and Gaussian distribution directions They conduct a unified sample complexity analysis across these different gradient estimators under a setting where problem (1) is nonconvex and the objective function is generally unbounded The key finding is that averaging over multiple directions, whether uniformly from the unit sphere or from a Gaussian distribution, achieves lower sample complexity than coordinate-wise directions Theoretical Results on Sample Complexity The theoretical analysis yields three key findings regarding the performance of different gradient estimators (a) For gradient estimators based on random directions, using more than one direction per iteration (N > 1) effectively suppresses the error between the gradient estimator and the true gradient (b) Averaging over multiple directions, sampled either uniformly from the unit sphere or from a Gaussian distribution, achieves lower sample complexity than that of coordinate-wise directions (c) After appropriately scaling the smoothing parameters, gradient estimators using directions uniformly distributed on the unit sphere and those using Gaussian directions yield equivalent estimation error relative to the true gradient Specifically, coordinate-wise estimators achieve O(d3ε−6) or O(d5/2ε−5), while random-direction estimators achieve O(d2ε−6) or O(d2ε−5) Empirical Validation and Conclusion Simulation experiments on multiple products pricing and strategic classification applications show that zeroth-order methods employing gradient estimators with directions following a Gaussian distribution or directions uniformly sampled from the unit sphere achieve superior performance under the studied assumptions The results are consistent with the theoretical analysis, demonstrating that random-direction estimators outperform coordinate-wise ones The paper concludes that gradient estimators that average over multiple directions (N > 1), either uniformly from the unit sphere or from a Gaussian distribution, achieve the lowest sample complexity and demonstrate stronger empirical performance under their assumptions Comparison with Prior Work The results reverse the conclusion of prior work by showing that when considering unbiased stochastic noise, increasing the number of random directions N allows for simultaneous reduction in both approximation error and variance from randomness This contrasts with previous studies that assumed biased noise, where increasing samples could not reduce the bias term The comparison shows that random-direction estimators are more effective than coordinate-wise estimators in this setting The authors also note that the performance of ZO-GA and ZO-SPH perform nearly identically, suggesting they are both highly effective methods Future Directions A direction for future research is to incorporate more advanced acceleration techniques such as momentum schemes into the framework to further enhance convergence properties for problem (1) This extension may improve the convergence rates of zeroth-order methods in this challenging setting The paper also notes that the current setup violates the smoothness requirement in Assumption 2 and 3 due to discontinuities in decision-dependent distributions, suggesting a need for methods robust to such violations The authors suggest incorporating momentum schemes from

Huang et al., 2022: into this framework The paper also suggests that the performance of ZO-GA and ZO-SPH is lower in experiments because the problem does not satisfy assumptions 2 and 3, highlighting the importance of these assumptions for theoretical guarantees The authors also note that the distribution is used only to generate sample demand in experiments, meaning they do not exploit any oracle access to D(x) The paper concludes by showing that both gradient estimators exhibit similar properties by scaling the smoothing parameter µ Experiments and Applications The authors conducted experiments on multiproduct pricing and strategic classification applications using semi-synthetic data In the pricing application, ZO-GA and ZO-SPH tend to achieve higher performance than ZO-CO and ZO-OG because coordinate-wise methods exhibit a greater distance between the gradient estimator and the true gradient In the strategic classification application, both ZO-SPH and ZO-CO achieved stronger performance overall The experimental results confirm that methods with lower theoretical sample complexity, like ZO-GA and ZO-SPH, tend to achieve higher performance in practice The experiments show that the objective value is reduced more sharply by ZO-GA and ZO-SPH compared to other methods The final conclusion is that random-direction estimators dominate the coordinate-wise estimator in terms of sample complexity and empirical performance under the studied assumptions References A.

Ada: S.

Emmy: Berahas, L.

Ada: Cao, K.

Paper summary: Ada: We’ve just covered the core of "Zeroth-Order Gradient Estimators under Decision-Dependent Noise." The authors are Yuya Hikima and Akiko Takeda, and they set out to unify the sample complexity analysis for various gradient estimators in this tough optimization setting >

Emmy: They proved that gradient estimators that average over multiple directions—whether uniformly from the unit sphere or from a Gaussian distribution—achieve the lowest sample complexity among existing zeroth-order methods when the objective function is nonconvex and potentially unbounded >

Kolya: What does this mean for us who are just trying to solve these kinds of problems in real applications? Is this a big step forward for how we approach derivative-free optimization?

Ada: It means that if you have a problem where the distribution of your data changes depending on the decision you make, you should consider averaging over multiple directions because it gives you the best theoretical bound on how many samples you need >

Emmy: The paper concludes that these random-direction estimators are better than coordinate-wise estimators in terms of both sample complexity and empirical performance under the assumptions they studied >

Kolya: So, to put it simply, if you’re stuck in a situation where your data is weirdly shaped by your choice, sampling randomly across multiple directions is the most efficient way to gather enough information >

Ada: That’s right. The paper emphasizes that these random-direction estimators outperform coordinate-wise ones because they effectively suppress the error between their gradient estimate and the true gradient >

Emmy: It also noted something interesting about prior work, where increasing samples couldn't reduce the bias term when dealing with biased noise, but this paper reverses that conclusion by showing that increasing directions can simultaneously reduce both approximation error and variance from randomness >

Kolya: That's a fair point. So the implication is that we shouldn't just look at the noise level, but how we structure our search around it >

Ada: Exactly. And for future work, they mentioned incorporating acceleration techniques like momentum schemes to see if they can further improve convergence properties for this problem class >

Emmy: It also flagged a limitation, which is that the current setup violates assumptions two and three because of discontinuities in those decision-dependent distributions >

Kolya: So even with these good results, the authors are telling us what's missing—that we need methods that can handle those sudden jumps in data behavior >

Ada: That’s it for this look at "Zeroth-Order Gradient Estimators under Decision-Dependent Noise." We've seen how averaging over multiple directions gives the best complexity bound for these difficult problems >

Conclusion: Ada: So we're wrapping up this look at "Zeroth-Order Gradient Estimators under Decision-Dependent Noise." Basically, this paper is showing how to make these gradient estimators work when the data changes based on what you choose to do.

Emmy: It’s about taking a problem where the data generating process adapts to your decision, like in pricing or classification, and finding a way to estimate that gradient without knowing exactly what that distribution is.

Kolya: The main thing they're proving is that averaging over multiple directions—whether you pick those directions randomly from a sphere or use some other random method—gives you the best theoretical guarantee on how many samples you need.

Ada: Exactly, so we're looking at sample complexity, which just means figuring out the minimum number of data points required to get a reliable answer.

Emmy: The authors found that these random-direction methods beat coordinate-wise methods because they handle those tricky, non-convex and unbounded objective functions better when the data isn't smooth.

Kolya: It’s interesting because this reverses what some older research suggested about how noise affects things; they showed that adding more random directions actually helps reduce both the error and the randomness at the same time.

Ada: That’s a big implication for anyone using these methods in practice, meaning if your problem has that decision-dependent noise, you should definitely try averaging over multiple directions instead of just one fixed direction.

Emmy: And while they show these random estimators are theoretically superior, they also pointed out that the setup itself has some rough spots because the data distribution can have sudden jumps where it's not smooth.

Kolya: So for future work, they’re looking at adding things like momentum schemes to see if those acceleration techniques can help fix those limitations in the setup.

Ada: Right, so they’ve set a very strong benchmark with these results showing that random-direction estimators are the way to go for getting the tightest bounds on sample size.

Emmy: But we still have to keep an eye on those assumptions about smoothness because if you don't meet those assumptions, even the best method might not give you the guarantees they promise.

Kolya: Next up, we're going to look at some of their actual experiments in pricing and classification applications to see how these theoretical bounds play out when we actually run them.

Yuya Hikima, Akiko Takeda

Graduate School of Information Science and Technology, University of Tokyo · Center for Advanced Intelligence Project, RIKEN

math.OC

Submitted: 2025-10-28

Updated: 2026-11-10

Comments: Accepted for publication in Computational Optimization and Applications (COAP). Author's website: https://yuya-hikima.github.io/

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 97/100

The gist: Zeroth-order gradient estimators that average over multiple directions achieve the lowest sample complexity for stochastic optimization problems with unknown decision-dependent distributions The…

Key concepts

Decision-Dependent Distributions
This describes a scenario where the underlying data generating process (the noise) changes depending on the specific decision ($x$) being made. In optimization, this means the noise is not fixed; it adapts to what you choose, which makes standard optimization much harder.
Zeroth-Order Gradient Estimators
These are methods used to estimate the gradient of a function without needing its analytical derivative. They work by sampling points or directions around the current decision $x$ and observing how the function value changes. The paper tests various ways these samples are chosen to get an accurate estimate.
Sample Complexity
This is a theoretical measure of how many data samples (iterations) are needed for an algorithm to reliably find a good solution. Lower sample complexity means the method learns faster or requires less data to perform well on complex problems.
Coordinate-wise Directions vs. Random Directions
Coordinate-wise directions use simple, fixed directions based on the dimensions of the problem (e.g., moving only along one axis at a time). Random directions, like those from a uniform sphere or Gaussian distribution, explore many different directions simultaneously. The study shows that exploring multiple random directions is more effective for estimating the true gradient.

Terminology

Summary

Zeroth-order gradient estimators that average over multiple directions achieve the lowest sample complexity for stochastic optimization problems with unknown decision-dependent distributions The attained sample complexities improve those of existing zeroth-order methods in the problem setting that allows nonconvexity and unboundedness of the objective function

Problem Formulation and Context

The paper studies a stochastic optimization problem with unknown decision-dependent distributions, formulated as min x∈Rd F(x):= Eξ∼D(x) [f(x, ξ)] This problem is the generalized problem for the classical stochastic problem min x∈Rd Eξ∼D[f(x, ξ)] The formulation (1) is also referred to as the performative prediction problem emphasizing that the data-generating process adapts to the deployed decision This setting is important in applications such as pricing and strategic classification where demand or agent features depend on the chosen decision x

Gradient Estimator Comparison

The authors investigate various gradient estimators, including one-point, two-point, coordinate-wise directions, directions sampled uniformly from the unit sphere, and Gaussian distribution directions They conduct a unified sample complexity analysis across these different gradient estimators under a setting where problem (1) is nonconvex and the objective function is generally unbounded The key finding is that averaging over multiple directions, whether uniformly from the unit sphere or from a Gaussian distribution, achieves lower sample complexity than coordinate-wise directions

Theoretical Results on Sample Complexity

The theoretical analysis yields three key findings regarding the performance of different gradient estimators (a) For gradient estimators based on random directions, using more than one direction per iteration (N > 1) effectively suppresses the error between the gradient estimator and the true gradient (b) Averaging over multiple directions, sampled either uniformly from the unit sphere or from a Gaussian distribution, achieves lower sample complexity than that of coordinate-wise directions (c) After appropriately scaling the smoothing parameters, gradient estimators using directions uniformly distributed on the unit sphere and those using Gaussian directions yield equivalent estimation error relative to the true gradient Specifically, coordinate-wise estimators achieve O(d3ε−6) or O(d5/2ε−5), while random-direction estimators achieve O(d2ε−6) or O(d2ε−5)

Empirical Validation and Conclusion

Simulation experiments on multiple products pricing and strategic classification applications show that zeroth-order methods employing gradient estimators with directions following a Gaussian distribution or directions uniformly sampled from the unit sphere achieve superior performance under the studied assumptions The results are consistent with the theoretical analysis, demonstrating that random-direction estimators outperform coordinate-wise ones The paper concludes that gradient estimators that average over multiple directions (N > 1), either uniformly from the unit sphere or from a Gaussian distribution, achieve the lowest sample complexity and demonstrate stronger empirical performance under their assumptions

Comparison with Prior Work

The results reverse the conclusion of prior work by showing that when considering unbiased stochastic noise, increasing the number of random directions N allows for simultaneous reduction in both approximation error and variance from randomness This contrasts with previous studies that assumed biased noise, where increasing samples could not reduce the bias term The comparison shows that random-direction estimators are more effective than coordinate-wise estimators in this setting The authors also note that the performance of ZO-GA and ZO-SPH perform nearly identically, suggesting they are both highly effective methods

Future Directions

A direction for future research is to incorporate more advanced acceleration techniques such as momentum schemes into the framework to further enhance convergence properties for problem (1) This extension may improve the convergence rates of zeroth-order methods in this challenging setting The paper also notes that the current setup violates the smoothness requirement in Assumption 2 and 3 due to discontinuities in decision-dependent distributions, suggesting a need for methods robust to such violations The authors suggest incorporating momentum schemes from [Huang et al., 2022] into this framework The paper also suggests that the performance of ZO-GA and ZO-SPH is lower in experiments because the problem does not satisfy assumptions 2 and 3, highlighting the importance of these assumptions for theoretical guarantees The authors also note that the distribution is used only to generate sample demand in experiments, meaning they do not exploit any oracle access to D(x) The paper concludes by showing that both gradient estimators exhibit similar properties by scaling the smoothing parameter µ

Experiments and Applications

The authors conducted experiments on multiproduct pricing and strategic classification applications using semi-synthetic data In the pricing application, ZO-GA and ZO-SPH tend to achieve higher performance than ZO-CO and ZO-OG because coordinate-wise methods exhibit a greater distance between the gradient estimator and the true gradient In the strategic classification application, both ZO-SPH and ZO-CO achieved stronger performance overall The experimental results confirm that methods with lower theoretical sample complexity, like ZO-GA and ZO-SPH, tend to achieve higher performance in practice The experiments show that the objective value is reduced more sharply by ZO-GA and ZO-SPH compared to other methods The final conclusion is that random-direction estimators dominate the coordinate-wise estimator in terms of sample complexity and empirical performance under the studied assumptions

References

A. S. Berahas, L. p. 1 Cao, K. Choromanski, and K. Scheinberg A theoretical and empirical comparison of gradient approximations in derivative-free optimization Foundations of Computational Mathematics 22(2):507–560 2022

J. Bergstra and Y. p. 4 Bengio Random search for hyper-parameter optimization Journal of machine learning research 13(2):2012

X. Chen, Y. Tang, and N. Li Improve single-point zeroth-order optimization using high-pass and low-pass filters In Proceedings of the International Conference on Machine Learning pages 3603–3620 2022

Y. Chen, W. Tang, C.-J. Ho, and Y. Liu Performative prediction with bandit feedback Learning through reparameterization In Proceedings of the International Conference on Machine Learning pages 7298–7324 2024

E. Cyffers, M. p. 1 S. Pydi, J. Atif, and O. Cappe Optimal classification under performative distribution shift Advances in Neural Information Processing Systems 37:68144–68160 2024

A. Flaxman, A. p. 2 T. Kalai, and H. B. McMahan Online convex optimization in the bandit setting gradient descent without a gradient In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms pages 385––94 2005

E. Frankel, K. p. 1 Kulkarni, D. Drusvyatskiy, S. Oh, and L. J. Ratliff Finite-time convergence rates in stochastic stackelberg games with smooth algorithmic agents In Proceedings of the International Conference on Machine Learning 2025

P. I. Frazier A tutorial on bayesian optimization arXiv preprint arXiv:1807. p. 402811 2018

J. E. Freund and R. E. Walpole Mathematical statistics Prentice-Hall Inc 1986

S. Ghadimi and G. p. 2 Lan Stochastic first-and zeroth-order methods for nonconvex stochastic programming SIAM journal on optimization 23(4):2341–2368 2013

Y. Hikima and A. p. 0 p. 0 Takeda Stochastic approach for price optimization problems with decision-dependent uncertainty European Journal of Operational Research 322(2):541–553 2025a

Y. Hikima and A. Takeda Zeroth-order methods for nonconvex stochastic problems with decision-dependent distributions In Proceedings of the AAAI Conference on Artificial Intelligence volume 39 pages 17195–17203 2025b

Y. Hikima, H. Sawada, and A. Fujino Guided zeroth-order methods for stochastic non-convex problems with decision-dependent distributions In Proceedings of the International Conference on Machine Learning 2025

F. Huang, S. Gao, J. Pei, and H. Huang Accelerated zeroth-order and first-order momentum methods from mini to minimax optimization Journal of Machine Learning Research 23(36):1–70 2022

H. Iwakiri, Y. p. 5 Wang, S. Ito, and A. Takeda Single loop gaussian homotopy method for non-convex optimization Advances in Neural Information Processing Systems 35:7065–7076 2022

Z. Izzo, L. Ying, and J. Zou How to learn when data reacts to your model performative gradient descent In Proceedings of the International Conference on Machine Learning pages 4641–4650 2021

Z. Izzo, J. Zou, and L. Ying How to learn when data gradually reacts to your model In Proceedings of the International Conference on Artificial Intelligence and Statistics pages 3998–4035 2022

M. Jagadeesan, T. p. 4 Zrnic, and C. p. 3 Mendler-Dunner Regret minimization with performative feedback In Proceedings of the International Conference on Machine Learning pages 9760–9785 2022

P. D. Khanh, B. S. Mordukhovich, and D. B. Tran Globally convergent derivative-free methods in nonconvex optimization with and without noise Mathematical Programming pages 1–61 2025

S. Levanon and N Rosenfeld Strategic classification made practical In Proceedings of the International Conference on Machine Learning pages 6243–6253 2021

Q. Li and H.-T. Wai Stochastic optimization schemes for performative prediction with nonconvex Advances in Neural Information Processing Systems 37:8673–8697 2024

L. Lin and T. Zrnic Plug-in performative optimization In Proceedings of the International Conference on Machine Learning pages 30546–30565 2024

H. Liu, Q. Li, and H.-T. Wai Two-timescale derivative free optimization for performative prediction with markovian data In Proceedings of the International Conference on Machine Learning pages 31425–31450 2024a

T. Liu, Y. Lin, and E. p. 3 Zhou Bayesian stochastic gradient descent for stochastic optimization with streaming input data SIAM Journal on Optimization 34(1):389–418 2024b

A. Maggiar, A. Wachter, I. S. Dolinskaya, and J. Staum A derivative-free trust-region algorithm for the optimization of functions smoothed via gaussian convolution using adaptive multiple importance sampling SIAM Journal on Optimization 28(2):1478–1507 2018

C. Mendler-Dunner, J. p. 0 Perdomo, T. p. 0 Zrnic, and M. p. 3 Hardt Stochastic optimization for performative prediction Advances in Neural Information Processing Systems pages 4929–4939 2020

M. Ray, L. J. Ratliff, D. Drusvyatskiy, and M. Fazel Decision-dependent risk minimization in geometrically decaying dynamic environments In Proceedings of the AAAI Conference on Artificial Intelligence pages 8081–8088 2022

B. Ustun, A. Spangher, and Y. Liu Actionable recourse in linear classification In Proceedings of the Conference on Fairness, Accountability, and Transparency pages 10–19 2019

J. Xue and B. Shen A novel swarm intelligence optimization approach sparrow search algorithm Systems Science & Control Engineering 8(1):22–34 2020

I.-C. Yeh and C. hui Lien The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients Expert Systems with Applications 36(2, Part 1):2473–2480 2009

A. Details of Our Experiments A. p. 4 p. 41 Experiments on multiproduct pricing A. p. 01.1 Problem setting We performed semi-synthetic experiments based on Hikima and Takeda 25 (a) 02/21–02/27 sample number 35 obj ZO-CO-33. p. 09

A. Details of Our Experiments A.1.3 Data details The experimental data New Product Sales Ranking provided by KSP-SP Co. p. 0, Ltd includes confectionery price data

--- Page 27 ---

Table 2 Experimental results for multiple product pricing in 20 randomly generated problem instances ZO-CO ZO-SPH ZO-GA ZO-OG ZO-OGVR obj sd train loss test loss test accuracy test AUC train loss test accuracy test AUC date 0.9 -33.9 1.0 -33.7 1.5

Table 3 Results of experiments on strategic classification for 100 randomly generated problem instances ZO-CO ZO-SPH ZO-GA ZO-OG ZO-OGVR mean sd train loss test loss test accuracy test AUC train loss test accuracy test AUC date 0.782 0.074 0.758 0.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Direction selection optimization allows for choosing gradient estimators that average over multiple directions, either uniformly from a unit sphere or from a Gaussian distribution, to achieve lower sample complexity than coordinate-wise directions or single-direction methods. This leads to the lowest complexity among existing zeroth-order methods in nonconvex settings with unbounded objective functions.

  2. The system can utilize the coordinate-wise gradient estimator for faster convergence when the problem setting allows for Lipschitz continuity of the Hessian, achieving a sample complexity of O(d 5/2 epsilon - 5). This provides a performance benchmark against which other estimators can be compared in specific structural settings.

  3. For applications where the true distribution D(x) is unknown but the objective function F is assumed to be M-smooth and H-Lipschitz continuous, using gradient estimators with directions uniformly sampled from the unit sphere or Gaussian directions yields equivalent estimation error relative to the true gradient when smoothing parameters are appropriately scaled. This allows practitioners to choose between these two distributions based on computational ease or specific performance needs.

  4. The system can achieve a sample complexity of O(d 2 epsilon - 6) for stationary point finding using the uniform distribution on the unit sphere estimator, which is superior to coordinate-wise estimators in terms of convergence rate when considering gradient Lipschitz continuity and unbiased stochastic noise.

Sources

Related papers