Covering Numbers for Convex Functions

DOI10.1109/TIT.2012.2235172zbMATH Open1364.52007arXiv1204.0147MaRDI QIDQ2989293FDOQ2989293

Authors: Adityanand Guntuboyina, Bodhisattva Sen 

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper we study the covering numbers of the space of convex and uniformly bounded functions in multi-dimension. We find optimal upper and lower bounds for the $epsilon$-covering number of $C([a,b{]}^d,B)$, in the $L_p$-metric, $1lep<infty$, in terms of the relevant constants, where $dgeq1$, $a<binmathbbR$, $B>0$, and $C([a,b{]}^d,B)$ denotes the set of all convex functions on $[a,b{]}^d$ that are uniformly bounded by $B$. We summarize previously known results on covering numbers for convex functions and also provide alternate proofs of some known results. Our results have direct implications in the study of rates of convergence of empirical minimization procedures as well as optimal convergence rates in the numerous convexity constrained function estimation problems.

Full work available at URL: https://arxiv.org/abs/1204.0147

Mathematics Subject Classification ID

Information theory (general) (94A15) Measures of information, entropy (94A17) Convex functions and convex programs in convex geometry (52A41)

Cited In (25)

• Bayesian fractional posteriors
• Metric entropy for functions of bounded total generalized variation
• Editorial: Special issue on ``Nonparametric inference under shape constraints
• Shape constraints in economics and operations research
• Performance analysis of the LapRSSLG algorithm in learning theory
• Covering functionals of convex polytopes
• Fréchet change-point detection
• Max-affine regression via first-order methods
• Adaptation in multivariate log-concave density estimation
• Bracketing numbers of convex and \(m\)-monotone functions on polytopes
• Functional covering numbers
• Learning rates for the kernel regularized regression with a differentiable strongly convex loss
• Global rates of convergence of the MLEs of log-concave and \(s\)-concave densities
• Empirical optimal transport between different measures adapts to lower complexity
• Approximations of semicontinuous functions with applications to stochastic optimization and statistical estimation
• Global risk bounds and adaptation in univariate convex regression
• Oracle posterior contraction rates under hierarchical priors
• The learning rates of regularized regression based on reproducing kernel Banach spaces
• Gromov-Wasserstein distances: entropic regularization, duality and sample complexity
• Covering numbers of \(L_{p}\)-balls of convex functions and sets
• On convex least squares estimation when the truth is linear
• Covering numbers for bounded variation functions
• Empirical optimal transport under estimated costs: distributional limits and statistical applications
• Entropy of convex functions on \(\mathbb R^d\)
• Metric entropy of classes of sets with positive reach

This page was built for publication: Covering Numbers for Convex Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989293)