論文の概要: Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models

• arxiv url: http://arxiv.org/abs/2412.21155v1
• Date: Mon, 30 Dec 2024 18:34:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-31 16:04:20.948444
• Title: Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
• Title（参考訳）: 低座標次アルゴリズムII:カテゴリー信号と一般化確率ブロックモデル
• Authors: Dmitriy Kunisky,
• Abstract要約: 低座標次数関数が高次元データにおけるカテゴリー構造の存在をテストできるかどうかについて検討する。 これはLCDFの連続構造試験における性能について研究したこのシリーズの最初の論文を補完するものである。
• 参考スコア（独自算出の注目度）: 2.4889993472438383
• License:
• Abstract: We study when low coordinate degree functions (LCDF) -- linear combinations of functions depending on small subsets of entries of a vector -- can test for the presence of categorical structure, including community structure and generalizations thereof, in high-dimensional data. This complements the first paper of this series, which studied the power of LCDF in testing for continuous structure like real-valued signals perturbed by additive noise. We apply the tools developed there to a general form of stochastic block model (SBM), where a population is assigned random labels and every $p$-tuple of the population generates an observation according to an arbitrary probability measure associated to the $p$ labels of its members. We show that the performance of LCDF admits a unified analysis for this class of models. As applications, we prove tight lower bounds against LCDF (and therefore also against low degree polynomials) for nearly arbitrary graph and regular hypergraph SBMs, always matching suitable generalizations of the Kesten-Stigum threshold. We also prove tight lower bounds for group synchronization and abelian group sumset problems under the "truth-or-Haar" noise model, and use our technical results to give an improved analysis of Gaussian multi-frequency group synchronization. In most of these models, for some parameter settings our lower bounds give new evidence for conjectural statistical-to-computational gaps. Finally, interpreting some of our findings, we propose a precise analogy between categorical and continuous signals: a general SBM as above behaves, in terms of the tradeoff between subexponential runtime cost of testing algorithms and the signal strength needed for a testing algorithm to succeed, like a spiked $p_*$-tensor model of a certain order $p_*$ that may be computed from the parameters of the SBM.
• Abstract（参考訳）: 低座標次数関数 (LCDF) -- ベクトルのエントリの小さな部分集合に依存する関数の線形結合 -- が、コミュニティ構造やその一般化を含むカテゴリ構造の存在を高次元データで検証できるかを検討する。 このシリーズの最初の論文を補完し、加法雑音によって乱される実数値信号のような連続的な構造の試験におけるLCDFのパワーについて研究した。 そこで開発されたツールを一般の確率ブロックモデル (SBM) に適用し, 人口にランダムなラベルが割り当てられ, 人口の各々の$p$-tupleが, 会員の$p$ラベルに関連する任意の確率尺度に従って観測結果を生成する。 LCDFの性能は,これらのモデルに対して統一的な解析を行うことを示す。 応用として、ほぼ任意のグラフと正規ハイパーグラフSBMに対してLCDF(従って低次多項式)に対して厳密な下界を証明し、ケステン・スティグムしきい値の適切な一般化に常に適合する。 また、「真実またはハール」ノイズモデルの下で、群同期とアーベル群サマセット問題に対して厳密な下限を証明し、その技術的結果を用いて、ガウス多周波群同期を改良した解析を行う。 これらのモデルの多くは、いくつかのパラメータ設定のために、下限は形容詞的統計的-計算的ギャップの新たな証拠を与える。 上述の一般的なSBMは、テストアルゴリズムの指数的実行コストと、テストアルゴリズムが成功するのに必要な信号強度とのトレードオフの観点から、SBMのパラメータから計算されるような、ある順序の$p_*$-tensorモデルのように振る舞う。

関連論文リスト

• Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests [5.3595271893779906]
  フェデレート学習は、さまざまな場所でデータが収集され分析される広範囲な設定で適用可能であることから、近年大きな注目を集めている。 分散差分プライバシー(DP)制約下でのホワイトノイズ・ウィズ・ドリフトモデルにおける非パラメトリック適合性試験について検討した。
  論文  参考訳（メタデータ） (2024-06-10T19:25:19Z)
• Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing [2.4889993472438383]
  低座標次関数 (LCDF) は高次元確率測度間の仮説テストを行うことができる。 LCDFはノイズチャネルを介して十分な「希薄」ランダム信号の存在をテストできることを示す。 これらの結果は、これら全てのモデルに対する任意の大きなアルゴリズムに対する最初の計算下界である。
  論文  参考訳（メタデータ） (2024-03-12T17:52:35Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Estimating Higher-Order Mixed Memberships via the $\ell_{2,\infty}$ Tensor Perturbation Bound [8.521132000449766]
  テンソルブロックモデルの一般化であるテンソル混合メンバーシップブロックモデルを提案する。 我々は,モデルの同定可能性を確立し,計算効率の良い推定手法を提案する。 本手法を実データおよびシミュレーションデータに適用し,個別のコミュニティメンバーシップを持つモデルから特定できない効果を示す。
  論文  参考訳（メタデータ） (2022-12-16T18:32:20Z)
• Instability and Local Minima in GAN Training with Kernel Discriminators [20.362912591032636]
  GAN(Generative Adversarial Networks)は、複雑なデータの生成モデリングに広く使われているツールである。 実験的な成功にもかかわらず、ジェネレータと判別器のmin-max最適化のため、GANの訓練は十分には理解されていない。 本稿では、真のサンプルと生成されたサンプルが離散有限集合であり、判別器がカーネルベースである場合に、これらの関節力学を解析する。
  論文  参考訳（メタデータ） (2022-08-21T18:03:06Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model [6.681901523019242]
  非一様ハイパーグラフブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 我々は,少なくとも$gamma$分の頂点を正しく分類した分割を出力するスペクトルアルゴリズムを提案し,$gammainはモデルの信号-雑音比(SNR)に依存する。 このアルゴリズムの理論的解析は、非一様ランダムハイパーグラフに対する隣接行列の濃度と正規化に依存しており、これは独立な関心を持つことができる。
  論文  参考訳（メタデータ） (2021-12-22T05:38:33Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。 この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。 本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。 我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
  論文  参考訳（メタデータ） (2021-05-27T23:41:01Z)
• Autoregressive Score Matching [113.4502004812927]
  自動回帰条件スコアモデル(AR-CSM)を提案する。 AR-CSMモデルでは、このデータ分布とモデル分布のばらつきを効率的に計算し、最適化することができ、高価なサンプリングや対向訓練を必要としない。 本研究では,合成データに対する密度推定,画像生成,画像復調,暗黙エンコーダを用いた潜在変数モデルの訓練に応用できることを示す。
  論文  参考訳（メタデータ） (2020-10-24T07:01:24Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  変分法による離散的グラフィカルモデルの推論は困難である。 エビデンス・ロウアーバウンド(ELBO)を推定するためのサンプリングに基づく多くの手法が提案されている。 Sum Product Networks (SPN) のような確率的回路モデルのトラクタビリティを活用する新しい手法を提案する。 選択的SPNが表現的変動分布として適していることを示し、対象モデルの対数密度が重み付けされた場合、対応するELBOを解析的に計算可能であることを示す。
  論文  参考訳（メタデータ） (2020-10-22T05:04:38Z)

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

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