  This paper concerns a convex, stochastic zeroth-order optimization (S-ZOO)
problem, where the objective is to minimize the expectation of a cost function
and its gradient is not accessible directly. To solve this problem, traditional
optimization techniques mostly yield query complexities that grow polynomially
with dimensionality, i.e., the number of function evaluations is a polynomial
function of 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 work with arguably more stringent
conditions such as everywhere sparse or compressible gradient. Thus, prior to
this research, it was unknown whether dimension-insensitive S-ZOO is possible
without such conditions. In this paper, we give an affirmative answer to this
question by proposing a sparsity-inducing stochastic gradient-free (SI-SGF)
algorithm. It is proved to achieve dimension-insensitive query complexity in
both convex and strongly convex cases when neither gradient sparsity nor
gradient compressibility is satisfied. Our numerical results demonstrate the
strong potential of the proposed SI-SGF compared with existing alternatives.
