Paper Info
Title
Which Factorization Machine Modeling is Better: A Theoretical Answer with Optimal Guarantee.
Abstract
Factorization machine (FM) is a popular machine learning model to capture the second order feature interactions. The optimal learning guarantee of FM and its generalized version is not yet developed. For a rank k generalized FM of d dimensional input, the previous best known sampling complexity is O[k(3)d . polylog(kd)] under Gaussian distribution. This bound is sub-optimal comparing to the information theoretical lower bound O(kd). In this work, we aim to tighten this bound towards optimal and generalize the analysis to sub-gaussian distribution. We prove that when the input data satisfies the so-called tau-Moment Invertible Property, the sampling complexity of generalized FM can be improved to O[k(2)d . polylog(kd)/tau(2)]. When the second order self-interaction terms are excluded in the generalized FM, the bound can be improved to the optimal O[kd . polylog(kd)] up to the logarithmic factors. Our analysis also suggests that the positive semi-definite constraint in the conventional FM is redundant as it does not improve the sampling complexity while making the model difficult to optimize We evaluate our improved FM model in real-time high precision GPS signal calibration task to validate its superiority.
Year
Venue
Field
2019
THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE
Mathematical optimization,Upper and lower bounds,Computer science,Algorithm,Gaussian,Factorization,Sampling (statistics),Logarithm,Invertible matrix,GPS signals,Calibration
DocType
Volume
Citations 
Journal
abs/1901.11149
0
PageRank 
References 
Authors
0.34
10
8
Name
Order
Citations
PageRank
Ming Lin124114.20
Shuang Qiu2133.71
Jieping Ye36943351.37
Xiaomin Song492.72
Qi Qian5869.42
Liang Sun650024.61
Zhu, Shenghuo72996167.68
Rong Jin86206334.26