論文の概要: On the Optimal Bounds for Noisy Computing

• arxiv url: http://arxiv.org/abs/2306.11951v1
• Date: Wed, 21 Jun 2023 00:31:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-22 15:15:55.076552
• Title: On the Optimal Bounds for Noisy Computing
• Title（参考訳）: ノイズコンピューティングのための最適境界について
• Authors: Banghua Zhu, Ziao Wang, Nadim Ghaddar, Jiantao Jiao and Lele Wang
• Abstract要約: Wevisit the problem of computing with noisy information considered in Feige et al. 1994。 与えられた要素に対して、目標は、各クエリの結果が確率$p$で反転されたときに、少なくとも1-delta$の確率で所望の関数を正しく回復することである。 本稿では、過去の結果に基づいて各クエリを適応的に設計できる適応型サンプリング設定と、過去の結果に依存しない非適応型サンプリング設定の両方について考察する。
• 参考スコア（独自算出の注目度）: 17.56584950469176
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the problem of computing with noisy information considered in Feige et al. 1994, which includes computing the OR function from noisy queries, and computing the MAX, SEARCH and SORT functions from noisy pairwise comparisons. For $K$ given elements, the goal is to correctly recover the desired function with probability at least $1-\delta$ when the outcome of each query is flipped with probability $p$. We consider both the adaptive sampling setting where each query can be adaptively designed based on past outcomes, and the non-adaptive sampling setting where the query cannot depend on past outcomes. The prior work provides tight bounds on the worst-case query complexity in terms of the dependence on $K$. However, the upper and lower bounds do not match in terms of the dependence on $\delta$ and $p$. We improve the lower bounds for all the four functions under both adaptive and non-adaptive query models. Most of our lower bounds match the upper bounds up to constant factors when either $p$ or $\delta$ is bounded away from $0$, while the ratio between the best prior upper and lower bounds goes to infinity when $p\rightarrow 0$ or $p\rightarrow 1/2$. On the other hand, we also provide matching upper and lower bounds for the number of queries in expectation, improving both the upper and lower bounds for the variable-length query model.
• Abstract（参考訳）: feige et al. 1994で検討されているノイズ情報を用いた計算の問題を再検討し,ノイズクエリからor関数を計算し,ノイズ対比較から最大関数,検索関数,ソート関数を計算する。 与えられた要素が$K$の場合、各クエリの結果が確率$p$で反転した場合、所望の関数を少なくとも1-\delta$で正しく回復することが目標である。 各クエリが過去の結果に基づいて適応的に設計できる適応型サンプリング設定と、クエリが過去の結果に依存しない非適応型サンプリング設定の両方を検討する。 以前の作業は、$K$への依存の観点から、最悪のクエリの複雑さに厳密な制限を与えている。 しかし、上界と下界は$\delta$と$p$への依存の観点からは一致しない。 適応クエリモデルと非適応クエリモデルの両方の下で、4つの関数の下位境界を改善する。 我々の下限のほとんどは、$p$ または $\delta$ が$0$ から離れたときの上限値と一致するが、最高の上限と下限の比率は$p\rightarrow 0$ または $p\rightarrow 1/2$ のとき無限大になる。 一方,予測されるクエリ数に対する上限値と下限値の整合性も提供し,可変長クエリモデルに対する上限値と下限値の両方を改善した。

関連論文リスト

• Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization [51.533164528799084]
  小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。 関数評価がノイズである場合でも,このパターンは真であることがわかった。
  論文  参考訳（メタデータ） (2024-01-11T07:45:09Z)
• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Order-Optimal Error Bounds for Noisy Kernel-Based Bayesian Quadrature [42.129843613950285]
  我々は、Match'ern-$nu$ kernel を用いて、Em Reproduction Kernel Hilbert Space (RKHS) の関数を考える。 ブラックボックスクエリが分散$sigma2$のガウスノイズを受ける場合、最大で$T$のアルゴリズムは平均絶対誤差$Omega(T-fracnud-1 + sigma T-frac12)$を発生しなければならない。
  論文  参考訳（メタデータ） (2022-02-22T01:49:41Z)
• Nearly Optimal Algorithms for Level Set Estimation [21.83736847203543]
  線形包帯に対する最近の適応的実験設計手法と関連づけることで, レベルセット推定問題に対する新しいアプローチを提案する。 我々は、我々の境界がほぼ最適であることを示す。すなわち、我々の上限は、しきい値線形帯域に対して既存の下限と一致する。
  論文  参考訳（メタデータ） (2021-11-02T17:45:02Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Query complexity of heavy hitter estimation [6.373263986460191]
  我々は、サブセット $mathcalSgamma_mathcalP$ を、基礎となる分布 $mathcalP$ をサポートする要素の特定の問題を考える。 それぞれのクエリはインデックス$i$であり、オラクルは値を$X_i$と$(b)$はペア$(i,j)$である。 それぞれの問合せモデルに対して、各ラウンドでどの問合せを全体に依存するかを決定するシーケンシャルな推定アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-05-29T07:15:46Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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