Zeroth-order gradient estimators for stochastic problems with decision-dependent distributions

Stochastic optimization problems with unknown decision-dependent distributions have attracted increasing attention in recent years due to its importance in applications. Since the gradient of the objective function is inaccessible as a result of the unknown distribution, various zeroth-order methods have been developed to solve the problem. However, it remains unclear which search direction to construct a gradient estimator is more appropriate and how to set the algorithmic parameters. In this paper, we conduct a unified sample complexity analysis of zeroth-order methods across gradient estimators with different search directions. As a result, we show that gradient estimators that average over multiple directions, either uniformly from the unit sphere or from a Gaussian distribution, achieve the lowest sample complexity. The attained sample complexities improve those of existing zeroth-order methods in the problem setting that allows nonconvexity and unboundedness of the objective function. Moreover, by simulation experiments on multiple products pricing and strategic classification applications, we show practical performance of zeroth-order methods with various gradient estimators.

• Publication year

  2025

• Venue

  Unknown venue

• Publication date

  2025-10-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2510.24929
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Globally convergent derivative-free methods in nonconvex optimization with and without noise

  2025influential reference
• Finite-Time Convergence Rates in Stochastic Stackelberg Games with Smooth Algorithmic Agents

  2025cited by this paper
• Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss

  2024cited by this paper
• Zeroth-Order Methods for Nonconvex Stochastic Problems with Decision-Dependent Distributions

  2024influential reference
• Optimal Classification under Performative Distribution Shift

  2024cited by this paper
• Stochastic approach for price optimization problems with decision-dependent uncertainty

  2023cited by this paper
• Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data

  2023influential reference
• Plug-in Performative Optimization

  2023cited by this paper
• Performative Prediction with Bandit Feedback: Learning through Reparameterization

  2023cited by this paper
• Performative Prediction with Neural Networks

  2023cited by this paper
• Regret Minimization with Performative Feedback

  2022cited by this paper
• Bayesian Stochastic Gradient Descent for Stochastic Optimization with Streaming Input Data

  2022cited by this paper
• Single Loop Gaussian Homotopy Method for Non-convex Optimization

  2022cited by this paper
• Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments

  2022influential reference
• Improve Single-Point Zeroth-Order Optimization Using High-Pass and Low-Pass Filters

  2021cited by this paper
• How to Learn when Data Reacts to Your Model: Performative Gradient Descent

  2021influential reference
• Outside the Echo Chamber: Optimizing the Performative Risk

  2021cited by this paper
• Strategic Classification Made Practical

  2021cited by this paper
• How to Learn when Data Gradually Reacts to Your Model

  2021cited by this paper
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization

  2020cited by this paper
• Stochastic Optimization for Performative Prediction

  2020influential reference
• A novel swarm intelligence optimization approach: sparrow search algorithm

  2020cited by this paper
• Performative Prediction

  2020influential reference
• A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization

  2019influential reference
• A Tutorial on Bayesian Optimization

  2018cited by this paper
• Actionable Recourse in Linear Classification

  2018cited by this paper
• A Derivative-Free Trust-Region Algorithm for the Optimization of Functions Smoothed via Gaussian Convolution Using Adaptive Multiple Importance Sampling

  2018cited by this paper
• Random Gradient-Free Minimization of Convex Functions

  2015influential reference
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming

  2013influential reference
• Random Search for Hyper-Parameter Optimization

  2012cited by this paper
• Mathematical Statistics

  2006cited by this paper
• Online convex optimization in the bandit setting: gradient descent without a gradient

  2004influential reference

• No citing papers are available for this paper.