論文の概要: Breaking The Dimension Dependence in Sparse Distribution Estimation
under Communication Constraints
- arxiv url: http://arxiv.org/abs/2106.08597v1
- Date: Wed, 16 Jun 2021 07:52:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-18 04:53:22.664311
- Title: Breaking The Dimension Dependence in Sparse Distribution Estimation
under Communication Constraints
- Title（参考訳）: コミュニケーション制約下におけるスパース分布推定における次元依存性の破れ
- Authors: Wei-Ning Chen, Peter Kairouz, Ayfer \"Ozg\"ur
- Abstract要約: サンプルサイズ$n$が最低しきい値$n*(s, d, b)$を超えると、$Oleft( fracsn2bright)$の$ell$推定誤差を達成できることを示す。
対話的な設定のために,新しい木に基づく推定手法を提案し,次元自由収束を実現するために必要な最小サンプルサイズを,さらに$n*(s, d, b)$に縮めることを示した。
- 参考スコア（独自算出の注目度）: 18.03695167610009
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of estimating a $d$-dimensional $s$-sparse discrete
distribution from its samples observed under a $b$-bit communication
constraint. The best-known previous result on $\ell_2$ estimation error for
this problem is $O\left( \frac{s\log\left( {d}/{s}\right)}{n2^b}\right)$.
Surprisingly, we show that when sample size $n$ exceeds a minimum threshold
$n^*(s, d, b)$, we can achieve an $\ell_2$ estimation error of $O\left(
\frac{s}{n2^b}\right)$. This implies that when $n>n^*(s, d, b)$ the convergence
rate does not depend on the ambient dimension $d$ and is the same as knowing
the support of the distribution beforehand.
We next ask the question: ``what is the minimum $n^*(s, d, b)$ that allows
dimension-free convergence?''. To upper bound $n^*(s, d, b)$, we develop novel
localization schemes to accurately and efficiently localize the unknown
support. For the non-interactive setting, we show that $n^*(s, d, b) = O\left(
\min \left( {d^2\log^2 d}/{2^b}, {s^4\log^2 d}/{2^b}\right) \right)$. Moreover,
we connect the problem with non-adaptive group testing and obtain a
polynomial-time estimation scheme when $n = \tilde{\Omega}\left({s^4\log^4
d}/{2^b}\right)$. This group testing based scheme is adaptive to the sparsity
parameter $s$, and hence can be applied without knowing it. For the interactive
setting, we propose a novel tree-based estimation scheme and show that the
minimum sample-size needed to achieve dimension-free convergence can be further
reduced to $n^*(s, d, b) = \tilde{O}\left( {s^2\log^2 d}/{2^b} \right)$.
- Abstract（参考訳）: 我々は,$d$-dimensional $s$-sparse離散分布を,$b$-bit通信制約の下で観測した標本から推定する問題を考察する。
この問題の$\ell_2$推定誤差の最もよく知られた結果は$o\left( \frac{s\log\left( {d}/{s}\right)}{n2^b}\right)$である。
驚いたことに、サンプルサイズ$n$が最低しきい値$n^*(s, d, b)$を超えると、$O\left( \frac{s}{n2^b}\right)$の$\ell_2$推定誤差が得られる。
これは、$n>n^*(s, d, b)$ の場合、収束率は環境次元 $d$ に依存しず、前もって分布の支持を知るのと同じであることを意味する。
次に質問する: ` `` は次元自由収束を可能にする最小の $n^*(s, d, b)$ とは何か?
上界の$n^*(s, d, b)$ に対して、未知のサポートを正確にかつ効率的にローカライズする新しいローカライズスキームを開発する。
非対話的な設定では、$n^*(s, d, b) = o\left( \min \left( {d^2\log^2 d}/{2^b}, {s^4\log^2 d}/{2^b}\right) \right) である。
さらに,n = \tilde{\omega}\left({s^4\log^4 d}/{2^b}\right)$の場合,非適応群テストと問題を結びつけ,多項式時間推定スキームを得る。
このグループテストベースのスキームはスパーシティパラメータ$s$に適応するので、それを知らずに適用することができる。
インタラクティブな設定のために,新しい木ベース推定スキームを提案し,次元自由収束を達成するのに必要な最小サンプルサイズをさらに$n^*(s, d, b) = \tilde{o}\left( {s^2\log^2 d}/{2^b} \right)$に削減できることを示した。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Interplay between depth and width for interpolation in neural ODEs [0.0]
それらの幅$p$と層遷移数$L$の相互作用について検討する。
高次元設定では、$p=O(N)$ニューロンが正確な制御を達成するのに十分であることを示す。
論文 参考訳（メタデータ） (2024-01-18T11:32:50Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Nonasymptotic one-and two-sample tests in high dimension with unknown
covariance structure [0.0]
テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。
本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
論文 参考訳（メタデータ） (2021-09-01T06:22:53Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。