論文の概要: SQ Lower Bounds for Random Sparse Planted Vector Problem
- arxiv url: http://arxiv.org/abs/2301.11124v1
- Date: Thu, 26 Jan 2023 14:22:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 13:34:50.871835
- Title: SQ Lower Bounds for Random Sparse Planted Vector Problem
- Title（参考訳）: ランダムスパース植込みベクトル問題に対するSQ下界
- Authors: Jingqiu Ding, Yiding Hua
- Abstract要約: 我々は,$nll rho2 d2$と$gg frac1sqrtd$の場合に,VSTATクエリの超多項式数が,より簡単な統計的テスト問題を解決するために必要であることを示す。
特に,$nll rho2 d2$と$gg frac1sqrtd$の場合に,VSTATクエリの超多項式数が,より簡単な統計的テスト問題を解決するために必要であることを示す。
- 参考スコア（独自算出の注目度）: 2.0305676256390934
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider the setting where a $\rho$-sparse Rademacher vector is planted in a
random $d$-dimensional subspace of $R^n$. A classical question is how to
recover this planted vector given a random basis in this subspace. A recent
result by [ZSWB21] showed that the Lattice basis reduction algorithm can
recover the planted vector when $n\geq d+1$. Although the algorithm is not
expected to tolerate inverse polynomial amount of noise, it is surprising
because it was previously shown that recovery cannot be achieved by low degree
polynomials when $n\ll \rho^2 d^{2}$ [MW21]. A natural question is whether we
can derive an Statistical Query (SQ) lower bound matching the previous low
degree lower bound in [MW21]. This will
- imply that the SQ lower bound can be surpassed by lattice based algorithms;
- predict the computational hardness when the planted vector is perturbed by
inverse polynomial amount of noise. In this paper, we prove such an SQ lower
bound. In particular, we show that super-polynomial number of VSTAT queries is
needed to solve the easier statistical testing problem when $n\ll \rho^2 d^{2}$
and $\rho\gg \frac{1}{\sqrt{d}}$. The most notable technique we used to derive
the SQ lower bound is the almost equivalence relationship between SQ lower
bound and low degree lower bound [BBH+20, MW21].
- Abstract（参考訳）: 例えば、$\rho$-sparse Rademacherベクトルが$R^n$のランダムな$d$-次元部分空間に植え付けられるような設定を考える。
古典的な疑問は、この部分空間においてランダムな基底を与えられたこの植込みベクトルの回復方法である。
ZSWB21] による最近の結果は,$n\geq d+1$ のとき,格子基底還元アルゴリズムが植付ベクトルを復元できることを示した。
このアルゴリズムは逆多項式の雑音を許容するものではないが、$n\ll \rho^2 d^{2}$ [MW21] のときの低次多項式によって回復が達成できないことがこれまで示されていたため、驚くべきものである。
自然な疑問は、[MW21]の前の低次下界と一致する統計的クエリ(SQ)の下界を導出できるかどうかである。
このことは、SQの下界が格子ベースのアルゴリズムによって超えられることを暗示する; - 植込みベクトルが逆多項式のノイズ量によって摂動されるときの計算硬度を予測する。
本稿では、そのようなSQの下限を証明する。
特に、n\ll \rho^2 d^{2}$ と $\rho\gg \frac{1}{\sqrt{d}}$ の場合、より簡単な統計テスト問題を解決するには、vstatクエリの超多項数が必要である。
我々がSQ下界を導出した最も顕著な手法は、SQ下界と低次下界 [BBH+20, MW21] のほぼ同値関係である。
関連論文リスト
- Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - One-half reflected entropy is not a lower bound for entanglement of
purification [6.578021055948705]
精製の絡み合う$E_p(A:B)$は、すべての$qgeq2$に対して$q$-R'enyi反射エントロピー$S_R(q)(A:B)$の半分で下界する。
この結果は、半古典的な重力双対を持つ CFT 状態のような制限された状態の集合が、問題となる境界に従う可能性を妨げるものではない。
論文 参考訳（メタデータ） (2023-09-05T18:00:13Z) - Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。
我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。
V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-19T01:09:24Z) - Planted Bipartite Graph Detection [13.95780443241133]
ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。
ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。
k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
論文 参考訳（メタデータ） (2023-02-07T18:18:17Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。