論文の概要: On the Convergence of Gradient Extrapolation Methods for Unbalanced
Optimal Transport
- arxiv url: http://arxiv.org/abs/2202.03618v1
- Date: Tue, 8 Feb 2022 03:22:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-09 16:20:00.898946
- Title: On the Convergence of Gradient Extrapolation Methods for Unbalanced
Optimal Transport
- 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)に基づくアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 16.972099310155787
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the Unbalanced Optimal Transport (UOT) between two measures of
possibly different masses with at most $n$ components, where marginal
constraints of the standard Optimal Transport (OT) are relaxed via
Kullback-Leibler divergence with regularization factor $\tau$. 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 n^2
\log\big(\frac{\tau n}{\varepsilon}\big) \big)$, where $\kappa$ is the
condition number depending on only the two input measures. Compared to the only
known complexity ${O}\big(\tfrac{\tau n^2 \log(n)}{\varepsilon}
\log\big(\tfrac{\log(n)}{{\varepsilon}}\big)\big)$ for solving the UOT problem
via the Sinkhorn algorithm, ours is better in $\varepsilon$ and lifts
Sinkhorn's linear dependence on $\tau$, which hindered its practicality to
approximate the standard OT via UOT. Our proof technique is based on a novel
dual formulation of the squared $\ell_2$-norm regularized UOT objective, which
is of independent interest and also leads to a new characterization of
approximation error between UOT and OT in terms of both the transportation plan
and transport distance. To this end, we further present an algorithm, based on
GEM-UOT with fine tuned $\tau$ and a post-process projection step, to find an
$\varepsilon$-approximate solution to the standard OT problem in $O\big( \kappa
n^2 \log\big(\frac{ n}{\varepsilon}\big) \big)$, which is a new complexity in
the literature of OT. 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)を介して緩和される。
グラデーション外挿法(gem-uot)に基づく新しいアルゴリズムを提案し、uot問題に対する$o\big( \kappa n^2 \log\big(\frac{\tau n}{\varepsilon}\big) \big)$,ただし$\kappa$は2つの入力測度のみに依存する条件数である。
唯一の既知の複雑性である${o}\big(\tfrac{\tau n^2 \log(n)}{\varepsilon} \log\big(\tfrac{\log(n)}{{\varepsilon}}\big)\big)$ をシンクホーンアルゴリズムで解くために、我々は$\varepsilon$の方が優れており、$\tau$に対するシンクホーンの線形依存を持ち上げている。
この証明手法は、2乗の$\ell_2$-norm正規化uot目的の新たな二重定式化に基づいているが、これは独立興味を持ち、輸送計画と輸送距離の両方の観点から、uotとotの近似誤差の新たなキャラクタリゼーションにつながる。
この目的のために、我々はさらに、$\tau$ の微調整された gem-uot とプロセス後の投影ステップに基づいて、標準 ot 問題に対する $o\big( \kappa n^2 \log\big(\frac{ n}{\varepsilon}\big) \big)$ の $\varepsilon$-approximate solution を見つけるアルゴリズムを提示する。
合成データと実データに関する広範な実験は,理論を検証し,実際の手法の良好な性能を示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。