State-Aware Zeroth-Order Search for DR-Submodular Maximization

We study zeroth-order continuous DR-submodular maximization over polyhedral constraints and introduce *state-aware direct search* (SDS), a new zeroth-order search paradigm in which local polyhedral geometry determines how search directions are obtained. On nondegenerate iterations, SDS directly polls feasible directions generated from the local geometry, while gradient estimation is used only in degenerate states. We develop a unified analysis framework that extends SDS to non-oblivious objectives whose stationarity yields approximation guarantees. For monotone and nonmonotone maximization over general polytopes, and nonmonotone maximization over down-closed polytopes, SDS achieves approximation factors $1-e^{-1}$, $(1-h)/4$, and $e^{-1}$, respectively, with $O({ϵ}^{-2})$ expected iterations in all three settings. Under exact and stochastic value oracles, the corresponding worst-case expected value-oracle complexities are $O({ϵ}^{-3})$ and $O({ϵ}^{-4})$, respectively. This matches the best known iteration dependence for general polytopes and improves the zeroth-order iteration complexity for the $e^{-1}$ guarantee in nonmonotone down-closed maximization from $O({ϵ}^{-3})$ to $O({ϵ}^{-2})$. Numerical experiments demonstrate the practical effectiveness of SDS, with degenerate states rarely encountered in practice.