論文の概要: Randomised Composition and Small-Bias Minimax
- arxiv url: http://arxiv.org/abs/2208.12896v1
- Date: Fri, 26 Aug 2022 23:32:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-29 14:26:04.832519
- Title: Randomised Composition and Small-Bias Minimax
- Title（参考訳）: ランダム化組成と小バイアスミニマックス
- Authors: Shalev Ben-David, Eric Blais, Mika G\"o\"os, Gilbert Maystre
- Abstract要約: クエリ複雑性に関する2つの結果が、$mathrmR(f)$であることを示す。
まず、「線形化」複雑性測度$mathrmLR$を導入し、内部衝突合成定理を満たすことを示す: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$と$g$。
- 参考スコア（独自算出の注目度）: 0.9252523881586053
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We prove two results about randomised query complexity $\mathrm{R}(f)$.
First, we introduce a "linearised" complexity measure $\mathrm{LR}$ and show
that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g)
\geq \Omega(\mathrm{R}(f) \mathrm{LR}(g))$ for all partial $f$ and $g$, and
moreover, $\mathrm{LR}$ is the largest possible measure with this property. In
particular, $\mathrm{LR}$ can be polynomially larger than previous measures
that satisfy an inner composition theorem, such as the max-conflict complexity
of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019).
Our second result addresses a question of Yao (FOCS 1977). He asked if
$\epsilon$-error expected query complexity $\bar{\mathrm{R}}_{\epsilon}(f)$
admits a distributional characterisation relative to some hard input
distribution. Vereshchagin (TCS 1998) answered this question affirmatively in
the bounded-error case. We show that an analogous theorem fails in the
small-bias case $\epsilon=1/2-o(1)$.
- Abstract（参考訳）: 乱数化クエリ複雑性 $\mathrm{R} に関する2つの結果を証明する。
(f)$。
まず、「線形化」複雑性測度$\mathrm{LR}$を導入し、内最適合成定理を満たすことを示す:$\mathrm{R}(f\circ)。
g) \geq \omega(\mathrm{r})
(f) \mathrm{lr}
(g))$ for all partial $f$ and $g$, さらに、$\mathrm{LR}$は、この性質で可能な最大の測度である。
特に、$\mathrm{LR}$ はガヴィンスキー、リー、サンサ、サニヤールの最大複雑性のような内部構成定理を満たす以前の測度よりも多項式的に大きい(ICALP 2019)。
第2の結果は,Yao (FOCS 1977) の問題に対処した。
彼は $\epsilon$-error expected query complexity $\bar{\mathrm{R}}_{\epsilon} について尋ねた。
(f)$は、あるハードな入力分布に対する分布的特徴付けを認める。
Vereshchagin (TCS 1998) はこの質問に答えた。
類似の定理は小バイアスの場合$\epsilon=1/2-o(1)$で失敗することを示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
論文 参考訳（メタデータ） (2024-03-04T18:30:33Z) - Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。
具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。
本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
論文 参考訳（メタデータ） (2023-11-22T04:34:09Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - 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) - The Complexity of Dynamic Least-Squares Regression [11.815510373329337]
動的最小二乗回帰の複雑さ。
ゴールは、$min_mathbfx(t)| mathbfA(t) mathbfb(t) |$ for all $tin に対する $epsilon-approximate ソリューションを維持することである。
論文 参考訳（メタデータ） (2022-01-01T18:36:17Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - A Tight Composition Theorem for the Randomized Query Complexity of
Partial Functions [1.2284934135116514]
合成関数のランダム化クエリ複雑性に関する2つの新しい結果を示す。
すべての$f$と$g$に対して、$(Rcirc g)=Omega(mathopnoisyR(f)cdot R(g))$, ここで$mathopnoisyR(f)$は、ノイズ入力に対する$f$の計算コストを表す尺度である。
論文 参考訳（メタデータ） (2020-02-25T11:58:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。