Stochastic regularized majorization-minimization with weakly convex and
  multi-convex surrogates
  Stochastic majorization-minimization (SMM) is a class of stochastic
optimization algorithms, which consists of sampling i.i.d. data points from a
fixed data distribution and minimizing recursively defined averaged surrogates
of an objective function. The surrogates are required to be strongly convex,
and convergence rate analysis was missing, in contrast to the extensive
literature on stochastic gradient descent (SGD) methods. In this paper, we
extend SMM where surrogates are allowed to be weakly convex or block
multi-convex, and the averaged surrogates are approximately minimized with
proximal regularization or block-minimized within diminishing radii,
respectively. Our general framework gives wider applicability to SMM including
online CANDECOMP/PARAFAC (CP) dictionary learning and yields greater
computational efficiency especially when the problem dimension is large. We
show that the first-order optimality gap of the proposed algorithm decays at
the rate $O((\log n)^{1+\eps}/n^{1/2})$ for the empirical loss and $O((\log
n)^{1+\eps}/n^{1/4})$ for the expected loss, where $n$ denotes the number of
data samples processed. Under some additional assumption, the latter
convergence rate can be improved to $O((\log n)^{1+\eps}/n^{1/2})$. Our
analysis shows that SMM could be faster than SGD in optimizing for the
empirical loss and could match the same optimal rate as SGD for the expected
loss. As a corollary, our results provide first convergence rate bounds for
various online matrix and tensor decomposition algorithms under a general
Markovian data setting.
