論文の概要: Semidefinite programming on population clustering: a global analysis
- arxiv url: http://arxiv.org/abs/2301.00344v1
- Date: Sun, 1 Jan 2023 04:52:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-05 16:17:22.804248
- Title: Semidefinite programming on population clustering: a global analysis
- Title（参考訳）: 集団クラスタリングにおける半定義型プログラミング:グローバル分析
- Authors: Shuheng Zhou
- Abstract要約: サブガウス分布の混合から引き出された小さいデータサンプルを$n$で分割する問題を考察する。
私たちは、個々のフィーチャが平均的な$gamma$が低い場合に興味を持ち、サンプルを正しく分割するためにできるだけ少数の機能を使用したいと思っています。
- 参考スコア（独自算出の注目度）: 0.6472434306724609
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider the problem of partitioning a small data sample of
size $n$ drawn from a mixture of $2$ sub-gaussian distributions. Our work is
motivated by the application of clustering individuals according to their
population of origin using markers, when the divergence between the two
populations is small. We are interested in the case that individual features
are of low average quality $\gamma$, and we want to use as few of them as
possible to correctly partition the sample. We consider semidefinite relaxation
of an integer quadratic program which is formulated essentially as finding the
maximum cut on a graph where edge weights in the cut represent dissimilarity
scores between two nodes based on their features. A small simulation result in
Blum, Coja-Oghlan, Frieze and Zhou (2007, 2009) shows that even when the sample
size $n$ is small, by increasing $p$ so that $np= \Omega(1/\gamma^2)$, one can
classify a mixture of two product populations using the spectral method therein
with success rate reaching an ``oracle'' curve. There the ``oracle'' was
computed assuming that distributions were known, where success rate means the
ratio between correctly classified individuals and the sample size $n$. In this
work, we show the theoretical underpinning of this observed concentration of
measure phenomenon in high dimensions, simultaneously for the semidefinite
optimization goal and the spectral method, where the input is based on the gram
matrix computed from centered data. We allow a full range of tradeoffs between
the sample size and the number of features such that the product of these two
is lower bounded by $1/{\gamma^2}$ so long as the number of features $p$ is
lower bounded by $1/\gamma$.
- Abstract（参考訳）: 本稿では,2ドルのサブガウス分布の混合分布から抽出したサイズ$n$の小さなデータサンプルを分割する問題を考える。
本研究の動機は,両個体間のばらつきが小さい場合に,その起源の個体数に応じたクラスタリングを指標として行うことにある。
個々の機能が平均的な品質で$\gamma$である場合に興味があり、サンプルを正しく分割するためにできるだけ少数の機能を使用したいと思っています。
本質的には、カットのエッジ重みが2つのノード間の相似性スコアを表すグラフ上での最大カットを求めるものとして定式化された整数二次プログラムの半定緩和を考える。
Blum, Coja-Oghlan, Frieze and Zhou (2007, 2009) の小さなシミュレーション結果によると、サンプルサイズ$n$が小さい場合でも、$np= \Omega(1/\gamma^2)$ を$p$にすることで、スペクトル法を用いて2つの積の集団の混合物を分類することができ、'oracle' 曲線に達する成功率を持つ。
ここで ``oracle'' は分布が知られていると仮定して計算され、成功率は正しく分類された個人とサンプルサイズ $n$ の比率を意味する。
本研究では、この観測された測定現象の高次元濃度の理論的基盤を半定値最適化目標とスペクトル法で同時に示し、その入力は中心データから計算されたグラム行列に基づいている。
サンプルサイズとこれらの2つの製品が1/{\gamma^2}$で区切られるような特徴の数の間の完全なトレードオフを、$p$が1/\gamma$で区切られる限り許す。
関連論文リスト
- Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。
我々は、下層の混合成分について分離を前提としない。
我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-29T17:30:36Z) - Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions [11.222970035173372]
カーネルベースのスコア推定器は$widetildeOleft(n-1 t-fracd+22(tfracd2 vee 1)rightの最適平均二乗誤差を達成する
核を用いたスコア推定器は,拡散モデルで生成した試料の分布の総変動誤差に対して,極小ガウスの下での最大平均2乗誤差を$widetildeOleft(n-1/2 t-fracd4right)$上界で達成することを示す。
論文 参考訳（メタデータ） (2024-02-23T20:51:31Z) - Debiasing and a local analysis for population clustering using
semidefinite programming [1.9761774213809036]
サブガウス分布の混合から引き出された小さいデータサンプルを$n$で分割する問題を考察する。
この研究は、起源の個体数に応じた集団化の応用によって動機付けられている。
論文 参考訳（メタデータ） (2024-01-16T03:14:24Z) - Clustering Mixtures of Bounded Covariance Distributions Under Optimal
Separation [44.25945344950543]
境界共分散分布の混合に対するクラスタリング問題について検討する。
このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。
我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
論文 参考訳（メタデータ） (2023-12-19T01:01:53Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳（メタデータ） (2021-11-12T01:51:50Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。