  We study (constrained) nonconvex (composite) optimization problems where the
decision variables vector can be split into blocks of variables. Random block
projection is a popular technique to handle this kind of problem for its
remarkable reduction of the computational cost from the projection. However,
this powerful method has not been proposed for the situation that first-order
information is prohibited and only zeroth-order information is available. In
this paper, we propose to develop different classes of zeroth-order stochastic
block coordinate type methods. Zeroth-order block coordinate descent (ZS-BCD)
is proposed for solving unconstrained nonconvex optimization problem. For
composite optimization, we establish the zeroth-order stochastic block mirror
descent (ZS-BMD) and its associated two-phase method to achieve the complexity
bound for finding $(\epsilon,\Lambda)$-solution. Furthermore, we also establish
zeroth-order stochastic block coordinate conditional gradient (ZS-BCCG) method
for nonconvex (composite) optimization. By implementing ZS-BCCG method, in each
iteration, only (approximate) linear programming subproblem needs to be solved
on a random block instead of a rather costly projection subproblem on the whole
decision space, in contrast to the existing traditional stochastic
approximation methods. In what follows, an approximate ZS-BCCG method and
corresponding two-phase ZS-BCCG method are proposed. This is also the first
time that a two-phase BCCG method has been developed to achieve the $(\epsilon,
\Lambda)$-solution of nonconvex composite optimization problem. To the best of
our knowledge, the proposed results in this paper are new in stochastic
nonconvex (composite) optimization literature.
