arXiv:2308.04264

Distance Estimation for High-Dimensional Discrete Distributions

Gunjan Kumar, Kuldeep S. Meel, Yash Pote

Published Aug 8, 2023• 0 citations

Abstract

Given two distributions $\mathcal{P}$ and $\mathcal{Q}$ over a high-dimensional domain $\{0,1\}^n$, and a parameter $\varepsilon$, the goal of distance estimation is to determine the statistical distance between $\mathcal{P}$ and $\mathcal{Q}$, up to an additive tolerance $\pm \varepsilon$. Since exponential lower bounds (in $n$) are known for the problem in the standard sampling model, research has focused on richer query models where one can draw conditional samples. This paper presents the first polynomial query distance estimator in the conditional sampling model ($\mathsf{COND}$). We base our algorithm on the relatively weaker \textit{subcube conditional} sampling ($\mathsf{SUBCOND}$) oracle, which draws samples from the distribution conditioned on some of the dimensions. $\mathsf{SUBCOND}$ is a promising model for widespread practical use because it captures the natural behavior of discrete samplers. Our algorithm makes $\tilde{\mathcal{O}}(n^3/\varepsilon^5)$ queries to $\mathsf{SUBCOND}$.

DOI: 10.48550/arxiv.2308.04264

Related papers

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

Clément L. Canonne, Chen, Xi, Gautam Kamath +2 more

arXiv:1911.07357Electronic colloquium on computational complexityNov 17, 20190 citations

A Sample of Samplers - A Computational Perspective on Sampling (survey).

Oded Goldreich

Electronic colloquium on computational complexityJan 1, 199777 citations

Estimating Euclidean Distance to Linearity

Bogdanov, Andrej, Taschin, Lorenzo

Leibniz international proceedings in informaticsJan 1, 20250 citations

The query complexity of sampling from strongly log-concave distributions in one dimension

Sinho Chewi, Patrik Gerber, Chen Lü +2 more

arXiv:2105.14163May 29, 20212 citations

Quantum Algorithms for Testing Properties of Distributions

Sergey B. Bravyi, Aram W. Harrow, Avinatan Hassidim

arXiv:0907.3920IEEE Transactions on Information TheoryMay 25, 201144 citations

Near-Optimal Parallel Approximate Counting via Sampling

David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2 more

arXiv:2604.01263Apr 1, 20260 citations

arXiv:2308.04264

Distance Estimation for High-Dimensional Discrete Distributions

Gunjan Kumar, Kuldeep S. Meel, Yash Pote

Published Aug 8, 2023• 0 citations

arXiv HTML PDF

Abstract

Given two distributions

\mathcal{P}

and

\mathcal{Q}

over a high-dimensional domain

\{0,1\}^n

, and a parameter

\varepsilon

, the goal of distance estimation is to determine the statistical distance between

\mathcal{P}

and

\mathcal{Q}

, up to an additive tolerance

\pm \varepsilon

. Since exponential lower bounds (in

n

) are known for the problem in the standard sampling model, research has focused on richer query models where one can draw conditional samples. This paper presents the first polynomial query distance estimator in the conditional sampling model (

\mathsf{COND}

). We base our algorithm on the relatively weaker \textit{subcube conditional} sampling (

\mathsf{SUBCOND}

) oracle, which draws samples from the distribution conditioned on some of the dimensions.

\mathsf{SUBCOND}

is a promising model for widespread practical use because it captures the natural behavior of discrete samplers. Our algorithm makes

\tilde{\mathcal{O}}(n^3/\varepsilon^5)

queries to

\mathsf{SUBCOND}

DOI: 10.48550/arxiv.2308.04264

Related papers

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

Clément L. Canonne, Chen, Xi, Gautam Kamath +2 more

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$ , which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$ , and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.

arXiv:1911.07357Electronic colloquium on computational complexityNov 17, 20190 citations

A Sample of Samplers - A Computational Perspective on Sampling (survey).

Oded Goldreich

