論文の概要: On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and
Efficient Gradient Methods
- arxiv url: http://arxiv.org/abs/2312.13970v2
- Date: Fri, 22 Dec 2023 15:28:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-25 17:36:52.193766
- Title: On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and
Efficient Gradient Methods
- Title（参考訳）: 部分最適輸送について:シンクホーンの実用性の改善と効率的な勾配法
- Authors: Anh Duc Nguyen, Tuan Dung Nguyen, Quang Minh Nguyen, Hoang H. Nguyen,
Lam M. Nguyen, Kim-Chuan Toh
- Abstract要約: 本稿では,少なくとも$n$の支持を持つ2つの不均衡測度間の部分最適輸送(POT)問題について検討する。
我々はPOTの新しいラウンドリングアルゴリズムを提案し、次に、$mathcalwidetilde O(n2/varepsilon4)$の複雑さを補正した実行可能なシンクホーン手順を提供する。
- 参考スコア（独自算出の注目度）: 17.14725907264431
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the Partial Optimal Transport (POT) problem between two
unbalanced measures with at most $n$ supports and its applications in various
AI tasks such as color transfer or domain adaptation. There is hence the need
for fast approximations of POT with increasingly large problem sizes in arising
applications. We first theoretically and experimentally investigate the
infeasibility of the state-of-the-art Sinkhorn algorithm for POT due to its
incompatible rounding procedure, which consequently degrades its qualitative
performance in real world applications like point-cloud registration. To this
end, we propose a novel rounding algorithm for POT, and then provide a feasible
Sinkhorn procedure with a revised computation complexity of
$\mathcal{\widetilde O}(n^2/\varepsilon^4)$. Our rounding algorithm also
permits the development of two first-order methods to approximate the POT
problem. The first algorithm, Adaptive Primal-Dual Accelerated Gradient Descent
(APDAGD), finds an $\varepsilon$-approximate solution to the POT problem in
$\mathcal{\widetilde O}(n^{2.5}/\varepsilon)$, which is better in $\varepsilon$
than revised Sinkhorn. The second method, Dual Extrapolation, achieves the
computation complexity of $\mathcal{\widetilde O}(n^2/\varepsilon)$, thereby
being the best in the literature. We further demonstrate the flexibility of POT
compared to standard OT as well as the practicality of our algorithms on real
applications where two marginal distributions are unbalanced.
- Abstract（参考訳）: 本稿では、最大$n$の非バランスな2つの測度間の部分最適輸送(POT)問題と、色移動やドメイン適応といった様々なAIタスクへの応用について検討する。
したがって、アプリケーションの原因となる問題のサイズがますます大きくなるPOTの高速な近似が必要である。
我々はまず,ポットに対する最先端のシンクホーンアルゴリズムの非互換な丸め手順による実現不可能性を理論的に実験的に検討し,ポイントクラウド登録のような実世界のアプリケーションにおける質的性能を低下させる。
そこで本研究では,POT の新たなラウンドリングアルゴリズムを提案し,計算複雑性を$\mathcal{\widetilde O}(n^2/\varepsilon^4)$に修正した,実行可能な Sinkhorn プロシージャを提案する。
丸めアルゴリズムはポット問題を近似する2つの一階法の開発も可能にしている。
最初のアルゴリズムであるadaptive primal-dual accelerated gradient descent (apdagd) は、修正されたシンクホーンよりも$\varepsilon$の方が良い$\mathcal{\widetilde o}(n^{2.5}/\varepsilon)$のポット問題に対する$\varepsilon$-approximate solutionを見つける。
2つ目の方法であるDual Extrapolationは、$\mathcal{\widetilde O}(n^2/\varepsilon)$の計算複雑性を実現する。
さらに,ポットの柔軟性を標準otと比較し,二つの限界分布が不均衡な実アプリケーションにおけるアルゴリズムの実用性を示す。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳（メタデータ） (2023-01-23T19:13:25Z) - 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) - On Unbalanced Optimal Transport: Gradient Methods, Sparsity and
Approximation Error [18.19398247972205]
我々は、少なくとも$n$の成分を持つ、おそらく異なる質量の2つの測度の間の不均衡最適輸送(UOT)について研究する。
UOT問題に対する$varepsilon$-approximateの解を求めるために,GEM-UOT(Gradient Extrapolation Method)に基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-08T03:22:39Z) - On Multimarginal Partial Optimal Transport: Equivalent Forms and
Computational Complexity [11.280177531118206]
我々は,少なくとも$n$のサポートを持つ離散的(アンバランスな)測度間のマルチマルジナル部分最適輸送(POT)問題について検討した。
まず、コストテンソルの新たな拡張を通じて、マルチマルジナルな最適輸送問題の観点から、マルチマルジナルPOT問題の2つの等価形式が得られることを証明した。
我々は、ApproxMPOTアルゴリズムが、$tildemathcalO(m3(n+1)m/ varの計算複雑性上界を持つマルチマルジナルPOT問題の最適値を近似できることを実証した。
論文 参考訳（メタデータ） (2021-08-18T06:46:59Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - 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) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm [24.09910756628079]
UOT問題に対する$varepsilon$-approximateソリューションを見つけるためのシンクホーンアルゴリズムの複雑さは、ほぼ直線時間である$widetildemathcalO(n2/ varepsilon)$である。
我々の証明手法は、エントロピー正則化 UOT 問題の最適双対解と原始解のいくつかの性質に対するシンクホーン更新の幾何収束に基づいている。
論文 参考訳（メタデータ） (2020-02-09T06:03:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。