論文の概要: On Robust Wasserstein Barycenter: The Model and Algorithm
- arxiv url: http://arxiv.org/abs/2312.15762v1
- Date: Mon, 25 Dec 2023 16:20:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-27 16:28:19.664337
- Title: On Robust Wasserstein Barycenter: The Model and Algorithm
- Title(参考訳): ロバストなwaserstein barycenter:モデルとアルゴリズムについて
- Authors: Xu Wang, Jiawei Huang, Qingyuan Yang, Jinpeng Zhang
- Abstract要約: 固定支援RWB (fixed-RWB) と自由支援RWB (free-RWB) の2種類のロバストなバリセンター問題 (RWB) の計算効率向上に焦点をあてる。
まず、モデル還元による効率の改善を行い、固定RWBと自由RWBの両方で機能する拡張ワッサーシュタインバリセンタ問題としてRWBを削減する。
次に,モデル削減手法とコアセット手法を組み合わせることで,重みと位置を交互に更新することで,自由RWBのアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 12.95062444722496
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Wasserstein barycenter problem is to compute the average of $m$ given
probability measures, which has been widely studied in many different areas;
however, real-world data sets are often noisy and huge, which impedes its
applications in practice. Hence, in this paper, we focus on improving the
computational efficiency of two types of robust Wasserstein barycenter problem
(RWB): fixed-support RWB (fixed-RWB) and free-support RWB (free-RWB); actually,
the former is a subroutine of the latter. Firstly, we improve efficiency
through model reducing; we reduce RWB as an augmented Wasserstein barycenter
problem, which works for both fixed-RWB and free-RWB. Especially, fixed-RWB can
be computed within $\widetilde{O}(\frac{mn^2}{\epsilon_+})$ time by using an
off-the-shelf solver, where $\epsilon_+$ is the pre-specified additive error
and $n$ is the size of locations of input measures. Then, for free-RWB, we
leverage a quality guaranteed data compression technique, coreset, to
accelerate computation by reducing the data set size $m$. It shows that running
algorithms on the coreset is enough instead of on the original data set. Next,
by combining the model reducing and coreset techniques above, we propose an
algorithm for free-RWB by updating the weights and locations alternatively.
Finally, our experiments demonstrate the efficiency of our techniques.
- Abstract(参考訳): ヴァッサーシュタインのバリセンタ問題は、多くの異なる領域で広く研究されている平均$m$の確率測度を計算することであるが、現実のデータセットはしばしばうるさくて巨大であり、実際にはその応用を妨げている。
そこで本稿では,2種類のロバストなWasserstein Barycenter問題(RWB):固定サポートRWB(fixed-RWB)と自由サポートRWB(free-RWB)の計算効率の向上に焦点をあてる。
まず、モデル還元による効率の改善を行い、固定RWBと自由RWBの両方で機能する拡張ワッサーシュタインバリセンタ問題としてRWBを削減する。
特に、固定rwb は、既定の加算誤差である $\epsilon_+$ と入力測度の位置の大きさである $n$ を用いて、既定のソルバを用いて $\widetilde{o}(\frac{mn^2}{\epsilon_+})$ 内で計算することができる。
そして,自由RWBの場合,品質保証データ圧縮技術であるcoresetを活用し,データセットサイズを$m$にすることで計算を高速化する。
コアセット上でのアルゴリズムの実行は、元のデータセットではなく、十分であることを示している。
次に,モデル削減手法とコアセット手法を組み合わせることで,重みと位置を交互に更新することで,自由RWBのアルゴリズムを提案する。
最後に,実験によりその効果を実証した。
関連論文リスト
- A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳(メタデータ) (2023-10-21T18:48:45Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Approximative Algorithms for Multi-Marginal Optimal Transport and
Free-Support Wasserstein Barycenters [0.0]
N$離散確率測度に対する2乗ユークリッドコストで, マルチマルジナル最適輸送(MOT)の解を近似する2つのアルゴリズムを提案する。
高速で、メモリ効率が高く、実装も簡単で、どのスパースOTソルバでもブラックボックスとして使用することができる。
論文 参考訳(メタデータ) (2022-02-02T10:59:54Z) - Wasserstein Iterative Networks for Barycenter Estimation [80.23810439485078]
生成モデルを用いて連続測度のワッサーシュタイン2バリセンターを近似するアルゴリズムを提案する。
有名人の顔のデータセットに基づいて、バリセンタアルゴリズムの定量的評価に使用できるAve, celeba!データセットを構築した。
論文 参考訳(メタデータ) (2022-01-28T16:59:47Z) - Dimensionality Reduction for Wasserstein Barycenter [6.327655795051619]
本稿では,Wasserstein Barycenter問題に対する次元還元手法について検討する。
ランダム化次元減少は、その問題を$d$と$k$に独立に次元$O(log n)$の空間にマッピングするために利用できることを示す。
また、Wasserstein Barycenter問題に対するコアセットの構成も提供し、入力分布を著しく減少させる。
論文 参考訳(メタデータ) (2021-10-18T02:57:25Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Projection Robust Wasserstein Barycenter [36.97843660480747]
ワッサースタイン・バリセンターの 近似は 次元の呪いのため 数値的に困難です
本稿では,次元の呪いを緩和するプロジェクションロバストなワッサーシュタインバリセンタ(PRWB)を提案する。
論文 参考訳(メタデータ) (2021-02-05T19:23:35Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Sparse Regression at Scale: Branch-and-Bound rooted in First-Order
Optimization [6.037383467521294]
我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。
私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。
実装をツールキットL0BnBでオープンソースにしています。
論文 参考訳(メタデータ) (2020-04-13T18:45:29Z) - Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。
本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
論文 参考訳(メタデータ) (2020-04-09T01:45:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。