論文の概要: 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 14:56:56.888857
• Title: Semidefinite programming relaxations and debiasing for MAXCUT-based clustering
• Title（参考訳）: MAXCUTに基づくクラスタリングのための半有限プログラミング緩和とデバイアス化
• Authors: Shuheng Zhou,
• Abstract要約: 2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$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 $\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)を除去する。 これらの推定器とその統計的分析は、私たちの知る限りでは新規である。 理論的予測を立証するシミュレーション証拠を提供する。

関連論文リスト

• Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians [2.311583680973075]
  楕円分布の共分散/散乱行列の計算効率の良いロバスト推定問題について検討する。 ガウスのケースを超えて拡張される、計算可能で、ほぼ最適な、ほぼ最適な共分散推定器を初めて得る。
  論文  参考訳（メタデータ） (2025-02-10T15:31:57Z)
• 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)
• Optimal score estimation via empirical Bayes smoothing [13.685846094715364]
  未知確率分布$rho*$のスコア関数を$n$独立分布および$d$次元における同一分布観測から推定する問題について検討する。 ガウスカーネルに基づく正規化スコア推定器は、一致するミニマックス下界によって最適に示され、この値が得られることを示す。
  論文  参考訳（メタデータ） (2024-02-12T16:17:40Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
  本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。 擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。 実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
  論文  参考訳（メタデータ） (2023-07-18T15:49:02Z)
• 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)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• 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)
• 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)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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