We revisit the well-studied problem of estimating the Shannon entropy of a probability distribution, now given access to a probability-revealing conditional sampling oracle. In this model, the oracle takes as input the representation of a set S, and returns a sample from the distribution obtained by conditioning on S, together with the probability of that sample in the distribution. Our work is motivated by applications of such algorithms in Quantitative Information Flow analysis (QIF) in programming-language-based security. Here, information-theoretic quantities capture the effort required on the part of an adversary to obtain access to confidential information. These applications demand accurate measurements when the entropy is small. Existing algorithms that do not use conditional samples require a number of queries that scale inversely with the entropy, which is unacceptable in this regime. On the other hand, prior work in the conditional sampling model only obtained a high-order polynomial query complexity, <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10703_2024_467_Article_IEq1.gif" Format="GIF" Height="26" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">${\mathcal {O}}(\frac{m^7}{\varepsilon ^8}\log \frac{1}{\delta })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mfrac> <msup> <mi>m</mi> <mn>7</mn> </msup> <msup> <mi>ε</mi> <mn>8</mn> </msup> </mfrac> <mo>log</mo> <mfrac> <mn>1</mn> <mi>δ</mi> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> queries, to obtain additive <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10703_2024_467_Article_IEq2.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">$\varepsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation>-approximations on a domain of size <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10703_2024_467_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">${\mathcal {O}}(2^m)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mi>m</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>; note furthermore that additive approximations are also unacceptable for such applications. No prior work could obtain polynomial-query multiplicative approximations to the entropy in the low-entropy regime. We obtain multiplicative <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10703_2024_467_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">$(1+\varepsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>ε</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-approximations using only <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10703_2024_467_Article_IEq5.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">${\mathcal {O}}(\frac{m}{\varepsilon ^2}\log \frac{1}{\delta })$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mfrac> <mi>m</mi> <msup> <mi>ε</mi> <mn>2</mn> </msup> </mfrac> <mo>log</mo> <mfrac> <mn>1</mn> <mi>δ</mi> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> queries to the probability-revealing conditional sampling oracle. Indeed, moreover, we obtain small, explicit constants, and demonstrate that our algorithm obtains a substantial improvement in practice over the previous state-of-the-art methods used for entropy estimation in QIF.

A scalable entropy estimator

期刊论文
发表日期：

2025年1月15日

查看全文

Priyanka Golia,
Brendan Juba,
Kuldeep S. Meel

摘要

We revisit the well-studied problem of estimating the Shannon entropy of a probability distribution, now given access to a probability-revealing conditional sampling oracle. In this model, the oracle takes as input the representation of a set S, and returns a sample from the distribution obtained by conditioning on S, together with the probability of that sample in the distribution. Our work is motivated by applications of such algorithms in Quantitative Information Flow analysis (QIF) in programming-language-based security. Here, information-theoretic quantities capture the effort required on the part of an adversary to obtain access to confidential information. These applications demand accurate measurements when the entropy is small. Existing algorithms that do not use conditional samples require a number of queries that scale inversely with the entropy, which is unacceptable in this regime. On the other hand, prior work in the conditional sampling model only obtained a high-order polynomial query complexity, ${\mathcal {O}}(\frac{m^7}{\varepsilon ^8}\log \frac{1}{\delta })$ $O (\frac{m^{7}}{ε^{8}} log \frac{1}{δ})$ queries, to obtain additive $\varepsilon $ $ε$ -approximations on a domain of size ${\mathcal {O}}(2^m)$ $O (2^{m})$ ; note furthermore that additive approximations are also unacceptable for such applications. No prior work could obtain polynomial-query multiplicative approximations to the entropy in the low-entropy regime. We obtain multiplicative $(1+\varepsilon )$ $(1 + ε)$ -approximations using only ${\mathcal {O}}(\frac{m}{\varepsilon ^2}\log \frac{1}{\delta })$ $O (\frac{m}{ε^{2}} log \frac{1}{δ})$ queries to the probability-revealing conditional sampling oracle. Indeed, moreover, we obtain small, explicit constants, and demonstrate that our algorithm obtains a substantial improvement in practice over the previous state-of-the-art methods used for entropy estimation in QIF.