Abstract. We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function f: {0, 1} n P −n → [0, 1], we wish to estimate 2 x∈{0,1} n f(x) upto an additive error of ǫ. We are allowed to employ a randomized algorithm that may err with probability at most δ. We survey known algorithms for this problem and focus on the ideas underlying their construction. In particular, we present an algorithm that makes O(ǫ −2 · log(1/δ)) queries and uses n + O(log(1/ǫ)) + O(log(1/δ)) coin tosses, both complexities being very close to the corresponding lower bounds.Abstract. We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function f: {0, 1} n P −n → [0, 1], we wish to estimate 2 x∈{0,1} n f(x) upto an additive error of ǫ. We are allowed to employ a randomized algorithm that may err with probability at most δ. We survey known algorithms for this problem and focus on the ideas underlying their construction. In particular, we present an algorithm that makes O(ǫ −2 · log(1/δ)) queries and uses n + O(log(1/ǫ)) + O(log(1/δ)) coin tosses, both complexities being very close to the corresponding lower bounds.

Electronic colloquium on computational complexityJan 1, 199777 citations

Estimating Euclidean Distance to Linearity

Bogdanov, Andrej, Taschin, Lorenzo

Given oracle access to a real-valued function on the n-dimensional Boolean cube, how many queries does it take to estimate the squared Euclidean distance to its closest linear function within ε? Our main result is that O(log³(1/ε) ⋅ 1/ε²) queries suffice. Not only is the query complexity independent of n but it is optimal up to the polylogarithmic factor. Our estimator evaluates f on pairs correlated by noise rates chosen to cancel out the low-degree contributions to f while leaving the linear part intact. The query complexity is optimized when the noise rates are multiples of Chebyshev nodes. In contrast, we show that the dependence on n is unavoidable in two closely related settings. For estimation from random samples, Θ(√n/ε + 1/ε²) samples are necessary and sufficient. For agnostically learning a linear approximation with ε mean-square regret under the uniform distribution, Ω(n/√ε) nonadaptively chosen queries are necessary, while O(n/ε) random samples are known to be sufficient (Linial, Mansour, and Nisan). Our upper bounds apply to functions with bounded 4-norm. Our lower bounds apply even to ± 1-valued functions.Given oracle access to a real-valued function on the n-dimensional Boolean cube, how many queries does it take to estimate the squared Euclidean distance to its closest linear function within ε? Our main result is that O(log³(1/ε) ⋅ 1/ε²) queries suffice. Not only is the query complexity independent of n but it is optimal up to the polylogarithmic factor. Our estimator evaluates f on pairs correlated by noise rates chosen to cancel out the low-degree contributions to f while leaving the linear part intact. The query complexity is optimized when the noise rates are multiples of Chebyshev nodes. In contrast, we show that the dependence on n is unavoidable in two closely related settings. For estimation from random samples, Θ(√n/ε + 1/ε²) samples are necessary and sufficient. For agnostically learning a linear approximation with ε mean-square regret under the uniform distribution, Ω(n/√ε) nonadaptively chosen queries are necessary, while O(n/ε) random samples are known to be sufficient (Linial, Mansour, and Nisan). Our upper bounds apply to functions with bounded 4-norm. Our lower bounds apply even to ± 1-valued functions.

Leibniz international proceedings in informaticsJan 1, 20250 citations

The query complexity of sampling from strongly log-concave distributions in one dimension

Sinho Chewi, Patrik Gerber, Chen Lü +2 more

We establish the first tight lower bound of $Ω(\log\logκ)$ on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number $κ$ in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in $κ$ , we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.We establish the first tight lower bound of $Ω(\log\logκ)$ on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number $κ$ in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in $κ$, we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.

arXiv:2105.14163May 29, 20212 citations

Quantum Algorithms for Testing Properties of Distributions

Sergey B. Bravyi, Aram W. Harrow, Avinatan Hassidim

Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).

arXiv:0907.3920IEEE Transactions on Information TheoryMay 25, 201144 citations

Near-Optimal Parallel Approximate Counting via Sampling

David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2 more

