Convergence and Complexity of Stochastic Block Majorization-Minimization

In this paper, we introduce stochastic block majorization-minimization, where the surrogates can now be only block multi-convex and a single block is optimized at a time within a diminishing radius. Relaxing the standard strong convexity requirements for surrogates in SMM, our framework gives wider applicability including online CANDECOMP/PARAFAC (CP) dictionary learning and yields greater computational efficiency especially when the problem dimension is large. We provide an extensive convergence analysis on the proposed algorithm, which we derive under possibly dependent data streams, relaxing the standard i.i.d. Our results provide first convergence rate bounds for various online matrix and tensor decomposition algorithms under a general Markovian data setting. Empirical loss minimization is a classical problem setting regarding parameter estimation with a growing number of observations, where one seeks to minimize a recursively defined empirical loss function as new data arrives. Some of its well-known applications include maximum likelihood estimation, or more generally, M-estimation [Gey94, GvdGW00, SB02], as well as the online dictionary learning literature [MBPS10, Mai13b, MMTV17, LNB20]. On the other hand, the expected loss minimization seeks to estimate a parameter by minimizing the loss function with respect to random data. It provides a general framework for stochastic optimization literature [SK07, Mar05, BB08, NJLS09]. Optimization algorithms for empirical or expected loss minimization are in nature'online', meaning that sampling new data points and adjusting the current estimation occurs recursively. Such onilne algorithms have proven to be particularly efficient in large-scale problems in statistics, optimization, and machine learning [Bot98, DS09, GL13, KB14].