論文の概要: Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs

• arxiv url: http://arxiv.org/abs/2510.07250v1
• Date: Wed, 08 Oct 2025 17:16:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.660594
• Title: Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
• Title（参考訳）: ガウス情報源からの効率的な削減と統計計算トレードオフへの応用
• Authors: Mengqi Lou, Guy Bresler, Ashwin Pananjady,
• Abstract要約: 我々はこの手法を利用して、平均ケースの複雑さにおいて広く信じられている予想の下で、いくつかの正準高次元統計モデルに対して、還元に基づく計算下界を確立する。 ガウス雑音を持つスパイクテンソルPCAの計算下界は、クラス内の他のガウス雑音分布にまで拡張可能であることを示す。
• 参考スコア（独自算出の注目度）: 8.162867143465382
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a single observation from a Gaussian distribution with unknown mean $\theta$, we design computationally efficient procedures that can approximately generate an observation from a different target distribution $Q_{\theta}$ uniformly for all $\theta$ in a parameter set. We leverage our technique to establish reduction-based computational lower bounds for several canonical high-dimensional statistical models under widely-believed conjectures in average-case complexity. In particular, we cover cases in which: 1. $Q_{\theta}$ is a general location model with non-Gaussian distribution, including both light-tailed examples (e.g., generalized normal distributions) and heavy-tailed ones (e.g., Student's $t$-distributions). As a consequence, we show that computational lower bounds proved for spiked tensor PCA with Gaussian noise are universal, in that they extend to other non-Gaussian noise distributions within our class. 2. $Q_{\theta}$ is a normal distribution with mean $f(\theta)$ for a general, smooth, and nonlinear link function $f:\mathbb{R} \rightarrow \mathbb{R}$. Using this reduction, we construct a reduction from symmetric mixtures of linear regressions to generalized linear models with link function $f$, and establish computational lower bounds for solving the $k$-sparse generalized linear model when $f$ is an even function. This result constitutes the first reduction-based confirmation of a $k$-to-$k^2$ statistical-to-computational gap in $k$-sparse phase retrieval, resolving a conjecture posed by Cai et al. (2016). As a second application, we construct a reduction from the sparse rank-1 submatrix model to the planted submatrix model, establishing a pointwise correspondence between the phase diagrams of the two models that faithfully preserves regions of computational hardness and tractability.
• Abstract（参考訳）: 未知平均$\theta$のガウス分布からの単一観測を考慮し、パラメータ集合内のすべての$\theta$に対して、異なるターゲット分布$Q_{\theta}$から観測を概略生成できる計算効率の良い手順を設計する。 我々はこの手法を利用して、平均ケースの複雑さにおいて広く信じられている予想の下で、いくつかの正準高次元統計モデルに対して、還元に基づく計算下界を確立する。 特に、 1.$Q_{\theta}$ は非ガウス分布を持つ一般的な位置モデルであり、軽尾の例(例えば、一般化正規分布)と重尾の例(例えば、学生の$t$-distributions)の両方を含む。 その結果、ガウス雑音を持つスパイクテンソルPCAの計算下界は、クラス内の他の非ガウス雑音分布にまで拡張可能であることを示した。 Q_{\theta}$ は、一般かつ滑らかで非線形なリンク関数 $f:\mathbb{R} \rightarrow \mathbb{R}$ に対して平均$f(\theta)$ を持つ正規分布である。 この還元を用いて、線形回帰の対称混合からリンク関数 $f$ の一般線形モデルへの還元を構築し、$f$ が偶関数であるときに$k$ スパース一般化線形モデルを解くための計算下界を確立する。 この結果は、$k$-to-$k^2$統計計算的ギャップを$k$-sparse相の探索で確認し、Cai et al (2016) の予想を解いた最初の還元に基づくものである。 第2の応用として,計算硬度とトラクタビリティの領域を忠実に保存する2つのモデルの相図間のポイントワイズ対応を確立することにより,スパースランク1サブ行列モデルから植木サブ行列モデルへの還元を構築する。

関連論文リスト

• Local minima of the empirical risk in high dimension: General theorems and convex examples [8.748904058015574]
  我々は、データベクトル$mathbfxi$が$d-最小化であるような高次元経験的リスクの一般的なモデルを考える。 我々は推定誤差と予測誤差に基づいてシャープを導出する。
  論文  参考訳（メタデータ） (2025-02-04T03:02:24Z)
• SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications [37.208622097149714]
  すべての$d inmathbb N$に対して、すべての中心部分ガウス分布 $mathcal D$ on $mathbb Rd$, and every even $p inmathbb N$, $d-optimal inmathbb N$, $d-optimal inmathbb N$ が成り立つような普遍定数 $C>0$ が存在することを証明している。 これは、すべてのサブガウス分布がemphS-certifiably subgaussianであることを示す。
  論文  参考訳（メタデータ） (2024-10-28T16:36:58Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。 グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
  論文  参考訳（メタデータ） (2024-01-16T03:14:24Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• $p$-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets [74.37849422071206]
  本稿では, 2次応答に対する一般化線形モデルである,$p$一般化プロビット回帰モデルについて検討する。 p$の一般化されたプロビット回帰に対する最大可能性推定器は、大容量データ上で$(1+varepsilon)$の係数まで効率的に近似できることを示す。
  論文  参考訳（メタデータ） (2022-03-25T10:54:41Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• 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)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
  本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。 統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。 また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
  論文  参考訳（メタデータ） (2020-02-05T00:24:53Z)

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

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