A Relational Gradient Descent Algorithm For Support Vector Machine Training
This work addresses a computational bottleneck for machine learning practitioners dealing with relational databases, though it is incremental as it focuses on stable instances rather than a general solution.
The paper tackles the problem of efficiently training Support Vector Machines (SVMs) on relational data, where gradient computation is #P-hard due to the 'subtraction problem'. It proposes an algorithm that computes a pseudo-gradient for stable instances, achieving convergence rates comparable to using the actual gradient.
We consider gradient descent like algorithms for Support Vector Machine (SVM) training when the data is in relational form. The gradient of the SVM objective can not be efficiently computed by known techniques as it suffers from the ``subtraction problem''. We first show that the subtraction problem can not be surmounted by showing that computing any constant approximation of the gradient of the SVM objective function is $\#P$-hard, even for acyclic joins. We, however, circumvent the subtraction problem by restricting our attention to stable instances, which intuitively are instances where a nearly optimal solution remains nearly optimal if the points are perturbed slightly. We give an efficient algorithm that computes a ``pseudo-gradient'' that guarantees convergence for stable instances at a rate comparable to that achieved by using the actual gradient. We believe that our results suggest that this sort of stability the analysis would likely yield useful insight in the context of designing algorithms on relational data for other learning problems in which the subtraction problem arises.