論文の概要: A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem
- arxiv url: http://arxiv.org/abs/2310.18446v2
- Date: Sat, 25 Nov 2023 19:05:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-30 13:26:35.331086
- Title: A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem
- Title（参考訳）: 動的最適輸送問題のための新しいスキップ直交リスト
- Authors: Xiaoyang Xu, Hu Ding
- Abstract要約: 興味深い離散的動的最適輸送問題を考える。
データポイントの重みや位置が変わった場合、最適なトランスポートプランを効率的に更新できますか?
- 参考スコア（独自算出の注目度）: 12.453673268803234
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Optimal transportation is a fundamental topic that has attracted a great
amount of attention from machine learning community in the past decades. In
this paper, we consider an interesting discrete dynamic optimal transport
problem: can we efficiently update the optimal transport plan when the weights
or the locations of the data points change? This problem is naturally motivated
by several applications in machine learning. For example, we often need to
compute the optimal transportation cost between two different data sets; if
some change happens to a few data points, should we re-compute the high
complexity cost function or update the cost by some efficient dynamic data
structure? We are aware that several dynamic maximum flow algorithms have been
proposed before, however, the research on dynamic minimum cost flow problem is
still quite limited, to the best of our knowledge. We propose a novel 2D Skip
Orthogonal List together with some dynamic tree techniques. Although our
algorithm is based on the conventional simplex method, it can efficiently
complete each pivoting operation within $O(|V|)$ time with high probability
where $V$ is the set of all supply and demand nodes. Since dynamic
modifications typically do not introduce significant changes, our algorithm
requires only a few simplex iterations in practice. So our algorithm is more
efficient than re-computing the optimal transportation cost that needs at least
one traversal over all the $O(|E|) = O(|V|^2)$ variables in general cases. Our
experiments demonstrate that our algorithm significantly outperforms existing
algorithms in the dynamic scenarios.
- Abstract（参考訳）: 最適な輸送は、過去数十年間、機械学習コミュニティから多くの注目を集めてきた基本的なトピックである。
本稿では,データポイントの重みや位置が変化するとき,最適輸送計画を効率的に更新できるかという,興味深い離散的動的最適輸送問題を考える。
この問題は、機械学習のいくつかの応用によって自然に動機付けられている。
例えば、2つの異なるデータセット間の最適な輸送コストを計算する必要がある。いくつかのデータポイントに何らかの変更が発生した場合、高複雑性コスト関数を再計算するか、あるいは効率的な動的データ構造によってコストを更新するべきか?
これまでいくつかの動的最大フローアルゴリズムが提案されてきたが、我々の知る限りでは、動的最小コストフロー問題の研究はまだかなり限られている。
本稿では,新しい2次元スキップ直交リストと動的木手法を提案する。
このアルゴリズムは従来のsimplex法に基づいているが、各ピボット操作をo(|v|)$時間で効率的に完了でき、そこでは$v$が全ての需給ノードの集合である確率が高い。
動的修正は通常大きな変更を起こさないため、我々のアルゴリズムは実際に数回の単純な反復しか必要としない。
したがって、一般的な場合、O(|E|) = O(|V|^2)$変数に対して少なくとも1つのトラバーサルを必要とする最適な輸送コストを再計算するよりも効率的である。
実験により,本アルゴリズムが動的シナリオにおいて既存のアルゴリズムを大きく上回ることを示した。
関連論文リスト
- Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
最適輸送理論はそのような写像を構築するための原則化された枠組みを提供する。
本稿では,Wasserstein-1に基づく新しい最適輸送解法を提案する。
実験により,提案した解法は,2次元データセット上に一意かつ単調な写像を求める際に,$W$ OTソルバを模倣できることを示した。
論文 参考訳（メタデータ） (2024-11-01T14:23:19Z) - Time-Varying Convex Optimization with $O(n)$ Computational Complexity [0.0]
コスト関数が時間とともに変化する非拘束凸最適化の問題を考える。
提案アルゴリズムは,決定変数に対するコスト関数の1次微分のみを必要とする。
具体的には、提案アルゴリズムは、計算コストを1タイムステップあたり$(n3)$から$O(n)$に削減する。
論文 参考訳（メタデータ） (2024-10-19T06:45:05Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳（メタデータ） (2021-11-30T14:16:48Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Fast Learning for Renewal Optimization in Online Task Scheduling [18.935043109084543]
本稿では,リニューアル・リワードシステムのオンライン最適化について考察する。
タスク型ベクトルの確率分布は未知である。
提案アルゴリズムは,古典的なRobins-Monroイテレーションに従って更新される補助変数を用いる。
論文 参考訳（メタデータ） (2020-07-18T22:44:13Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - An Efficient $k$-modes Algorithm for Clustering Categorical Datasets [8.528384027684194]
我々は, OTQT と呼ばれる$k$-modes の斬新で効率的な実装を提供する。
OTQTは既存の$k$-modesアルゴリズムでは検出不可能な目的関数を改善するために更新されていることを証明している。
OTQTはイテレーション毎に常に正確で、最終最適化までほぼ常に高速である(一部のデータセットではわずかに遅い)。
論文 参考訳（メタデータ） (2020-06-06T18:41:36Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Constrained Multiagent Rollout and Multidimensional Assignment with the
Auction Algorithm [0.0]
本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。
提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。
コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
論文 参考訳（メタデータ） (2020-02-18T07:09:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。