Nonconvex stochastic zeroth-order optimization with decision-dependent distributions: from momentum tracking to coupled sampling

In this paper, we study nonconvex stochastic optimization with {decision-dependent distributions}, where the decision variable influences the underlying sampling distribution and only stochastic function-value feedback is available. We address two challenges {induced by decision-dependent distributions}: transport error in momentum-based gradient tracking and variance inflation in zeroth-order estimation. We first develop a Polyak-momentum zeroth-order method that tracks the smoothed gradient under decision-dependent distributions, and establish a sample complexity of $\mathcal O(d^2\epsilon^{-6})$ under first-order smoothness. We then introduce implicit gradient transport (IGT) to mitigate the first-order transport error in the tracking recursion, improving the sample complexity to $\mathcal O(d^2\epsilon^{-4.5})$ under second-order smoothness. Finally, for a structured class of {problems with decision-dependent distributions} admitting a common-latent-source representation, we develop a marginal-preserving coupled sampling framework that exploits shared latent randomness between function evaluations to reduce estimator variance. Under this coupled-sampling setting, the proposed methods achieve sample complexities $\mathcal O(d^2\epsilon^{-4})$ and $\mathcal O(d^2\epsilon^{-3.5})$ under first- and second-order smoothness, respectively. Numerical test results are also reported to showcase the performances of proposed methods.

Article

Download

View PDF