Rényi divergence-based uniformity guarantees for $k$-universal hash functions

• URL: http://arxiv.org/abs/2410.16459v1
• Date: Mon, 21 Oct 2024 19:37:35 GMT
• Title: Rényi divergence-based uniformity guarantees for $k$-universal hash functions
• Authors: Madhura Pathegama, Alexander Barg,
• Abstract summary: Universal hash functions map the output of a source to random strings over a finite alphabet. We show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy.
• Score: 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.

Related papers

• Replicable Uniformity Testing [1.5883812630616523]
  This work revisits uniformity testing under the framework of algorithmic replicability. We obtain a replicable tester using only $tildeO(sqrtn varepsilon-2 rho-1)$ samples.
  arXiv  Detail & Related papers  (2024-10-12T02:55:17Z)
• How to Shrink Confidence Sets for Many Equivalent Discrete Distributions? [17.52590726972374]
  We exploit permutation-equivalence in machine learning problems. We show that the size of confidence sets shrinks at rates of $O/sqrtn_k)$ and $O/max_kin K n_k)$.
  arXiv  Detail & Related papers  (2024-07-22T14:19:19Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
  We consider a decision maker allocating one unit of renewable and divisible resource in each period on a number of arms. The arms have unknown and random rewards whose means are proportional to the allocated resource and whose variances are proportional to an order $b$ of the allocated resource.
  arXiv  Detail & Related papers  (2023-06-28T21:59:11Z)
• Metric-Fair Classifier Derandomization [6.269732593554894]
  We study the problem of classifier derandomization in machine learning. We show that the prior derandomization approach is almost maximally metric-unfair. We devise a derandomization procedure that provides an appealing tradeoff between these two.
  arXiv  Detail & Related papers  (2022-06-15T21:36:57Z)
• Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds [0.8594140167290096]
  We show that a randomly chosen linear map over a finite field gives a good hash function in the $ell_infty$ sense. By known bounds from the load balancing literature [RS98], our results are tight and show that linear functions hash as well as trully random function up to a constant factor in the entropy loss.
  arXiv  Detail & Related papers  (2022-04-04T17:21:10Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.