論文の概要: Rényi divergence-based uniformity guarantees for $k$-universal hash functions

• arxiv url: http://arxiv.org/abs/2410.16459v1
• Date: Mon, 21 Oct 2024 19:37:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-23 14:26:49.290863
• Title: Rényi divergence-based uniformity guarantees for $k$-universal hash functions
• Title（参考訳）: レーニ発散に基づく$k$-ユニバーサルハッシュ関数の均一性保証
• Authors: Madhura Pathegama, Alexander Barg,
• Abstract要約: 普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。 ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
• 参考スコア（独自算出の注目度）: 59.90381090395222
• License:
• Abstract: Universal hash functions map the output of a source to random strings over a finite alphabet, aiming to approximate the uniform distribution on the set of strings. A classic result on these functions, called the Leftover Hash Lemma, gives an estimate of the distance from uniformity based on the assumptions about the min-entropy of the source. We prove several results concerning extensions of this lemma to a class of functions that are $k^\ast$-universal, i.e., $l$-universal for all $2\le l\le k$. As a common distinctive feature, our results provide estimates of closeness to uniformity in terms of the $\alpha$-R\'enyi divergence for all $\alpha\in (1,\infty]$. For $1\le \alpha\le k$ we show that it is possible to convert all the randomness of the source measured in $\alpha$-R\'enyi entropy into approximately uniform bits with nearly the same amount of randomness. For large enough $k$ we show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy. We also extend these results to hashing with side information.
• Abstract（参考訳）: ユニバーサルハッシュ関数は、ソースの出力を有限アルファベット上のランダムな文字列にマッピングし、文字列の集合上の一様分布を近似する。 これらの関数の古典的な結果、すなわち左上ハッシュ補題は、源のミンエントロピーに関する仮定に基づいて一様性からの距離を推定する。 この補題を$k^\ast$-ユニバーサル、すなわち$l$-ユニバーサルとする函数のクラスへ拡張するいくつかの結果が証明される。 共通の特徴として、我々の結果は、すべての$\alpha\in (1,\infty]$に対して$\alpha$-R\'enyi の発散という観点から、一様性への近さを推定する。 $1\le \alpha\le k$ に対して、$\alpha$-R\'enyi エントロピーで測定されたソースのすべてのランダム性は、ほぼ同じ量のランダム性を持つほぼ均一なビットに変換可能であることを示す。 十分大きな$k$の場合、min-エントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。 また、これらの結果をサイド情報によるハッシュに拡張します。

関連論文リスト

• Replicable Uniformity Testing [1.5883812630616523]
  この研究は、アルゴリズムの複製性という枠組みの下で一様性テストを再考する。 我々は, $tildeO(sqrtn varepsilon-2 rho-1)$サンプルのみを用いて複製可能なテスタを得る。
  論文  参考訳（メタデータ） (2024-10-12T02:55:17Z)
• How to Shrink Confidence Sets for Many Equivalent Discrete Distributions? [17.52590726972374]
  機械学習問題における置換等価性を利用する。 信頼集合のサイズは$O/sqrtn_k)$と$O/max_kin K n_k)$で縮小することを示す。
  論文  参考訳（メタデータ） (2024-07-22T14:19:19Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
  我々は、各期間に複数の武器で再生可能資源の1単位を割り当てる意思決定者について検討する。 アームは未知でランダムな報酬であり、その手段は割り当てられたリソースに比例し、分散は割り当てられたリソースのオーダー$b$に比例する。
  論文  参考訳（メタデータ） (2023-06-28T21:59:11Z)
• Metric-Fair Classifier Derandomization [6.269732593554894]
  機械学習における分類器のデランドマイズ問題について検討する。 事前のデランドマイズ法は, ほぼ最大値の不等式であることを示す。 我々はこれらの2つの間の魅力的なトレードオフを提供するデランドマイズ手順を考案する。
  論文  参考訳（メタデータ） (2022-06-15T21:36:57Z)
• Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds [0.8594140167290096]
  有限体上のランダムに選択された線型写像が $ell_infty$ の意味でよいハッシュ関数を与えることを示す。 負荷分散文献[RS98]からの既知のバウンダリにより、この結果は厳密であり、線形関数とトラリーランダム関数がエントロピー損失の定数因子であることを示す。
  論文  参考訳（メタデータ） (2022-04-04T17:21:10Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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