論文の概要: Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization

• arxiv url: http://arxiv.org/abs/2007.00419v1
• Date: Wed, 1 Jul 2020 12:22:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-14 22:08:30.138227
• Title: Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization
• Title（参考訳）: Tsallis分枝規則化によるスパースランダム化最短経路ルーティング
• Authors: Pierre Leleux, Sylvain Courtain, Guillaume Guex and Marco Saerens
• Abstract要約: 本研究は、重み付き有向グラフG上のソースノートsからターゲットノードtに到達するための最適ルーティングポリシーを設計する問題について詳述する。 ノードクラスタリングと半教師付き分類タスクの実験的比較により,予測されるルーティングコストに基づく導出相似度測定が最先端の結果をもたらすことが示された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work elaborates on the important problem of (1) designing optimal randomized routing policies for reaching a target node t from a source note s on a weighted directed graph G and (2) defining distance measures between nodes interpolating between the least cost (based on optimal movements) and the commute-cost (based on a random walk on G), depending on a temperature parameter T. To this end, the randomized shortest path formalism (RSP, [2,99,124]) is rephrased in terms of Tsallis divergence regularization, instead of Kullback-Leibler divergence. The main consequence of this change is that the resulting routing policy (local transition probabilities) becomes sparser when T decreases, therefore inducing a sparse random walk on G converging to the least-cost directed acyclic graph when T tends to 0. Experimental comparisons on node clustering and semi-supervised classification tasks show that the derived dissimilarity measures based on expected routing costs provide state-of-the-art results. The sparse RSP is therefore a promising model of movements on a graph, balancing sparse exploitation and exploration in an optimal way.
• Abstract（参考訳）: This work elaborates on the important problem of (1) designing optimal randomized routing policies for reaching a target node t from a source note s on a weighted directed graph G and (2) defining distance measures between nodes interpolating between the least cost (based on optimal movements) and the commute-cost (based on a random walk on G), depending on a temperature parameter T. To this end, the randomized shortest path formalism (RSP, [2,99,124]) is rephrased in terms of Tsallis divergence regularization, instead of Kullback-Leibler divergence. この変化の主な結果は、t が減少すると経路ポリシー(局所遷移確率)がスパーザーとなるため、t が 0 になると最小コストの有向非巡回グラフに収束する g 上のスパースランダムウォークを誘導する。 ノードクラスタリングと半教師付き分類タスクの実験的比較により,予測されるルーティングコストに基づく導出相似度測定が最先端の結果をもたらすことが示された。 したがってスパース rsp はグラフ上の動きの有望なモデルであり、スパース搾取と探索を最適な方法でバランスさせる。

関連論文リスト

• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。 本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
  論文  参考訳（メタデータ） (2023-06-27T08:15:28Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Generalization Error Bounds for Deep Neural Networks Trained by SGD [3.148524502470734]
  勾配降下(SGD)により訓練された深度に対する一般化誤差境界を導出する。 境界は、トレーニング軌跡に沿った損失に明示的に依存する。 その結果、ニューラルネットワークとネットワークハイパースの変化により、境界は非空洞で堅牢であることが判明した。
  論文  参考訳（メタデータ） (2022-06-07T13:46:10Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks [30.231314171218994]
  分散学習において、ノードのネットワークは、通常、その局所的な目的の有限サムである全体的な目的関数を最小化するために協力する。 そこで本研究では,分散縮小手法を利用して分散学習を高速化する新しいアルゴリズムDPSVRGを提案する。
  論文  参考訳（メタデータ） (2021-12-20T08:23:36Z)
• Relative Entropy-Regularized Optimal Transport on a Graph: a new algorithm and an experimental comparison [0.0]
  本研究は,ランダム化された最短経路形式におけるグラフ問題に対する最適輸送を解くための,新しい相対エントロピー正規化アルゴリズムについて検討する。 この新たな定式化の主な利点は、エッジフローキャパシティの制約に容易に対応できるという事実である。 結果として得られる最適ルーティングポリシー、すなわち各ノードのエッジに従う確率分布はマルコビアンであり、入力と出力を所定の限界確率に制限することで計算される。
  論文  参考訳（メタデータ） (2021-08-23T08:25:51Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• A hybrid variance-reduced method for decentralized stochastic non-convex optimization [15.447966950703947]
  textttGTHSGDアルゴリズムは、グローバルな勾配を追跡するためにネットワークを実装している。 textttGTHSGDは、必要なエラートレランス$epsilon$が十分小さいときに、ネットワークの複雑さを$O(n-1)$にします。
  論文  参考訳（メタデータ） (2021-02-12T20:13:05Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)

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

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