From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation

Abstract

We consider an extension of $\epsilon$-entropy to a KL-divergence based complexity measure for randomized density estimation methods. Based on this extension, we develop a general information-theoretical inequality that measures the statistical complexity of some deterministic and randomized density estimators. Consequences of the new inequality will be presented. In particular, we show that this technique can lead to improvements of some classical results concerning the convergence of minimum description length and Bayesian posterior distributions. Moreover, we are able to derive clean finite-sample convergence bounds that are not obtainable using previous approaches.

Published at http://dx.doi.org/10.1214/009053606000000704 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (62)

• Rényi Divergence and Kullback-Leibler Divergence
• A General Framework for Updating Belief Distributions
• A Bayesian Sampling Approach to Exploration in Reinforcement Learning
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• Gibbs posterior for variable selection in high-dimensional classification and data mining
• Calibrating general posterior credible regions
• Dynamics of Bayesian Updating with Dependent Data and Misspecified Models
• Learning by mirror averaging
• Bayesian variable selection for high dimensional generalized linear models: convergence rates of the fitted densities
• Asymptotically minimax empirical Bayes estimation of a sparse normal mean vector
• Minimum Description Length Revisited
• Quasi-Bayesian analysis of nonparametric instrumental variables models
• A Primer on PAC-Bayesian Learning
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Provably Good Batch Reinforcement Learning Without Great Exploration
• A comparison of learning rate selection methods in generalized Bayesian inference
• Mirror averaging with sparsity priors
• Variational Gaussian Dropout is not Bayesian
• Sparse recovery in convex hulls via entropy penalization
• Pac-bayesian bounds for sparse regression estimation with exponential weights
• Assigning a value to a power likelihood in a general Bayesian model
• Bayes factor consistency
• Model-free posterior inference on the area under the receiver operating characteristic curve
• Approximating Bayes in the 21st Century
• Safe-Bayesian Generalized Linear Regression
• Gibbs posterior inference on multivariate quantiles
• Adaptive Variable Selection for Sequential Prediction in Multivariate Dynamic Models
• Information Complexity and Generalization Bounds
• Empirical Risk Minimization with Relative Entropy Regularization
• PAC-Bayes Mini-tutorial: A Continuous Union Bound
• PAC-Bayesian aggregation and multi-armed bandits
• Lower bounds and aggregation in density estimation
• Convergence Rates of Variational Posterior Distributions
• Fast learning rates with heavy-tailed losses
• Linear and convex aggregation of density estimators
• Statistical Inference in Mean-Field Variational Bayes
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• A Tight Excess Risk Bound via a Unified PAC-Bayesian-Rademacher-Shtarkov-MDL Complexity
• PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
• Adaptive variational Bayes: Optimality, computation and applications
• Probably approximate Bayesian computation: nonasymptotic convergence of ABC under misspecification
• Complexity of stochastic branch and bound methods for belief tree search in Bayesian reinforcement learning
• Fast rates in statistical and online learning
• Weakly Supervised Cross-platform Teenager Detection with Adversarial BERT
• On the Robustness to Misspecification of $\alpha$-Posteriors and Their Variational Approximations
• Calibrating generalized predictive distributions
• Characterizing the Generalization Error of Gibbs Algorithm with Symmetrized KL information
• Characterizing and Understanding the Generalization Error of Transfer Learning with Gibbs Algorithm
• On the benefits of maximum likelihood estimation for Regression and Forecasting
• Practical calibration of the temperature parameter in Gibbs posteriors
• Unifying Variational Inference and PAC-Bayes for Supervised Learning that Scales
• Asymptotics for power posterior mean estimation
• Revisiting minimum description length complexity in overparameterized models
• Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
• Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors
• PAC-Bayesian inductive and transductive learning
• Posterior concentration and fast convergence rates for generalized Bayesian learning
• Generalized Posterior Calibration via Sequential Monte Carlo Sampler
• Weighted Particle-Based Optimization for Efficient Generalized Posterior Calibration
• Suboptimality of Penalized Empirical Risk Minimization in Classification
• Quasi-Bayesian Dual Instrumental Variable Regression
• Finite-sample risk bounds for maximum likelihood estimation with arbitrary penalties