  Nonconvex optimization is central in solving many machine learning problems,
in which block-wise structure is commonly encountered. In this work, we propose
cyclic block coordinate methods for nonconvex optimization problems with
non-asymptotic gradient norm guarantees. Our convergence analysis is based on a
gradient Lipschitz condition with respect to a Mahalanobis norm, inspired by a
recent progress on cyclic block coordinate methods. In deterministic settings,
our convergence guarantee matches the guarantee of (full-gradient) gradient
descent, but with the gradient Lipschitz constant being defined w.r.t.~a
Mahalanobis norm. In stochastic settings, we use recursive variance reduction
to decrease the per-iteration cost and match the arithmetic operation
complexity of current optimal stochastic full-gradient methods, with a unified
analysis for both finite-sum and infinite-sum cases. We prove a faster linear
convergence result when a Polyak-{\L}ojasiewicz (P{\L}) condition holds. To our
knowledge, this work is the first to provide non-asymptotic convergence
guarantees -- variance-reduced or not -- for a cyclic block coordinate method
in general composite (smooth + nonsmooth) nonconvex settings. Our experimental
results demonstrate the efficacy of the proposed cyclic scheme in training deep
neural nets.
