Minimax Lower Bounds for Estimating Distributions on Low-dimensional Spaces
Authors: Saptarshi Chakraborty
Venue: Accepted by TMLR ()

Abstract: Recent statistical analyses of Generative Adversarial Networks (GAN) suggest that the error in estimating the target distribution in terms of the $\beta$-H\"{o}lder Integral Probability Metric (IPM) scales as $\mathcal{O}\left(n^{-\frac{\beta}{\overline{d}_{\mathbb{M}}+\delta}} \vee n^{-1/2} \log n \right)$. Here $\overline{d}_{\mathbb{M}}$ is the upper Minkowski dimension of the corresponding support $\mathbb{M}$ of the data distribution and $\delta$ is a positive constant. It is, however, unknown as to whether this rate is minimax optimal, i.e. whether there are estimators that achieve a better test-error rate. This paper demonstrates that the minimax rate for estimating unknown distributions in the $\beta$-H\"{o}lder IPM  on $\mathbb{M}$ scales as $\Omega\left(n^{-\frac{\beta}{\underline{d}_{\mathbb{M}}-\delta}} \vee n^{-1/2}\right)$, where $\underline{d}_{\mathbb{M}}$ is the lower Minkowski dimension of $\mathbb{M}$. Thus if the low-dimensional structure $\mathbb{M}$ is regular in the Minkowski sense, i.e. $\overline{d}_{\mathbb{M}} = \underline{d}_{\mathbb{M}}$, GANs are roughly minimax optimal in estimating distributions on $\mathbb{M}$. Further, the paper shows that the minimax estimation rate in the $p$-Wasserstein metric scales as $\Omega\left(n^{-\frac{1}{\underline{d}_{\mathbb{M}}-\delta}} \vee n^{-1/(2p)}\right)$.

