Thank you for your review!
We appreciate your insightful and valuable comments. We would like to highlight the significance of our results in comparison to Kelner et al., 2023b. Indeed, Kelner et al., 2023b offers a theoretically state-of-the-art sample complexity and runtime for a non-convex programming-based algorithm in matrix completion. Under standard incoherence assumptions, they achieve a sample complexity of $|\Omega|=O(nk^{2+o(1)})$ and a runtime of $\widetilde O(|\Omega|k)$. However, their approach significantly diverges from the algorithms commonly used in matrix completion practice.
Their algorithm, broadly speaking, is grounded in the 'short-flat decomposition' developed in their earlier work (Kelner et al., 2023a) on semi-random sparse recovery. This decomposition separates the observation into a useful term and a noisy term with 'flat' singular values. The algorithm begins with initial matrices $U_0, V_0=0$, and processes a set of observations from M by first removing large rows and columns from $P_{\Omega_t}(M-U_tV_t^\top)$, followed by running a top-k SVD procedure from Musco and Musco, 2015. This procedure is iterated for ${\rm polylog}(1/\epsilon)$ rounds. Due to dropping rows and columns with large norms, they need to recover them back in the post-processing. This can be achieved through regression 'tests' to determine if a set of columns can linearly form a targeted column. The recovery algorithm then proceeds by sampling columns, tests for linear independence, and this process repeats for ${\rm polylog}(n)$ times. Ultimately, the selected columns help fill missing entries for a partially completed matrix for $U$, and the matrix $V$ is completed via Nesterov’s accelerated gradient descent (AGD). They employ Nesterov’s AGD for its good condition number dependence. Of course, they also need a bound on the initial error, which is done via estimating $\log(1/\epsilon)$ many spectral norms over independent samples of $M$, and outputting the median using Chernoff bound.
From a practical standpoint, their algorithm is likely slower than alternating minimization or SGD due to the need for top-k SVD computation and linear independence testing for ${\rm polylog}(n, 1/\epsilon)$ rounds, along with an additional $\log(1/\epsilon)$ rounds for multiple response regression using Nesterov’s AGD. The randomized top-k SVD algorithm they employ, based on block Krylov subspace iteration, is known for numerical instability. While Nesterov’s AGD offers theoretical advantages, it is challenging to achieve fast practical implementation, often making Polyak’s momentum a preferred choice for its simplicity and practical efficacy.
In contrast, alternating minimization and stochastic gradient descent are the most widely applied approaches in practice for matrix completion, despite theoretically inferior sample complexity. These methods are practically efficient, generally involving a sequence of least squares problems solvable by iterative methods. Our robust alternating minimization framework provides a theoretical justification for the practical success of alternating minimization, benefiting from faster solvers. We also believe that further tightening the sample complexity bound for alternating minimization could lead to direct runtime improvements for our algorithm.
Kelner et al., 2023a. Kelner, Li, Liu, Sidford and Tian. Semi-random sparse recovery in nearly-linear time. COLT’2023.
Kelner et al., 2023b. Kelner, Li, Liu, Sidford and Tian. Matrix completion in almost-verification time. FOCS’2023.
Musco and Musco, 2015. Randomized block krylov methods for stronger and faster approximate singular value decomposition. NeurIPS’2015.