論文の概要: Low coordinate degree algorithms I: Universality of computational
thresholds for hypothesis testing
- arxiv url: http://arxiv.org/abs/2403.07862v1
- Date: Tue, 12 Mar 2024 17:52:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 19:49:03.400051
- Title: Low coordinate degree algorithms I: Universality of computational
thresholds for hypothesis testing
- Title（参考訳）: 低座標次アルゴリズムI:仮説テストのための計算しきい値の普遍性
- Authors: Dmitriy Kunisky
- Abstract要約: 低座標次関数 (LCDF) は高次元確率測度間の仮説テストを行うことができる。
LCDFはノイズチャネルを介して十分な「希薄」ランダム信号の存在をテストできることを示す。
これらの結果は、これら全てのモデルに対する任意の大きなアルゴリズムに対する最初の計算下界である。
- 参考スコア（独自算出の注目度）: 2.4889993472438383
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study when low coordinate degree functions (LCDF) -- linear combinations
of functions depending on small subsets of entries of a vector -- can
hypothesis test between high-dimensional probability measures. These functions
are a generalization, proposed in Hopkins' 2018 thesis but seldom studied
since, of low degree polynomials (LDP), a class widely used in recent
literature as a proxy for all efficient algorithms for tasks in statistics and
optimization. Instead of the orthogonal polynomial decompositions used in LDP
calculations, our analysis of LCDF is based on the Efron-Stein or ANOVA
decomposition, making it much more broadly applicable. By way of illustration,
we prove channel universality for the success of LCDF in testing for the
presence of sufficiently "dilute" random signals through noisy channels: the
efficacy of LCDF depends on the channel only through the scalar Fisher
information for a class of channels including nearly arbitrary additive i.i.d.
noise and nearly arbitrary exponential families. As applications, we extend
lower bounds against LDP for spiked matrix and tensor models under additive
Gaussian noise to lower bounds against LCDF under general noisy channels. We
also give a simple and unified treatment of the effect of censoring models by
erasing observations at random and of quantizing models by taking the sign of
the observations. These results are the first computational lower bounds
against any large class of algorithms for all of these models when the channel
is not one of a few special cases, and thereby give the first substantial
evidence for the universality of several statistical-to-computational gaps.
- Abstract（参考訳）: 低座標次関数(lcdf) -- ベクトルのエントリの小さな部分集合に依存する関数の線形結合 -- が高次元確率測度間の仮説検定を行う場合について検討する。
これらの関数は、ホプキンスの2018年の論文で提案された一般化であるが、統計学と最適化における全ての効率的なアルゴリズムのプロキシとして近年の文献で広く使われている低次多項式(LDP)のクラスとして研究されることは滅多にない。
LDP計算で用いられる直交多項式分解の代わりに、LCDFの解析はEfron-SteinあるいはANOVA分解に基づいており、より広く適用できる。
lcdfの有効性は、ほぼ任意の添加物i.i.d.ノイズやほぼ任意の指数関数族を含む種類のチャネルのスカラーフィッシャー情報を通してのみチャネルに依存する。
応用として, スパイク行列およびテンソルモデルのldpに対する下限を加法ガウス雑音下で, 一般雑音下におけるlcdfに対する下限まで拡張する。
また,無作為モデルにおける観測を消去し,観測のサインを取ることにより,検閲モデルの効果を簡易かつ統一的に処理する。
これらの結果は、チャネルがいくつかの特別なケースのうちの1つでない場合、これらのモデルの全ての大きなクラスのアルゴリズムに対する最初の計算上の下限であり、その結果、いくつかの統計から計算へのギャップの普遍性に関する最初の実質的な証拠を与える。
関連論文リスト
- Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
CoT(Chain-of-Thought)の促進とその変種は、多段階推論問題を解決する効果的な方法として人気を集めている。
統計的推定の観点からCoTのプロンプトを解析し,その複雑さを包括的に評価する。
論文 参考訳（メタデータ） (2024-08-25T04:07:18Z) - Proximal Interacting Particle Langevin Algorithms [0.0]
本稿では,潜時変動モデルにおける推論と学習のためのPIPLAアルゴリズムを提案する。
非微分不可能な統計モデルにおけるパラメータ推定の問題に合わせた、新しい近位IPLAファミリー内のいくつかの変種を提案する。
我々の理論と実験は、PIPLAファミリーが非微分可能モデルの潜在変数モデルにおけるパラメータ推定問題のデファクト選択であることを示している。
論文 参考訳（メタデータ） (2024-06-20T13:16:41Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Fundamental limits of Non-Linear Low-Rank Matrix Estimation [18.455890316339595]
ベイズ最適性能は、有効前のガウスモデルによって特徴づけられる。
信号を正確に再構成するためには、Nfrac 12 (1-1/k_F)$として増加する信号対雑音比が必要であり、$k_F$は関数の最初のゼロでないフィッシャー情報係数である。
論文 参考訳（メタデータ） (2024-03-07T05:26:52Z) - Max-affine regression via first-order methods [7.12511675782289]
最大アフィンモデルは信号処理と統計学の応用においてユビキタスに現れる。
最大アフィン回帰に対する勾配降下(GD)とミニバッチ勾配降下(SGD)の非漸近収束解析を行った。
論文 参考訳（メタデータ） (2023-08-15T23:46:44Z) - A Framework for Analyzing Cross-correlators using Price's Theorem and
Piecewise-Linear Decomposition [5.094549132183797]
本稿では,片方向線形関数の混合を用いて構築したクロスコレレータを解析できる汎用的な数学的枠組みを提案する。
最も有望なクロスコレレータのいくつかは、Huberの損失関数、マージンプロパゲーション(MP)関数、log-sum-exp(LSE)関数に基づいている。
論文 参考訳（メタデータ） (2023-04-18T19:03:27Z) - On High dimensional Poisson models with measurement error: hypothesis
testing for nonlinear nonconvex optimization [13.369004892264146]
我々は高次元の回帰モデルの推定と検証を行い、データ解析に広く応用する。
ペナル化された一貫性を最小化することで回帰パラメータを推定する。
提案手法はアルツハイマー病イニシアチブに適用される。
論文 参考訳（メタデータ） (2022-12-31T06:58:42Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳（メタデータ） (2022-10-08T08:26:22Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
正規化フローの微分同相性に基づいて、閉領域上の累積分布関数(CDF)を推定する。
一般的なフローアーキテクチャとUCIデータセットに関する実験は,従来の推定器と比較して,サンプル効率が著しく向上したことを示している。
論文 参考訳（メタデータ） (2022-02-23T06:11:49Z) - Probabilistic Circuits for Variational Inference in Discrete Graphical
Models [101.28528515775842]
変分法による離散的グラフィカルモデルの推論は困難である。
エビデンス・ロウアーバウンド(ELBO)を推定するためのサンプリングに基づく多くの手法が提案されている。
Sum Product Networks (SPN) のような確率的回路モデルのトラクタビリティを活用する新しい手法を提案する。
選択的SPNが表現的変動分布として適していることを示し、対象モデルの対数密度が重み付けされた場合、対応するELBOを解析的に計算可能であることを示す。
論文 参考訳（メタデータ） (2020-10-22T05:04:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。