In statistical inference problems, we wish to obtain lower bounds on the minimax risk, that is to bound the performance of any possible estimator. A standard technique to obtain risk lower bounds involves the use of Fano's inequality. In an information-theoretic setting, it is known that Fano's inequality typically does not give a sharp converse result (error lower bound) for channel coding problems. Moreover, recent work has shown that an argument based on binary hypothesis testing gives tighter results. We adapt this technique to the statistical setting, and argue that Fano's inequality can always be replaced by this approach to obtain tighter lower bounds that can be easily computed and are asymptotically sharp. We illustrate our technique in three applications: density estimation, active learning of a binary classifier, and compressed sensing, obtaining tighter risk lower bounds in each case.
Birg ' e @cite_20 gives stronger, but less transparent, bounds than Fano's inequality using Fano-type arguments; again, @math is bounded in terms of an average of Kullback--Leibler divergences, but these are used as the argument for a function, rather than directly substituted. Sason and Verd 'u [Section 3] sasonV18arimoto recently derived a generalized Fano's inequality in terms of the Arimoto-R 'enyi conditional entropy. They also obtained upper bounds on @math in terms of the pairwise R 'enyi divergences [Section 4] sasonV18arimoto .
@cite_20
2101412426
Lower bounds involving f-divergences between the underlying probability measures are proved for the minimax risk in estimation problems. Our proofs just use simple convexity facts. Special cases and straightforward corollaries of our bounds include well known inequalities for establishing minimax lower bounds such as Fano's inequality, Pinsker's inequality and inequalities based on global entropy conditions. Two applications are provided: a new minimax lower bound for the reconstruction of convex bodies from noisy support function measurements and a different proof of a recent minimax lower bound for the estimation of a covariance matrix. In this technical note, we give two extensions of the classical Fano inequality in information theory. The first extends Fano's inequality to the setting of estimation, providing lower bounds on the probability that an estimator of a discrete quantity is within some distance @math of the quantity. The second inequality extends our bound to a continuum setting and provides a volume-based bound. We illustrate how these inequalities lead to direct and simple proofs of several statistical minimax lower bounds. Working under local differential privacy-a model of privacy in which data remains private even from the statistician or learner-we study the tradeoff between privacy guarantees and the utility of the resulting statistical estimators. We prove bounds on information-theoretic quantities, including mutual information and Kullback-Leibler divergence, that influence estimation rates as a function of the amount of privacy preserved. When combined with minimax techniques such as Le Cam's and Fano's methods, these inequalities allow for a precise characterization of statistical rates under local privacy constraints. In this paper, we provide a treatment of two canonical problem families: mean estimation in location family models and convex risk minimization. For these families, we provide lower and upper bounds for estimation of population quantities that match up to constant factors, giving privacy-preserving mechanisms and computationally efficient estimators that achieve the bounds. Estimating divergences in a consistent way is of great importance in many machine learning tasks. Although this is a fundamental problem in nonparametric statistics, to the best of our knowledge there has been no finite sample exponential inequality convergence bound derived for any divergence estimators. The main contribution of our work is to provide such a bound for an estimator of R 'enyi- @math divergence for a smooth H "older class of densities on the @math -dimensional unit cube @math . We also illustrate our theoretical results with a numerical experiment. Fano's inequality lower bounds the probability of transmission error through a communication channel. Applied to classification problems, it provides a lower bound on the Bayes error rate and motivates the widely used Infomax principle. In modern machine learning, we are often interested in more than just the error rate. In medical diagnosis, different errors incur different cost; hence, the overall risk is cost-sensitive. Two other popular criteria are balanced error rate (BER) and F-score. In this work, we focus on the two-class problem and use a general definition of conditional entropy (including Shannon's as a special case) to derive upper lower bounds on the optimal F-score, BER and cost-sensitive risk, extending Fano's result. As a consequence, we show that Infomax is not suitable for optimizing F-score or cost-sensitive risk, in that it can potentially lead to low F-score and high risk. For cost-sensitive risk, we propose a new conditional entropy formulation which avoids this inconsistency. In addition, we consider the common practice of using a threshold on the posterior probability to tune performance of a classifier. As is widely known, a threshold of 0.5, where the posteriors cross, minimizes error rate--we derive similar optimal thresholds for F-score and BER. In the random sampling setting we estimate the entropy of a probability density distribution by the entropy of a kernel density estimator using the double exponential kernel. Under mild smoothness and moment conditions we show that the entropy of the kernel density estimator equals a sum of independent and identically distributed (i.i.d.) random variables plus a perturbation which is asymptotically negligible compared to the parametric rate n sup -1 2 . An essential part in the proof is obtained by exhibiting almost sure bounds for the Kullback-Leibler divergence between the kernel density estimator and its expected value. The basic technical tools are Doob's submartingale inequality and convexity (Jensen's inequality). This paper studies the basic question of whether a given channel @math can be dominated (in the precise sense of being more noisy) by a @math -ary symmetric channel. The concept of "less noisy" relation between channels originated in network information theory (broadcast channels) and is defined in terms of mutual information or Kullback-Leibler divergence. We provide an equivalent characterization in terms of @math -divergence. Furthermore, we develop a simple criterion for domination by a @math -ary symmetric channel in terms of the minimum entry of the stochastic matrix defining the channel @math . The criterion is strengthened for the special case of additive noise channels over finite Abelian groups. Finally, it is shown that domination by a symmetric channel implies (via comparison of Dirichlet forms) a logarithmic Sobolev inequality for the original channel. Lower bounds for the average probability of error of estimating a hidden variable X given an observation of a correlated random variable Y, and Fano's inequality in particular, play a central role in information theory. In this paper, we present a lower bound for the average estimation error based on the marginal distribution of X and the principal inertias of the joint distribution matrix of X and Y. Furthermore, we discuss an information measure based on the sum of the largest principal inertias, called k-correlation, which generalizes maximal correlation. We show that k-correlation satisfies the Data Processing Inequality and is convex in the conditional distribution of Y given X. Finally, we investigate how to answer a fundamental question in inference and privacy: given an observation Y, can we estimate a function f(X) of the hidden random variable X with an average error below a certain threshold? We provide a general method for answering this question using an approach based on rate-distortion theory. It was recently shown that estimating the Shannon entropy @math of a discrete @math -symbol distribution @math requires @math samples, a number that grows near-linearly in the support size. In many applications @math can be replaced by the more general R 'enyi entropy of order @math , @math . We determine the number of samples needed to estimate @math for all @math , showing that @math requires a near-linear @math samples, but, perhaps surprisingly, integer @math requires only @math samples. Furthermore, developing on a recently established connection between polynomial approximation and estimation of additive functions of the form @math , we reduce the sample complexity for noninteger values of @math by a factor of @math compared to the empirical estimator. The estimators achieving these bounds are simple and run in time linear in the number of samples. Our lower bounds provide explicit constructions of distributions with different R 'enyi entropies that are hard to distinguish. Let @math be a 3-uniform hypergraph of order @math and size @math , and let @math be a subset of vertices of @math . The set @math is a strong transversal in @math if @math contains at least two vertices from every edge of @math . The strong transversal number @math of @math is the minimum size of a strong transversal in @math . We show that @math , and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph @math of order @math and size @math that achieves equality in this bound. A set @math of vertices in a graph @math is a double total dominating set of @math if every vertex of @math is adjacent to at least two vertices in @math . The minimum cardinality of a double total dominating set of @math is the double total domination number @math of @math . Let @math be a connected graph of order @math with minimum degree at least three. As an application of our hypergraph results, we show that @math with equality if and only if @math is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if @math is not the Heawood graph, we show that @math , while if @math is a cubic graph different from the Heawood graph, we show that @math , and this bound is sharp. We study the asymptotic-capacity-achieving score function that was recently proposed by for bias-based traitor tracing codes. For the bias function, we choose the Dirichlet distribution with a cutoff. Using Bernstein's inequality and Bennett's inequality, we upper bound the false-positive and false-negative error probabilities. From these bounds we derive sufficient conditions for the scheme parameters. We solve these conditions in the limit of large coalition size c0 and obtain asymptotic solutions for the cutoff, the sufficient code length, and the corresponding accusation threshold. We find that the code length converges to its asymptote approximately as c0?1 2 @math , which is faster than the c0?1 3 @math of Tardos' score function. MSC:94B60 This note explores the connections and differences between three commonly used methods for constructing minimax lower bounds in nonparametric estimation problems: Le Cam’s, Assouad’s and Fano’s. Two connections are established between Le Cam’s and Assouad’s and between Assouad’s and Fano’s. The three methods are then compared in the context of two estimation problems for a smooth class of densities on [0,1]. The two estimation problems are for the integrated squared first derivatives and for the density function itself. Let D and V denote respectively Information Divergence and Total Variation Distance. Pinsker's and Vajda's inequalities are respectively D ≥ [ 1 2] V2 and D ≥ log[( 2+V) ( 2-V)] - [( 2V) ( 2+V)]. In this paper, several generalizations and improvements of these inequalities are established for wide classes of f -divergences. First, conditions on f are determined under which an f-divergence Df will satisfy Df ≥ cf V2 or Df ≥ c2,f V2 + c4,f V4, where the constants cf, c2,f and c4,f are best possible. As a consequence, lower bounds in terms of V are obtained for many well known distance and divergence measures, including the χ2 and Hellinger's discrimination and the families of Tsallis' and Renyi's divergences. For instance, if D(α) (P||Q) = [α(α-1)]-1 [∫pαq1-αdμ-1] and ℑα (P||Q) = (α-1)-1 log[∫pαq1-αdμ] are respectively the relative information of type α and the Renyi's information gain of order α, it is shown that D(α) ≥ [ 1 2] V2 + [ 1 72] (α+1)(2-α) V4 whenever -1 ≤ α ≤ 2, α ≠ 0,1 and that ℑα ≥ [( α) 2] V2 + [ 1 36] α(1 + 5 α- 5 α2 ) V4 for 0 <; α <; 1. In a somewhat different direction, and motivated by the fact that these Pinsker's type lower bounds are accurate only for small variation (V close to zero), lower bounds for Df which are accurate for both small and large variation (V close to two) are also obtained. In the special case of the information divergence they imply that D ≥ log[ 2 ( 2-V)] - [( 2-V) 2] log[( 2+V) 2], which uniformly improves Vajda's inequality. A novel class of information-theoretic divergence measures based on the Shannon entropy is introduced. Unlike the well-known Kullback divergences, the new measures do not require the condition of absolute continuity to be satisfied by the probability distributions involved. More importantly, their close relationship with the variational distance and the probability of misclassification error are established in terms of bounds. These bounds are crucial in many applications of divergence measures. The measures are also well characterized by the properties of nonnegativity, finiteness, semiboundedness, and boundedness. > We give a lower bound of @math for the degree-4 Sum-of-Squares SDP relaxation for the planted clique problem. Specifically, we show that on an Erd "os-R 'enyi graph @math , with high probability there is a feasible point for the degree-4 SOS relaxation of the clique problem with an objective value of @math , so that the program cannot distinguish between a random graph and a random graph with a planted clique of size @math . This bound is tight. We build on the works of Deshpande and Montanari and , who give lower bounds of @math and @math respectively. We improve on their results by making a perturbation to the SDP solution proposed in their work, then showing that this perturbation remains PSD as the objective value approaches @math . In an independent work, Hopkins, Kothari and Potechin [HKP15] have obtained a similar lower bound for the degree- @math SOS relaxation. This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen–Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate–reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters @math and @math are guaranteed to achieve a rate @math and an error exponent @math . The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed. A natural term rewriting framework for the Bellantoni Cook schemata of predicative recursion, which yields a canonical definition of the polynomial time computable functions, is introduced. In terms of an exponential function both, an upper bound and a lower bound are proved for the resulting derivation lengths of the functions in question. It is proved that any natural reduction strategy yields an algorithm which runs in exponential time. We give an example in which this estimate is tight. It is proved that the resulting derivation lengths become polynomially bounded in the lengths of the inputs if the rewrite rules are only applied to terms in which the safe arguments – no restrictions are assumed for the normal arguments – consist of values, i.e. numerals, and not of names, i.e. non numeral terms. It is proved that in the latter situation any inside first reduction strategy and any head reduction strategy yield algorithms, for the function under consideration, for which the running time is bounded by an appropriate polynomial in the lengths of the input. A feasible rewrite system for predicative recursion with predicative parameter substitution is defined. It is proved that the derivation lengths of this rewrite system are polynomially bounded in the lengths of the inputs. As a corollary we reobtain Bellantoni’s result stating that predicative recursion is closed under predicative parameter recursion. We study bounds on the exit time of Brownian motion from a set in terms of its size and shape, and the relation of such bounds with isoperimetric inequalities. The first result is an upper bound for the distribution function of the exit time from a subset of a sphere or hyperbolic space of constant curvature in terms of the exit time from a disc of the same volume. This amounts to a rearrangement inequality for the Dirichlet heat kernel. To connect this inequality with the classical isoperimetric inequality, we derive a formula for the perimeter of a set in terms of the heat flow over the boundary. An auxiliary result generalizes Riesz' rearrangement inequality to multiple integrals. Working under a model of privacy in which data remain private even from the statistician, we study the tradeoff between privacy guarantees and the risk of the resulting statistical estimators. We develop private versions of classical information-theoretical bounds, in particular those due to Le Cam, Fano, and Assouad. These inequalities allow for a precise characterization of statistical rates under local privacy constraints and the development of provably (minimax) optimal estimation procedures. We provide a treatment of several canonical families of problems: mean estimation and median estimation, generalized linear models, and nonparametric density estimation. For all of these families, we provide lower and upper bounds that match up to constant factors, and exhibit new (optimal) privacy-preserving mechanisms and computationally efficient estimators that achieve the bounds. Additionally, we present a variety of experimental results for estimation problems involving sensitive data, including salaries, censored blog posts and articles, and drug abuse; these experiments demonstrate the importance of deriving optimal procedures. Supplementary materials for this article are available online. We present simple and computationally efficient nonparametric estimators of R 'enyi entropy and mutual information based on an i.i.d. sample drawn from an unknown, absolutely continuous distribution over @math . The estimators are calculated as the sum of @math -th powers of the Euclidean lengths of the edges of the generalized nearest-neighbor' graph of the sample and the empirical copula of the sample respectively. For the first time, we prove the almost sure consistency of these estimators and upper bounds on their rates of convergence, the latter of which under the assumption that the density underlying the sample is Lipschitz continuous. Experiments demonstrate their usefulness in independent subspace analysis.