論文の概要: Debiasing and a local analysis for population clustering using
semidefinite programming
- arxiv url: http://arxiv.org/abs/2401.10927v1
- Date: Tue, 16 Jan 2024 03:14:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-28 15:55:12.120183
- Title: Debiasing and a local analysis for population clustering using
semidefinite programming
- Title（参考訳）: 半定義型プログラミングによる集団クラスタリングのデバイアスと局所解析
- Authors: Shuheng Zhou
- Abstract要約: サブガウス分布の混合から引き出された小さいデータサンプルを$n$で分割する問題を考察する。
この研究は、起源の個体数に応じた集団化の応用によって動機付けられている。
- 参考スコア（独自算出の注目度）: 1.9761774213809036
- License: http://creativecommons.org/licenses/by-nc-nd/4.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. In particular,
we analyze computational efficient algorithms proposed by the same author, to
partition data into two groups approximately according to their population of
origin given a small sample. This work is motivated by the application of
clustering individuals according to their population of origin using $p$
markers, when the divergence between any two of the populations is small. We
build upon the semidefinite relaxation of an integer quadratic program that 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 $p$ features. Here we use $\Delta^2 :=p \gamma$ to denote the $\ell_2^2$
distance between two centers (mean vectors), namely, $\mu^{(1)}$, $\mu^{(2)}$
$\in$ $\mathbb{R}^p$. The goal is to allow a full range of tradeoffs between
$n, p, \gamma$ in the sense that partial recovery (success rate $< 100\%$) is
feasible once the signal to noise ratio $s^2 := \min\{np \gamma^2, \Delta^2\}$
is lower bounded by a constant. Importantly, we prove that the
misclassification error decays exponentially with respect to the SNR $s^2$.
This result was introduced earlier without a full proof. We therefore present
the full proof in the present work. Finally, for balanced partitions, we
consider a variant of the SDP1, and show that the new estimator has a superb
debiasing property. This is novel to the best of our knowledge.
- Abstract（参考訳）: 本稿では,2ドルのサブガウス分布の混合分布から抽出したサイズ$n$の小さなデータサンプルを分割する問題を考える。
特に,同一著者が提案する計算効率のよいアルゴリズムを解析し,サンプルが与えられた場合の原産地人口にほぼ比例してデータを2つのグループに分割する。
この研究は、これらの2つの集団間のばらつきが小さいときに、$p$マーカーを使用して、起源の個体数に応じてクラスタリングする個人の応用によって動機付けられている。
我々は、本質的にグラフ上の最大カットを求めるものとして定式化された整数二次プログラムの半定緩和の上に構築し、カットのエッジウェイトは、それらの$p$の特徴に基づいて2つのノード間の相似性スコアを表す。
ここで、$\delta^2 :=p \gamma$を用いて、2つの中心(平均ベクトル)の間の$\ell_2^2$の距離、すなわち$\mu^{(1)}$、$\mu^{(2)}$ $\in$ $$$\mathbb{r}^p$を表す。
目的は、信号からノイズ比が$s^2 := \min\{np \gamma^2, \Delta^2\}$が定数で下限となると、部分回復(success rate $<100\%$)が実現可能であるという意味で、$n, p, \gamma$間の完全なトレードオフを許容することである。
重要なことは、SNR$s^2$に対して誤分類誤差が指数関数的に崩壊することを証明する。
この結果は、完全な証明なしで早く導入された。
したがって、本研究の完全な証明を提示する。
最後に、バランスの取れた分割に対して、SDP1の変種を考えると、新しい推定器がスーパーブデバイアス特性を持つことを示す。
これは私たちの知る限りでは新鮮だ。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - Multiple-policy Evaluation via Density Estimation [30.914344538340412]
本稿では,この問題に対して$mathrmCAESAR$というアルゴリズムを提案する。
低次かつ対数的な$mathrmCAESAR$は、$tildeOleft(fracH4epsilon2sum_h=1Hmax_kin[K]sum_s,afrac(d_hpik(s,a))2mu*_h(s,a)right)$である。
論文 参考訳（メタデータ） (2024-03-29T23:55:25Z) - 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) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Semidefinite programming on population clustering: a global analysis [0.6472434306724609]
サブガウス分布の混合から引き出された小さいデータサンプルを$n$で分割する問題を考察する。
私たちは、個々のフィーチャが平均的な$gamma$が低い場合に興味を持ち、サンプルを正しく分割するためにできるだけ少数の機能を使用したいと思っています。
論文 参考訳（メタデータ） (2023-01-01T04:52:25Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Overparametrized linear dimensionality reductions: From projection
pursuit to two-layer neural networks [10.368585938419619]
$mathbbRd$に$n$のデータポイントのクラウドが与えられると、$mathbbRd$の$m$次元部分空間へのすべての射影を考える。
この確率分布の集まりは、$n,d$が大きくなるとどのように見えるか?
この極限の低次元射影として生じる $mathbbRm$ の確率分布の集合の α$ を $mathscrF_m で表すと、$mathscrF_ に新たな内界と外界を確立する。
論文 参考訳（メタデータ） (2022-06-14T00:07:33Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。