An Almost Sure Convergence Analysis of Zeroth-Order Mirror Descent Algorithm

In this paper, we show almost sure convergence of zeroth-order mirror descent algorithm. The algorithm admits non-smooth convex functions and assumes only an estimate of the gradient is available, obtained using Nesterov's Gausssian Approximation technique (NGA). We establish that under suitable condition of step-size, the function value of the iterates of the algorithm converge to a neighborhood of the optimal function value almost surely. We extend the analysis to the distributed implementation of the zeroth-order mirror descent algorithm.