In very large-scale sparse settings, the optimization strategy is tightly coupled to the modeling, not orthogonal to it. The reason why is that &quot;data beats algorithm&quot;: meaning that a &quot;dumb&quot; model that can be trained on 1TB of data using a &quot;dumb&quot; optimizer will easily outperform a fancier model for which we only have at our disposal more complex optimizers that can only eat 1GB of data in the same amount of time. This paper is a classic when it comes to the kind of trade-offs you have to deal with in large-scale web settings: <a href="http:&#x2F;&#x2F;papers.nips.cc&#x2F;paper&#x2F;3323-the-tradeoffs-of-large-scale-learning.pdf" rel="nofollow">http:&#x2F;&#x2F;papers.nips.cc&#x2F;paper&#x2F;3323-the-tradeoffs-of-large-scal...</a><p>The kernel trick uses an <i>implicit</i> mapping into a higher-dimensional feature-space. On the other hand, Factorization Machines uses an <i>explicit</i> mapping into the polynomial kernel space. However it learns jointly the &quot;right&quot; polynom, by mapping the <i>base</i> features into a low-dimensional dense space where the higher-order terms of the polynom are dot-products (we&#x27;re not taking dot-products in the original feature-space!). FM then <i>learns</i> the right polynomial (a non-convex taks) jointly with learning the original supervised learning task.