論文の概要: On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
- arxiv url: http://arxiv.org/abs/2002.03293v2
- Date: Thu, 19 Nov 2020 04:02:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 14:52:22.866720
- Title: On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
- Title（参考訳）: 非平衡最適輸送について:シンクホーンアルゴリズムの解析
- Authors: Khiem Pham and Khang Le and Nhat Ho and Tung Pham and Hung Bui
- Abstract要約: UOT問題に対する$varepsilon$-approximateソリューションを見つけるためのシンクホーンアルゴリズムの複雑さは、ほぼ直線時間である$widetildemathcalO(n2/ varepsilon)$である。
我々の証明手法は、エントロピー正則化 UOT 問題の最適双対解と原始解のいくつかの性質に対するシンクホーン更新の幾何収束に基づいている。
- 参考スコア（独自算出の注目度）: 24.09910756628079
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide a computational complexity analysis for the Sinkhorn algorithm
that solves the entropic regularized Unbalanced Optimal Transport (UOT) problem
between two measures of possibly different masses with at most $n$ components.
We show that the complexity of the Sinkhorn algorithm for finding an
$\varepsilon$-approximate solution to the UOT problem is of order
$\widetilde{\mathcal{O}}(n^2/ \varepsilon)$, which is near-linear time. To the
best of our knowledge, this complexity is better than the complexity of the
Sinkhorn algorithm for solving the Optimal Transport (OT) problem, which is of
order $\widetilde{\mathcal{O}}(n^2/\varepsilon^2)$. Our proof technique is
based on the geometric convergence of the Sinkhorn updates to the optimal dual
solution of the entropic regularized UOT problem and some properties of the
primal solution. It is also different from the proof for the complexity of the
Sinkhorn algorithm for approximating the OT problem since the UOT solution does
not have to meet the marginal constraints.
- Abstract（参考訳）: 我々は,最大$n$成分の異なる質量の2つの測度間のエントロピー正則化不平衡最適輸送(uot)問題を解く,シンクホーンアルゴリズムの計算複雑性解析を提供する。
uot問題に対する$\varepsilon$-approximate 解を見つけるためのシンクホーンアルゴリズムの複雑さは、ほぼ線形時間である$\widetilde{\mathcal{o}}(n^2/ \varepsilon)$である。
我々の知る限り、この複雑さは最適輸送(OT)問題を解くシンクホーンアルゴリズムの複雑さよりも優れており、これは$\widetilde{\mathcal{O}}(n^2/\varepsilon^2)$である。
この証明手法は,エントロピー正則化 uot 問題の最適双対解に対するシンクホーン更新の幾何学的収束と原始解のいくつかの性質に基づいている。
また、UTT解が限界制約を満たす必要がないため、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) - A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems with Optimal Iteration Complexity [2.815239177328595]
凸凹極小最適化問題の解法として,Lipschitz-free Cubal regularization (LF-CR)アルゴリズムを提案する。
また,この問題のパラメータを必要としない完全パラメータフリー立方正則化(FF-CR)アルゴリズムを提案する。
我々の知る限り、FF-CRアルゴリズムは凸凹極小最適化問題の解法として初めて完全にパラメータフリーな2次アルゴリズムである。
論文 参考訳（メタデータ） (2024-07-04T01:46:07Z) - On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and
Efficient Gradient Methods [17.14725907264431]
本稿では,少なくとも$n$の支持を持つ2つの不均衡測度間の部分最適輸送(POT)問題について検討する。
我々はPOTの新しいラウンドリングアルゴリズムを提案し、次に、$mathcalwidetilde O(n2/varepsilon4)$の複雑さを補正した実行可能なシンクホーン手順を提供する。
論文 参考訳（メタデータ） (2023-12-21T15:56:09Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - 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) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - On Robust Optimal Transport: Computational Complexity, Low-rank
Approximation, and Barycenter Computation [14.80695185915604]
我々は、最適なトランスポートの2つの頑健なバージョン、$textitRobust Semi-constrained Optimal Transport$ (RSOT) と $textitRobust Unconstrained Optimal Transport$ (ROT) を考える。
離散設定における両方の問題に対して、$widetildemathcalO(fracn2varepsilon)$timeでRSOTとROTの$varepsilon$-approximationsを生成するSinkhornベースのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-13T03:55:52Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。