論文の概要: Semidefinite programming relaxations and debiasing for MAXCUT-based clustering

• arxiv url: http://arxiv.org/abs/2401.10927v2
• Date: Mon, 17 Mar 2025 02:24:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-18 12:35:49.563716
• Title: Semidefinite programming relaxations and debiasing for MAXCUT-based clustering
• Title（参考訳）: MAXCUTに基づくクラスタリングのための半有限プログラミング緩和とデバイアス化
• Authors: Shuheng Zhou,
• Abstract要約: 2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
• 参考スコア（独自算出の注目度）: 1.9761774213809036
• License:
• 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 $\mathbb{R}^p$. We consider semidefinite programming relaxations of an integer quadratic program that is formulated 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. 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. Denote by $\Delta^2:=p \gamma$ the $\ell_2^2$ distance between two centers (mean vectors) 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. For both balanced and unbalanced cases, we allow each population to have distinct covariance structures with diagonal matrices as special cases. In the present work, (a) we provide a unified framework for analyzing three computationally efficient algorithms, namely, SDP1, BalancedSDP, and Spectral clustering; and (b) we prove that the misclassification error decays exponentially with respect to the SNR $s^2$ for SDP1. Moreover, for balanced partitions, we design an estimator {\bf BalancedSDP} with a superb debiasing property. Indeed, with this new estimator, we remove an assumption (A2) on bounding the trace difference between the two population covariance matrices while proving the exponential error bound as stated above. These estimators and their statistical analyses are novel to the best of our knowledge. We provide simulation evidence illuminating the theoretical predictions.
• Abstract（参考訳）: 本稿では,2つの準ガウス分布を混合した$\mathbb{R}^p$から引き出された小さいデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定プログラミング緩和を考える。 個々のフィーチャが平均品質が低く$\gamma$である場合に興味があります。 詳しくは$\Delta^2:=p \gamma$ the $\ell_2^2$ distance between two center (mean vectors) in $\mathbb{R}^p$を参照。 目的は、信号からノイズ比が$s^2 := \min\{np \gamma^2, \Delta^2\}$が定数で下限となると、部分回復(success rate $<100\%$)が実現可能であるという意味で、$n, p, \gamma$間の完全なトレードオフを許容することである。 バランスの取れた場合とバランスの取れない場合の両方において、各個体は特別の場合として対角行列と異なる共分散構造を持つことができる。 現在の作品。 a) SDP1, BalancedSDP, Spectralクラスタリングという3つの計算効率の良いアルゴリズムを解析するための統一的なフレームワークを提供する。 b) SDP1 の SNR $s^2$ に対して誤分類誤差が指数関数的に崩壊することを証明する。 さらに、平衡分割に対しては、超脱バイアス特性を持つ推定器 {\bf BalancedSDP} を設計する。 実際、この新しい推定器では、上記のように指数誤差が有界であることを証明しながら、2つの集団共分散行列の間のトレース差を有界にするという仮定(A2)を除去する。 これらの推定器とその統計的分析は、私たちの知る限りでは新規である。 理論的予測を立証するシミュレーション証拠を提供する。

関連論文リスト

• Entangled Mean Estimation in High-Dimensions [36.97113089188035]
  信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。 最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
  論文  参考訳（メタデータ） (2025-01-09T18:31:35Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。