論文の概要: Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions

• arxiv url: http://arxiv.org/abs/2309.03986v1
• Date: Thu, 7 Sep 2023 19:37:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-11 16:43:41.426649
• Title: Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions
• Title（参考訳）: $\mathsf{OR}$と$\mathsf{MAX}$関数の雑音計算
• Authors: Banghua Zhu, Ziao Wang, Nadim Ghaddar, Jiantao Jiao, Lele Wang
• Abstract要約: ノイズの多いクエリを使って$n$変数の関数を計算することの問題を考察する。 我々は, [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] のクエリ数が十分であり,両関数の計算に必要であることを示す。
• 参考スコア（独自算出の注目度）: 22.847963422230155
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of computing a function of $n$ variables using noisy queries, where each query is incorrect with some fixed and known probability $p \in (0,1/2)$. Specifically, we consider the computation of the $\mathsf{OR}$ function of $n$ bits (where queries correspond to noisy readings of the bits) and the $\mathsf{MAX}$ function of $n$ real numbers (where queries correspond to noisy pairwise comparisons). We show that an expected number of queries of \[ (1 \pm o(1)) \frac{n\log \frac{1}{\delta}}{D_{\mathsf{KL}}(p \| 1-p)} \] is both sufficient and necessary to compute both functions with a vanishing error probability $\delta = o(1)$, where $D_{\mathsf{KL}}(p \| 1-p)$ denotes the Kullback-Leibler divergence between $\mathsf{Bern}(p)$ and $\mathsf{Bern}(1-p)$ distributions. Compared to previous work, our results tighten the dependence on $p$ in both the upper and lower bounds for the two functions.
• Abstract（参考訳）: ノイズの多いクエリを使って$n$変数の関数を計算することの問題は、各クエリが固定され既知の確率$p \in (0,1/2)$で誤りである。 具体的には、$n$ビットの$\mathsf{OR}$関数(クエリはビットのノイズリードに対応する)と$\mathsf{MAX}$関数(クエリはノイズペア比較に対応する)の計算を考える。 1 \pm o(1)) \frac{n\log \frac{1}{\delta}}{d_{\mathsf{kl}}(p \| 1-p)} \] の期待されたクエリ数は、双方の関数を消滅するエラー確率 $\delta = o(1)$ で計算するのに十分かつ必要であることを示し、ここで $d_{\mathsf{kl}}(p \| 1-p)$ は $\mathsf{bern}(p)$ と $\mathsf{bern}(1-p)$ の間のkullback-leibler の発散を表す。 先行研究と比較して,2つの関数の上限値と下限値の両方において,p$依存性が強くなった。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。 f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
  論文  参考訳（メタデータ） (2024-08-22T17:57:58Z)
• Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
  サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。 以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
  論文  参考訳（メタデータ） (2023-09-29T14:14:53Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• On relating one-way classical and quantum communication complexities [6.316693022958221]
  通信複雑性とは、関数入力が複数のパーティに分散されるときに、関数を計算するのに必要な通信量である。 量子情報の基本的な問題は、一方通行の量子と古典的な通信の複雑さの関係である。
  論文  参考訳（メタデータ） (2021-07-24T14:35:09Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)

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

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