論文の概要: Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers
- arxiv url: http://arxiv.org/abs/2404.13401v1
- Date: Sat, 20 Apr 2024 15:01:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-23 19:10:11.630654
- Title: Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers
- Title（参考訳）: 外れ値付き$k$Sparse Wasserstein Barycenterの近似アルゴリズム
- Authors: Qingyuan Yang, Hu Ding,
- Abstract要約: 我々は、外乱が存在する場合に、$k$-sparse Wasserstein Barycenter問題を研究する。
既存のWBアルゴリズムは、ケースを外れ値で処理するために直接拡張することはできない。
本稿では,外乱問題のある$k$sparse WBに対して定数近似係数を求めるクラスタリングに基づくLP法を提案する。
- 参考スコア（独自算出の注目度）: 10.259254824702555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Wasserstein Barycenter (WB) is one of the most fundamental optimization problems in optimal transportation. Given a set of distributions, the goal of WB is to find a new distribution that minimizes the average Wasserstein distance to them. The problem becomes even harder if we restrict the solution to be ``$k$-sparse''. In this paper, we study the $k$-sparse WB problem in the presence of outliers, which is a more practical setting since real-world data often contains noise. Existing WB algorithms cannot be directly extended to handle the case with outliers, and thus it is urgently needed to develop some novel ideas. First, we investigate the relation between $k$-sparse WB with outliers and the clustering (with outliers) problems. In particular, we propose a clustering based LP method that yields constant approximation factor for the $k$-sparse WB with outliers problem. Further, we utilize the coreset technique to achieve the $(1+\epsilon)$-approximation factor for any $\epsilon>0$, if the dimensionality is not high. Finally, we conduct the experiments for our proposed algorithms and illustrate their efficiencies in practice.
- Abstract（参考訳）: Wasserstein Barycenter (WB) は最適輸送における最も基本的な最適化問題の1つである。
分布の集合が与えられた場合、WBの目標は、平均ワッサーシュタイン距離を最小化する新しい分布を見つけることである。
解を ``$k$-sparse'' に制限すれば、問題はさらに難しくなる。
本稿では,外乱が存在する場合のWB問題として$k$sparseの問題について検討する。
既存のWBアルゴリズムは、ケースを外れ値で処理するために直接拡張できないため、いくつかの新しいアイデアを開発するために緊急に必要である。
まず、アウトレーヤを持つ$k$sparse WBと(アウトレーヤを持つ)クラスタリング問題との関係について検討する。
特に,外乱問題のある$k$-sparse WBに対して,定数近似係数を求めるクラスタリングに基づくLP法を提案する。
さらに, 1+\epsilon)$-approximation factor を任意の $\epsilon>0$ に対して達成するためにコアセット法を用いる。
最後に,提案アルゴリズムの実験を行い,その実効性を実証する。
関連論文リスト
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。
我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。
PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
論文 参考訳（メタデータ） (2024-11-02T02:50:12Z) - Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
本稿では,Wasserstein Barycenter問題を解くための新しいスケーラブルなアプローチを提案する。
我々の手法は最近のNeural OTソルバをベースとしている。
また,提案手法の理論的誤差境界も確立する。
論文 参考訳（メタデータ） (2024-02-06T09:17:07Z) - On Robust Wasserstein Barycenter: The Model and Algorithm [12.95062444722496]
固定支援RWB (fixed-RWB) と自由支援RWB (free-RWB) の2種類のロバストなバリセンター問題 (RWB) の計算効率向上に焦点をあてる。
まず、モデル還元による効率の改善を行い、固定RWBと自由RWBの両方で機能する拡張ワッサーシュタインバリセンタ問題としてRWBを削減する。
次に,モデル削減手法とコアセット手法を組み合わせることで,重みと位置を交互に更新することで,自由RWBのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-25T16:20:32Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Randomized Greedy Algorithms and Composable Coreset for k-Center
Clustering with Outliers [11.546734084378683]
外れ値の存在は計算の複雑さを著しく増大させる。
我々のアイデアは、通常の$k$-centerクラスタリング問題を解決するために開発されたgreedy法にインスパイアされている。
論文 参考訳（メタデータ） (2023-01-07T09:26:01Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Approximative Algorithms for Multi-Marginal Optimal Transport and
Free-Support Wasserstein Barycenters [0.0]
N$離散確率測度に対する2乗ユークリッドコストで, マルチマルジナル最適輸送(MOT)の解を近似する2つのアルゴリズムを提案する。
高速で、メモリ効率が高く、実装も簡単で、どのスパースOTソルバでもブラックボックスとして使用することができる。
論文 参考訳（メタデータ） (2022-02-02T10:59:54Z) - 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) - Consistent $k$-Median: Simpler, Better and Robust [20.692372082600972]
簡単な局所探索に基づくオンラインアルゴリズムでは,O(k2 log2 (nD))$ swaps of centrals (recourse) という問題に対して,バイクリテリア定数を近似することができることを示す。
外れ値のない問題に制限される場合、我々のアルゴリズムはより単純で決定論的であり、近似比とレコメンデーションがより良くなる。
論文 参考訳（メタデータ） (2020-08-13T20:24:28Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。