論文の概要: A Relational Gradient Descent Algorithm For Support Vector Machine Training

• arxiv url: http://arxiv.org/abs/2005.05325v1
• Date: Mon, 11 May 2020 17:50:36 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-04 20:57:50.196380
• Title: A Relational Gradient Descent Algorithm For Support Vector Machine Training
• Title（参考訳）: ベクトルマシン訓練支援のための関係勾配Descentアルゴリズム
• Authors: Mahmoud Abo-Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs, Alireza Samadian
• Abstract要約: 我々は、データをリレーショナル形式にする場合に、SVM(Support Vector Machine)トレーニングのためのアルゴリズムのような勾配勾配を考える。 まず、SVM の目的関数の勾配の定数近似が非巡回結合に対しても$#P$-hardであることを示すことによって、減算問題を克服できないことを示す。 我々は、実際の勾配を用いて達成されたものと同等の速度で安定したインスタンスの収束を保証する疑似勾配'を計算する効率的なアルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 15.338931971492288
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: 我々は、データをリレーショナル形式にする場合に、SVM(Support Vector Machine)トレーニングのためのアルゴリズムのような勾配勾配を考える。 SVM の目的の勾配は ``サブトラクション問題'' に苦しむため、既知の手法で効率的に計算することはできない。 まず, svm 目的関数の勾配の定数近似の計算は非巡回結合であっても $\#p$-hard であることを示すことにより, 減算問題は克服できないことを示した。 しかし、我々は、安定なインスタンスに注意を向けることによって減算問題を回避し、直感的には、ポイントがわずかに摂動した場合、ほぼ最適解がほぼ最適であるインスタンスである。 実際の勾配を用いて達成した値に匹敵する速度で安定インスタンスの収束を保証する `pseudo-gradient''' を計算する効率的なアルゴリズムを与える。 その結果,このような安定性が,減算問題が発生する他の学習問題に対して,関係データに基づくアルゴリズム設計の文脈において有用な知見をもたらす可能性が示唆された。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Efficient Gradient Approximation Method for Constrained Bilevel Optimization [2.0305676256390934]
  大規模高次元データを用いたバイレベル最適化が開発されている。 本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
  論文  参考訳（メタデータ） (2023-02-03T19:34:56Z)
• A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization [10.820943271350442]
  本稿では,雑音の多いコストサンプルに対する期待値であるスムーズな目的関数を最小化するための凸勾配アルゴリズムを提案する。 また,本アルゴリズムは局所最小値への収束を示唆し,レートリリアを回避できることも示している。
  論文  参考訳（メタデータ） (2022-07-30T18:50:36Z)
• Random-reshuffled SARAH does not need a full gradient computations [61.85897464405715]
  StochAstic Recursive grAdientritHm (SARAH)アルゴリズムは、Gradient Descent (SGD)アルゴリズムのばらつき低減版である。 本稿では,完全勾配の必要性を除去する。 集約された勾配は、SARAHアルゴリズムの完全な勾配の見積もりとなる。
  論文  参考訳（メタデータ） (2021-11-26T06:00:44Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Stochastic Compositional Gradient Descent under Compositional constraints [13.170519806372075]
  目的関数と制約関数が凸であり,関数の合成として表される制約最適化問題について検討する。 この問題は、公平な分類/回帰とキューシステムの設計に生じる。 提案手法は最適かつ実現可能な解をほぼ確実に見つけることが保証されている。
  論文  参考訳（メタデータ） (2020-12-17T05:38:37Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。