論文の概要: New Distinguishers for Negation-Limited Weak Pseudorandom Functions

• arxiv url: http://arxiv.org/abs/2203.12246v1
• Date: Wed, 23 Mar 2022 07:41:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-25 04:07:08.567936
• Title: New Distinguishers for Negation-Limited Weak Pseudorandom Functions
• Title（参考訳）: 否定限定弱擬似関数の新しい識別器
• Authors: Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, Xiaoming Sun
• Abstract要約: 我々は,一様ランダム関数と否定回路を区別する方法を示す。 以前の最良の区別器は$expbig(tildeO(n1/2 k)big)$ timeである。 否定制限回路の「中間」スライスには、強い低度フーリエ濃度がある。
• 参考スコア（独自算出の注目度）: 9.58461381434398
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show how to distinguish circuits with $\log k$ negations (a.k.a $k$-monotone functions) from uniformly random functions in $\exp\left(\tilde{O}\left(n^{1/3}k^{2/3}\right)\right)$ time using random samples. The previous best distinguisher, due to the learning algorithm by Blais, Cannone, Oliveira, Servedio, and Tan (RANDOM'15), requires $\exp\big(\tilde{O}(n^{1/2} k)\big)$ time. Our distinguishers are based on Fourier analysis on \emph{slices of the Boolean cube}. We show that some "middle" slices of negation-limited circuits have strong low-degree Fourier concentration and then we apply a variation of the classic Linial, Mansour, and Nisan "Low-Degree algorithm" (JACM'93) on slices. Our techniques also lead to a slightly improved weak learner for negation limited circuits under the uniform distribution.
• Abstract（参考訳）: ランダムなサンプルを用いた$\exp\left(\tilde{o}\left(n^{1/3}k^{2/3}\right)\right)$ timeにおける一様ランダム関数と、$\log k$ negations(すなわち$k$モノトン関数)で回路を区別する方法を示す。 それまでの最良の区別器は、Blais, Cannone, Oliveira, Servedio, Tan(RANDOM'15)の学習アルゴリズムにより、$\exp\big(\tilde{O}(n^{1/2} k)\big)$時間を必要とする。 我々の区別は、ブール立方体のemph{slices of the boolean cube}のフーリエ解析に基づいている。 否定制限回路の「中間」スライスには強い低次フーリエ濃度があることを示し、次に古典的なLinial, Mansour, Nisan "Low-Degree Algorithm" (JACM'93) の変種をスライスに適用する。 また,本手法により,一様分布下での制限回路の無効化に対して,弱学習が若干改善される。

関連論文リスト

• 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)
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier [6.47243430672461]
  2tildeO(sqrtn/varepsilon)$ 未知関数 $f:pm 1n rightarrow pm 1$ の一様ランダムな例を与えられたとき、我々のアルゴリズムは仮説 $g:pm 1n rightarrow pm 1$ を出力する。 また,2tildeO(sqrt)の実行時間を用いて,未知関数$f$からモノトンへの距離を加算誤差$varepsilon$まで推定するアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2023-04-05T18:52:10Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• 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)
• Private High-Dimensional Hypothesis Testing [4.133655523622441]
  我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。 具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
  論文  参考訳（メタデータ） (2022-03-03T06:25:48Z)
• Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits [21.70169149901781]
  低ランクのような単純な相関構造を持つモデルがより高速な学習率をもたらすかどうかを考察する。 特に,新しいemphBlock-RankベースのRUMモデルを導入し,最もよい項目は$(epsilon,delta)$-PACで,$O(r epsilon-2 log(n/delta))$サンプルのみを学習可能であることを示した。
  論文  参考訳（メタデータ） (2022-02-23T21:34:20Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)
• A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
  新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。 ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。 また、Impagliazzoのハードコアの改良版も証明した。
  論文  参考訳（メタデータ） (2020-02-25T11:46:08Z)

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

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