{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T00:10:07Z","timestamp":1705018207418},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"01","license":[{"start":{"date-parts":[[2019,7,17]],"date-time":"2019-07-17T00:00:00Z","timestamp":1563321600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.aaai.org"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAAI"],"abstract":"<jats:p>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[k3d \u00b7 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 \u03c4-Moment Invertible Property, the sampling complexity of generalized FM can be improved to O[k2d \u00b7 polylog(kd)\/\u03c42]. When the second order self-interaction terms are excluded in the generalized FM, the bound can be improved to the optimal O[kd \u00b7 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.<\/jats:p>","DOI":"10.1609\/aaai.v33i01.33014312","type":"journal-article","created":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T07:33:59Z","timestamp":1567496039000},"page":"4312-4319","source":"Crossref","is-referenced-by-count":3,"title":["Which Factorization Machine Modeling Is Better: A Theoretical Answer with Optimal Guarantee"],"prefix":"10.1609","volume":"33","author":[{"given":"Ming","family":"Lin","sequence":"first","affiliation":[]},{"given":"Shuang","family":"Qiu","sequence":"additional","affiliation":[]},{"given":"Jieping","family":"Ye","sequence":"additional","affiliation":[]},{"given":"Xiaomin","family":"Song","sequence":"additional","affiliation":[]},{"given":"Qi","family":"Qian","sequence":"additional","affiliation":[]},{"given":"Liang","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Shenghuo","family":"Zhu","sequence":"additional","affiliation":[]},{"given":"Rong","family":"Jin","sequence":"additional","affiliation":[]}],"member":"9382","published-online":{"date-parts":[[2019,7,17]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/4340\/4218","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/4340\/4218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T06:29:09Z","timestamp":1667802549000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/4340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,17]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,7,23]]}},"URL":"https:\/\/doi.org\/10.1609\/aaai.v33i01.33014312","relation":{},"ISSN":["2374-3468","2159-5399"],"issn-type":[{"value":"2374-3468","type":"electronic"},{"value":"2159-5399","type":"print"}],"subject":[],"published":{"date-parts":[[2019,7,17]]}}}