  This paper concerns a convex, stochastic zeroth-order optimization (S-ZOO)
problem. The objective is to minimize the expectation of a cost function whose
gradient is not directly accessible. For this problem, traditional optimization
algorithms mostly yield query complexities that grow polynomially with
dimensionality (the number of decision variables). Consequently, these methods
may not perform well in solving massive-dimensional problems arising in many
modern applications. Although more recent methods can be provably
dimension-insensitive, almost all of them require arguably more stringent
conditions such as everywhere sparse or compressible gradient. In this paper,
we propose a sparsity-inducing stochastic gradient-free (SI-SGF) algorithm,
which provably yields a dimension-free (up to a logarithmic term) query
complexity in both convex and strongly convex cases. Such insensitivity to the
dimensionality growth is proven, for the first time, to be achievable when
neither gradient sparsity nor gradient compressibility is satisfied. Our
numerical results demonstrate a consistency between our theoretical prediction
and the empirical performance.
