論文の概要: 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] よりも近似比と帰納法が優れている。
関連論文リスト
- Efficient Algorithms for Empirical Group Distributional Robust
Optimization and Beyond [15.664414751701718]
経験的GDROを$textittwo-level$ finite-sum convex-concave minimax Optimization問題として定式化する。
我々は、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。
注目すべきは、我々の手法が最先端の手法よりも$sqrtm$で優れていることだ。
論文 参考訳(メタデータ) (2024-03-06T09:14:24Z) - 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) - Better Algorithms for Individually Fair $k$-Clustering [4.936817539835045]
Jung, Kannan, Lutz [FORC 2020]は、$ell_infty$または$k$-Centerの目的に対して、証明可能な(近似的な)フェアネスと客観的保証を備えたクラスタリングアルゴリズムを導入した。Mahabadi氏とVakilian氏(ICML 2020)は、この問題を再考して、すべての$ell_p$-normsに対してローカル検索アルゴリズムを提供する。
我々は、既知のLPラウンドリング技術を変更することで、MV20よりもはるかに優れた目標に対して最悪のケースを保証できることを実証的に証明し、この目標が最適に非常に近いことを実証した。
論文 参考訳(メタデータ) (2021-06-23T04:16:46Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - 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) - Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。
本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
論文 参考訳(メタデータ) (2020-04-09T01:45:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。