Published in Transactions on Machine Learning Research (02/2025)
Minimax Lower Bounds for Estimating Distributions on Low- dimensional Spaces
Saptarshi Chakraborty
soptarshicc@ieekkeee...d
Department of Statistics
University of California, Berkeley
Reviewed on OpenReview: https: openreview. net/ forun? gdV3Ig0
Abstract
Recent statistical analyses of Generative Adversarial Networks (GAN) suggest that the error in estimating the target distribution in terms of the B-Hölder Integral Probability Metric (IPM) scales as O iss V -n log1//logn) Here di is the upper Minkowski dimension of
the corresponding support M of the data distribution and a positive constant. It is, how- ever, unknown as to whether this rate is minimax optimal, i.c. whether there are estimators that achieve a better test-error rate. This paper demonstrates that the minimax rate for
estimating unknown distributions in the 3-Hölder IPM on M scales as S2 th vn
where du is the lower Minkowski dimension of M. Thus if the low-dimensional structure M is regular in the Minkowski sense, i.e. dm das GANs are roughly minimax optimal in estimating distributions M.. Further, the paper shows that the minimax estimation rate in the p- Wasserstein metric scales as Ω the vn-1/(2p))
Nouparametric density estimation, aimed at approximating probability distribution from a finite collection of identically and independently distributed (i.i.d)) samples, holds extensive application in the realms of statistics and machine learning. Nonparametrie density estimation finds application in various fields such
as mode estimation (Parzen 1962). nonparametric classificatinn (Rigollet) 2007 Chaudhuri et al. 2008
Monte Carlo computational methods (Doucet et al.) 2001),, and clustering (Chaudhuri & Dasgupta, 2010
Chakraborty et al. 2021 Rinaldo & Wassorman (0100), among others. Typical techniques for nonparametric
density estimation encompass the histogram method, kernel methods, k-nearest Neighbors (kNN) (Devroye
& Wagner 1996) and more. Notably, the recent ad advancements in deep learning have led to the groundbreaking concept of Generative Adversarial Networks (GANs) (Goodfellow et al. 2014 which has revolutionised the field of nonparametric density estimation to obtain superhuman performance, especially for handling vision data.
1977: Bhattacharya Mack 1987 Zhao & Lai (002)), wavelet-based methods (Donoho et al.
The empirical successes of GANs have motivated researchers to study their theoretical guarantees. Biau et al. 22000) analyzed the asymptotic properties of vanilla GANs along with parametric rates, Biau et al. (2021) also analyzed the asymptotic properties of WGANs. Liang (2021) explored the min-max rates for WGANs for different non-parametric density classes and under sampling scheme from a kernel density estimate of
the data distribution; while Schreuder et al. (2021) studied the finite-sample rates under adversarial noise.
Uppal et al. (2019) derived the convergence rates for Besov discriminator classes for WGANs. Luise et al.
(2020) conducted theoretical analysis of WGANs under an optimal transport-based paradigm. Recently, Asatryan et al. (2023) and Belooessty et al. (2021) improved upon the works of Biau et al. (2020) to understand the behaviour of GANs for Hölder class of density functions. Arora et al. (2017) showed that gencralisation might not hold in standard metrics. However, they show that under a restricted "neural-nct Arrnat
distance", the GAN is indeed guaranteed to generalize well. Recently, Arora et al. 20188) showed that GANs and their variants might not be well-equipped against mode collapse.

---

Published in Transactions on Machine Learning Research (02/2025)
Although significant progress has been made in our theoretical understanding of GAN, some limitations of the existing results are yet to be addressed. For instance, the generalisation bounds frequently suffer from the curse of dimensionality. In practical applications, data distributions tend to have high dimensionality, making the convergence rates that have been proven excoedingly slow. However, high-dimensional data, such as images, texts, and natural languages, often possess latent low-dimensionall structures that reduce the complexity of the problem. For example, is hypothesised that natural images lie on a low-dimensional structure, in spite of its high-dimensional pixel-wise representation (Pope et al., 2020). Though in classical statistics there have been various approaches, especially using kernel tricks and Gaussian process regression that achieve fast. rate of convergence that depends only on their low intrinsic dimensionality (Bickel &
Li 2007; Kim et al. 2019), such results are largely unexplored in the context of GANs. Recently, Huang et al. (2022) expressed the generalisation rates for GAN when the data has low-dimensional support in the Minkowski sense and the latent space is one- one-dimesii:nal: while Dahal et al. (2022) derived the convergence rates under the Wasscrstein-1 distance in terms of the manifold dimension. It is important to note that the compact Riemannian manifold assumption of the support of the larget distribution and the assumption of a bounded density of the target distribution this manifold by Dahal et al. (2022) is a very strong assumption that might not hold in practice.
Despite these recent advances, it remains uncertain whether GAN estimates of the target distribution are optimal in the minimax sense for estimating distributions that are supported on a low-dimensional structure. The proposed analysis addresses this gap in the current literature by providing a comprehensive analysis of the minimax lower bound for estimating low-dimensional distributions and demonstrate that when n i.i.d. samples are available from any target distribution on set M, the convergence rate for any estimator
(in the 3-Hölder IPM) is at lcast ?? n de- vn-1/2 where 5 is a positive constant in the range of (0,
dæ)), and dx is the lower Minkowski dimension of the set M. Thus, when the set M is Minkowski regular, GANs almost match this rate, when the networks are properly chosen. In particular, Huang et al. (2022) showed that when the generator and discriminators are realized by a feod-forward neural network with RcLU activation, with respective depths Lgen; Lais and widths W geo: Wais; then one can choose W Log Z n and
W Waig 23 nz ((D(22du+2)) log" n (D denotes the dimension of the data space) to ensure that the error rate for
the GAN estimate of the distribution scales as ((n-9((hc+))) V Vn-1/2 n). In this case, the discriminator network has to satisfy regularity condition in terms of its maximum Lipschitz constant. I refer the reader to Theorem 19 of Huang et al. (2022) for more details. Additionally, this work demonstrates that the minimax estimation rate in the p- Wasserstein metric decreases in proportion to Ω nn" - V n-n1//00 -1((22)).
1
Background
1.1
Related Work
Recent research has explored the minimax rates under the Wasserstein distances under various settings, Singh& & Póczos (2018) demonstrated the minimax convergence rates assuming the distribution is compactly supported. In related context, Liang (002)) and Uppal et al. (209 established minimax convergence rates for the Wasserstein-1 distance under a smoothness assumption on the corresponding density. It has been demonstrated that estimating under the Integral Probability Metric (IPM) with smooth functions can lead to enhanced rates of convergence for empirical measures Kloeckner 2020 Niles- Weed & Berthet (2022) established the minimax convergence rates for Besov densities for the Wasserstein-p metric. For smooth densities, the derived minimax rates can be improved (MeDonald. 2017 Liang 2021) in the sense that es- timating a smooth density is easier than estimating non-smooth one. However, all the aforementioned findings primarily consider the minimax rates when the corresponding distribution varies across all proba- bility measures on a compact set, resulting in rates of O(n1//D or similar for estimating distributions of D.. Recently, TTng & Yangl (2023) derived the minimax rates when the data is supported on a smooth sub-manifold with a positively bounded reach, and has a smooth density w.r.t. the volume measure on this manifold. In contrast to the work of Tang & Yangl (2023), this analysis does not impose a smooth manifold structure on the data support, allowing for highly non-smooth and irregular geometries. Moreover, this work does not assume the existence of density for the distribution on this potentially irregular low-dimensional
2

---

Published in Transactions on Machine Learning Research (02/2025)
Table 1: comparison of different upper and lower bounds for distribution estimation on the D-dimensional unit hypercube (D 2 3). The upper bounds do not show possible poly-log factors in n.
Result
Assumption Distri-
Assumption Density
Result Type
Metric
Bound
bution Support
Liang
2021
None
a- a-Hölder
Upper and Tower
B-Hölder IPM
n
Zu D
Vn
1/2 Vn-
Bound
Niles- Weed
None
8- Besov
Upper and Bound
Wasserstein
Das V n2 n1
11/20
Berthet
Lower
2002
Huang et al.
Minkowski dimension
None
Upper Bound
B-Hölder IPM
11 B/(d+))
n 1/2
2022]
d
Tang & Yang
d-dimensional
-- o-Hölder and lower
Upper and
B-Hölder IPM
20-d
20+7
2023
smooth (y >
2)
Lower
n 1/2
sub-manifold with bounded lower-bounded reach
Bound
B H-Hölder IPM
B/(d-5) V n 1/2
This work
Minkowski dimension d None
Lower Bound
Wasserstein
1/(0-31Vi 1/(2p)
support, enabling to accommodate singular distributions this structure within the proposed framework. While both this work and the one by Tang & Yangl (2023) leverage the principles of minimax error bounds via Fano's method, their reliance on smooth manifolds and the existence of smooth densities simplifies the corresponding testing problem for rate derivation. In contrast, the proposed approach circumvents these assumptions by constructing point measures on the low-dimensional structure, enabling more general anal- ysis under minimal assumptions. Further, while Tang Yang (2023) derive the minimax error bounds for 3-Hölder IPMs, the proposed analyses also cover Wasserstein p-distances. Table 1 provides comparison of error rates from several prominent works in the literature, contextualizing the findings of this paper within the broader scope of existing research.
In addition to the mathematical results (Huang et al., 2022) that the error rates for GANs depend on the intrinsic data dimension, empirical results also indicate such phenomena occur in practice. For example, the recent works by (Chakraborty Bartletl (2024a) show that the lest error rales the Wasserstein-1 distance for Wasserstein Autoencoders (Tolstikhin et al. 2018) depend only on the Minkowski dimension of the data support. Similar results have also been established both theoretically and empirically for deep regression (Nakada & Imaizuni 2020 and federated learning models (Chakraborty & Bartlell, 2024b).
1.2 Preliminaries and Notations
Before going into the details of the theoretical results, let us introduce some notation and recall some preliminary concepts.
We will use the notation rVy == max(x, Bo(x,r) denotes the open ball of radius r around æ, with respect
to (w.r.t.) the metric o. For any measure 7, the support of is defined as, supp(>) = (a 7 (B)(zr)) > O, for all r> > 0}. For any function f S - R, and any measure y on S, let [Ifll,,,,,) := (Js (((r)) 1/2 if 0 < p < 00. Also let, [If (n) == css supassupp(s) [f()) We say An 3 B, (also written as A. O(B.) + Bn ((A,)) there exists C > O, independent n, such that An CCB, We say A. x Bn, if An 3 Bn and B,, - A,, For any N, we let [k] {l....,k} kk.. 1(-) denotes the indicator function. For any measure p. 8n denotes the n-product measure of p. Let us also recall some useful definitions as follows.
Definition 1 (Covering and Packing Numbers). For a metric space (S. the e-covering number w.r.t. & is defined as: Nic, S. = inf(n n N 3æ1....2; Fy such that U Bz(2,,)) c) 2 S}. Similarly, the e-packing number is defined as: M(e Ø) sup(m N: -xi.... S such that e( xr)) e, for all + $
3

---

Published in Transactions on Machine Learning Research (02/2025)
Definition 2 (Hölder functions). Let f S - R be function, where S S RD.. For multi-index al
(8)) let, f da D p. denote the weak partial derivative of f, where, | ΣE= sg. A function f: + R is said to be 3-Hölder (for 3 > 0) if
1000 (xx) 8" s(v]] 8 [8] < CC.
1 =
Σ
1000 flloo +
Σ sup #øy
|
11
s:10
If f: : + RR", then define II = -ド
D' [1lll For notational simplicity, let, (S S2. C) = {
S S2 : C). Here, both S₁ and S2 subsets of real vector spaces. If Si [0, 1] S2 and C= we write H in stead of (S,, C).
Next, let us recall the definitions of Total Variation and Wasserstein-p distances as well as Integral Probability Metrics (IPMs).
Definition (Total Variation Distance). Let Ω be a Polish space and suppose that μ and are two probability measures defined on S2. Then, the total variation distance between μ and defined as,
(V sup In(B) rBB] inf (X >ET(u,))
(E
Here, (S2) denotes the Borel o-algebra on Ω and r(u, v) denotes the of all measure couples between μ and The reader is referred to Proposition 4.7 of Levin & Peres (017 ) for proof of the second equality in 1
Definition 4 (Wasserstein p-ditaance). Let (9t, dist) be a Polish space and let and v be two probability measures on the same with finite p-moments. Then the p- Wasserstein distance between f and v is defined 88:
Wp(m,v) = ((_inf inf F(x,y (ddist(;,, f))) (vET().))
1/P
In what follows, dist(-,-) is taken to be the fg-norm on RD. Definition 5 (Integral Probability Metric). For a function class F, the F-Integral Probability Metric (IPM) between two probabiloty measures μ and defined as,
/ Idu sdu-f sdu
|1 - =||== = sup
FEF
1.3 Minkowski Dimension
Often, real data is hypothesized to lie on a lower-dinensional structure within the high-dimensional repre- sentative feature space. To characterize this oww-dimesionnality of the data, researchers have defined various notions of the effective dimension of the underlying mcasure from which the data is assumed to be generated. Among these approaches, the most popular ones use some sort of rate of increase of the covering number, in the log-scale, of most of the support of this data distríbution. Let (S, be compact Polish space and let be a probability measure defined on it. Throughout the remainder of the paper, e is taken to be the foe-norm The low-dimensional nature of the data distribution is characterised by the Minkowski dimension of the support of μ.. Let us recall the definition of Minkowski dimensions (Falconer) 2004).
Definition 6 (Minkowski dimension). For a bounded metric space (S, e), the upper Minkwoski dimension of S is defined as
LogN((: S)
ds limsup c_0
log(1/e)
Similorly, the lower Minkowski dimension of S given by.
logN(e;; S, Ø)
ds lim inf cJ0
log(1/e)
If ds = ds, say that S is Minkowski regular and has Minkowski dimension of ds limejo log[1/e)
Wie: S.
4

---

Published in Transactions on Machine Learning Research (02/2025)
The Minkowski dimension essentially measures how the covering number of S is affected by the radius of the covering balls. Since this notion of dimensionality depends only the covering numbers and does not assume the existence of a smooth correspondence to a smaller dimensional Euclidean space, this notion not only incorporates smooth manifolds but also covers highly non-smooth sets such as fractals. In the literature, Kolmogorov & Tikhomirov (1961) provided comprehensive study on the dependence of the covering number of different function classes on the underlying Minkowski dimension of the support. Nakada & Imaizumi (2020) showed how deep learners can incorporate this low-dimensionality of the data that is also reflected in their convergence rates. Recently, Huang et al. (2022) showed that WGANs can also adapt to this low- dimensionality of the data. In particular they showed that when the data is independent and identically distributed from a distribution μ1, for the GAN estimate for the density (denoted as pCAN), ll - i JGANNI ||
decays at a rate of In the following section, attempt to understand whether this rate is optimal or not.
71 The Vn 1/2 log where M is the support of μ and 6 > a pre- fixed constant.
2 Theoretical Analysis
Suppose that M C [o, 1j2t and let 1h denote the set all probability distributions on M. Let us assume that one has access to n samples, X,,..., Xn. generated independently from μ e Is.. The goal is to understand how well any estimate of μ,, based the data, performs. This performance is charecterised in terms of the B-Hölder IPM or the p- p-Wasserstein distance, iee. for estimate á, its performance is measured - or ( p). To characterise this nolion of best-performing estimator, researchers use the concept of minimax risk Le. the risk of the best-performing estimator that achieves the minimum risk with respect to all members in ly. Formally, the minimax risk for the problem is given by,
nn, = inf sup Eyllă elles or Mr = inf sup E, W (P,, P. wEllæ
A нεlla
where the infimum is taken over all mcasurable estimates of μ. i.c. on fp : (XI...., X,,) + Ho..j f is measurable). Here, Ey, is used to denole that the expectation is taken with respect to the joint distri- bution of Xi...., Xn, which are independently and identically distributed μ. Theorem 7 states the main lower bound of this paper, which lower bounds N,, in terms of the (ower-Minkowsk. dimension of M and the number of samples when is large. The proof of this result is given in Section
3
Theorem 7 (Main Result). Suppose that XI...., Xn are i.i.d. and let 8 E (0, (0,da)) Then there crists
E N such that if n 2 no,
inf sup Epli mllas 2 n 2x V n n11 Helly where the infirmmm is taken over all measurable estimates of n. based the data, XI,..., Xn. Furthermore,
(2)
inf sup E, W. p)) 2 2 Vn 20
(3)
A pellx
If M is Minkowski regular, from Theorem note that for any 5 E (0, das).
inf sup Epliã Mlleas 2 n --- V 1/2
wells
GANs can achiove a rate of convergence of O n पे Vn-1/21ogm) implying that GANs are almost optimal in learning distributions when the data is low-dimensional in the Minkowski sense, barring poly-log factors in the sample size.
From the results dcrived by Huang et al. 2022
It is important to note that the lower bound in (3) closely resembles the ones derived by Niles- Weed & Berthet (2022) for distributions with Besov densities. Furthermore, from Theorem 1 of Weed & Bach (2019), note that the empirical distribution inn scales as IEW p)) A n -1/(((((+)) where d)(4) denotes the p-upper Wasserstein dimension of p. Since y supported on M, by Proposition 2 of Weed & Bach 2019). (n( S des.
5

---

Published in Transactions on Machine Learning Research (02/2025)
when dM 2 2p. Thus, EWp(Rn 11) 3 1///(+++)) Hence, when dx > 2p. we choose 5 > 0, such that, inf, suppel> F,, W (P (4) 2 n - Hence, in this case, the empirical distribution almost achieves this minimax optimal rate when dxc > 2p and M is Minkowski regular.
Remark 1 (ô-term in Theorem 7 We observe that the 8-term is an artefact of the definition of the Minkowski dimension. If (c, fxc c for some d E (0, D), i.c. when the limit in the computation of the lower Minkowski dimension can be achieved exactly, following the proof of Theorem 7 (see Section 3 note that under the same assumptions M, ž n n- V n n-1/2 for n large. The 8-term in the lower bound is only an artefact of the definition of the lower Minkowski dimension and can be removed by assuming the lower bound for the covering number. Further, if one assumes that (,,, 3 e e- then the analyses by Huang et al. (2022) shows that the error rate for GANs for estimating a distribution μ4, supported on M scales as (n-P/d V 1/2) log n (see Theorem 19 of Huang et al. (2022)) Thus, when (ee,, MI, (x0) x e e-d, the error rates for GANs match the minimax rate except for an excess oog-factr in the number of samples.
Inference for distributions supported on a Manifold When the support is regular, one can say that the minimax rate for estimating distributions decays at rate whose exponent is inversely proportional to its regularity dimension. We recall that a set M is d-regular w.r.t. the d-dimensional Hausdorff measure yd if
(B, x r")
for all x E M (see Definition 6 of Weed & Bach 2019 defined as,
Recall that the d-Hausdorff measure of set S is
Ht (S) = lim inf
1 : Σ Belaxare), S. Vk Vk)
<10
It is known (Mattila 1999) that if M is d-regular, then der d. Thus, when M is d-regular, the minimax rate roughly scales at [ 372). Since, compact d-dimensional differentiable manifolds are d-regular (Weed & Bach 2019 Proposition 9), this implies that for when M is a compact differentiable d-dimensional manifold, the error rates scale as 2(n -A/a). This result underscores that GANs are nearly minimax optimal, given that the corresponding upper bounds derived by Dahal et al. (2022) match this minimax rate, albeit under some additional assumptions regarding the smoothness of the manifold. A similar result holds when M is nonempty, compact convex set spanned by an affine space of dimension d; the relative boundary of a nonemply, compact convex set of dimension d + 1; a self-similar set with similarity dimension d as all these sets are d-regular by (Weed & Bach 2019
Proposition 9).
3 Proof of the Main Result (Theorem 7
As a first step for deriving a minimax bound, let first show that the Hölder IPM can be lower bounded by the total variation distance and the minimum separation of the support of the distributions. For any finite set, we use the notation, sep(E)= = infg,e'==:;ft" ||s -'llloe-
Lemma 8. Let E be a finite subset of Re and let, P.Q E IIs. Then, there exists a constant 11 (that might depend on B) such that, ||P Qllaa("P 2 (s) QQl
1 1| < 1} be the standard bump function on R. For any x E R² and Proof. Let b(x) = exp ---1
E E 1), let, ho(x)= a 1 b2z Here a is such that ab(x) E HD (R, R, C). It casy to observe that h& E H 1). Let P and Q be two distributions on = = (EI...., Let 5 = 1/ mingzy [ls, - E, loc. Define (x) D (x) with a E (1), to be chosen later. Since the individual terms h are members of H (RR, TR, 1) and have disjoint supports, h* H R, 1). Taking a, 21 (P(E) 2 Q(E)) 1, it is easy to see that,
R |P Q (Ia 2 hrap- - htdQ - Σ
a oz a5%.. (P(E)) Q(Ei)) =a5
P((s) Q(5i)
1=1
=2a08 -QIITv
6

---

Published in Transactions on Machine Learning Research (02/2025)
2a 3 (sep (sep(E))
QliTv.
Taking æ1 3
2a gives us the desired result.
Similar Lemma on discrete space, the p- p-Wasscrstcin metric is lower bounded by the total variation distance.
Lemma 9. Let =\t be finile subsel of Rd and let, P.Q TTg. Then, W (P(,QQ) 2 -
Proof. Let X and Y ~ Q. Note that || 1 2 { # Y) sE) Thus,
( X - Y 11) 1/2 (P + x)) 1/2 sep(E..
Taking infimum w.r.t. all measure couples between P and Q gives us the desired result.
With the above two lemmas at our disposal, that if P < Q, the KT-divergence between P and Q is given by, KL(PIIQ) log(dP//dQ)PP. Similarly, the diveeeegee is given by, (P(l() [ (dPP/dQ)² -I. 1.
ready to prove the main result of this paper. Recall
3.1 Proof of Theorem
With Lemmata 8 and we are now ready to prove Theorem 7
We use Fano's method obtain the minimax
lower bound. I refer the reader Chapter 15 Wainwrihtt 2019) for detailed exposition. Let, dx 6. Míc, M, fxc 2 c Take
find cu E (0. 1), such that if (0, co (c, Thus, (128(co)=*) 8192. Suppose (m/128)-1/s, Let θ = (01,... 02 be e-separated set in M. For 2 No
2 c
the above choices of n and observe that one can take, h = E = =n/128 2 64 and n 2 64k.
Let ()(x)= 1/2 = },} - 1f2 U1/2]+sh for all = 1, 1..... [k/2]. Let, w E (0.1) [4/2]_ Define the probability mass function on O,
8% [k/2]
(w(x)
1
Σ wgdz(x),
j=l
with 6 E (0, 1/2]. By construction, Pw E 1lM.
Furthermore,
6x || - w'll1.
Pw Pw = k
By the Varshamov-Gilbert bound Tsybakov 2009, Lemma 2.9), let Ω S {0, (3.1/1 be such that | 2 18/2] and ||ا w'lli Lk/2], for all o w both in Ω. Thus for any + w', both in Ω
8& [k/2]
Pw Purllrv 2
(4)
8k
Hence, by Lemma
|| Pwr Pa 2 m 18/221
Similarly, by Lemma is easy to note that
Wp(Pw. Pw.) 2 86 [k/2]] Furthermore, obscrve that
# (Pa Pw
(L.P@~1P@@ = KL(P s (P =
<2nk Σ (Pw - - Pw)
PE)
1=1
<2nk (ookk(///100 (k/2]
12 n2k/2262

---

Published in Transactions on Machine Learning Research (02/2025)
Thus,
E K < n2/k/2662
12
k
WOEER
Let = {Pu : w W RJ. Let J ~ (2i and ZJ w ~ Pw. By the convexity of KL divergence (see
equation 15.34 of Wainwright (2019). , it is known that,
KL (PP 88" n
I(Z:J)
Σ
122
k
W.w' En
Thus,
I(Z + logg
log [92] < [[ + log
no
8
no
S 64
+
S
64
#
+
(5)
[k/2] log?
log 2
[k/2]
k
log 2
4'
The last inequality follows since h: 2 64. Take 6x = 16 makes,
k log
Clearly, S 1/2 as 2 64k. This choice of
T(2; J) + log 2
- 2
log [22]
Thus, by Theorem 15.12 of Wainwright (2019) (taking ((x) and p(P,Q) - 1|P Q[
6x [k/]
|k/2|
k log
T |k/2] 1
log 2
inf sup Enlla - ullmo 2 aie" pellx
11e
k 16 V
k
k
16
n
128
2 T2C
n -3/s 3/s
(6)
6k kk/k//2
1/p
Similarly,
inf sup E2, W, (2. 1) 2 # wells
x n 1/8
(7)
To show that inf su ll - Allx 2 n n-1 1/2 one can use Le Cam's method /Wainwrihtt 2019 Chapter
15.2). Let Oo 0 E M. be such that |10 - 02 lloe 2 diam(M))/2 Let Po(O)) = P) = 1/2 and P1 (0%) =
1- ((,)) = 1/2 with 8 E (0,1/4) Clearly TV(P. P1) = Thus, by Lemma observe that
|| Poll 2 (diam(M)/2)882
Similarly, (P 2 (diam(M)/2)0 2 8//P Again,
KT |P KL Snx (PPPPP) 4n82.
By Pinsker's inequality
Tsybakov
2009
Lemma 2.5), note that,
TV(PS" poa) (L 28 1/4,
if 1. Thus from equation 15.14 of Wainwright (009)) observe that, 8/5
inf sup E. Allas 2 8x 1/vn. pella
(8)
Similarly,
inf sup Ep (p, 2 81/8 - + welly
(9)
The result now follows from combining and from combining 7 and
The minimax rate for the Wasserstein distance follows
8

---

Published in Transactions on Machine Learning Research (02/2025)
4 Conclusion
This paper aimed to study the fundamental question of whether GANs are optimal in providing accurate estimates of target distributions, especially when the data exhibit a low-dimensional structure. This notion of low dimensionality is characterised by the so-called Minkowski dimension. In scenarios where n independent and identically distributed samples are available from a target distribution on set M,, the convergence rate - (n- Vn vn=*) in the
for any estimator is bounded by Q n 5M- V Vn=1//
in the 3-Hölder IPM and 52 (n
Wasserstein p- p-metric. When the support is regular in the Minkowski sense, the convergence rates for GANs closely resemble this lower bound (in the 3-Hölder IPM), when the networks are properly chosen. Some future results in this direction might render fruitful avenues for understanding similar lower bounds, especially with different notion of the dimensionality of the data distribution, such the Wasserstein dimension (Weed & Bach 2019). Further, while GANs are known achieve optimal rates in the Wasserstein- distance, it remains an open question whether this result extends to Wasscrstein-p distances for p 2 2.
Acknowledgement
would sincerely like to thank Prof. Peter L. Bartlett for his invaluable insights, thoughtful discussions and constant guidance. The author also gratefully acknowledges the support of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS- 2031883 and #814639, the NSF's support of FODSI through grant DMS-2023505, and the support of the ONR through MURI award N000142112431.
References
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang, Generalization and equilibrium in generative adversarial nets (gans). In International Conference on Machine Learning, pp. 224-232. PMI.R 2017.
Sanjeev Arora, Andrej Risteski, and Yi Zhang. Do GANs learn the distribution? some theory and empirics. In International Conference on Learning Representations, 2018. URL htcta:://penrrviieeeeet//eeeeeee id BJehNfwO-
Hayk Asatryan, Hanno Gottschalk, Marieke Lippert, and Matthias Rottmann. convenient infinite dimen- sional framework for gencrative adversarial learning. Electronic Journal of Statistics, 17(1):391 - 428,
2023. doi: FJJ1214/ URL /tttp:://oii.orrttt htt////i...g//.1011/1//1 0rt//10.1214/22-JJ52144
Denis Belomestny, Eric Moulines, Alexey Naumov, Nikita Puchkin, and Sergey Samsonov. Rates of conver- gence for density estimation with gans. arXiv preprinl arXiv:2102.001 2021.
P K Bhattacharya and Y P Mack. Weak convergence k-nn density and regression estimators with varying k and applications. Annals of Stalistics, 15(3):976 994, 1987.
Gérard Biau, Benoît Cadre, Maxime Sangnier, and Ugo Tanielian. Some theoretical properties of gans. The Annals of Statistics, (8(3):1539-153)) 2020.
Gérard Biau, Maxime Sangnier, and Ugo Tanielian. Some theoretical insights into wasserstein gans. Journal of Machine Learning Research, 22(1):5287-5333) 2021.
Peter Bickel and Bo Li. Local polynomial regression on unknown manifolds. Lecture Notes- Monnoraphh Series, pp. 177-186, 2007.
Saptarshi Chakraborty and Peter Bartlett. A statistical analysis of wasserstein autoencoders for intrinsically low-dimensional data. In The Twelfth International Conference on Learning Representations, 2024a. URL htttps///ppeneerise..ntfffooorre tettf
Saptarshi Chakraborty and Peter L. Bartlett. A statistical analysis of deep federated lcarning for intrinsically low-dimensional data, 2024b. URL httpss:/arrze wwwp:/or.//.....et..... ab/p////./220..5

---

Published in Transactions on Machine Learning Research (02/2025)
Saptarshi Chakraborty, Debolina Paul, and Swagatam Das. Automated clustering of high-dimensional data with a feature weighted mean shift algorithm. In Proceedings of the AAAT Conference on Arlificial Intel- ligence, volume 35, pp. 6930 6938, 2021.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for the cluster tree. Advances in neural information processing systems, 23, 2010.
Probal Chaudhuri, Anil K Ghosh, and Hannu Oja. Classification based on hybridization of parametric and nonparametric classifiers. IEEE transactions on pottern analysis and machine intelligence, 31((): 1153-1164, 2008.
Biraj Dahal, Alexander Havrilla, Minshuo Chen, Tuo Zhao, and Wenjing Liao. On deep generative models for approximation and estimation of distributions on manifolds. Advances in Neural Information Processing Systems, 35:10615 106288, 2022.
Luc P Devroye and Terry Wagner. The strong uniform consistency of nearest neighbor density estimates.
The Annals of Statistics, pp. 536-540, 1977.
David Donoho, Iain M Johnstone, Gérard Kerkyacharian, and Dominique Picard. Density estimation by wavelet thresholding. The Anmals of statistics, pp. 508 0889, 1996.
Arnaud Doucet, Nando De Freitas, and Neil Gordon. An introduction to sequential monte carlo methods. Sequential Monte Carlo methods in practice, pp. 3-14, 2001.
Kenneth Falconer. Fractal geomelry: mathemalical foundalions and uppliculions. John Wiley & Sons, 2004.
Ian Goodfellow, Jean Touget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farles Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Nets. In Adoances in Newral Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Jian Huang, Yuling Jiao, Zhen Li, Shiao Liu, Yang Wang, and Yunfei Yang. An error analysis generative adversarial networks for learning distributions. Journal of Machine Learning Research, 23(116): 2022. URL http:// httpa/rrrr/ppppps////111-7-- html
Jisu Kim, Jachyeok Shin, Alessandro Rinaldo, and Larry Wasserman. Uniform convergence rate of the kernel density estimator adaptive to intrinsic volume dimension. In International Conference Machine Learning, pp. 3398-3407. PMLR, 2019.
Benoît R Kloeckner. Fapirrcaal measures: regularity is a counter-curse to dimensionality. ESA IM: Probability and Statistics, 24:408-43: 434, 2020.
Andrey Kolmogorov and Vladimir Mikhaulovich Tikhomirov. e-entropy and e-capacity of sets in function spaces. Translations of the American Mathematical Society, 17:277-364, 1961.
David A Levin and Yuval Peres. Markov chains and miring times, volume 107. American Mathematical Society, 2017.
Tengyuan Liang. How well generative adversarial networks learn distributions. Journal of Machine Learning Research, 22(11:0336610446 2021.
Giulia Luise, Massimiliano Pontil, and Carlo Ciliberto. Generalization properties of optimal transport gans with latent distribution learning. arXiv preprint 1rX1 2020.
Pertti Mattila. Geometry of sets and measures in Euclidean spaces: fractals and rectifiability. Number 44. Cambridge University Press, 1999.
Daniel McDonald, Minimax density estimation for growing dimension. In Artifficial Intelligence and Statistics, pp. 194-203. PMI.R, 2017.
10

---

Published in Transactions on Machine Learning Research (02/2025)
Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and generalization of deep neural network
with intrinsic dimensionality. Journal of Machine Learning Research, (1(14)):1-38, 2020. URL http:
//jmlt.org/papeeeeeee. ort.paapers//22/220002. html
Jonathan Niles-Weed Weed and Quentin Berthet. Minimax estimation of smooth densities in Wasserstein distance.
The Annals of Statistics, 50(3):1519 1540, 2022. doi: 10.1214/21-A022161. URL https://doi.org:
10. 1211421111111116
Emanuel Parzen. On estimation of a probability density function and mode. The annals of mathematical slalislics, 33(3):1065-1013 1076, 1962.
Phil Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension images and its impact on learning. In International Conference on Learning Representations, 2020.
Philippe Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(7), 2007.
Alessandro Rinaldo and Larry Wasserman. Generalized density clustering. Annals of Statistics, 38(5):
2678-2722 2010.
Nicolas Schreuder, models without domination. Algorithmic Learning Theory, pp. 1051 1071. PMLR, 2021.
Brunel, and Arnak Dalalyan. Statistical guarantees for generative
Shashank Singh and Barnahás Póczos. Minimax distribution cstimation in wasserstein distance. arXiv preprinl ar Xi0: 08855, 2018.
Rong Tang and Yun Yang. Minimax rate of distribution estimation unknown submanifolds under adver- sarial losses. The Annals of Statistics, 51(():1282211)) 1308, 2023.
Πlya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf. Wasserstein aulo-encoders. International Conference on Learning Representations, 2018.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, Springer New York, NY, edition, 2009. ISBN 978-0-387-79051-0, doi: 10.1007/b13794 URL https: 7/doi
Published: 26 November 2008.
Ananya Uppal, Shashank Singh, and Barnabás Póczos.
Nonparametric density estimation & convergence rates for gans under besov ipm losses. Advances in neural information processing systems, 32, 2019.
Martin J Wainwright. Higgh-dmenssoonll statistics: A Non-asymplotic Viewpoint, volume 48. Cambridge University Press, 2019.
Jonathan Weed and Francis Bach. Sharp Asymptotic and Finite-Sample Rates of Convergence of Empirical Measures Wasserstein Distance. Bernoulli, (5(4A):2620 2648, 2019. doi:
URL
Puning Zhao and Lifeng Lai. Analysis of knn density estimation. JEEE Transactions on Information Theory, 68(12):7971 7995, 2022.
11


Reviews:
[{"review_id": "ugV97U9Zgb", "reviewer": "Reviewer_Ptbn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The paper gives the minimax lower bound of GAN in terms of low dimension structure. The paper is well-written and is easy to follow\n\nWeakness: \n\n1. The contribution seems to be incremental, especially compared with Tang, Rong, and Yun Yang. \"Minimax rate of distribution estimation on unknown submanifolds under adversarial losses.\" The Annals of Statistics 51.3 (2023): 1282-1308. It will be better if the author could point out the technical challenges to increase the contribution. \n\n2. The comparison with the literature is weak. Some tables which could contain all the upper/lower bounds of GAN could make the comparison more concrete.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper gives the minimax lower bound  of GNAS in terms of low dimension structure for the measure.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Could the authors add a table which compares lower bound and upper bound of GAN under different settings? In that way, the readers can have a better understanding of the literature and the contributions in this paper.\n2. Could the authors clarify, if GAN is still optimal, in terms of the Wasserstein distance? That is to say, what is the upper bound of GAN in terms of Minkowski dimension and Wasserstein distance?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "h1iwdFH9KF", "reviewer": "Reviewer_RHKH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n*) Deriving theoretical guarantees for machine learning algorithms is important.\n\n*) The paper is well-structured and well-written. While I was not able to check the full proof in detail, it appeared reasonable when looking through it.\n\nWeaknesses:\n\n\n*) Throughout the paper, I noticed quite a few typos (see the requested changes below). Hence, the paper should be carefully proofread again.\n\n*) While I understand that this is a theory paper, it would have been interesting to see a brief discussion on bounds that have been observed empirically for the chosen metrics. If such results exist, it would be good to briefly discuss this aspect, for example in the related work section.\n\n*) On page 2, at the end of the introduction it says that \"... GANs almost match this rate, when the networks are properly chosen\". What does it mean for the networks to be properly chosen? This point should be made more precise.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In the paper, lower bounds for the minimax estimation rate of probability distributions in terms of both the $\\beta$-Hölder metric and the p-Wasserstein distance are derived. Special attention is given to data with low-dimensional support and it is shown, by comparing to results from previous work, that in such cases GANs achieve almost optimal convergence rates.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses above.\n\n\nMinor issues:\n\nSection 2, first paragraph \"... best performing estimator that achieves the maximum risk\": maximum -> minimum\n\nTheorem 7: \"... exists and\" -> \"... exists an\"\n\nPage 5: \"the sample mean almost achieves this minimax optimal rate\": sample mean -> empirical distribution\n\nPage 5: \"it is well known that We recall that\"\n\nPage 5: d-Hausdroff -> d-Hausdorff\n\nPage 6, last equation: \")\" missing before ^2 at the end", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xnEFfrTRsa", "reviewer": "Reviewer_ZUsU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper is well-written. The results are solid.\n\nWeaknesses: I think some of the statements and proofs need to be explained in more detail for the readers' convenience. See [Requested Changes] for examples.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of how well one can estimate unknown distributions with low-dimensional structures. The authors prove lower bounds for the minimax rates in H\\\"older IPM and p-Wasserstein metric, and show that the rates depend on the Minkowski dimension of the support of the distribution rather that the ambient dimension. Combining with recent results on the convergence rates of GANs, it is shown that GANs are nearly minimax optimal in estimating low-dimensional distributions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The convergence rate of GANs presented in this paper is slightly different from the reference [Huang et al. JMLR 2022] (A $\\delta$-term is added to the rate). The statement is correct, but the authors should explain the relation and difference of these two bounds (I think the difference is from the different assumptions on the covering number). This is also related to the $\\delta$-term in the lower bound. It is said in the third paragraph of Page 5 that the $\\delta$-term is an artifact of the definition of the Minkowski dimension. I think it would be better to write this paragraph as a remark and discuss how assumptions on the covering number affect the upper and lower bounds for the convergence rate.\n\n2. In the proof of Theorem 7, the authors apply Theorem 15.2 and equation 15.14 of [Wainwright 2019] to derive lower bounds (6)-(9). Can the authors explain how the results of [Wainwright 2019] are used here. What are the function $\\Phi$ and metric $\\rho$? Please also check whether ``Theorem 15.2'' is the correct reference.\n\n3. Minor issues and typos:\n\n(1) Page 5, Paragraph 4, ``t is well known that We recall that we call a set''.\n\n(2) Page 6, the last equality in the Proof of Lemma 8, I think $\\delta = sep(\\Xi)/3$ rather than $\\delta = sep(\\Xi)$.\n\n(3) Page 6, the second paragraph of the Proof of Theorem 7, I think $\\omega \\in$ \\{0,1\\}$^k$ should be $\\omega \\in$ \\{0,1\\}$^{\\lfloor k/2 \\rfloor}$.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper gives solid theoretical analysis to derive minimax lower bounds. Interestingly, the lower bounds depend on the low-dimensional structure of the data which is useful for high-dimensional problems. The paper presents clear tables and discussions to compare the derived results with existing results, e.g., removing some assumptions and more general results. All the reviewers are satisfied with the revision and the discussions. 

Minor comment:
- page 3: "Tang and Yang(2023)" should be "Tang and Yang (2023)"
Decision: Accept (poster)