論文の概要: Solving a Special Type of Optimal Transport Problem by a Modified
Hungarian Algorithm
- arxiv url: http://arxiv.org/abs/2210.16645v1
- Date: Sat, 29 Oct 2022 16:28:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 18:38:45.366309
- Title: Solving a Special Type of Optimal Transport Problem by a Modified
Hungarian Algorithm
- Title（参考訳）: 修正ハンガリーアルゴリズムによる特殊型最適輸送問題の解法
- Authors: Yiling Xie, Yiling Luo, Xiaoming Huo
- Abstract要約: 本稿では,特殊な輸送問題 (OT) について検討し,それを正確に解くための改良されたハンガリーのアルゴリズムを提案する。
m$と$n$の原子を持つ辺り間のOT問題に対して、提案アルゴリズムの計算複雑性は$O(m2n)$である。
- 参考スコア（独自算出の注目度）: 2.1485350418225244
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We observe that computing empirical Wasserstein distance in the independence
test is an optimal transport (OT) problem with a special structure. This
observation inspires us to study a special type of OT problem and propose a
modified Hungarian algorithm to solve it exactly. For an OT problem between
marginals with $m$ and $n$ atoms ($m\geq n$), the computational complexity of
the proposed algorithm is $O(m^2n)$. Computing the empirical Wasserstein
distance in the independence test requires solving this special type of OT
problem, where we have $m=n^2$. The associate computational complexity of our
algorithm is $O(n^5)$, while the order of applying the classic Hungarian
algorithm is $O(n^6)$. Numerical experiments validate our theoretical analysis.
Broader applications of the proposed algorithm are discussed at the end.
- Abstract（参考訳）: 独立性テストにおける経験的wasserstein距離の計算は、特別な構造を持つ最適輸送(ot)問題である。
この観察は,ot問題の特殊型を研究することを促し,それを正確に解くための修正ハンガリーアルゴリズムを提案する。
m$と$n$の原子(m\geq n$)間のOT問題に対して、提案アルゴリズムの計算複雑性は$O(m^2n)$である。
独立性テストにおける実験的なワッサーシュタイン距離を計算するには、この特別な種類のOT問題を解く必要がある。
我々のアルゴリズムの計算複雑性は$O(n^5)$であり、古典ハンガリーのアルゴリズムを適用する順序は$O(n^6)$である。
数値実験は我々の理論解析を検証する。
最後に,提案アルゴリズムの幅広い応用について論じる。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
ショアのアルゴリズムは、ノイズ中間量子時代の最も重要な量子アルゴリズムの1つであると考えられている。
Shorのアルゴリズムに必要なリソースを削減するために、我々は新しい分散量子古典ハイブリッド順序決定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T13:52:05Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - An Accelerated Stochastic Algorithm for Solving the Optimal Transport
Problem [2.1485350418225244]
線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた一次2次元加速勾配降下法を提案する。
PDASGDは最もよく知られた計算複雑性を享受しており、$widetildemathcalO(n2/epsilon)$、$n$は原子の数、$epsilon>0$は精度である。
論文 参考訳（メタデータ） (2022-03-02T01:16:10Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。