Online Statistical Inference for Stochastic Optimization via Gradient-free Kiefer-Wolfowitz Methods

In this paper, we investigate the problem of statistical inference of the model parameters in stochastic optimization problems via the Kiefer-Wolfowitz algorithm with random search directions. We first present the asymptotic distribution for the Polyak-Ruppert-averaging type Kiefer-Wolfowitz (AKW) estimators, whose asymptotic covariance matrices depend on the function query complexity and the distribution of search directions. The distributional result reflects the trade-off between statistical efficiency and function query complexity. We further analyze the choices of random search directions to minimize the asymptotic covariance matrix, and conclude that the optimal search direction depends on the optimality criteria with respect to different summary statistics of the Fisher information matrix. Based on the asymptotic distribution result, we conduct one-pass statistical inference by providing two constructions of valid confidence intervals. We provide numerical experiments verifying our theoretical results with the practical effectiveness of the procedures.