Decentralized Rank-Adaptive Matrix Factorization—Part II: Convergence Analysis

The matrix factorization (MF) model has a wide range of applications in signal processing and machine learning. Existing decentralized MF methods require to know the matrix rank a prior, which however is difficult to obtain especially when the data are distributively stored in a network. In the two-part paper, we study a rank-adaptive MF algorithm which proceeds in decentralized setting and meanwhile does not need to know the matrix rank precisely. In the Part-I paper, we have proposed to achieve the rank adaption through a novel <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell_{1}$</tex-math></inline-formula>-norm regularizer, and demonstrated its efficacy via numerical experiments. In this Part-II paper, our goal is to build the convergence conditions and the convergence rate of the proposed rank-adaptive algorithm. In particular, we first consider the decentralized MF algorithm with known rank and show that when the step size is set as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(t^{-\delta})$</tex-math></inline-formula> for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\delta\in(1/2,2/3]$</tex-math></inline-formula>, the algorithm converges to the global optima with rate <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(t^{-\delta})$</tex-math></inline-formula> with high probability, whereas when the step-size is a constant, the algorithm converges with a linear rate, but only to the neighborhood of the global optima. Then we extend the analysis to the rank-adaptive algorithm.