Application of Quantum Gradient Descent as a Learning Algorithm for Factorization Machines
Narges Alavi Samani, Hossein Aghababa · 2018
Gradient Descent is an optimization algorithm used for finding the minima of a function. It moves along the function with steps proportional to the negative of the gradient. Quantum version of this algorithm has the advantage of exponential speedup for problems with high dimensional inputs. On the other hand, Factorization Machines (FMs) are modeling classes with important advantages in comparison with other modeling ones such as SVMs. They, in contrast to SVMs, use factorized parameters in order to model all interactions between variables. Accordingly, unlike SVMs, they can estimate interactions in problems with large sparsity. In this work, we show that Factorization Machine can be implemented on quantum computers, using quantum gradient descent to learn the parameters of a FM. The parameters we have chosen to learn via quantum gradient descent is a bottleneck in learning parameters of a FM. Our proposed idea results in time computational complexity O(k polylog n) where k and n are the dimensions of the parameter matrix. By doing so and under some constraints on the dimensions, an exponential speedup over classical algorithms can be obtained.