論文の概要: Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations

• arxiv url: http://arxiv.org/abs/2411.12512v1
• Date: Tue, 19 Nov 2024 13:53:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-20 13:34:58.868824
• Title: Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
• Title（参考訳）: 雑音線形方程式の解法における準最適時空間トレードオフ
• Authors: Kiril Bangachev, Guy Bresler, Stefan Tiegel, Vinod Vaikuntanathan,
• Abstract要約: 次元 $Theta において、$mathbbZ/qmathbbZ$ 上の雑音線型方程式を解くことによる時間短縮を提案する。 密接な問題からスパース問題の硬さを推定する。
• 参考スコア（独自算出の注目度）: 17.957489763446496
• License:
• Abstract: We present a polynomial-time reduction from solving noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $\Theta(k\log n/\mathsf{poly}(\log k,\log q,\log\log n))$ with a uniformly random coefficient matrix to noisy linear equations over $\mathbb{Z}/q\mathbb{Z}$ in dimension $n$ where each row of the coefficient matrix has uniformly random support of size $k$. This allows us to deduce the hardness of sparse problems from their dense counterparts. In particular, we derive hardness results in the following canonical settings. 1) Assuming the $\ell$-dimensional (dense) LWE over a polynomial-size field takes time $2^{\Omega(\ell)}$, $k$-sparse LWE in dimension $n$ takes time $n^{\Omega({k}/{(\log k \cdot (\log k + \log \log n))})}.$ 2) Assuming the $\ell$-dimensional (dense) LPN over $\mathbb{F}_2$ takes time $2^{\Omega(\ell/\log \ell)}$, $k$-sparse LPN in dimension $n$ takes time $n^{\Omega(k/(\log k \cdot (\log k + \log \log n)^2))}~.$ These running time lower bounds are nearly tight as both sparse problems can be solved in time $n^{O(k)},$ given sufficiently many samples. We further give a reduction from $k$-sparse LWE to noisy tensor completion. Concretely, composing the two reductions implies that order-$k$ rank-$2^{k-1}$ noisy tensor completion in $\mathbb{R}^{n^{\otimes k}}$ takes time $n^{\Omega(k/ \log k \cdot (\log k + \log \log n))}$, assuming the exponential hardness of standard worst-case lattice problems.
• Abstract（参考訳）: 次数 $\mathbb{Z}/q\mathbb{Z}$ 上のノイジー線型方程式を解くことによる多項式時間短縮について述べる: 次元 $\Theta(k\log n/\mathsf{poly}(\log k,\log q,\log \log n))$ 次元 $\mathbb{Z}/q\mathbb{Z}$ 上のノイジー線型方程式に一様ランダムな係数行列を持つ。 これにより、より密接な問題からスパース問題の硬さを推定できる。 特に、以下の標準設定で硬度を導出する。 1) 多項式サイズの体上の$\ell$-dimensional (dense) LWE を仮定すると、時間は 2,^{\Omega(\ell)}$, $k$-sparse LWE in dimension $n$ take time $n^{\Omega({k}/{(\log k \cdot (\log k + \log \log n))} である。 $ 2)$\ell$-dimensional (dense) LPN over $\mathbb{F}_2$ take time $2^{\Omega(\ell/\log \ell)}$, $k$-sparse LPN in dimension $n$ take time $n^{\Omega(k/(\log k \cdot (\log k + \log \log n)^2)~ これらの実行時間の低い境界は、どちらもスパース問題を十分に多くのサンプルを与えられた時間$n^{O(k)}で解くことができるので、ほぼ厳密である。 さらに、$k$-sparse LWE からノイズテンソル完備化へ還元する。 具体的には、次数-$k$ rank-$2^{k-1}$ noisy tensor completion in $\mathbb{R}^{n^{\otimes k}}$ take time $n^{\Omega(k/ \log k \cdot (\log k + \log \log n))}$である。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• 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)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Kernel Thinning [26.25415159542831]
  カーネルの薄型化は、サンプリングや標準的な薄型化よりも効率的に$mathbbP$を圧縮するための新しい手順である。 我々は、ガウス、マタン、およびB-スプライン核に対する明示的な非漸近的な最大誤差境界を導出する。
  論文  参考訳（メタデータ） (2021-05-12T17:56:42Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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