A Relational Gradient Descent Algorithm For Support Vector Machine Training

Mahmoud Abo Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian

Introduction

In modern data science, a significant friction point exists between data storage and model training. While the vast majority of enterprise data is stored in structured, relational databases (SQL), machine learning (ML) algorithms typically require a single, flat "design matrix." The conventional solution—joining multiple tables into a single wide table—often results in a "join explosion," where the resulting dataset is exponentially larger than the original relational components due to redundancy.

This paper addresses the "Relational Learning Question" specifically for Support Vector Machines (SVMs), proposing a method to train these models directly on relational data without materializing the costly full join.

The Challenge: Join Explosion and the Subtraction Problem

The standard "Join-then-Train" pipeline is computationally expensive and memory-intensive. For example, joining a Customers table with a Purchases table repeats customer information for every transaction. Across many tables, this redundancy scales poorly.

While relational learning has been successfully applied to simpler models like Linear Regression, Support Vector Machines present a unique challenge known as the subtraction problem. The SVM gradient requires identifying and summing points that fall on the "wrong" side of a decision boundary. In a relational setting, calculating this sum involves counting combinations of rows across tables. If the calculation involves subtracting two very large, nearly equal numbers, even infinitesimal approximation errors can lead to a gradient that points in the wrong direction, causing the optimization to fail.

Theoretical Hardness

The authors establish a fundamental theoretical barrier: approximating the SVM gradient on relational data is #P-hard, even for simple acyclic joins. This result, derived via a reduction from the "Counting Knapsack Problem," implies that no efficient algorithm can compute an exact or highly accurate gradient for all possible relational inputs. This hardness explains why previous attempts at relational SVM training have struggled with numerical stability.

Overcoming Hardness through Stability

To bypass the #P-hardness, the authors introduce the concept of (\alpha, \delta, \gamma)-stability. A dataset is considered stable if small perturbations in the data points do not drastically alter the optimal decision boundary.

The researchers argue that stability is a reasonable assumption for real-world applications. If a model's performance is so fragile that a 1% change in data points results in a completely different classifier, the model is likely overfit or poorly specified. By focusing on stable instances, the authors move the goalpost from "solving every possible case" to "solving cases that matter in practice."

The Pseudo-gradient Algorithm

The core contribution of the paper is a pseudo-gradient algorithm designed for relational data. Instead of attempting to solve the #P-hard problem of exact gradient computation, the algorithm calculates a "pseudo-gradient" that ignores points extremely close to the decision boundary—the primary source of the subtraction problem.

The algorithm leverages specialized database techniques:

  1. FAQ-AI Queries: A framework for Functional Aggregate Queries that allows for efficient summation over joins.
  2. Inside-Out Algorithm: A dynamic programming approach that enables counting and summing rows across tables without ever materializing the full join.

This approach allows the algorithm to operate in time polynomial to the size of the input tables ($n$), the number of tables ($m$), and the dimensions ($d$), rather than the size of the joined result.

Key Results and Convergence

The paper provides both negative and positive results:

  • Negative Result: Proved that $O(1)$-approximating the partial derivative of the SVM objective is #P-hard for relational data.
  • Positive Result: Developed a relational algorithm that computes a pseudo-gradient in polynomial time. For stable instances, the authors proved that this pseudo-gradient descent algorithm converges to a $(1 + \gamma)$ approximation of the optimal SVM objective at a rate comparable to standard gradient descent.

Conclusion and Future Directions

This work demonstrates that while exact relational SVM training is theoretically "impossible" in the general case, it is practically achievable for stable datasets. By avoiding the join explosion, the proposed algorithm offers a path toward more efficient ML pipelines that respect the relational structure of data.

Future research directions include extending the algorithm to cyclic joins (using hypertree width techniques) and exploring whether this stability-based approach can be applied to other complex models, such as robust regression or specific neural network architectures, where relational training has previously been hindered by numerical instability.

Summary updated

Abstract

We consider gradient descent like algorithms for Support Vector Machine (SVM) training when the data is in relational form. For relational data the gradient of the SVM objective cannot be efficiently computed by known techniques as it suffers from the “subtraction problem”. We first show that the subtraction problem cannot be surmounted by showing that computing any constant approximation of the gradient of the SVM objective function is #P-hard, even for acyclic joins. However, we 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 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.
BibTeX
@inproceedings{khamis2021relational,
  author = {Mahmoud Abo Khamis and Sungjin Im and Benjamin Moseley and Kirk Pruhs and Alireza Samadian},
  title = {{A Relational Gradient Descent Algorithm For Support Vector Machine Training}},
  booktitle = {APOCS},
  year = {2021},
  url = {https://openreview.net/forum?id=2izglydcLog},
}
Figure