I was recently asked this question in an interview and wondered what the answer would be - "How do Factorization Machines get around the overfitting problem when using second-order interactions?"
Here are some excerpts from the original paper that I think are key to understanding the question:
Instead of using an own model parameter for each interaction, the FM models the interaction by factorizing it. We will see later on, that this is the key point which allows high quality parameter estimates of higher-order interactions under sparsity.
Factorization machines can estimate interactions even in these settings (sparse data) well because they break the independence of the interaction parameters by factorizing them. In general this means that the data for one interaction helps also to estimate the parameters for related interactions.
In other words, instead of fitting an independent parameter for every second order interaction, it factorizes the parameters which reduces the parameter space and the model complexity, and thus making the model less prone to over fitting.
Hope this helps understand some aspects of the question.