A Non-convex One-Pass Framework for Generalized Factorization Machine and Rank-One Matrix Sensing

We develop an efficient alternating framework for learning a generalized version of Factorization Machine (gFM) on steaming data with provable guarantees. When the instances are sampled from ddimensional random Gaussian vectors and the target second order coefficient matrix in gFM is of rank k, our algorithm converges linearly, achieves O() recovery error after retrieving O(k3dlog(1/)) training instances, consumes O(kd) memory in one-pass of dataset and only requires matrixvector product operations in each iteration. The key ingredient of our framework is a construction of an estimation sequence endowed with a so-called Conditionally Independent RIP condition (CI-RIP). As special cases of gFM, our framework can be applied to symmetric or asymmetric rank-one matrix sensing problems, such as inductive matrix completion and phase retrieval.