title: On the High Accuracy Limitation of Adaptive Property Estimation
authors: Yanjun Han
text: 
  
  
  
  
  
  
  On the High Accuracy Limitation of Adaptive Property Estimation
      Yanjun HanYanjun Han is with the Department of Electrical Engineering, Stanford University, email: <yjhan@stanford.edu>. 
      Received: date / Accepted: date
  =============================================================================================================================
  
  
  
  
  
  Recent years have witnessed the success of adaptive (or unified) approaches in estimating symmetric properties of discrete distributions, where the learner first obtains a distribution estimator independent of the target property, and then plugs the estimator into the target property as the final estimator. Several such approaches have been proposed and proved to be adaptively optimal, i.e. they achieve the optimal sample complexity for a large class of properties within a low accuracy, especially for a large estimation error ε≫ n^-1/3 where n is the sample size. 
  
  In this paper, we characterize the high accuracy limitation, or the penalty for adaptation, for general adaptive approaches. Specifically, we obtain the first known adaptation lower bound that under a mild condition, any adaptive approach cannot achieve the optimal sample complexity for every 1-Lipschitz property within accuracy ε≪ n^-1/3. In particular, this result disproves a conjecture in <cit.> that the profile maximum likelihood (PML) plug-in approach is optimal in property estimation for all ranges of ε, and confirms a conjecture in <cit.> that their competitive analysis of the PML is tight.
  
  
  
  
  
  § INTRODUCTION AND MAIN RESULTS
  
  Given n i.i.d. samples drawn from a discrete distribution p = (p_1,⋯,p_k) of support size k, the problem of symmetric (or permutation-invariant) property estimation is to estimate the following quantity
  
      F(p) = ∑_i=1^k f(p_i)
  
  or its variants within a small additive error, for a given function f: [0,1]→. This is a fundamental problem in computer science and statistics with applications in neuroscience <cit.>, physics <cit.>, ecology <cit.>, and others <cit.>.
  
  Over the past decade, there are two main lines of research towards the symmetric property estimation. The first line of research aims to work out the minimax estimation rate and construct the minimax rate-optimal estimators for a given property, including entropy <cit.>, support size <cit.>, support coverage <cit.>, distance to uniformity <cit.>, sorted ℓ_1 distance <cit.>, Rényi entropy <cit.>, nonparametric functionals <cit.>, and many others. One of the main findings in these work is that, plugging the empirical distribution into the property often leads to a strictly suboptimal estimator, especially when the function f has some non-smooth parts. They also provided general recipes for the construction of minimax rate-optimal estimators, while the detailed construction crucially depends on the specific property in hand (i.e. classify the smooth and non-smooth parts of f, and apply different procedures).
  
  The other line of research aims to achieve a more ambitious goal: find an adaptive (or unified) estimator that achieves the optimal sample complexity for all (or most of) the above symmetric properties. Specifically, the learner aims to obtain a unified distribution estimator p of the true distribution p independent of the property F in hand, and hopes that the plug-in estimator F(p) is minimax rate-optimal in estimating F(p) for a large class of properties F. This goal may sound too good to be true, for at least two reasons: 
  
  	
    * as shown above, the plug-in approach of the empirical distribution, possibly the most natural choice of p, does not give the rate-optimal estimator;
  	
    * the construction of the optimal estimator even for known F is typically quite involved. 
  
  However, surprising recent developments show that there does exist such an estimator p, and there are even multiple such estimators. One estimator is the local moment matching (LMM) estimator in <cit.> (and its refinement in <cit.>), which is minimax rate-optimal in estimating the true distribution p up to permutation. Moreover, plugging the LMM estimator into the entropy, power sum function, support size, and all 1-Lipschitz functionals attains the optimal sample complexity for the respective properties within any accuracy ε≫ n^-1/3. Another estimator is the profile maximum likelihood (PML) estimator proposed in <cit.>, whose statistical performance was analyzed in <cit.> via a competitive analysis with an amplification factor exp(3√(n)) of the error probability; this factor was later improved to exp(c'n^1/3+c) for any c>0 in <cit.>. Consequently, for a large class of symmetric properties F where there exists a sample-optimal estimator with a sub-Gaussian error probability exp(-cnε^2), the above analyses imply that the PML plug-in approach is also adaptively optimal within any accuracy parameter ε≫ n^-1/3. 
  
  These adaptive estimators, albeit promising, still leave some questions. Specifically, we notice the following discrepancy: the estimators constructed in the property-specific manner could achieve the optimal sample complexity for the entire accuracy regime ε≫ n^-1/2, while both adaptive estimators above are shown to be optimal only when ε≫ n^-1/3. This discrepancy leaves alone the following important question: 
  
  
  
  	Is there a fundamental limit for general adaptive approaches of property estimation in the high-accuracy regime where n^-1/2≪ε≪ n^-1/3?
  
  
  
  Note that there are three possible answers to this question: first, this high-accuracy regime is uncovered simply due to an artifact of the analyses for the above adaptive estimators, and a better theoretical guarantee may be possible. Second, there may exist another fully adaptive estimator which is currently missing. Third, this high-accuracy regime may be a fundamental burden for any adaptive estimator. Specializing this question to the PML, <cit.> conjectured that “the PML based approach is indeed optimal for all ranges of ε", while <cit.> conjectured that ε≫ n^-1/3 is the best possible range for the PML to be adaptively optimal. However, even for the PML, which is a specific choice of an adaptive estimator, the lower bound analysis is missing. 
  
  In this paper, we show that the latter conjecture is true even for general adaptive estimation: there is a phase transition for the performance of adaptive estimators at the accuracy parameter ε≍ n^-1/3, while beyond this point, there is an unavoidable price that any adaptive estimator needs to pay on the sample complexity. In other words, for a reasonable family of symmetric properties, although property-specific approaches are optimal for the full accuracy range ε≫ n^-1/2, any adaptive approach fails to achieve the optimal sample complexity for at least one of the properties if ε≪ n^-1/3. Specifically, our main contributions are as follows: 
  
  
  	
    * We prove the first tight adaptation lower bound for the class of all 1-Lipschitz properties. We show that although the sample complexity for each 1-Lipschitz property is at most O(k/(ε^2log k)) for any ε≫ n^-1/2, under a mild assumption, any adaptive estimator must incur a sample complexity at least Ω(k/ε^2) for every ε≪ n^-1/3. 
  	
    * As a corollary, we obtain a tight competitive analysis for the PML plug-in approach. Specifically, we show that the amplification factor of the error probability in the PML competitive analysis is at least exp(Ω(n^1/3-c)) for every c>0, resolving the tightness conjecture of the upper bound exp(O(n^1/3+c)) for every c>0 in <cit.>. 
  	
    * We consider a new class of adaptive estimation problems, where we aim to adapt to a family of loss functions instead of the parameter sets in the traditional setting. We propose a generalized Fano's inequality to establish the adaptation lower bound for the new problem, which could be of independent interest. 
  
  
  The rest of the paper is organized as follows. We introduce the necessary notations in Section <ref>, and state the main adaptation lower bound in Section <ref>. We also compare our setting and results with an extensive set of prior work in Section <ref>. For the proofs of main results, Section <ref> and <ref> present the detailed proofs of Theorems <ref> and <ref>, respectively. In particular, Section <ref> presents a novel and general idea in proving the adaptation lower bound, and Section <ref> presents a generalized Fano's inequality. Conclusions and open problems are drawn in Section <ref>. 
  
  
  
   §.§ Notations
  
  Throughout the paper we adopt the following notations. Let  be the set of all positive integers, and for n∈, let [n]≜{1,2,…,n}. For a finite set A, let |A| be the cardinality of A. For k∈, let _k be the set of all discrete distributions supported on [k]. For two probability measures P,Q on the same probability space, let P-Q_TV = ∫ |dP-dQ|/2, D_KL(P  Q) = ∫ dPlog(dP/dQ), and χ^2(PQ) = ∫ (dP - dQ)^2/dQ be the total variation (TV) distance, the Kullback–Leibler (KL) divergence, and the χ^2-divergence between P and Q, respectively. For random variables X and Y, let I(X;Y) = ∫ dP_XYlog(dP_XY/dP_X⊗ dP_Y) be the mutual information. For p∈_k, let _p and _p denote the probability and expectation taken with respect to the i.i.d. samples X_1,⋯,X_n∼ p, respectively. We also adopt the following asymptotic notations. For non-negative sequences {a_n} and {b_n}, we write a_n≲ b_n (or a_n = O(b_n)) to denote that lim sup_n→∞a_n/b_n<∞, and a_n ≳ b_n (or a_n = Ω(b_n)) to denote b_n≲ a_n, and a_n≍ b_n (or a_n = Θ(b_n)) to denote both a_n≲ b_n and b_n≲ a_n. We also write a_n≪ b_n to denote that lim sup_ε→ 0lim sup_n→∞ n^ε a_n/b_n = 0, and a_n ≫ b_n to denote b_n≪ a_n. 
  
  
  
   §.§ Main Results
  
  To state our main adaptation lower bound, we first need to define the family of adaptive estimators as well as the family of symmetric property estimation problems. In this paper, we consider the class _Lip of all 1-Lipschitz properties expressed as F(p) = ∑_i=1^k f(p_i) with a 1-Lipschitz function f: [0,1] →ℝ, i.e. |f(x) - f(y)|≤ |x-y| for all x,y∈ [0,1]. As for the class of adaptive estimators, we require that the learner obtains a single discrete distribution estimator p = (p_1,⋯,p_k) based on the observations X^n, and then uses the plug-in estimator F(p) to estimate the property F(p). To measure the performance of this adaptive estimator, we consider the expected estimation error _p |F(p) - F(p)| for the worst-case discrete distribution p∈_k and the worst-case 1-Lipschitz property F∈_Lip. In other words, in this paper we are interested in characterizing the following adaptive minimax risk: 
  
      R_adaptive^⋆(n,k) ≜inf_psup_F ∈_Lipsup_p∈_k_p |F(p) - F(p)|.
  
  
  For technical reasons, we also assume the following mild assumption for the single distribution estimator p. 
  
  For each n,k∈, we assume that the distribution estimator p(X^n) = (p_1,⋯,p_k) satisfies (where _k denotes the permutation group over [k])
  
      sup_p∈_k_p [min_σ∈_k∑_i=1^k |p_σ(i) - p_i| ] ≤ A(n)·√(k/n),
  
  with A(n) ≪ n^δ for every δ > 0. We will use  to denote the class of all such estimators p. 
  
  
  Assumption <ref> essentially requires that the single distribution estimator p used in the adaptive approach must be a reasonably good estimator of the true distribution p up to permutation, where the term reasonably means that the estimator cannot be much worse than the empirical estimator. We provide three reasons on why we believe this assumption to be mild. First, it is very natural to expect or require that a good distribution estimator used in the adaptive approach should be sound not only after being plugging into various properties, but also before the plug-in process in terms of the (sorted) distribution estimation. In other words, Assumption <ref> could be treated as an additional requirement for any sound adaptive approach. Second, Assumption <ref> holds for many natural or known estimators. For example, the empirical distribution satisfies Assumption <ref> with A(n)≡ 1 (see, e.g. <cit.>), and both known adaptive estimators, i.e. LMM and PML, also belong to  with A(n) = polylog(n) (cf. <cit.> for the LMM, and the proof of Theorem <ref> for the PML). Hence, restricting to the estimator class  still leads to non-trivial lower bounds for these known estimators. Third, a larger quantity A(n) in Assumption <ref> only shrinks the accuracy regime from ε≪ n^-1/3 to ε≪ (nA(n))^-1/3, but does not affect the claimed minimax lower bound in the new accuracy regime. In addition to these reasons, we remark that Assumption <ref> is mostly a technical assumption, and we conjecture that the following Theorem <ref> still holds without it. 
  
  Restricting to the estimator class , the following theorem characterizes the tight adaptive minimax rate for 1-Lipschitz property estimation. 
  
  For each n,k∈, it holds that 
  
      inf_p∈sup_F ∈_ Lipsup_p∈_k_p |F(p) - F(p)| ≍√(k/nlog n)   if  n^1/3≪ k≲ nlog n, 
      √(k/n)   if  1 ≪ k≪ n^1/3.
  
  
  
  Theorem <ref> can also be equivalently formulated in terms of the optimal sample complexity. 
  
  It is sufficient and necessary to have n=Θ(k/(ε^2log k)) samples for the existence of an adaptive estimator in  to estimate all 1-Lipschitz properties within error ε if ε≫ n^-1/3, and it is sufficient and necessary to have n=Θ(k/ε^2) samples for the existence of an adaptive estimator in  to estimate all 1-Lipschitz properties within error ε if n^-1/2≪ε≪ n^-1/3. 
  
  
  Let us appreciate the result of Theorem <ref> via the comparison with other results. First, there will be no phase transition in the high-accuracy regime if we do not require an adaptive estimator. Specifically, the following result was shown in <cit.>:[The original paper did not require to use a plug-in estimator, but any estimator F could be clipped to the range of F(·) and written as F(p) for some p∈_k.] 
  
      sup_F ∈_ Lipinf_Fsup_p∈_k_p |F - F(p)| ≍√(k/nlog n),    1≪ k≲ nlog n.
  
  Comparing Theorem <ref> and (<ref>), we observe that simply after a swap of the infimum and supremum, the minimax risk becomes significantly different. In particular, there is a strict separation between the best achievable errors for adaptive and non-adaptive approaches, and the learner may need to pay a strict penalty on the estimation error to achieve adaptation. 
  
  Second, we also compare Theorem <ref> with a similar form of the minimax risk in the problem of estimating sorted distribution, where <cit.> shows that
  
      inf_psup_p∈_k_p[ sup_F ∈_ Lip|F(p) - F(p)| ] ≍√(k/nlog n)   if  n^1/3≪ k≲ nlog n, 
      √(k/n)   if  1 ≪ k≪ n^1/3.
  
  As [sup_n X_n]≥sup_n[X_n], the quantity in (<ref>) is no smaller than our adaptive minimax risk in (<ref>), and thus implies the upper bound in Theorem <ref>. However, the lower bound of Theorem <ref> is the most challenging part and stronger than what (<ref>) gives. In particular, we remark that after exchanging the expectation and supremum, the lower bound argument will become fundamentally different, and the traditional approaches fail to give the tight adaptive lower bound. We refer to Section <ref> for more details. Moreover, comparing the results of Theorem <ref> and (<ref>), we remark that (<ref>) gives a tight phase transition for the problem, while the adaptive lower bound in Theorem <ref> shows a tight phase transition only for adaptive approaches. Technically, the former transition could be derived by studying different regimes of the problem, while the latter transition requires to also take into account the crucial nature of the adaptive approach. 
  
  The general adaptive lower bound of Theorem <ref> also gives tight and non-trivial lower bounds for some known adaptive approaches. For example, for the LMM adaptive approach in <cit.>, Theorem <ref> shows that the condition ε≫ n^-1/3 required for its optimality in property estimation is not superfluous, but in general unavoidable. The implication for the PML adaptive approach <cit.> is even more surprising; to fully describe this we need to recall some basics of PML.
  
  Given n i.i.d. observations X_1,⋯,X_n drawn from a discrete distribution p supported on the domain [k], the profile of the observations is defined as a vector ϕ = (ϕ_0,⋯,ϕ_n) with ϕ_i being the number of domain elements j∈ [k] which appear exactly i times in the sample. For example, ϕ_0 is the number of unseen elements, and ϕ_1 is the number of unique elements, i.e. appearing exactly once. Let Φ_n,k be the set of all possible profiles with n observations and support size k. Note that for any ϕ∈Φ_n,k and p∈_k, we could compute the probability that the resulting profile is ϕ under true distribution p, denoted by (p,ϕ). The profile maximum likelihood (PML) distribution estimator is then defined as
  
      p^PML(ϕ) = max_p∈_k(p, ϕ).
  
  In other words, upon observing the profile ϕ, the PML estimator is the discrete distribution which maximizes the probability of observing ϕ. This estimator is interesting in several aspects. From the optimization side, the probability (p,ϕ) is a highly non-convex function of p, and it is very challenging to compute the exact or approximate PMLs. From the statistical side, as (p,ϕ) does not admit an additive form even under i.i.d. models (unlike the traditional log-likelihood), even first-order asymptotic properties are challenging to establish for the PML. After 13 years of its invention, a useful statistical property of the PML was established in <cit.> in terms of an interesting competitive analysis: for every property F and accuracy parameter ε, it holds that
  
      sup_p∈_k_p( |F(p^PML)- F(p)| ≥ 2ε )≤exp(3√(n))·inf_Fsup_p∈_k_p( |F - F(p)| ≥ε ).
  
  Specifically, (<ref>) gives an indirect statistical analysis of the PML plug-in approach which depends on the performance of another estimator. For many properties (such as all 1-Lipschitz properties), the minimax error probability in the RHS of (<ref>) behaves as exp(-Ω(nε^2)) when n exceeds the optimal sample complexity, thus (<ref>) shows that the PML plug-in approach is adaptively optimal for ε≫ n^-1/4. The proof of (<ref>) used only the defining property of PML in a delicate way, and the error amplification factor exp(3√(n)) follows from a simple union bound and a cardinality bound on the number of profiles |Φ_n,k|≤exp(3√(n)). 
  
  The paper <cit.> asked whether the above error amplification factor exp(3√(n)) could be improved in general; three years later <cit.> provided an affirmative answer. Specifically, using a chaining property of the PML distributions, <cit.> showed the following improvement
  
      sup_p∈_k_p( |F(p^PML)- F(p)| ≥ (2+o(1))ε )≤exp(c'n^1/3+c)·(inf_Fsup_p∈_k_p( |F - F(p)| ≥ε ))^1-c
  
  for any absolute constant c>0 and some c'>0 depending only on c. Using (<ref>), the accuracy range for the optimality of PML could be improved to ε≫ n^-1/3 for the aforementioned properties. It was also conjectured in <cit.> that the new amplification factor in (<ref>) is tight, but little intuition was provided. 
  
  Surprisingly, without directly analyzing the PML adaptive approach, Theorem <ref> implies the tightness of the error amplification factor in (<ref>), as summarized in our next main theorem. 
  
  
  For any given constants C>0, c_1∈ (0,1/3) and c_2∈ (0,1), it holds that 
  
      lim inf_n→∞ n^-(1/3-c_1)·sup_F∈_ Lipsup_k,ε>0logsup_p∈_k_p( |F(p^ PML)- F(p)| ≥ Cε )/(inf_Fsup_p∈_k_p( |F - F(p)| ≥ε ))^1-c_2 = +∞.
  
  
  
  After some algebra, it is clear that Theorem <ref> rules out the possibility that the exponent O(n^1/3+c) of the amplification factor in (<ref>) could be improved to O(n^1/3-c) in general. Therefore, Theorem <ref> implies that the general competitive analysis of the PML in <cit.> is essentially tight, thereby resolves the conjecture in <cit.>. 
  
  We provide two additional remarks on Theorem <ref>. First, the validity of Theorem <ref> is irrelevant to Assumption <ref>, as the PML estimator is a simple instance which satisfies Assumption <ref>. Second, the lower bound in Theorem <ref> does not rule out the possibility that the PML adaptive approach could be fully optimal for some property. For example, it was shown in <cit.> that the PML plug-in approach is fully optimal in estimating the support size. It will be an understanding open question to propose a tight analysis of the PML estimator for specific properties. 
  
  
  
   §.§ Related Work
  
  Property Estimation. There has been a rich line of research towards the optimal estimation of properties (or functionals) of high-dimensional parameters, especially in the past decade. Starting from some early work <cit.>, the fully minimax rate-optimal estimators in all accuracy regimes were obtained for the Shannon entropy in <cit.>. They also provided general recipes for both the estimator construction and tight minimax lower bounds. Specifically, the crux of the optimal estimator construction lies in the classification of smooth and non-smooth regimes and the usage of polynomial approximation to reduce bias in the non-smooth regime, and the minimax lower bound relies on the duality between moment matching and best polynomial approximation. Since then, these general recipes together with their non-trivial extensions have been applied to various other properties, e.g. the Rényi entropy <cit.>, support size <cit.>, support coverage <cit.>, distance to uniformity <cit.>, general 1-Lipschitz property <cit.>, L_1 distance <cit.>, KL divergence <cit.>, and nonparametric functionals <cit.>. We refer to the survey <cit.> for an overview of these results. There is also another line of recent work on estimating a population of parameters or distribution under a Wasserstein distance, a problem closely related to property estimation, via projection-based methods without explicit polynomial approximation <cit.>. While the above work completely characterized the complexity of many given problems in property estimation, the complexity of adaptive estimation in a set of such problems is largely missing. For example, the Ω(√(k/(nlog n))) lower bound for large k in Theorem <ref> simply follows from the complexity of estimating a particular 1-Lipschitz property, but the main Ω(√(k/n)) lower bound for small k becomes the crucial complexity of adaptive approaches and thus does not follow from the above set of results or tools. 
  
  
  
  Adaptive Property Estimation. More recently the problem of adaptive, or unified, property estimation has drawn several research attention. As reviewed in the introduction, possibly the most well-known adaptive approach is the PML plug-in approach, with early statistical developments in <cit.>. Since <cit.> provided the first competitive analysis of the PML plug-in approach, there have been several follow-up papers on the statistical analysis of the PML. Some work focused on the application of the competitive analysis and the construction of the estimator achieving the minimax error probability in (<ref>), e.g. <cit.>. Some work focused on proper modifications of the PML to achieve better adaptation, e.g. <cit.>; however, these modified distribution estimators will depend on the target property and are thus not fully unified. Other work aimed to improve the competitive analysis in <cit.>; for example, <cit.> obtained a distribution-dependent amplification factor without changing the worst-case analysis, and <cit.> improved this factor to exp(O(n^1/3+c)) in general. However, none of the above work studied the limitation of the PML plug-in approach, even for concrete examples. Therefore, the lower bound analysis, especially the possible separation compared with the optimal estimator, of the PML is missing. 
  
  Another adaptive approach plugs in the LMM estimator proposed in <cit.>. Different from the general competitive analysis of PML, the performance of the LMM approach could be directly analyzed for given properties based on its moment matching performance in each local interval. Built on the LMM performance analysis in estimating entropy, power sum function, and support size, the authors of <cit.> commented that the LMM pays some penalty for being a unified approach. However, this comment was only an insight, and there was no lower bound to support it rigorously. The current work fills in this gap and shows that the price observed for the LMM is in fact unavoidable even for general adaptive approaches. 
  
  
  
  Adaptation Lower Bound. We also review and compare with some known tools to establish adaptation lower bounds, mainly taken from the statistics literature. Adaptation is an important topic in statistics; for example, in nonparametric estimation one may aim to design a density estimator adapting to different smoothness parameters, or in hypothesis testing one may wish to propose an adaptive test procedure against several different alternatives. However, for some problems the adaptation could be achieved without paying any penalty (e.g. density estimation <cit.>, L_r norm estimation with non-even r <cit.>), while for others some adaptation penalties are inevitable (e.g. linear <cit.> or quadratic <cit.> functional of densities). The main technical tool to establish tight penalties of adaptation is the constrained risk inequality originally developed in <cit.> and generalized in <cit.>. Roughly speaking, this type of inequality asserts that if an estimator achieves a too small error at one point, it must incur a too large error at another point; therefore, adaptation may incur a penalty as it might be required to adapt to easier problems and achieve a too small error. For testing, there is also another approach to establish adaptation lower bounds, where the key is to use a mixture of different alternative distributions which could be closer to the null than any fixed alternative; see <cit.> and also <cit.> for examples. 
  
  However, we remark that our adaptive estimation problem is fundamentally different. In the above work, the target of adaptive estimation is to adapt to different (usually a nest of) parameter sets, such as Hölder balls with different smoothness parameters. In contrast, we consider a fixed parameter set (i.e. p∈_k), but wish to adapt to different loss functions for the final estimator. Establishing adaptation lower bounds for different losses is novel to our knowledge, and the above tools are not applicable in this problem. Consequently, we aim to provide useful tools (cf. Section <ref>) for this new adaptation problem, and expect them to be a helpful addition to the literature on adaptive estimation. 
  
  
  
  § PROOF OF THEOREM <REF>
  
  This section is devoted to the proof of Theorem <ref>. Note that the upper bound is achieved by the LMM estimator for k≫ n^1/3 and the empirical distribution for k≪ n^1/3 <cit.>[Note that <cit.> shows that both the LMM and empirical distributions belong to .], and the lower bound for k≫ n^1/3 follows from the minimax lower bound for estimating a specific 1-Lipschitz property, i.e. the distance to uniformity F(p) = ∑_i=1^k |p_i - 1/k| <cit.>. Therefore, it remains to prove the following adaptation lower bound:
  
      inf_p∈sup_F ∈_ Lipsup_p∈_k_p |F(p) - F(p)| ≳√(k/n),    1≪ k≪ n^1/3.
  
  
  This section is organized as follows. Section <ref> presents a high-level overview of the idea in proving the adaptation lower bounds to a class of loss functions in an abstract decision-theoretic setup, and Section <ref> introduces a generalized Fano's inequality for the adaptation lower bounds. The details to feed into these tools are worked out in Section <ref>. 
  
  
  
   §.§ High-level Idea
  
  We consider a general decision-theoretic setup <cit.>. Let (P_θ)_θ∈Θ be a general statistical model with parameter set Θ, and  be the space of all possible actions the learner could take. In other words, the learner obtains an observation X∼ P_θ with some unknown θ, and then maps X to a random action a(X)∈. Let L: Θ×→_+ be any (measurable) loss function, the problem of minimax estimation is to characterize the following minimax risk:
  
      R^⋆(Θ,,L) = inf_asup_θ∈Θ_θ[L(θ, a(X))].
  
  Similarly, the problem of adaptive minimax estimation with respect to a class of loss functions  is to characterize the following adaptive minimax risk: 
  
      R^⋆(Θ,,) = inf_asup_θ∈Θsup_L∈_θ[L(θ, a(X))].
  
  To see how (<ref>) is related to the adaptive property estimation, we could set P_θ to be the distribution of n i.i.d. samples from the discrete distribution θ, with Θ = _k. Moreover, = _k, L_F(θ,a) = |F(θ) - F(a)|, and = {L_F: F  is a 1-Lipschitz property}.
  
  There are several well-known tools to establish the lower bound of (<ref>), where a standard and prominent tool is the reduction to hypothesis testing problems; see, e.g. <cit.>. The main step is to find θ_1,⋯,θ_M∈Θ such that both the separation condition and the indistinguishability condition hold: the separation condition typically requires that inf_a∈ [L(θ_i, a) + L(θ_j, a)]≥Δ for some separation parameter Δ>0 and all i≠ j, and the indistinguishability condition essentially states that any learner could not determine the true parameter θ_i based on her observations if the truth i∈ [M] is chosen uniformly at random. Then it might be tempting to think that one only needs to replace L(θ,a) by sup_L∈ L(θ,a) in the above arguments to lower bound (<ref>). However, this approach will place the supremum in L inside the expectation in (<ref>), and thus provide a lower bound for a larger quantity like (<ref>). An alternative way is to use the trivial inequality R^⋆(Θ,,) ≥sup_L∈R^⋆(Θ,,L) and then lower bound the latter quantity. Although this gives a valid lower bound, it is not strong enough in our problem where R^⋆(Θ,,) ≫sup_L∈R^⋆(Θ,,L) in view of Theorem <ref> and (<ref>). 
  
  The main idea to fix the above difficulty is that in addition to choose M points θ_1,⋯,θ_M ∈Θ corresponding to different statistical models, we also find M different loss functions L_1,⋯,L_M∈ tailored for the respective models. Specifically, the indistinguishability condition is unchanged as it depends only on θ_1,⋯,θ_M, while the separation condition could be replaced by inf_a∈ [L_i(θ_i, a) + L_j(θ_j, a)]≥Δ for all i≠ j. Despite its simplicity, this idea gives the tight adaptation lower bound for the property estimation, and can thus be viewed as an adaptive version of the hypothesis testing approach for the adaptation lower bound. 
  
  
  
   §.§ Generalized Fano's Inequality
  
  There is an additional difficulty to apply the aforementioned high-level idea to our problem, i.e. the new separation condition L_i(θ_i, a) + L_j(θ_j, a) ≥Δ does not hold for any action a∈, but instead holds for the random action a(X) with a strictly positive probability. To account for this subtlety, we propose the following version of the Fano's inequality. 
  
  
  In the above decision-theoretic setup, suppose that θ_1,⋯,θ_M∈Θ and L_1,⋯,L_M∈ are chosen. Assume that there exists _0 ⊆ such that
  
      inf_a∈_0[ L_i(θ_i, a) + L_j(θ_j, a) ] ≥Δ > 0,   ∀ i,j ∈ [M], i≠ j,
  
  and an estimator a(X) satisfies that P_θ_i(a(X) ∈_0) ≥ p_min > 0 for all i∈ [M]. Then for this estimator we have
  
      sup_θ∈Θsup_L∈_θ[L(θ,a(X))] ≥Δ/2(p_min - I(U;X)+p_minlog 2/log M),
  
  where I(U;X) denotes the mutual information between U∼ Uniform([M]) and X| U∼ P_θ_U. 
  
  
  Note that when L_i≡ L and p_min = 1, Lemma <ref> reduces to the traditional Fano's inequality <cit.>. Hence, Lemma <ref> is a generalization of the Fano's inequality in the sense that it gives an adaptation lower bound with a soft separation condition. We prove Lemma <ref> in the remainder of this subsection. First, as the maximum is no smaller than the average, we have
  
      sup_θ∈Θsup_L∈_θ[L(θ,a(X))] ≥1/M∑_i=1^M _θ_i[L_i(θ_i,a(X))].
  
  For each i∈ [M], let Q_i be the conditional distribution of a(X) with X∼ P_θ_i conditioning on the event a(X) ∈_0. Then by the non-negativity of each L_i and definition of p_min, 
  
      _θ_i[L_i(θ_i,a(X))] ≥ P_θ_i(a(X)∈_0) ·_a∼ Q_i[L_i(θ_i, a)]≥ p_min·_a∼ Q_i[L_i(θ_i, a)],
  
  and therefore (<ref>) gives
  
      sup_θ∈Θsup_L∈_θ[L(θ,a(X))] ≥ p_min·1/M∑_i=1^M _a∼ Q_i[L_i(θ_i, a)].
  
  The next few steps are similar to the proof of the traditional Fano's inequality. For each a∈_0, define a test Ψ(a) = min_i ∈ [M]L_i(θ_i,a). Then by the separation condition, we have
  
      L_i(θ_i, a) ≥L_i(θ_i, a) + L_Ψ(a)(θ_Ψ(a), a) /2≥Δ/2·(Ψ(a)≠ i),   ∀ i∈ [M], a∈_0,
  
  and therefore (<ref>) gives
  
      sup_θ∈Θsup_L∈_θ[L(θ,a(X))] ≥Δ p_min/2·1/M∑_i=1^M Q_i(Ψ(a) ≠ i) ≥Δ p_min/2(1 - I(U;Y)+log 2/log M),
  
  where the second inequality is due to the traditional Fano's inequality <cit.>, with U∼ Uniform([M]) and Y| U∼ Q_U. To proceed, we introduce a few notations: let R_i be the distribution of a(X) with X∼ P_θ_i, R be the distribution of a(X) with X∼ M^-1∑_i=1^M P_θ_i, and Q be the restriction of the distribution R to the set _0. Then 
  
      I(U; Y)    ≤_U[D_KL(Q_U  Q) ] 
         ≤_U[1/P_θ_U(a(X)∈_0)· D_KL(R_U  R)  ] 
         ≤1/p_min·_U[D_KL(R_U  R)] 
         =I(U;a(X))/p_min
         ≤I(U;X)/p_min,
  
  where (a) is due to the variational representation of the mutual information I(U;Y) = min_Q_Y_U[D_KL(P_Y|UQ_Y)], (b) follows from the data-processing property of the KL divergence D_KL(PQ)≥ P(A)· D_KL(P_·| AQ_·| A), (c) is due to the assumption of Lemma <ref>, (d) is the definition of the mutual information, and (e) is the data-processing property of the mutual information. Now combining the above inequality with (<ref>) completes the proof of Lemma <ref>. 
  
  
  
   §.§ Proof of Adaptation Lower Bound
  
  Recall that to formulate our adaptive property estimation problem in the general framework of (<ref>), we identify θ∈Θ and a∈ with the distributions p, p∈_k, and Θ= = _k. Moreover, the loss function is the absolute difference in the property value L_F(p, p) = |F(p) - F(p)|, and the family of losses is = {L_F: F  is a 1-Lipschitz property}. In this section, we apply Lemma <ref> to a suitable choice of distributions p_1,⋯,p_M ∈_k and 1-Lipschitz properties F_1, ⋯, F_M∈_Lip, and prove the target adaptation lower bound in (<ref>). 
  
  Without loss of generality we assume that k=2k_0 is an even integer. Consider the following distribution p_0 = (p_0,1,⋯,p_0,k)∈_k serving as the “center" of all hypotheses: 
  
      p_0 = (1/2k, 1/2k + 1/k(k-1), 1/2k+2/k(k-1), ⋯, 3/2k).
  
  Fix a parameter
  
      δ∈(0, 1/4k(k-1))
  
  to be chosen later, for each u∈≜{± 1 }^k_0 we also associate a distribution p_u = (p_u,1,⋯,p_u,k)∈_k with
  
      p_u,i = p_0,i + u_iδ,    p_u,k_0+i = p_0,k_0+i - u_iδ,   ∀ i∈ [k_0].
  
  Clearly each p_u is a valid probability distribution, and this is known as the Paninski's construction <cit.>. By the Gilbert–Varshamov bound, there exists _0 ⊆ such that the minimum pairwise Hamming distance between distinct elements of _0 is at least k_0/5, and |_0|≥exp(k_0/8). We will set {p_u}_u∈_0 as the parameters θ_1,⋯,θ_M in Lemma <ref>, with M = |_0| ≥exp(k_0/8). 
  
  For each u∈_0, we also need to specify the associated loss, or equivalently the 1-Lipschitz property F_u∈_Lip. The detailed choice of F_u is given by
  
      F_u(p) = ∑_i=1^k f_u(p_i) = ∑_i=1^k min_j∈ [k] |p_i - p_u,j|,    p = (p_1,⋯,p_k), u ∈_0.
  
  As the map x↦ |x-x_0| is 1-Lipschitz for any x_0∈, and the pointwise minimum of 1-Lipschitz functions is still 1-Lipschitz, each F_u is a valid 1-Lipschitz property. 
  
  Finally, to apply Lemma <ref>, it remains to specify the subset _0. For each i∈ [k], let I_i be the open interval (p_0,i - 1/(2k(k-1)), p_0,i + 1/(2k(k-1))); clearly I_1,⋯,I_k are disjoint intervals by the definition of p_0. Now we define _0 as
  
      _0 ≜{q=(q_1,⋯,q_k)∈_k: ∑_i=1^k ∏_j=1^k (q_j ∉ I_i) ≤k/10}.
   
  In other words, the subset _0 consists of all probability vectors which intersect with at least 9/10 of the intervals I_1,⋯,I_k. 
  
  With the above construction and definitions, we are about to use Lemma <ref> for the adaptation lower bound. Specifically, we are left with three tasks: to lower bound the separation parameter Δ, to lower bound the minimum probability p_min for all estimators p∈, and to upper bound the mutual information I(U;X^n). 
  
  
  
  Lower bound of Δ. First, we aim to find a lower bound of |F_u(q) - F_u(p_u)| + |F_u'(q) - F_u'(p_u')| for all q∈_0 and u≠ u'∈_0. By construction of F_u, it is clear that F_u(p_u) = 0 for all u∈_0, and the above quantity can be written as
  
      |F_u(q) - F_u(p_u)| + |F_u'(q) - F_u'(p_u')| = ∑_i=1^k (min_j∈ [k] |q_i - p_u,j| + min_j∈ [k] |q_i - p_u',j| ).
  
  One could check the following simple fact: if q_i∈ I_j(i) for some j(i)∈ [k], then 
  
      min_j∈ [k] |q_i - p_u,j| + min_j∈ [k] |q_i - p_u',j| ≥ |p_u,j(i) - p_u', j(i)| ∈{0, 2δ}.
  
  By the definition of q∈_0, we know that the set {j(i)}_i∈ [k] contains at least 9k/10 elements of [k]. Moreover, by the minimum distance property of _0, for any u≠ u'∈_0, there are at least k/5 indices j∈ [k] such that |p_u,j - p_u', j| = 2δ. By an inclusion-exclusion principle, there are at least 9k/10 + k/5 - k = k/10 elements in the set {j(i)}_i∈ [k] such that |p_u,j(i) - p_u', j(i)| = 2δ, and therefore
  
      |F_u(q) - F_u(p_u)| + |F_u'(q) - F_u'(p_u')| ≥k/10· 2δ = kδ/5,   ∀ u≠ u'∈_0, q∈_0.
  
  In other words, Δ≥ kδ/5 in Lemma <ref>. 
  
  
  
  Lower bound of p_min. Next, we lower bound the probability _p_u(p(X)∈_0) for all p∈ and u∈_0. Here we need to use the definition of  in Assumption <ref>. Assume without loss of generality that p_1≤⋯≤p_k, as any permutation of p does not affect the validity of Assumption <ref>. Also, by the definition of p_u and the choice of δ in (<ref>), the entries of each p_u are monotonically increasing as well. Consequently, choosing p = p_u in Assumption <ref> gives
  
      _p_u[∑_i=1^k |p_i - p_u,i| ] ≤ A(n)√(k/n).
  
  On the other hand, if the event p∉_0 occurs, there are at least k/10 indices i∈ [k] such that p_j ∉ I_i for all j∈ [k]. Consequently, for such an index i, one has |p_i - p_u,i| ≥ 1/(2k(k-1)) - δ≥ 1/(4k(k-1)) by the choice of δ in (<ref>). Therefore, 
  
      ∑_i=1^k |p_i - p_u,i| ≥k/10·1/4k(k-1)·(p∉_0) ≥1/40k·(p∉_0).
  
  Combining the above two inequalities, we conclude that
  
      sup_p∈max_u∈_0_p_u(p(X)∉_0) ≤ 40A(n)·√(k^3/n),
  
  which is far smaller than 1 as k≪ n^1/3 and the assumption A(n)≪ n^δ for all δ>0. Consequently, we may choose p_min≥ 1/2. 
  
  
  
  Upper bound of I(U;X^n). The upper bound of the mutual information could be established in a similar way as <cit.>. Specifically, the following chain of inequalities holds:
  
      I(U;X^n)    ≤_U[D_KL(p_U^⊗ n p_0^⊗ n) ] 
         = n·_U[D_KL(p_U p_0) ] 
         ≤ n·_U[∑_i=1^k (p_U,i - p_0,i)^2/p_0,i] 
         ≤ 2nk^2δ^2,
   
  where (a) is due to the variational representation of the mutual information I(U;X) = min_Q_X_U[D_KL(P_X|UQ_X)] and the fact that P_X^n|U = p_U^⊗ n, (b) follows from the chain rule of the KL divergence, (c) uses the inequality D_KL(P  Q)≤χ^2(PQ), and (d) follows from min_i∈ [k] p_0,i≥ 1/(2k) and simple algebra. Consequently, the mutual information could be upper bounded as I(U;X^n)≤ 2nk^2δ^2. 
  
  
  
  Combining the above analysis, Lemma <ref> gives that
  
      inf_p∈sup_F ∈_ Lipsup_p∈_k_p |F(p) - F(p)| ≥kδ/10(1/2 - 2nk^2δ^2+log 2/k/20).
  
  Consequently, choosing δ = c/√(nk) for a small enough constant c>0 completes the proof of the target lower bound (<ref>) (note that the condition (<ref>) on δ is also fulfilled as k≪ n^1/3). 
  
  
  
  § PROOF OF THEOREM <REF>
  
  This section is devoted to the proof of Theorem <ref>. The proof consists of two steps: first, we show that the PML distribution belongs to the class  in Assumption <ref>, and therefore the adaptation lower bound of Theorem <ref> holds for the PML estimator; second, we argue by contradiction that if Theorem <ref> is false, then the PML plug-in approach will also achieve the rate-optimal minimax rate for all 1-Lipschitz properties for some k≪ n^1/3, a contradiction to Theorem <ref>. 
  
  
  
  Step I: show that p^ PML∈. First, for the empirical distribution p, <cit.> shows that
  
      sup_p∈_k_p[∑_i=1^k |p_i - p_i|] ≤√(k/n).
  
  Moreover, a single perturbation of the observations X_1,⋯,X_n only changes the quantity ∑_i=1^k |p_i - p_i| by at most 2/n. Hence, by McDiarmid's inequality, we have
  
      sup_p∈_k_p [min_σ∈_k∑_i=1^k |p_σ(i) - p_i| ≥√(k/n) + ε] ≤ 2exp(-nε^2/2)
  
  for every ε>0. As for the PML distribution, the competitive analysis of <cit.> shows that
  
      sup_p∈_k_p [min_σ∈_k∑_i=1^k |p_σ(i)^PML - p_i| ≥ 2ε] ≤ |Φ_n,k|·sup_p∈_k_p [min_σ∈_k∑_i=1^k |p_σ(i) - p_i| ≥ε],
  
  where |Φ_n,k| is the cardinality of all possible profiles with length n and support size k. Note that trivially |Φ_n,k|≤ (n+1)^k holds, the above two inequalities lead to
  
      sup_p∈_k_p [min_σ∈_k∑_i=1^k |p_σ(i)^PML - p_i| ≥ 2ε]≤min{1,2exp(klog(n+1) - n/2(ε - √(k/n))_+^2 )}.
  
  Now integrating the RHS of (<ref>) over ε∈ (0,∞) gives that p^PML∈ with A(n) = O(√(log n)). 
  
  
  
  Step II: proof by contradiction. Assume by contradiction that Theorem <ref> is false, i.e. there exists an absolute constant c_0 such that for some large enough n, it holds that
  
      sup_p∈_k_p( |F(p^ PML)- F(p)| ≥ Cε ) ≤exp(c_0n^1/3-c_1)·(inf_Fsup_p∈_k_p( |F - F(p)| ≥ε ))^1-c_2
  
  for all k∈, ε>0 and F∈_Lip. For any ε≫ n^-1/2 and k≫ 1, it was shown in <cit.> that the minimax error probability for any 1-Lipschitz property estimation is at most
  
      inf_Fsup_p∈_k_p( |F - F(p)| ≥ε ) ≤ 2exp(-c_δ n^1-δ(ε - d_δ√(k/nlog n))_+^2 ),
  
  for an arbitrary constant δ>0 and constants c_δ, d_δ>0 depending only on δ. Consequently, (<ref>) implies that 
  
      sup_F∈_Lipsup_p∈_k_p( |F(p^ PML)- F(p)| ≥ Cε ) ≤ 2exp(c_0n^1/3-c_1 - (1-c_2)c_δ n^1-δ(ε - d_δ√(k/nlog n))_+^2 ).
   
  Choosing δ<c_1/4, ε = 2d_δ√(k/(nlog n)) and k ≍ n^1/3-c_1/2, the above inequality shows that there exists an absolute constant c_0'>0 depending only on (c_0,c_1,c_2,C) such that 
  
      sup_F∈_Lipsup_p∈_k_p( |F(p^ PML)- F(p)| ≥1/c_0'√(k/nlog n)) ≤ 2exp(-c_0'n^1/3-c_1).
  
  Hence, using that |X| ≤ t + X_∞·(|X|≥ t) for any t>0 implies that for k≍ n^1/3 - c_1/2 and n tending to infinity (possibly along some subsequence), we arrive at
  
      sup_F∈_Lipsup_p∈_k_p|F(p^ PML)- F(p)| ≲√(k/nlog n),
   
  a contradiction to Theorem <ref> as p^PML∈. Therefore, the inequality (<ref>) does not hold, and the proof of Theorem <ref> is completed. 
  
  
  
  § CONCLUSION AND OPEN PROBLEMS
  
  In this paper we showed that there is a high-accuracy limitation for general adaptive approaches of property estimation, which in turn implied tight lower bounds for the known adaptive approaches such as the PML and LMM. A number of directions could be of interest. First, we believe that Assumption <ref> is an artifact of our proof and unnecessary for Theorem <ref> to hold, and a better choice of the loss functions in Lemma <ref> could remove this assumption. Second, the adaptation lower bound for PML does not rule out the possibility that PML could be fully optimal for certain properties. However, to show this, one need to go beyond the competitive analysis of the PML and seek for additional properties. Third, our current lower bound for PML only shows the existence of a property requiring ε≫ n^-1/3 for the PML to be optimal, and it is interesting to construct such a property explicitly. 
  
  
  
  § ACKNOWLEDGEMENT
   
  Yanjun Han is grateful to Kirankumar Shiragur for helpful discussions, and anonymous reviewers for their valuable comments to improve the presentation of this paper.
  
  alpha
  
   
  
  