Stochastic Non-Smooth Non-Convex Optimization with Decision-Dependent Distributions

Abstract

We study stochastic zeroth-order optimization with decision-dependent distributions, where the sampling law depends on the current decision and only noisy function values are available. For the non-smooth non-convex setting, we establish an explicit convergence guarantee for finding a $(\hat{I}´,\hat{I}\mu )$-Goldstein stationary point with stochastic zeroth-order oracle (SZO) complexity of $\mathcal{O}(d^2\hat{I}{´}^{-3}\hat{I}{\mu }^{-3})$. In addition, we show that the above complexity can be achieved with single SZO feedback per iteration. We further extend the analysis to smooth and Hessian-Lipschitz objectives, obtaining complexities $\mathcal{O}(d^2\hat{I}{\mu }^{-6})$ and $\mathcal{O}(d^2\hat{I}{\mu }^{-9/2})$, respectively. In the Hessian-Lipschitz case, this improves the best-known dependence on $\hat{I}\mu$ for decision-dependent zeroth-order methods by a factor of $\hat{I}{\mu }^{-1/2}$.