論文の概要: On Generalization Bounds for Projective Clustering
- arxiv url: http://arxiv.org/abs/2310.09127v1
- Date: Fri, 13 Oct 2023 14:15:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-16 12:50:48.869081
- Title: On Generalization Bounds for Projective Clustering
- Title（参考訳）: 射影クラスタリングの一般化境界について
- Authors: Maria Sofia Bucarelli, Matilde Fjelds{\o} Larsen, Chris
Schwiegelshohn, Mads Bech Toftrup
- Abstract要約: ポイントのセットが与えられた場合、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントのパーティションを見つけることで構成される。
中心に基づく目的に対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
j$-次元部分空間を持つ部分空間クラスタリングに対しては、$tildeOleft(sqrtfrackj2nright)$の収束率を示す。
- 参考スコア（独自算出の注目度）: 3.4490841399255823
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a set of points, clustering consists of finding a partition of a point
set into $k$ clusters such that the center to which a point is assigned is as
close as possible. Most commonly, centers are points themselves, which leads to
the famous $k$-median and $k$-means objectives. One may also choose centers to
be $j$ dimensional subspaces, which gives rise to subspace clustering. In this
paper, we consider learning bounds for these problems. That is, given a set of
$n$ samples $P$ drawn independently from some unknown, but fixed distribution
$\mathcal{D}$, how quickly does a solution computed on $P$ converge to the
optimal clustering of $\mathcal{D}$? We give several near optimal results. In
particular,
For center-based objectives, we show a convergence rate of
$\tilde{O}\left(\sqrt{{k}/{n}}\right)$. This matches the known optimal bounds
of [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016]
and [Bartlett, Linder, and Lugosi, IEEE Trans. Inf. Theory 1998] for $k$-means
and extends it to other important objectives such as $k$-median.
For subspace clustering with $j$-dimensional subspaces, we show a convergence
rate of $\tilde{O}\left(\sqrt{\frac{kj^2}{n}}\right)$. These are the first
provable bounds for most of these problems. For the specific case of projective
clustering, which generalizes $k$-means, we show a convergence rate of
$\Omega\left(\sqrt{\frac{kj}{n}}\right)$ is necessary, thereby proving that the
bounds from [Fefferman, Mitter, and Narayanan, Journal of the Mathematical
Society 2016] are essentially optimal.
- Abstract（参考訳）: ポイントの集合が与えられると、クラスタリングは、ポイントが割り当てられた中心が可能な限り近いように、$k$クラスタにセットされたポイントの分割を見つけることで構成される。
最も一般的には、センター自体がポイントであり、有名な$k$-median と $k$-means の目的に繋がる。
また、中心を$j$ 次元の部分空間に選び、それが部分空間のクラスタリングを引き起こすこともある。
本稿では,これらの問題に対する学習境界について考察する。
つまり、ある未知の値から独立して引き出された$n$サンプルのセット$P$が与えられたとき、$\mathcal{D}$は、$P$で計算された解が$\mathcal{D}$の最適クラスタリングにどれだけ早く収束するか?
最適に近い結果がいくつかある。
特に、中心に基づく目的に対しては、$\tilde{O}\left(\sqrt{{k}/{n}}\right)$ の収束率を示す。
これは[fefferman, mitter, and narayanan, journal of the mathematical society 2016]と[bartlett, linder, and lugosi, ieee trans. inf. theory 1998]の既知の最適境界とk$-meansで一致し、$k$-medianのような他の重要な目的にも拡張される。
j$-次元部分空間を持つ部分空間クラスタリングに対しては、$\tilde{o}\left(\sqrt{\frac{kj^2}{n}}\right)$という収束率を示す。
これらはこれらの問題に対する最初の証明可能な境界である。
k$-平均を一般化する射影クラスタリングの特定の場合において、$\Omega\left(\sqrt {\frac{kj}{n}}\right)$ の収束速度は必要であり、したがって [Fefferman, Mitter, and Narayanan, Journal of the Mathematical Society 2016] の限界が本質的に最適であることを示す。
関連論文リスト
- Clustering to Minimize Cluster-Aware Norm Objectives [0.3481985817302898]
与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。
中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。
目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
論文 参考訳（メタデータ） (2024-10-31T16:33:40Z) - Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
この論文は、一般的なマルコフ的な設定でステップサイズの選択を再考する。
大きな結論は、$rho =0$ または $rho1/2$ の選択は、選択した設定でのみ正当化されるということである。
論文 参考訳（メタデータ） (2024-05-28T05:11:05Z) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Improved Learning-augmented Algorithms for k-means and k-medians
Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。
本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。
我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文 参考訳（メタデータ） (2022-10-31T03:00:11Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - 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) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Local Correlation Clustering with Asymmetric Classification Errors [12.277755088736864]
相関クラスタリング問題では、エッジを"similar"と"dissimilar"とラベルした完全な重み付きグラフ$G$が与えられる。
クラスタリングの$mathcalC$ of graph $G$の場合、同じエッジが$mathcalC$、エンドポイントが別のクラスタに属している場合は$mathcalC$、エンドポイントが同じクラスタに属している場合は$mathcalC$と一致しない。
我々は$pgeq 1$に対する不一致ベクトルの$ell_p$ノルムを最小化するクラスタリングを生成する。
論文 参考訳（メタデータ） (2021-08-11T12:31:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。