論文の概要: How to send a real number using a single bit (and some shared randomness)

• arxiv url: http://arxiv.org/abs/2010.02331v4
• Date: Thu, 20 May 2021 09:41:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 22:41:22.067590
• Title: How to send a real number using a single bit (and some shared randomness)
• Title（参考訳）: 1ビット(と何らかの共有ランダム性)を使って実数を送る方法
• Authors: Ran Ben-Basat, Michael Mitzenmacher, Shay Vargaftik
• Abstract要約: 一つのビットを用いて実数の推定を伝達する問題を考える。 共有ランダム性は, 単一ビット以下で, 双方のケースのコストを削減できることを示す。
• 参考スコア（独自算出の注目度）: 22.42784112323806
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the fundamental problem of communicating an estimate of a real number $x\in[0,1]$ using a single bit. A sender that knows $x$ chooses a value $X\in\set{0,1}$ to transmit. In turn, a receiver estimates $x$ based on the value of $X$. We consider both the biased and unbiased estimation problems and aim to minimize the cost. For the biased case, the cost is the worst-case (over the choice of $x$) expected squared error, which coincides with the variance if the algorithm is required to be unbiased. We first overview common biased and unbiased estimation approaches and prove their optimality when no shared randomness is allowed. We then show how a small amount of shared randomness, which can be as low as a single bit, reduces the cost in both cases. Specifically, we derive lower bounds on the cost attainable by any algorithm with unrestricted use of shared randomness and propose near-optimal solutions that use a small number of shared random bits. Finally, we discuss open problems and future directions.
• Abstract（参考訳）: 1ビットを用いて実数 $x\in[0,1]$ の見積もりを伝える基本的な問題を考える。 x$ を知っている送信者は、送信する値 $x\in\set{0,1}$ を選択する。 すると、受信者は$X$の値に基づいて$x$を推定する。 偏りと偏りのない推定問題を考慮し、コストを最小化する。 偏りのある場合、コストは($x$の選択よりも)予測された二乗誤差の最悪のケースであり、アルゴリズムが偏りをなくす必要がある場合の分散と一致する。 まず,偏りや偏りのない推定手法を概観し,共有ランダム性が認められない場合の最適性を証明する。 そして、共有ランダム性が小さければ1ビット程度の低さで、両方のケースでコストを削減できることを示す。 具体的には、共有乱数を制限しないアルゴリズムで実現可能なコストの下限を導出し、少数の共有乱数ビットを用いた近似最適解を提案する。 最後に、オープンな問題と今後の方向性について論じる。

関連論文リスト

• Distribution-Aware Mean Estimation under User-level Local Differential Privacy [5.267844649650687]
  ユーザレベルのローカル差分プライバシに基づく平均推定の問題について考察する。 分布認識平均推定アルゴリズムに基づいて、平均推定タスクに対して、最悪の場合のリスクに対して、$M$依存上界を確立する。
  論文  参考訳（メタデータ） (2024-10-12T11:57:52Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances [15.990720051907864]
  Subset-of-Signalsモデルはヘテロスケダティック平均推定のベンチマークとして機能する。 我々のアルゴリズムは、このオープンな問題を対数的要因に分解する。 たとえ$d=2$であっても、我々の手法は各サンプルのばらつきを知るのに匹敵するレートを可能にします。
  論文  参考訳（メタデータ） (2023-12-05T01:13:10Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• CountSketches, Feature Hashing and the Median of Three [18.85876632959721]
  古典的なCountSketch法は、(高次元)ユークリッドベクトル $v$ を次元 $(2t-1) s$ に変換するスパースでランダムな射影である。 我々の主な貢献は、Count-Sketchの新しい分析であり、$t > 1$ のとき、$O(min|v|2/s2,|v|2/s2)$ への分散の改善を示す。 この結果は、基本的にCountSketchと同一であるが中央値を使用しないFeature Hashing法が可能であることを示唆している。
  論文  参考訳（メタデータ） (2021-02-03T18:45:21Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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