  Zeroth-order optimization, which does not use derivative information, is one
of the significant research areas in the field of mathematical optimization and
machine learning. Although various studies have explored zeroth-order
algorithms, one of the theoretical limitations is that oracle complexity
depends on the dimension, i.e., on the number of variables, of the optimization
problem. In this paper, to reduce the dependency of the dimension in oracle
complexity, we propose a zeroth-order random subspace algorithm by combining a
gradient-free algorithm (specifically, Gaussian randomized smoothing with
central differences) with random projection. We derive the worst-case oracle
complexity of our proposed method in non-smooth and convex settings;
{\color{black} it is equivalent to standard results for full-dimensional
non-smooth convex algorithms. Furthermore,} we prove that ours also has a local
convergence rate independent of the original dimension under additional
assumptions. In addition to the theoretical results, numerical experiments show
that when an objective function has a specific structure, the proposed method
can become experimentally more efficient due to random projection.
