論文の概要: Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm
- arxiv url: http://arxiv.org/abs/2002.04783v11
- Date: Sat, 17 Jul 2021 06:25:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 20:31:58.500832
- Title: Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm
- Title（参考訳）: 固定サポートwaserstein barycenters: 計算のハードネスと高速アルゴリズム
- Authors: Tianyi Lin, Nhat Ho, Xi Chen, Marco Cuturi, and Michael I. Jordan
- Abstract要約: 固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
- 参考スコア（独自算出の注目度）: 100.11971836788437
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the fixed-support Wasserstein barycenter problem (FS-WBP), which
consists in computing the Wasserstein barycenter of $m$ discrete probability
measures supported on a finite metric space of size $n$. We show first that the
constraint matrix arising from the standard linear programming (LP)
representation of the FS-WBP is \textit{not totally unimodular} when $m \geq 3$
and $n \geq 3$. This result resolves an open question pertaining to the
relationship between the FS-WBP and the minimum-cost flow (MCF) problem since
it proves that the FS-WBP in the standard LP form is not an MCF problem when $m
\geq 3$ and $n \geq 3$. We also develop a provably fast \textit{deterministic}
variant of the celebrated iterative Bregman projection (IBP) algorithm, named
\textsc{FastIBP}, with a complexity bound of
$\tilde{O}(mn^{7/3}\varepsilon^{-4/3})$, where $\varepsilon \in (0, 1)$ is the
desired tolerance. This complexity bound is better than the best known
complexity bound of $\tilde{O}(mn^2\varepsilon^{-2})$ for the IBP algorithm in
terms of $\varepsilon$, and that of $\tilde{O}(mn^{5/2}\varepsilon^{-1})$ from
accelerated alternating minimization algorithm or accelerated primal-dual
adaptive gradient algorithm in terms of $n$. Finally, we conduct extensive
experiments with both synthetic data and real images and demonstrate the
favorable performance of the \textsc{FastIBP} algorithm in practice.
- Abstract（参考訳）: 固定支援ワッサーシュタイン・バリセンタ問題 (FS-WBP) は、ワッサーシュタイン・バリセンタが$m$の離散確率測度を計算し、大きさが$n$の有限距離空間で支援するものである。
まず、FS-WBPの標準線形プログラミング(LP)表現から生じる制約行列が、$m \geq 3$ および $n \geq 3$ であるときに \textit{not completely unimodular} であることを示す。
この結果は、標準LP形式のFS-WBPが m \geq 3$ および $n \geq 3$ のときの MCF 問題ではないことを証明するため、FS-WBP と最小コストフロー(MCF)問題との関係に関するオープンな疑問を解決する。
また、祝福された反復的ブレグマン射影(IBP)アルゴリズムの証明可能な高速な \textit{deterministic} 変種である \textsc{FastIBP} を開発し、複雑さは$\tilde{O}(mn^{7/3}\varepsilon^{-4/3})$で、$\varepsilon \in (0, 1)$は所望の許容値である。
この複雑性境界は、$\tilde{O}(mn^2\varepsilon^{-2})$と$\tilde{O}(mn^{5/2}\varepsilon^{-1})$の条件でIPPアルゴリズムに対して、$n$の条件でアクセラレーションされた交代最小化アルゴリズムまたはアクセラレーションされた原始双対適応勾配アルゴリズムよりも優れている。
最後に, 合成データと実画像の両方を用いて広範な実験を行い, 実際に, textsc{FastIBP} アルゴリズムの性能を実証する。
関連論文リスト
- Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳（メタデータ） (2021-11-28T14:08:25Z) - 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) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。