論文の概要: Estimation of Entropy in Constant Space with Improved Sample Complexity
- arxiv url: http://arxiv.org/abs/2205.09804v1
- Date: Thu, 19 May 2022 18:51:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-23 16:02:44.305120
- Title: Estimation of Entropy in Constant Space with Improved Sample Complexity
- Title(参考訳): サンプル複雑性が向上した定空間エントロピーの推定
- Authors: Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
- Abstract要約: サンプルの複雑さを$(k/epsilon2)cdot textpolylog (1/epsilon)$に削減する新しい定数メモリスキームを提供する。
これは$textpolylog (1/epsilon)$ factorまで最適であると推測する。
- 参考スコア(独自算出の注目度): 14.718968517824756
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent work of Acharya et al. (NeurIPS 2019) showed how to estimate the
entropy of a distribution $\mathcal D$ over an alphabet of size $k$ up to
$\pm\epsilon$ additive error by streaming over $(k/\epsilon^3) \cdot
\text{polylog}(1/\epsilon)$ i.i.d. samples and using only $O(1)$ words of
memory. In this work, we give a new constant memory scheme that reduces the
sample complexity to $(k/\epsilon^2)\cdot \text{polylog}(1/\epsilon)$. We
conjecture that this is optimal up to $\text{polylog}(1/\epsilon)$ factors.
- Abstract(参考訳): acharya et al. (neurips 2019) の最近の研究では、$(k/\epsilon^3) \cdot \text{polylog}(1/\epsilon)$ i.i.d.のサンプルをストリーミングし、$o(1)$のメモリのみを使用して、大きさのアルファベット上の$\mathcal d$の分布のエントロピーを推定する方法が示されている。
この研究では、サンプルの複雑さを$(k/\epsilon^2)\cdot \text{polylog}(1/\epsilon)$にする新しい定数メモリスキームを与える。
これは$\text{polylog}(1/\epsilon)$ factor まで最適であると推測する。
関連論文リスト
- Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳(メタデータ) (2024-09-05T16:59:56Z) - Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳(メタデータ) (2024-02-22T02:20:24Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳(メタデータ) (2023-03-30T02:50:49Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - The Price of Tolerance in Distribution Testing [31.10049510641336]
サンプルの複雑さは [fracsqrtnvarepsilon2 + fracnlog n cdotmaxleftfracvarepsilon2 であることが示され、この2つの既知事例の間に円滑なトレードオフをもたらす。
また、p$ と$q$ の両方が未知である寛容同値検定の問題についても同様の特徴を与える。
論文 参考訳(メタデータ) (2021-06-25T03:59:42Z) - 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) - Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication
Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。
我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文 参考訳(メタデータ) (2020-06-23T20:21:27Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。