  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 $O(\epsilon)$ recovery error after
retrieving $O(k^{3}d\log(1/\epsilon))$ training instances, consumes $O(kd)$
memory in one-pass of dataset and only requires matrix-vector 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.
