論文の概要: On Unbalanced Optimal Transport: Gradient Methods, Sparsity and
Approximation Error
- arxiv url: http://arxiv.org/abs/2202.03618v4
- Date: Mon, 8 Jan 2024 06:10:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-10 00:58:51.224216
- Title: On Unbalanced Optimal Transport: Gradient Methods, Sparsity and
Approximation Error
- Title（参考訳）: 不均衡最適輸送について:勾配法、スパーシティおよび近似誤差
- Authors: Quang Minh Nguyen, Hoang H. Nguyen, Yi Zhou, Lam M. Nguyen
- Abstract要約: 我々は、少なくとも$n$の成分を持つ、おそらく異なる質量の2つの測度の間の不均衡最適輸送(UOT)について研究する。
UOT問題に対する$varepsilon$-approximateの解を求めるために,GEM-UOT(Gradient Extrapolation Method)に基づく新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 18.19398247972205
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the Unbalanced Optimal Transport (UOT) between two measures of
possibly different masses with at most $n$ components, where the marginal
constraints of standard Optimal Transport (OT) are relaxed via Kullback-Leibler
divergence with regularization factor $\tau$. Although only Sinkhorn-based UOT
solvers have been analyzed in the literature with the iteration complexity of
${O}\big(\tfrac{\tau \log(n)}{\varepsilon}
\log\big(\tfrac{\log(n)}{{\varepsilon}}\big)\big)$ and per-iteration cost of
$O(n^2)$ for achieving the desired error $\varepsilon$, their positively dense
output transportation plans strongly hinder the practicality. On the other
hand, while being vastly used as heuristics for computing UOT in modern deep
learning applications and having shown success in sparse OT problem, gradient
methods applied to UOT have not been formally studied. In this paper, we
propose a novel algorithm based on Gradient Extrapolation Method (GEM-UOT) to
find an $\varepsilon$-approximate solution to the UOT problem in $O\big( \kappa
\log\big(\frac{\tau n}{\varepsilon}\big) \big)$ iterations with
$\widetilde{O}(n^2)$ per-iteration cost, where $\kappa$ is the condition number
depending on only the two input measures. Our proof technique is based on a
novel dual formulation of the squared $\ell_2$-norm UOT objective, which fills
the lack of sparse UOT literature and also leads to a new characterization of
approximation error between UOT and OT. To this end, we further present a novel
approach of OT retrieval from UOT, which is based on GEM-UOT with fine tuned
$\tau$ and a post-process projection step. Extensive experiments on synthetic
and real datasets validate our theories and demonstrate the favorable
performance of our methods in practice.
- Abstract（参考訳）: 標準最適輸送(OT)の限界制約は、正規化係数$\tau$でクルバック・リーブラー分散(Kullback-Leibler divergence)を介して緩和される。
Sinkhorn をベースとした UOT ソルバは、文献において ${O}\big(\tfrac{\tau \log(n)}{\varepsilon} \log\big(\tfrac{\log(n)}{{\varepsilon}}\big)\big)$ と per-iteration cost of $O(n^2)$ の反復複雑性でのみ分析されているが、その正に密度の高い出力輸送計画が実用性を強く妨げている。
一方、現代の深層学習アプリケーションにおいて、UOT計算のヒューリスティックスとして広く使われており、疎部OT問題に成功しているにもかかわらず、UOTに適用された勾配法は公式には研究されていない。
本稿では,Gdient Extrapolation Method (GEM-UOT) に基づく新しいアルゴリズムを提案し,UOT問題に対する$\varepsilon$-approximate Solution を$O\big( \kappa \log\big(\frac{\tau n}{\varepsilon}\big) \big)$ iterations with $\widetilde{O}(n^2)$ per-iteration cost, where $\kappa$は2つの入力手段のみに依存する条件数である。
この証明手法は、2乗の$\ell_2$-norm uot 目的の新たな二重定式化に基づくもので、uot と ot の近似誤差の新たなキャラクタリゼーションを導出する。
この目的のために我々はさらに,$\tau$ を微調整した gem-uot に基づいた uot からの ot 検索手法と後処理の投影ステップを提案する。
合成データと実データに関する広範な実験は,理論を検証し,実際の手法の良好な性能を示す。
関連論文リスト
- Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization [48.84672493756553]
我々は,1ステップあたり$Obig(slogfrac dsbig)$クエリのみを使用する勾配のクエリ効率と精度の高い推定器を提案する。
Indyk-Price-Woodruff (IPW) アルゴリズムを線形測定から非線形関数への圧縮センシングにおいて一般化した。
論文 参考訳（メタデータ） (2024-05-27T03:52:53Z) - 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) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Double Thompson Sampling in Finite stochastic Games [10.559241770674724]
有限割引マルコフ決定プロセスの下での探索と利用のトレードオフ問題を考察する。
このような問題を解決するために、二重トンプソンサンプリング強化学習アルゴリズム(DTS)を提案する。
論文 参考訳（メタデータ） (2022-02-21T06:11:51Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - 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) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。