We consider gradient descent like algorithms for Support Vector Machine (SVM)\ntraining when the data is in relational form. The gradient of the SVM objective\ncan not be efficiently computed by known techniques as it suffers from the\n``subtraction problem''. We first show that the subtraction problem can not be\nsurmounted by showing that computing any constant approximation of the gradient\nof the SVM objective function is $\\#P$-hard, even for acyclic joins. We,\nhowever, circumvent the subtraction problem by restricting our attention to\nstable instances, which intuitively are instances where a nearly optimal\nsolution remains nearly optimal if the points are perturbed slightly. We give\nan efficient algorithm that computes a ``pseudo-gradient'' that guarantees\nconvergence for stable instances at a rate comparable to that achieved by using\nthe actual gradient. We believe that our results suggest that this sort of\nstability the analysis would likely yield useful insight in the context of\ndesigning algorithms on relational data for other learning problems in which\nthe subtraction problem arises.\n