論文の概要: Online Coresets for Clustering with Bregman Divergences
- arxiv url: http://arxiv.org/abs/2012.06522v1
- Date: Fri, 11 Dec 2020 17:39:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-11 02:50:21.956624
- Title: Online Coresets for Clustering with Bregman Divergences
- Title（参考訳）: Bregman Divergencesによるクラスタリングのためのオンラインコアセット
- Authors: Rachit Chhaya, Jayesh Choudhari, Anirban Dasgupta, Supratim Shit
- Abstract要約: bregman divergencesの幅広いサブセットに従って,クラスタ問題に対してオンライン環境でコアセットを作成するアルゴリズムを提案する。
特に、私たちのコアセットは、軽量コアセットBachem etと同様、小さな添加誤差を持っています。
アル
2018.
- 参考スコア（独自算出の注目度）: 11.650724544695498
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present algorithms that create coresets in an online setting for
clustering problems according to a wide subset of Bregman divergences. Notably,
our coresets have a small additive error, similar in magnitude to the
lightweight coresets Bachem et. al. 2018, and take update time $O(d)$ for every
incoming point where $d$ is dimension of the point. Our first algorithm gives
online coresets of size $\tilde{O}(\mbox{poly}(k,d,\epsilon,\mu))$ for
$k$-clusterings according to any $\mu$-similar Bregman divergence. We further
extend this algorithm to show existence of a non-parametric coresets, where the
coreset size is independent of $k$, the number of clusters, for the same
subclass of Bregman divergences. Our non-parametric coresets are larger by a
factor of $O(\log n)$ ($n$ is number of points) and have similar (small)
additive guarantee. At the same time our coresets also function as lightweight
coresets for non-parametric versions of the Bregman clustering like DP-Means.
While these coresets provide additive error guarantees, they are also
significantly smaller (scaling with $O(\log n)$ as opposed to $O(d^d)$ for
points in $\~R^d$) than the (relative-error) coresets obtained in Bachem et.
al. 2015 for DP-Means. While our non-parametric coresets are existential, we
give an algorithmic version under certain assumptions.
- Abstract（参考訳）: bregman divergencesの幅広いサブセットに従って,クラスタ問題に対してオンライン環境でコアセットを作成するアルゴリズムを提案する。
特に、我々のコアセットは、Bachemなどの軽量コアセットと同様、小さな加算誤差を持つ。
アル
そして、$d$がポイントの次元である入射点ごとに$o(d)$を更新します。
我々の最初のアルゴリズムは、$\tilde{O}(\mbox{poly}(k,d,\epsilon,\mu))$ for $k$-clusterings according by any $\mu$-similar Bregman divergence。
さらに、このアルゴリズムを拡張して非パラメトリックなコアセットの存在を示す。コアセットのサイズは、bregman divergencesの同じサブクラスに対して、クラスタ数である$k$から独立している。
我々の非パラメトリックコアセットは$O(\log n)$$$n$ is number of points)の係数で大きくなり、同様の(小さな)加法保証を持つ。
同時に、コアセットはDP-MeansのようなBregmanクラスタリングの非パラメトリックバージョンのための軽量コアセットとしても機能します。
これらのコアセットは付加的なエラー保証を提供するが、Bachemなどで得られた(相対エラー)コアセットよりもはるかに小さい($O(\log n)$と$O(d^d)$でスケーリングする)。
アル
2015年、DP-Meansに入社。
非パラメトリックコアセットは存在するが、特定の仮定の下でアルゴリズム版を与える。
関連論文リスト
- 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) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Universal Weak Coreset [3.1509756165776635]
弱コアセットは点の部分集合の対$(J,S)$であり、そこでは点集合の要約として$S$が作用し、ポテンシャル中心の集合として$J$が作用する。
我々は、制約付きクラスタリング設定のために、ユニバーサル弱コアセットと呼ばれるこのフレームワークを開発した。
論文 参考訳（メタデータ） (2023-05-26T12:51:16Z) - Coresets for Time Series Clustering [33.801060211529354]
本稿では,時系列データを用いたクラスタリング問題に対するコアセット構築の問題について検討する。
我々の主な貢献は混合モデルのためのコアセットを構築するアルゴリズムである。
合成データを用いて,コアセットの性能を実証的に評価した。
論文 参考訳（メタデータ） (2021-10-28T16:21:13Z) - FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。
$cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。
$mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文 参考訳（メタデータ） (2021-10-19T17:43:50Z) - Nearly-Tight and Oblivious Algorithms for Explainable Clustering [8.071379672971542]
Moshkovitz, Dasgupta, Rashtchian, Frost (ICML 2020) によって初めて定式化された設定における説明可能なクラスタリングの問題について検討する。
k$クラスタリングは、各内部ノードデータが1次元(機能)で閾値をカットした点を示す決定木によって与えられる場合、説明可能であると言われる。
我々は、$k$-mediansの目的に対して最適な(必ずしも説明できない)クラスタリングと比較して、少なくとも$O(log2 k)$の係数を失う説明可能なクラスタリングを出力するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-30T15:49:41Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。