The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is achieved via simulated annealing, where the counting problem is formulated in terms of estimating the ratio $Q={Z(β_{\max})}/{Z(β_{\min})}$ between partition functions $Z(β)=\sum_{x\in Ω} \exp(βH(x))$ of Gibbs distributions $μ_β$ over $Ω$ with Hamiltonian $H$ , given access to a sampling oracle that produces samples from $μ_β$ for $β\in [β_{\min}, β_{\max}]$ . The best bound achieved by known annealing algorithms with relative error $\varepsilon$ is $O(q \log h / \varepsilon^2)$ , where $q, h$ are parameters which respectively bound $\ln Q$ and $H$ . However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters $β$ depend on previous samples. We develop a simple non-adaptive algorithm for approximate counting using $O(q \log^2 h / \varepsilon^2)$ samples, as well as an algorithm that achieves $O(q \log h / \varepsilon^2)$ samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms. We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is achieved via simulated annealing, where the counting problem is formulated in terms of estimating the ratio $Q={Z(β_{\max})}/{Z(β_{\min})}$ between partition functions $Z(β)=\sum_{x\in Ω} \exp(βH(x))$ of Gibbs distributions $μ_β$ over $Ω$ with Hamiltonian $H$, given access to a sampling oracle that produces samples from $μ_β$ for $β\in [β_{\min}, β_{\max}]$. The best bound achieved by known annealing algorithms with relative error $\varepsilon$ is $O(q \log h / \varepsilon^2)$, where $q, h$ are parameters which respectively bound $\ln Q$ and $H$. However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters $β$ depend on previous samples. We develop a simple non-adaptive algorithm for approximate counting using $O(q \log^2 h / \varepsilon^2)$ samples, as well as an algorithm that achieves $O(q \log h / \varepsilon^2)$ samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms. We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.

arXiv:2604.01263Apr 1, 20260 citations

Given two distributions

\mathcal{P}

and

\mathcal{Q}

over a high-dimensional domain

\{0,1\}^n

, and a parameter

\varepsilon

, the goal of distance estimation is to determine the statistical distance between

\mathcal{P}

and

\mathcal{Q}

, up to an additive tolerance

\pm \varepsilon

. Since exponential lower bounds (in

n

\mathsf{COND}

). We base our algorithm on the relatively weaker \textit{subcube conditional} sampling (

\mathsf{SUBCOND}

) oracle, which draws samples from the distribution conditioned on some of the dimensions.

\mathsf{SUBCOND}

is a promising model for widespread practical use because it captures the natural behavior of discrete samplers. Our algorithm makes

\tilde{\mathcal{O}}(n^3/\varepsilon^5)

queries to

\mathsf{SUBCOND}

We give a nearly-optimal algorithm for testing uniformity of distributions supported on

\{-1,1\}^n

, which makes

\tilde O (\sqrt{n}/\varepsilon^2)

queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on

\{-1,1\}^n

, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.

We establish the first tight lower bound of

Ω(\log\logκ)

on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number

κ

in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in

κ

, we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.

Q={Z(β_{\max})}/{Z(β_{\min})}

between partition functions

Z(β)=\sum_{x\in Ω} \exp(βH(x))

of Gibbs distributions

μ_β

over

Ω

with Hamiltonian

H

, given access to a sampling oracle that produces samples from

μ_β

for

β\in [β_{\min}, β_{\max}]

. The best bound achieved by known annealing algorithms with relative error

\varepsilon

O(q \log h / \varepsilon^2)

, where

q, h

are parameters which respectively bound

\ln Q

and

H

. However, all known algorithms attaining this near-optimal complexity are inherently sequential, or *adaptive*: the queried parameters

β

depend on previous samples. We develop a simple non-adaptive algorithm for approximate counting using

O(q \log^2 h / \varepsilon^2)

samples, as well as an algorithm that achieves

O(q \log h / \varepsilon^2)

samples with just two rounds of adaptivity, matching the best sample complexity of sequential algorithms. These algorithms naturally give rise to work-efficient parallel (RNC) counting algorithms. We discuss applications to RNC counting algorithms for several classic models, including the anti-ferromagnetic 2-spin, monomer-dimer and ferromagnetic Ising models.