Abstract 

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 d dimensional random Gaussian vectors and the target second order coefficient matrix in gFM is of rank k, our algorithm converges linearly, achieves recovery error after retrieving training instances, consumes 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.