  In this paper, we propose and analyze algorithms for zeroth-order
optimization of non-convex composite objectives, focusing on reducing the
complexity dependence on dimensionality. This is achieved by exploiting the low
dimensional structure of the decision set using the stochastic mirror descent
method with an entropy alike function, which performs gradient descent in the
space equipped with the maximum norm. To improve the gradient estimation, we
replace the classic Gaussian smoothing method with a sampling method based on
the Rademacher distribution and show that the mini-batch method copes with the
non-Euclidean geometry. To avoid tuning hyperparameters, we analyze the
adaptive stepsizes for the general stochastic mirror descent and show that the
adaptive version of the proposed algorithm converges without requiring prior
knowledge about the problem.
