論文の概要: A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials

• arxiv url: http://arxiv.org/abs/2504.03097v1
• Date: Fri, 04 Apr 2025 00:32:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-07 14:48:55.976241
• Title: A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials
• Title（参考訳）: 低次多項式による多変量シャッフル線形回帰検出のための計算遷移
• Authors: Zhangsong Li,
• Abstract要約: モデル $Y=tfrac1sqrt1+sigma2(Pi_* X Q_* + sigma Z) について検討する。 このモデルを$X$と$Y$の場合と区別する仮説テスト問題を考える。 その結果、この問題に対する低次アルゴリズムの有効性の円滑な遷移が確立された。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In this paper, we study the problem of multivariate shuffled linear regression, where the correspondence between predictors and responses in a linear model is obfuscated by a latent permutation. Specifically, we investigate the model $Y=\tfrac{1}{\sqrt{1+\sigma^2}}(\Pi_* X Q_* + \sigma Z)$, where $X$ is an $n*d$ standard Gaussian design matrix, $Z$ is an $n*m$ Gaussian noise matrix, $\Pi_*$ is an unknown $n*n$ permutation matrix, and $Q_*$ is an unknown $d*m$ on the Grassmanian manifold satisfying $Q_*^{\top} Q_* = \mathbb I_m$. Consider the hypothesis testing problem of distinguishing this model from the case where $X$ and $Y$ are independent Gaussian random matrices of sizes $n*d$ and $n*m$, respectively. Our results reveal a phase transition phenomenon in the performance of low-degree polynomial algorithms for this task. (1) When $m=o(d)$, we show that all degree-$D$ polynomials fail to distinguish these two models even when $\sigma=0$, provided with $D^4=o\big( \tfrac{d}{m} \big)$. (2) When $m=d$ and $\sigma=\omega(1)$, we show that all degree-$D$ polynomials fail to distinguish these two models provided with $D=o(\sigma)$. (3) When $m=d$ and $\sigma=o(1)$, we show that there exists a constant-degree polynomial that strongly distinguish these two models. These results establish a smooth transition in the effectiveness of low-degree polynomial algorithms for this problem, highlighting the interplay between the dimensions $m$ and $d$, the noise level $\sigma$, and the computational complexity of the testing task.
• Abstract（参考訳）: 本稿では,線形モデルにおける予測器と応答の対応が潜時変による難読化される多変量シャッフル線形回帰問題について検討する。 具体的には、モデル $Y=\tfrac{1}{\sqrt{1+\sigma^2}}(\Pi_* X Q_* + \sigma Z)$, where $X$ is a $n*d$ standard Gaussian design matrix, $Z$ is a $n*m$ Gaussian noise matrix, $\Pi_*$ is a unknown $n*n$ permutation matrix, $Q_*$ is a unknown $d*m$ with $Q_*^{\top} Q_* = \mathbb I_m$。 このモデルを、それぞれ$X$と$Y$が独立なガウス確率行列である場合と、$n*d$と$n*m$とを区別する仮説テスト問題を考える。 本結果から, この課題に対する低次多項式アルゴリズムの性能の相転移現象が明らかとなった。 1)$m=o(d)$ の場合、$D^4=o\big( \tfrac{d}{m} \big)$ が与えられたとしても、すべての次数-$D$多項式はこれらの2つのモデルを区別できないことを示す。 2)$m=d$と$\sigma=\omega(1)$のとき、すべての次数-$D$多項式は$D=o(\sigma)$の2つのモデルを区別できないことを示す。 (3)$m=d$と$\sigma=o(1)$のとき、この2つのモデルを強く区別する定数次多項式が存在することを示す。 これらの結果は、この問題に対する低次多項式アルゴリズムの有効性の円滑な遷移を確立し、次元$m$と$d$の相互作用、ノイズレベル$\sigma$、およびテストタスクの計算複雑性を強調した。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
  1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。 目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
  論文  参考訳（メタデータ） (2024-03-14T15:04:45Z)
• The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime [0.0]
  2つの相関したランダムな幾何グラフのマッチングの問題に触発され、潜在ノード置換によって相関した2つのガウス幾何学モデルのマッチング問題を研究する。 A_i,j=langle X_i,X_j rangle$, $B_i,j=langle Y_i,Y_j rangle$ で与えられるエッジウェイトを持つ2種類の(相関した)重み付き完全グラフを考える。
  論文  参考訳（メタデータ） (2024-02-23T04:58:54Z)
• Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
  我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。 我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
  論文  参考訳（メタデータ） (2022-05-31T17:59:09Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Chi-square and normal inference in high-dimensional multi-task regression [7.310043452300736]
  本稿では,Multi-Task(MT)線形モデルにおける未知の係数行列$B*$サイズ$ptimes T$に対するカイ二乗法および正規手法を提案する。
  論文  参考訳（メタデータ） (2021-07-16T11:19:49Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Learning Polynomials of Few Relevant Dimensions [12.122488725065388]
  多項式回帰は学習と統計の基本的な原始である。 およそ$N = O_r,d(n log2(1/epsilon) (log n)d)$と$O_r,d(N n2)$である。
  論文  参考訳（メタデータ） (2020-04-28T18:00:18Z)

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

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