Two New Families of Local Asymptotically Minimax Lower Bounds in Parameter Estimation Authors: Neri Merhav, Raúl Alcaraz, Luca Faes, Leandro Pardo, Boris Ryabko Published: 2024 ABSTRACT AbstractWe propose two families of asymptotically local minimax lower bounds on parameter estimation performance. The first family of bounds applies to any convex, symmetric loss function that depends solely on the difference between the estimate and the true underlying parameter value (i.e., the estimation error), whereas the second is more specifically oriented to the moments of the estimation error. The proposed bounds are relatively easy to calculate numerically (in the sense that their optimization is over relatively few auxiliary parameters), yet they turn out to be tighter (sometimes significantly so) than previously reported bounds that are associated with similar calculation efforts, across many application examples. In addition to their relative simplicity, they also have the following advantages: (i) Essentially no regularity conditions are required regarding the parametric family of distributions. (ii) The bounds are local (in a sense to be specified). (iii) The bounds provide the correct order of decay as functions of the number of observations, at least in all the examples examined. (iv) At least the first family of bounds extends straightforwardly to vector parameters.Keywords: parameter estimation, minimax estimation, mean-square error, hypothesis testing, probability of error, Fisher information 1. Introduction The theory of parameter estimation consists of a very large plethora of lower bounds (as well as upper bounds), which characterize the fundamental performance limits of any estimator in a given parametric model. In this context, it is common to distinguish between Bayesian bounds (see, e.g., the Bayesian Cramér–Rao bound [1], the Bayesian Bhattacharyya bound, the Bobrovsky–Zakai bound [2], the Bellini–Tartara bound [3], the Chazan–Zakai–Ziv bound [4], the Weiss–Weinstein bound [5,6], and more (see [7] for a comprehensive overview), and non-Bayesian bounds, where in the former, the parameter to be estimated is considered a random variable with a given probability law, as opposed to the latter, where it is assumed an unknown deterministic constant. The category of non-Bayesian bounds is further subdivided into two subclasses; one is associated with local bounds that hold for classes of estimators with certain limitations, such as unbiased estimators (see, e.g., the Cramér–Rao bound [8,9,10,11,12], the Bhattacharyya bound [13], the Barankin bound [14], the Chapman–Robbins bound [15], the Fraser–Guttman bound [16], the Keifer bound [17], and more), and the other is the subclass of minimax bounds (see, e.g., Ziv and Zakai [18], Hajek [19], Le Cam [20], Assouad [21], Fano [22], Lehmann (Sections 4.2–4.4 in [23]), Nazin [24], Yang and Barron [25], Guntuboyina [26,27], Kim [28], and many more). In this paper, we focus on the minimax approach, and more concretely, on the local minimax approach. According to the minimax approach, we are given a parametric family of probability density functions (or probability mass functions, in the discrete case), {p(x1,…,xn|θ),(x1,…,xn)∈Rn,θ∈Θ}, where θ is a d-dimensional parameter vector, Θ⊆Rd is the parameter space, n is a positive integer designating the number of observations, and we define a loss function, l(θ,θ^n), where θ^n is an estimator, which is a function of the observations x1,…,xn only. The minimax performance is defined as where Eθ denotes expectation w.r.t. p(·|θ). As customary, we consider here loss functions with the property that l(θ,θ^n) depends on θ and θ^n only via their difference, that is, l(θ,θ^n)=ρ(θ−θ^n), where the function ρ(·) satisfies certain assumptions (see Section 2). The local asymptotic minimax performance at the point θ∈Θ is defined as follows (see also, e.g., [19]). Let {ζn*,n≥1} be a positive sequence, tending to infinity, with the property that is a strictly positive finite constant. Then, we say that r(θ) is the local asymptotic minimax performance with respect to (w.r.t.) {ζn*} at the point θ∈Θ. Roughly speaking, the significance is that the performance of a good estimator, θ^n, at θ is about Eθ{ρ(θ−θ^n)}≈r(θ)/ζn*. For example, in the scalar mean square error (MSE) case, where ρ(ε)=ε2, and where the observations are Gaussian, i.i.d., with mean θ and known variance σ2, it is actually shown in Example 2.4, p. 257 in [23] that r(θ)=σ2 w.r.t. ζn*=n, for all θ∈R, which is attained by the sample mean estimator, θ^n=1n∑i=1nxi. Our focus in this work is on the derivation of some new lower bounds that are as follows: (i) essentially free of regularity conditions on the smoothness of the parametric family {p(·|θ),θ∈Θ}, (ii) relatively simple and easy to calculate, at least numerically, which amounts to the property that the bound contains only a small number of auxiliary parameters to be numerically optimized (typically, no more than two or three parameters), (iii) tighter than earlier reported bounds that are associated with similar calculation efforts as described in (ii), and (iv) lend themselves to extensions that yield even stronger bounds (albeit with more auxiliary parameters to be optimized), as well as extensions to vector parameters. We propose two families of lower bounds on Rn(Θ), along with their local versions, of bounding r(θ), with the four above-described properties. The first applies to any convex, symmetric loss function ρ(·), whereas the second is more specifically oriented to the moments of the estimation error, ρ(ε)=|ε|t, where t is a positive real, not necessarily an integer, with special attention devoted to the MSE case, t=2. For the sake of simplicity and clarity of the exposition, in the first two main sections of the paper (Section 3 and Section 4), our focus is on the case of a scalar parameter, as most of our examples are associated with the scalar case. In Section 5, we extend some of our findings to the vector case. To put this work in the perspective of earlier work on minimax estimation, we next briefly review some of the basic approaches in this problem area. Admittedly, considering the vast amount of literature on the subject, our review below is by no means exhaustive. For a more comprehensive review, the reader is referred to Kim [28]. First, observe the simple fact that the minimax performance is lower bounded by the Bayesian performance of the same loss function (see, e.g., [1,2,3,4,5,6,7]) for any prior on the parameter, θ, and so, every lower bound on the Bayesian performance is automatically a valid lower bound also on the minimax performance (see Section 4.2 in [23]). Indeed, in Section 2.3 in [26], it is argued that the vast majority of existing minimax lower bounding techniques are based upon bounding the Bayes risk from below w.r.t. some prior. Many of these Bayesian bounds, however, are subjected to certain restrictions and regularity conditions concerning the smoothness of the prior and the family of densities, {p(·|θ),θ∈Θ}. Dating back to Ziv and Zakai’s 1969 article [18] on parameter estimation, applied mostly in the context of time-delay estimation, this prior puts all its mass equally on two values, θ0 and θ1, of the parameter θ, and considering an auxiliary hypothesis testing problem of distinguishing between the two hypotheses, H0:θ=θ0 and H1:θ=θ1 with equal priors (see Section 2 for exact definitions). A simple argument regarding the sub-optimality of a decision rule that is based on estimating θ and deciding on the hypothesis with the closer value of θ, combined with Chebychev’s inequality, yields a simple lower bound on the corresponding Bayes risk, and hence also the minimax risk, in terms of the probability of error of the optimal decision rule. Five years later, Bellini and Tartara [3], and then independently, Chazan, Zakai, and Ziv [4], improved the bound of [18] using somewhat different arguments and obtained Bayesian bounds that apply to the uniform prior. These bounds are also given in terms of the error probability pertaining to the optimal maximum a posteriori (MAP) decision rule of binary hypothesis testing with equal priors, but this time, it had an integral form. These bounds were demonstrated to be fairly tight in several application examples, but they are rather difficult to calculate in most cases. Shortly before the Bellini–Tartara and the Chazan–Zakai–Ziv articles were published, Le Cam [20] proposed a minimax lower bound, which is also given in terms of the error probability associated with binary hypothesis testing, or equivalently, the total variation between p(·|θ0) and p(·|θ1), under the postulate that the loss function l(·,·) is a metric. We will refer to Le Cam’s bound in a more detailed manner later, in the context of our first proposed bound. A decade later, Assouad [21] extended Le Cam’s two-point testing bound to multiple points, where instead of just two test points, θ0 and θ1, as before, there are, more generally, m test points, θ0,θ1,…,θm−1, and correspondingly, the auxiliary hypothesis testing problem consists of m hypotheses, Hi:θ=θi, i=0,1,…,m−1, with certain priors (again, to be defined in Section 2). Based on those test points, Assouad devised the so-called hypercube method. Another related bounding technique that is based on multiple test points, and referred to as Fano’s method, amounts to further bounding from below the error probability of multiple hypotheses using Fano’s inequality (see Section 2.10 in [29]). Considering the large number of auxiliary parameters to be optimized when multiple hypotheses are present, these bounds demand heavy computational efforts. Also, Fano’s inequality is often loose, even though it is adequate enough for the purpose of proving converse-to-coding theorems in information theory [29]. In later years, Le Cam [30] and Yu [31] extended Le Cam’s original approach to apply to testing mixtures of densities. More recently, Yang and Barron [25] related the minimax problem to the metric entropy of the parametric family, {p(·|θ,θ∈Θ}, and Cai and Zhou [32] combined Le Cam’s and Assouad’s methods by considering a larger number of dimensions. Guntuboyina [26,27] pursued a different direction by deriving minimax lower bounds using f-divergences. The outline of this article is as follows. In Section 2, we define the problem setting, provide a few formal definitions along with background, and establish the notation. In Section 3, we develop the first family of bounds, and in Section 4, we present the second family, both for the scalar parameter case. Finally, in Section 5, we extend some of our findings to the vector case. 2. Problem Setting, Background, Definitions, and Notation As outlined in the last paragraph of the Introduction, Section 3 and Section 4 are on the scalar parameter case, whereas in Section 5, we extend some of the results to the case of a vector parameter with dimension d. In order to avoid repetition, we formalize the problem and define the notation here for the more general vector case, with the understanding that for the scalar case, all definitions remain the same, except that they are confined to the special case of d=1. Consider a family of probability density functions (PDFs), {p(·|θ),θ∈Θ}, where θ is a parameter vector of dimension d to be estimated, and Θ⊆Rd is the parameter space. We denote by Eθ{·} the expectation operator w.r.t. p(·|θ). Let X =(X1,…,Xn) be a random vector of observations, governed by p(·|θ) for some θ∈Θ. The support of p(·|θ) is assumed Xn, the nth Cartesian power of the alphabet X of each component Xi, i=1,…,n. The alphabet X may be a finite set, a countable set, a finite interval, an infinite interval, or the entire real line. In the first two cases, the PDFs should be understood to be replaced by probability mass functions and integrations over the observation space should be replaced by summations. A realization of X will be denoted by x=(x1,…,xn)∈Xn. An estimator, θ^n, is given by any function of the observation vector, gn:Xn→Θ, that is, θ^n=gn[x]. Since X is random, so is the estimate gn[X], as well as the estimation error, εn[X]=θ^n−θ=gn[X]−θ. We associate with every possible vector value, ϵ, of εn[X] a certain loss (or “cost”, or “price”), ρ(ϵ), where ρ(·) is a non-negative function with the following properties: (i) monotonically non-increasing in each component, ϵi, of ϵ, wherever ϵi<0, i=1,2,…,d, (ii) monotonically non-decreasing in each component, ϵi, of ϵ, wherever ϵi≥0, i=1,2,…,d, and (iii) ρ(0)=0. Referring to Section 3 and Section 4, which deals with the scalar case (d=1), we further adopt the following assumptions regarding the loss function ρ. In Section 3, we assume that ρ(·) is as follows: (iv) convex, and (v) symmetric, i.e., ρ(−ϵ)=ρ(ϵ) for every ϵ. In Section 4, we assume, more specifically, that ρ(ε)=|ε|t, where t is a positive constant, not necessarily an integer. This is a special case of the class of loss functions considered in Section 3, except when t∈(0,1), in which case, |ε|t is a concave (rather than a convex) function of ε. In Section 5, for the vector extension of the results of Section 3, the above-mentioned symmetry assumption (v) is extended to become radial symmetry; namely, ρ(ϵ) will be assumed to depend on ϵ only via its Euclidean norm, ∥ϵ∥. The expected cost of an estimator gn at a point θ∈Θ, is defined as The global minimax performance is defined as Another related notion is that of local asymptotic minimax performance, defined in Section 1, and repeated here for the sake of completeness. Let {ζn*,n≥1} be a positive sequence, tending to infinity, with the property that r(θ), defined as in (2), is a strictly positive finite constant. Then, we say that r(θ) is the local asymptotic minimax performance w.r.t. {ζn*} at θ∈Θ. The sequence {1/ζn*} is referred to as the convergence rate of the minimax estimator. Similarly, as in earlier articles on minimax lower bounds, many of our proposed bounds are given in terms of the error probability pertaining to certain auxiliary hypothesis testing problems that are associated with two or more test points in the parameter space, and the choice of those test points is subjected to optimization. We therefore provide a few definitions, notation conventions, and background associated with elementary hypothesis testing. For further details, the reader is referred to any one of many textbooks that cover the topic, for example, Van Trees (see Sections 2.2 and 2.3 in [1]), Helstrom (see Chapter III in [33]), or Whalen (see Chapter 5 in [34]). For given θ0 and θ1, both in Θ, consider the problem of deciding between two possible hypotheses regarding the probability distribution that governs the given vector of observations, X. Under hypothesis H0, X is governed by p(·|θ0), and under hypothesis H1, X is governed by p(·|θ1). Suppose also that the a priori probability of H0 to be the actual underlying hypothesis is Pr{H0}=q, where 0≤q≤1 is given, and so the a priori probability of H1 is the complementary probability, Pr{H1}=1−q. When q=12, we say that the priors are equal; otherwise, the priors are unequal. A decision rule Ω=(Ω0,Ω1) is a partition of the observation space, Xn, into two disjoint decision regions, Ω0⊆Xn and its complementary region, Ω1=Ω0c: Given that X=x∈Ω0, we decide in favor of H0; otherwise, we decide in favor of H1. The probability of error, associated with the hypotheses H0 and H1, referring to test points θ0 and θ1, respectively, with priors q and 1−q, respectively, when using the decision rule Ω, is defined as A well-known elementary result in decision theory asserts that the optimal decision rule, Ω*=(Ω0*,Ω1*), in the sense of minimizing Pe(q,θ0,θ1,Ω), is given by where it should be pointed out that attributing the case of a tie, q·(x|θ0)=(1−q)·p(x|θ1), to Ω0* is completely arbitrary, and could have been attributed alternatively to Ω1* without affecting the probability of error. Here and in the sequel, the minimum probability of error, associated with Ω*, namely, Pe(q,θ0,θ1,Ω*), will be denoted more simply by Pe(q,θ0,θ1). On substituting Ω* into the above definition of the probability of error, we obtain The expression of the second to the last line will appear in some of our lower bounds in the sequel and will be recognized and interpreted as Pe(q,θ0,θ1). The expression of the last line is the one that extends to multiple hypothesis testing, as will be detailed below. The auxiliary problem of binary hypothesis testing extends from two hypotheses to a general number, m, of hypotheses, associated with m test points, θ0,θ1,…,θm−1, in the following manner. Under hypothesis Hi, the observation vector X is governed by p(·|θi) and the a priori probability of Hi being the underlying true hypothesis, Pr{Hi}, is denoted qi, i=0,1,…,m−1, where q0,q1,…,qm−1 are given non-negative numbers summing to unity. Here, a decision rule Ω=(Ω0,Ω1,…,Ωm−1) is a partition of Xn into m disjoint regions such that if x∈Ωi, we decide in favor of Hi, i=0,1,…,m−1. The probability of error associated with Ω, θ0,θ1,…,θm−1 and q=(q0,q1,…,qm−1) is defined as where Ωic is complementary to Ωi. The optimal MAP decision rule Ω* selects the hypothesis Hi whose index i maximizes the product qi·p(x|θi) among all i∈{0,1,…,m−1}, for the given x, where ties are broken arbitrarily. The probability of error, associated with Ω*, denoted Pe(q,θ0,θ1,…,θm−1), is well known to be given by Note that for m>2, this is different from the expression as the latter can be interpreted as the probability that the index i of the true hypothesis Hi minimizes (rather than maximizes) the product qip(x|θi) over i∈{0,1,…,m−1} for the given x. Imagine an observer that, upon observing a realization x of the random vector X, creates a list of indices {i} with the k largest values of qip(x|θi) for some kx0(q), one decides in favor of H0; otherwise, one decides in favor of H1. Thus, In summary, It turns out that for q=12, Pe(12,1,2)=38=0.375, whereas the maximum is 0.382, attained at q=1−55=0.5528. Thus, This concludes Example 1. In the above example, we considered just one observation, n=1. From now on, we will refer to the case where n≫1. In particular, the following simple corollary to Theorem 1 yields a local asymptotic minimax lower bound. For a given θ∈Θ and a constant s, let {ξn}n≥1 denote a positive sequence tending to zero with the property that exists and is given by a strictly positive constant, which will be denoted by Pe∞(θ,s). Also, let Then, the local asymptotic minimax performance w.r.t. ζn=1/ρ(ξn) is lower bounded by Corollary 1 is readily obtained from Theorem 1 by substituting θ0=θ and θ1=θ+2sξn in Equation (11), then multiplying both sides of the inequality by ζn=1/ρ(ξn), and finally, taking the limit inferior of both sides. Next, we study a few examples of the use of Corollary 1. As in Example 1, we emphasize again in Example 2 below the importance of having the degree of freedom to maximize over the prior q rather than to fix q=12. Also, in all the examples that were examined, the rate of convergence, 1/ζn=ρ(ξn), is the same as the optimal rate of convergence, 1/ζn*. In other words, it is tight in the sense that there exists an estimator (for example, the maximum likelihood estimator) for which Rn(θ,gn) tends to zero at the same rate. In some of these examples, we compare our lower bound to r(θ) to those of earlier reported results on the same models. Let X1,…,Xn be independently, identically distributed (i.i.d.) random variables, uniformly distributed in the range [0,θ]. In the corresponding hypothesis testing problem of Theorem 1, the hypotheses are θ=θ0 and θ=θ1>θ0 with priors, q and 1−q. There are two cases: If q/θ0n<(1−q)/θ1n, or equivalently, q<θ0n/(θ0n+θ1n), one decides always in favor of H1 and so, the probability of error is q. If, on the other hand, q/θ0n>(1−q)/θ1n, namely, q>θ0n/(θ0n+θ1n), we decide in favor of H1 whenever maxiXi>θ0 and then an error occurs only if H1 is true, yet maxiXi<θ0, which happens with probability (1−q)θ0θ1n. Thus, which is readily seen to be maximized by q=θ0nθ0n+θ1n and then Now, to apply Corollary 1, we let θ0=θ and θ1=θ0(1+2σ/n), which amounts to s=θ0σ=θσ and ξn=1/n. Then, In the case of the MSE criterion, ρ(ε)=ε2, we have ω(s)=s2, and so, w.r.t. ζn=1/ρ(ξn)=1/(1/n)2=n2. This bound will be further improved upon in Section 4. If instead of maximizing w.r.t. q, we select q=1/2, then and then the resulting bound would become w.r.t. ζn=n2. Therefore, the maximization over q plays an important role here in terms of tightening the lower bound to r(θ). More generally, for ρ(ε)=|ε|t (t≥1), ω(s)=|s|t, and we obtain w.r.t. ζn=nt, where the supremum, which is in fact a maximum, can always be calculated numerically for every given t. For large t, the maximizing u is approximately t/2, which yields On the other hand, for q=1/2, we end up with For large t, the bound of q=1/2 is inferior to the bound with the optimal q, by a factor of about 1/2. This concludes Example 2. Let X1,X2,…,Xn be i.i.d. random variables, uniformly distributed in the interval [θ,θ+1]. For the hypothesis testing problem, let θ1 be chosen between θ0 and θ0+1. Clearly, if miniXi<θ1, the underlying hypothesis is certainly H1. Likewise, if maxiXi>θ0+1, the decision is in favor of H0 with certainty. Thus, an error can occur only if all {Xi} fall in the interval [θ1,θ0+1], an event that occurs with probability (θ0+1−θ1)n. In this event, the best to do is to select the hypothesis with the larger prior with a probability of error given by min{q,1−q}. Thus, and so, achieved by q=1/2. Now, let us select ξn=1/n, which yields For ρ(ε)=|ϵ|t, (t≥1), we have w.r.t. ζn=1/|1/n|t=nt. For the case of MSE, t=2, r(θ)≥e−2≈0.1353. The constant 0.1353 should be compared with 1−1/2128≈0.0023 (see Example 4.9 in [35]), which is two orders of magnitude smaller. This concludes Example 3. Let Xi=θ+Zi, where {Zi} are i.i.d., Gaussian random variables with zero mean and variance σ2. Here, for the corresponding binary hypothesis testing problem, the optimal value of q is always q*=12. This can be readily seen from the concavity of Pe(q,θ0,θ1) in q and its symmetry around q=1/2, as Pe(q,θ0,θ1)=Pe(1−q,θ0,θ1). Since where we select ξn=1n, which yields θ1−θ0=2sn and then for the MSE case, ω(s)=s2, w.r.t. ζn=1/(1/n)2=n, and so, the asymptotic lower bound to Rn(θ,gn) is 0.3314σ2/n. We now compare this bound (which will be further improved in Section 4) with a few earlier reported results. In one of the versions of Le Cam’s bound (see Example 4.7 in [35]) for the same model, the lower bound to r(θ) turns out to be σ224=0.0417σ2, namely, an order of magnitude smaller. Also, in Example 3.1 in [28], another version of Le Cam’s method yields r(θ)≥(1−1/2)σ2/8=0.0366σ2. According to Corollary 4.3 in [36], r(θ)≥σ28e=0.046σ2. Yet another comparison is with Theorem 5.9 in [37], where we find an inequality, which in our notation reads as follows: Combining it with Chebychev’s inequality yields In [23] (p. 257), it is shown that when Θ=R, the minimax estimator for this model is the sample mean, and so, in this case, the correct constant in front of σ2 is actually 1. This concludes Example 4. The next example is related to Example 4, as it is based on the use of the central limit theorem (CLT), which means that the Gaussian tail distribution is used here too. Consider an exponential family, where T(·) is a given function and Z(θ) is a normalization function given by assuming that the integral converges. In the auxiliary binary hypothesis problem, the test statistic is ∑i=1nT(Xi). If q=1/2, ξn=1/n and θ1−θ0=2s/n, the LRT amounts to examining whether ∑i=1n[T(Xi)−Eθ{T(Xi)}] is larger than In this case, the probability of error can be asymptotically assessed using the CLT, which after a simple algebraic manipulation, becomes: where I(θ) is the Fisher information. Thus, for the MSE, w.r.t. ζn=1/(1/n)2=n. This concludes Example 5. In several earlier examples, our bound was shown to outperform (sometimes significantly so) earlier reported bounds for the corresponding models. However, to be honest and fair, we should not ignore the fact that there are also situations where our bound may not be tighter than earlier bounds applied to the same model. Such a case is demonstrated in Example 6 below, where our result is compared to those of Ziv and Zakai [18] and Chazan, Zakai, and Ziv [4] in the context of estimating the delay of a known continuous-time signal corrupted by additive white Gaussian noise (for further developments and applications of the Ziv–Zakai and the Chazan–Zakai–Ziv bounds, see, e.g., [38,39,40,41,42,43,44,45] and references therein). Having said that, it should also be kept in mind that our emphasis in this work is on bounds that are relatively simple and easy to calculate (at least numerically), whereas the Chazan–Zakai–Ziv bound, although very tight in many situations, is notoriously difficult to calculate. Indeed, in this setting, the explicit behavior of the resulting complicated bound of [4] is clearly transparent only at high values of the signal-to-noise ratio (SNR)—see Equations (11), (12), and (14) in [4]. Let X(t)=s(t,θ)+N(t), t∈[0,T], where N(t) is additive white Gaussian noise (AWGN) with double-sided spectral density N0 and s(t,θ) is a deterministic signal that depends on the unknown parameter, θ. It is assumed that the signal energy, E=∫0Ts2(t,θ)dt, does not depend on θ (which is the case, for example, when θ is a delay parameter of a pulse fully contained in the observation interval, or when θ is the frequency or the phase of a sinusoidal waveform). We further assume that s(t,θ) is at least twice differentiable w.r.t. θ, and that the energies of the first two derivatives are also independent of θ. Then, as shown in Appendix A, for small |θ1−θ0|, where E˙ is the energy s˙(t,θ)=∂s(t,θ)/∂θ. The optimal LRT in deciding between the two hypotheses is based on the comparison between the correlations, ∫0TX(t)s(t,θ0)dt and ∫0TX(t)s(t,θ1)dt. Again, the optimal value of q is q*=1/2. Thus, where P˙=E˙/T is the power of s˙(t,θ). Since we are dealing here with continuous time, instead of a sequence ξn, we use a function, ξ(T), of the observation time, T, which in this case would be ξ(T)=1T. Let θ0=θ and θ1=θ+2sT. Then, which, for the MSE case, yields w.r.t. ζ(T)=1/(1/T)2=T, which means that the minimax loss is lower bounded by r(θ)/T≥0.3314N0/E˙. This has the same form as the Cramér–Rao lower bound (CRLB), except that the multiplicative factor is 0.3314 rather than 1. In Equation (20) in [18], the bound is of the same form, but with a multiplicative constant of 0.16 for a high signal-to-noise ratio (SNR). However, in [4], the constant of proportionality was improved to 1 in the high SNR limit, just like in the Cramér–Rao lower bound for the same model. The constant 0.3314 will be improved later to 0.4549 (under Example 9 in the sequel), but it will still be below 1. The case where s(t,θ) is not everywhere differentiable w.r.t. θ can be handled in a similar manner, but some caution should be exercised. For example, consider the model, where −∞θ0. Then, The maximum w.r.t. q is attained when (1−r)q=r(1−q)α, namely, for q=q*=▵αr/[1−(1−α)r], which yields Let us denote β=▵1−α∈(0,1). The maximum of r(1−r)/(1−βr) is attained for which yields To obtain a local bound in the spirit of Corollary 1, take θ0=θ, θ1=θ(1+snθ), which yields α=e−s/θ in the limit of large n, and so, w.r.t. ζn=n2, which improves on our earlier bound in Example 2, r(θ)≥0.2414θ2. This concludes Example 7. More generally, for general moments of the estimation error, a similar derivation yields the following: For ρ(ε)=|ε|t, t≥1 (not necessarily an integer), Applying the local version of Theorem 2 to Example 7, we obtain w.r.t. ζn=nt. Changing the optimization variable from s to σ=s/t, we end up with The factor of (0.2785t)t should be compared with (1/2e)t=0.1839t of Example 2, pertaining to the choice q=r=1/2. The gap increases exponentially with t. For the maximum likelihood estimator pertaining to Example 2, which is gn[X]=maxiXi, it is easy to show that whenever t is an integer, and so, the asymptotic gap is between t! and (0.2785t)t. Considering the Stirling approximation, the ratio between the upper bound and the lower bound is about 2πt·(1.3211)t. 4.2. Three Test Points The idea behind the bounds of Section 4.1 can be conceptually extended to be based on more than two test points, but the resulting expressions become cumbersome very quickly as the number of test points grows. For three points, however, this is still manageable and can provide improved bounds. Let us select the three test points to be θ0−Δ, θ0, and θ0+Δ for some θ0 and Δ, and let us assign weights q, r, and w=1−q−r. Consider the bound where Considering the case of the MSE, can be found in closed-form. Denoting temporarily a=qp(x|θ0−Δ), b=rp(x|θ0), and c=wp(x|θ0+Δ), Ψ(x,θ0,Δ,q,r) is attained by On substituting ϑ* into the sum of squares, we end up with The lower bound on the MSE is then the sum of three integrals Revisiting again Example 2, for a given t>0, let us denote C(t)=[0,t]n, and then p(x|θ0+iΔ)=[θ0+iΔ]−n·I{x∈C(θ0+iΔ), i=−1,0,1. Then, For Δ=θ0s/n, we then have, for large n: Similarly, Thus, w.r.t. ζn=n2, which is a significant improvement of nearly 50% over the previous bound, 0.3102θ02, which was obtained on the basis of two test points, let alone the bound of Theorem 1, which was 0.2414θ02. This concludes Example 8. In general, the integrals I1, I2, and I3 are not easy to calculate due to the summations at the denominators of the integrands. One way to proceed is to apply Lemma 1 to the sum of k=3 terms, but this would introduce two additional parameters to be optimized. Returning to the earlier shorthand notation of a, b, and c, a different approach to get rid of summations at the denominators, at the expense of some loss of tightness, is the following: and so, Note that by setting w=0, we recover the bound obtained by integrating (53), and therefore, by optimizing w, the resulting bound cannot be worse. A slightly different (better, but more complicated) route in (81) is to apply Lemma 1 with k=2 in the following manner: and so, We have just proved the following result: For the MSE case, where the maximum over q, r, and w is under the constraints that they are all non-negative and sum to unity. Revisiting Example 4, it is natural that both error probabilities would correspond to a prior of 1/2. This dictates the relations, and so, the bound becomes which is an improvement on the bound of Example 4, which was 0.3314σ2/n. Similarly, in Example 6, for smooth signals, the multiplicative constant also improves from 0.3314 to 0.4549, and for the rectangular pulse, it improves from 0.7544 to 1.0352 (about 37% improvement in all of them). This concludes Example 9. Revisiting Example 2, we now have whose maximum is 0.3909/n2, an improvement relative to the earlier bound of 0.3102/n2. This concludes Example 10. 5. Extensions to the Vector Case In this section, we outline extensions of some of our findings in Section 3 and Section 4 to the vector case. Let θ be a parameter vector of dimension d and Θ⊆Rd. Let ρ(ε) be a convex loss function that depends on the d-dimensional error vector ε only via its norm, ∥ε∥ (that is, ρ has radial symmetry). First, observe that Theorem 1 extends verbatim to the vector case, as nothing in the proof of Theorem 1 is based on any assumption or property that holds only if θ is a scalar parameter. Corollary 1 can also be extended by letting the two test points of the auxiliary hypothesis testing problem, θ0 and θ1, be selected such that the distance between them, ∥θ1−θ0∥, would decay at an appropriate rate as a function of n, so as to make the probability of error, maxqPe(q,θ0,θ1), converge to a positive constant as n→∞, as was achieved in Corollary 1 for the scalar case. But in the vector case considered now, there is an additional degree of freedom, which is the direction of the displacement vector, θ1−θ0. This direction can now be optimized so as to yield the largest (hence the tightest) lower bound. To be specific, in the vector case, Corollary 1 remains the same except that now s should be thought of as a d-dimensional vector rather than a scalar, ρ(u) in the denominator of (19) should be replaced by ρ(v·u), where v∈Rd is an arbitrary fixed non-zero vector (for example, any unit norm vector in the case of MSE), and the supremum in (20) should be taken over Rd. To demonstrate this point, we now revisit Example 5, but this time, for the vector case. Consider the case where p(x|θ)=∏i=1np(xi|θ), with each factor in this product PDF being given by a d-dimensional exponential family, where θ′T(x) is the inner product of the d-dimensional parameter vector θ and a d-dimensional vector of statistics, T(x)=(T1(x),T2(x),…,Td(x)), and provided that the integral converges. In the above notation, both θ and T(x) are understood to be column vectors and θ′ denotes transposition of θ to a row vector. Similarly as in Corollary 1, to obtain a local bound at a given θ, we let θ0=θ and θ1=θ+2sn, where s∈Rd. A simple extension of the derivation in Example 5 (using the CLT) yields where s is considered a column vector, the superscript prime denotes vector transposition as before, and I(θ)=∇2lnZ(θ) is the d×d Fisher information matrix of the exponential family. Considering the case of the MSE, ρ(ϵ)=∥ϵ∥2 with v being any unit norm vector, we have and then the following lower bound is obtained w.r.t. 1/∥v/n∥2=n: where λmin(θ) is the smallest eigenvalue of I(θ). In this example, it is apparent that the chosen direction of the vector s is that of the eigenvector corresponding to the smallest eigenvalue of the Fisher information matrix. This completes Example 11. In the vector case considered in this section, it is also instructive to extend the scope from two test points, θ0 and θ1, to multiple test points, θ0,θ1,…,θm−1, along with the corresponding weights (or priors), q0,q1,…,qm−1 (see the exposition at the end of Section 2). Interestingly, this will also lead to new bounds even for the case of m=2 test points. To this end, we also consider a set of m unitary transformation matrices, T0,T1,T2,…,Tm−1, with the properties: (i) θ∈Θ if and only if Tiθ∈Θ for all i=0,1,…,m−1, and (ii) T0+T1+⋯+Tm−1=0. For example, if d=2, take Ti to be matrices of rotation by 2πi/m, i=0,1,…,m−1. Let θ0,θ1,…,θm−1∈Θ⊆Rd, d≥1 and q0,q1,…,qm−1 be given, and let T0,T1,…Tm−1 be unitary transformations that sum to zero, as described in the above paragraph. Then, for a convex loss function ρ(ε) that depends on ε only via ∥ε∥, we have: As explained in Section 2, the integral on the right-hand side can be interpreted as the probability of list error with a list size of m−1. The proof is a direct extension of the proof of Theorem 1: where in (a), we have used the unitarity (and hence the norm-preserving property) of {Ti}, as ρ(·) is assumed to depend only on the norm of the error vector; in (b), we used the convexity of ρ, and in (c), we used the fact that ∑i=0m−1Ti=0, which implies that ∑i=0m−1Tign[X]=0, thus making the bound independent of the estimator, gn. This completes the proof of Theorem 4. □ Theorem 1 is a special case where m=2, T0=I, and T1=−I, where I is the d×d identity matrix. The integral associated with the lower bound of Theorem 4 might not be trivial to evaluate in general for m≥3. However, there are some choices of the auxiliary parameters that may facilitate calculations. One such choice is as follows. For some positive integer k2 cannot be worse than our bound of m=2. We do not have, however, precisely the same argument for an odd m, but for a large m, it becomes immaterial if m is even or odd. In its general form, the bound of Theorem 4 is a heavy optimization problem, as we have the freedom to optimize θ0,…,θm−1, T0,…,Tm−1 (under the constraints that they are all unitary and sum to zero), and q0,…,qm−1 (under the constraints that they are all non-negative and sum to unity). Another relatively convenient choice is to take θi=Ti−1θ0, i=1,…,m−1 to obtain another corollary to Theorem 4: Let the conditions of Theorem 2 be satisfied. Then, To demonstrate a calculation of the extended lower bound for m=3, consider the following model. We are observing a noisy signal, where ϑ is the desired parameter to be estimated, ζ is a nuisance parameter, taking values within an interval [−δ,δ] for some δ>0, {Ni} are i.i.d. Gaussian random variables with zero mean and variance σ2, and ϕi and ψi are two given orthogonal waveforms with ∑i=1nϕi2=∑i=1nψi2=n. Suppose we are interested in estimating ϑ based on the sufficient statistics X=1n∑i=1nZiϕi and Y=1n∑i=1nZiψi, which are jointly Gaussian random variables with the mean vector (ϑ,ϑ+ζ) and the covariance matrix σ2n·I, I being the 2×2 identity matrix. We denote realizations of (X,Y) by (x,y). Let us also denote θ=(ϑ,ϑ+ζ). Since we are interested only in estimating ϑ, our loss function will depend only on the estimation error of the first component of θ, which is ϑ. Consider the choice m=3 and let Ti be counter-clockwise rotation transformations by 2πi/3, i=0,1,2. For a given Δ∈(0,δ], let us select θ0=(−Δ,0), θ1=T1−1θ0=(Δ/2,Δ3/2), and θ2=T2−1θ0=(Δ/2,−Δ3/2). Finally, let q0=q1=q2=13. In order to calculate the integral the plane R2 can be partitioned into three slices over which the integrals contributed are equal. In each such region, the smallest p(x,y|θi) is integrated. In other words, every p(x,y|θi) in its turn is integrated over the region whose Euclidean distance to θi is larger than the distances to the other two values of θ. For θ0=(−Δ,0), this is the region {(x,y):x≥0,|y|≤x3}. The factor of 13 cancels with the three identical contributions from θ0, θ1, and θ2 due to the symmetry. Therefore, Our next mathematical manipulations in this example are in the spirit of the passage from Theorem 1 to Corollary 1, that is, selecting the test points increasingly close to each other as functions of n, so that the probability of list error would tend to a positive constant. To this end, we change the integration variable x to u=xn/σ and select Δ=sσ/n for some s≥0 to be optimized later. Then, The MSE bound then becomes This bound is not as tight as the corresponding bound of m=2, which results in 0.3314σ2/n, but it should be kept in mind that here, we have not attempted to optimize the choices of θ0, θ1, θ2, T0, T1, T2, q0, and q1. Instead, we have chosen these parameter values from considerations of computational convenience, just to demonstrate the calculation. This concludes Example 12. Finally, a comment is in order regarding the possible extensions of Section 4 to the vector case. Such extensions are conceptually straightforward whenever the loss function of the error vector is given by the sum of losses associated with the different components of the error vector. Most notably, when the loss function is the MSE, ρ(ϵ)=∥ϵ∥2, each component of the estimation error can be handled separately by the methods of Section 4. Of course, the two or three test points should be chosen such that they differ in all components of the parameter vector. In the case of three test points, it makes sense to select them equally spaced along a certain straight line of a general direction in Θ. We will not pursue any further this extension in the framework of this work. Appendix A Consider the Taylor series expansion, where s˙(t,θ) and s¨(t,θ) are the first two partial derivatives of s(t,θ) w.r.t. θ. Correlating both sides with s(t,θ) yields Now, since the energy E is assumed independent of θ. Also, since ∂2E∂θ2=0, we have which yields and so, and hence, □ Appendix B First, observe that and since the inequality ∑i=1kai≤max{a1/r1,…,ak/rk} applies to all r∈S, it also applies to the infimum of max{a1/r1,…,ak/rk} over S, thus establishing the inequality “≤” between the two sides. To establish the “≥” inequality, r*∈S is defined to be the vector whose components are given by ri*=ai/∑j=1kaj. Then, This completes the proof of Lemma 1. □ Data Availability Statement The original contributions presented in the study are included in the article, further inquiries can be directed to the corresponding author. Conflicts of Interest The author declares no conflict of interest. Funding Statement This research received no external funding. Footnotes Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. References Associated Data Data Availability Statement The original contributions presented in the study are included in the article, further inquiries can be directed to the corresponding author.