A Relational Gradient Descent Algorithm For Support Vector Machine Training
A Relational Gradient Descent Algorithm For Support Vector Machine Training
复制标题
支持向量机训练的关系梯度下降算法
DOI：
10.1137/1.9781611976489.8
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Samadian, A.
中科院分区：
文献类型：
--
作者：
Abo-Khamis, M.;Im, S.;Moseley, B.;Pruhs, K.;Samadian, A.
我们考虑梯度下降算法的支持向量机（SVM）的训练时，数据是在关系的形式。对于关系数据，SVM目标的梯度不能通过已知技术有效地计算，因为它遭受“减法问题”。我们首先表明，减法问题不能通过计算SVM目标函数的梯度的任何常数近似来克服，即使是非循环连接。然而，我们通过将注意力限制在稳定的实例来规避减法问题，这些实例直观地是如果点稍微扰动，则接近最优解仍然接近最优的实例。我们给出了一个有效的算法，计算一个“伪梯度”，保证收敛稳定的情况下，通过使用实际梯度达到的速度。我们相信，我们的研究结果表明，这种稳定性分析可能会产生有用的洞察力的背景下，设计算法的关系数据的其他学习问题中出现的减法问题。
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.
登录
查看更多内容
DOI：
10.1137/1.9781611976489.7
发表时间：
2021
期刊：
Symposium on Algorithmic Principles of Computer Systems (APOCS
影响因子：
--
作者：
Abo-Khamis, M.;Im, S.;Moseley, B.;Pruhs, K.;Samadian, A.
通讯作者：
Samadian, A.
带有否定的联合查询的布尔张量分解
DOI：
--
发表时间：
2017
期刊：
International Conference on Database Theory
影响因子：
--
作者：
Mahmoud Abo Khamis;H. Ngo;Dan Olteanu;Dan Suciu
通讯作者：
Dan Suciu
DOI：
--
发表时间：
2019-01
期刊：
--
影响因子：
--
作者：
A. Burkov
通讯作者：
A. Burkov
影响因子：
0.9
作者：
Bilu, Yonatan;Linial, Nathan
通讯作者：
Linial, Nathan
超越最坏情况分析
影响因子：
22.7
作者：
Roughgarden, Tim
通讯作者：
Roughgarden, Tim