Fugu-MT 論文翻訳(概要): Average-Case Reductions for $k$-XOR and Tensor PCA

論文の概要: Average-Case Reductions for $k$-XOR and Tensor PCA

arxiv url: http://arxiv.org/abs/2601.19016v1
Date: Mon, 26 Jan 2026 23:05:54 GMT
ステータス: 翻訳完了
システム内更新日: 2026-02-04 14:06:11.266628
Title: Average-Case Reductions for $k$-XOR and Tensor PCA
Title（参考訳）: k$-XOR と Tensor PCA の平均値削減
Authors: Guy Bresler, Alina Harbuzova,
Abstract要約: 本稿では,2つの平均ケース問題(ノイズ$kmathsftext-XOR$とPCA)について検討する。それらの計算特性を,多時間平均ケースリダクションを用いて関連づける。
参考スコア（独自算出の注目度）: 5.481629070036533
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study two canonical planted average-case problems -- noisy $k\mathsf{\text{-}XOR}$ and Tensor PCA -- and relate their computational properties via poly-time average-case reductions. In fact, we consider a \emph{family of problems} that interpolates between $k\mathsf{\text{-}XOR}$ and Tensor PCA, allowing intermediate densities and signal levels. We introduce two \emph{densifying} reductions that increase the number of observed entries while controlling the decrease in signal, and, in particular, reduce any $k\mathsf{\text{-}XOR}$ instance at the computational threshold to Tensor PCA at the computational threshold. Additionally, we give new order-reducing maps (e.g., $5\to 4$ $k\mathsf{\text{-}XOR}$ and $7\to 4$ Tensor PCA) at fixed entry density.
Abstract（参考訳）: 本稿では,2つの標準植込み平均ケース問題(ノイズ$k\mathsf{\text{-}XOR}$とTensor PCA)について検討し,その計算特性を多時間平均ケース還元法を用いて検討する。実際、$k\mathsf{\text{-}XOR}$ と Tensor PCA を補間し、中間密度と信号レベルを許容する \emph{ Family of problems} を考える。信号の減少を制御しながら観察されたエントリ数を増加させる2つの'emph{densifying'還元を導入し、特に計算しきい値の$k\mathsf{\text{-}XOR}$インスタンスを計算しきい値のTensor PCAに還元する。さらに、新しい順序還元写像(例えば、$5\to 4$ $k\mathsf{\text{-}XOR}$と$7\to 4$ Tensor PCA)を固定エントリー密度で与える。

関連論文リスト

PCA of probability measures: Sparse and Dense sampling regimes [0.509780930114934]
我々はPCAを$n$の確率測度がそれぞれ$m$のサンプルによって観測される二重体制で研究する。経験的共分散作用素とPCA過剰リスクに対して$n-1/2 + m-$という形の収束率を導出する。実験的な共分散誤差に対して, 密度レジメレートが極小であることを示す。
論文参考訳（メタデータ） (2026-02-02T14:56:58Z)
Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
論文参考訳（メタデータ） (2025-10-09T09:47:40Z)
A Smooth Computational Transition in Tensor PCA [0.0]
重み付きハイパーグラフの特定の族をカウントしたテンソルPCAの効率的なアルゴリズムを提案する。この結果から,信号対雑音比と計算コストとの間には円滑なトレードオフが認められた。
論文参考訳（メタデータ） (2025-09-12T00:21:20Z)
Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA [17.75853665586128]
本稿では,汚染されたデータからmathbbRn_1times n$の低ランク行列$boldsymbolXstarの列部分空間を推定することに関心がある。信号-雑音比 (SNR) の広帯域化を図りながら, 最適な統計的精度を得る方法は困難である。
論文参考訳（メタデータ） (2023-03-10T20:22:18Z)
Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
すべての$t ll k$に対して、[gtrsim fracksqrtntsqrtln(2 + td/k2)$] さえあれば、この問題を解決するアルゴリズムがncdot dO(t)$で実行されていることを示す。スパース植込みベクター問題に対する時間アルゴリズムは,一部の制度における技術状況よりも高い保証が得られる。
論文参考訳（メタデータ） (2023-02-20T18:45:24Z)
Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文参考訳（メタデータ） (2023-02-13T22:51:07Z)
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)
Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文参考訳（メタデータ） (2022-11-10T00:40:37Z)
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)
The Complexity of Sparse Tensor PCA [1.90365714903665]
1leq leq k$の場合、我々のアルゴリズムは信号対雑音比$lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$のスパースベクトルを時間内に回収する。 PCAの制限されたケースでさえ、既知のアルゴリズムは、$lambda geq tildemathcalO(k cdot r)のスパースベクトルのみを復元する一方、我々のアルゴリズムは$lambda geを必要とする。
論文参考訳（メタデータ） (2021-06-11T10:57:00Z)
Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文参考訳（メタデータ） (2020-11-24T22:39:21Z)
Robust Interference Management for SISO Systems with Multiple Over-the-Air Computations [16.52374405363812]
複素数値を共有するMAC上での総和のオーバー・ザ・エア計算について考察する。適切なTx-Rxスケーリング因子を見つけることは、$s_n$の計算における低エラーとそれによって引き起こされる干渉との間にバランスをとる。
論文参考訳（メタデータ） (2020-04-21T11:15:26Z)

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