Fugu-MT 論文翻訳(概要): Consistent $k$-Median: Simpler, Better and Robust

論文の概要: Consistent $k$-Median: Simpler, Better and Robust

arxiv url: http://arxiv.org/abs/2008.06101v1
Date: Thu, 13 Aug 2020 20:24:28 GMT
ステータス: 処理完了
システム内更新日: 2022-10-30 23:57:12.335952
Title: Consistent $k$-Median: Simpler, Better and Robust
Title（参考訳）: Consistent $k$-Median: よりシンプルで、より良く、ロバスト
Authors: Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian
Abstract要約: 簡単な局所探索に基づくオンラインアルゴリズムでは,O(k2 log2 (nD))$ swaps of centrals (recourse) という問題に対して,バイクリテリア定数を近似することができることを示す。外れ値のない問題に制限される場合、我々のアルゴリズムはより単純で決定論的であり、近似比とレコメンデーションがより良くなる。
参考スコア（独自算出の注目度）: 20.692372082600972
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper we introduce and study the online consistent $k$-clustering with outliers problem, generalizing the non-outlier version of the problem studied in [Lattanzi-Vassilvitskii, ICML17]. We show that a simple local-search based online algorithm can give a bicriteria constant approximation for the problem with $O(k^2 \log^2 (nD))$ swaps of medians (recourse) in total, where $D$ is the diameter of the metric. When restricted to the problem without outliers, our algorithm is simpler, deterministic and gives better approximation ratio and recourse, compared to that of [Lattanzi-Vassilvitskii, ICML17].
Abstract（参考訳）: 本稿では,オンライン一貫した$k$-clusteringを外れ値問題で導入し,[Lattanzi-Vassilvitskii, ICML17]で検討された問題の非外れ値バージョンを一般化する。単純な局所探索に基づくオンラインアルゴリズムは、o(k^2 \log^2 (nd))$の中央値(経路)のスワップで問題に対してビクライトリア定数近似を与えることができ、そこでは$d$が計量の直径である。外れ値のない問題に限定すると,アルゴリズムは単純で決定論的であり, [lattanzi-vassilvitskii, icml17] よりも近似比と帰納法が優れている。

関連論文リスト

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)
Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers [10.259254824702555]
我々は、外乱が存在する場合に、$k$-sparse Wasserstein Barycenter問題を研究する。既存のWBアルゴリズムは、ケースを外れ値で処理するために直接拡張することはできない。本稿では,外乱問題のある$k$sparse WBに対して定数近似係数を求めるクラスタリングに基づくLP法を提案する。
論文参考訳（メタデータ） (2024-04-20T15:01:35Z)
Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文参考訳（メタデータ） (2024-04-18T17:57:53Z)
A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文参考訳（メタデータ） (2024-02-09T19:01:48Z)
Revisiting Rotation Averaging: Uncertainties and Robust Losses [51.64986160468128]
現在の手法の主な問題は、推定エピポーラを通して入力データと弱い結合しか持たない最小コスト関数である。本稿では,点対応から回転平均化への不確実性を直接伝播させることにより,基礎となる雑音分布をモデル化することを提案する。
論文参考訳（メタデータ） (2023-03-09T11:51:20Z)
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)
Distributed k-Means with Outliers in General Metrics [0.6117371161379208]
一般距離空間に対する$z$アウトレイアを持つk平均に対する分散コアセットに基づく3ラウンド近似アルゴリズムを提案する。我々のアルゴリズムの重要な特徴は、距離空間の2倍の次元で捉えられたデータセットの本質的な複雑さに鮮明に適応することである。
論文参考訳（メタデータ） (2022-02-16T16:24:31Z)
Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors [13.231906521852718]
大規模なデータセットを小さなグループに分割する分散学習シナリオを考察する。分類,回帰,密度推定のための固定k$-NN情報を集約する最適ルールを提案する。十分多数のグループに固定された$k$の分散アルゴリズムは、乗算対数係数までの最小誤差率を得ることを示す。
論文参考訳（メタデータ） (2022-02-05T01:59:09Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。