Covering Numbers for Convex Functions

DOI10.1109/TIT.2012.2235172MaRDI QIDQ2989293zbMATH OpenFDO

Authors Adityanand Guntuboyina, Bodhisattva Sen

Publication date 8 June 2017

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

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)

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.

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
• Bracketing numbers of convex and m-monotone functions on polytopes
• Adaptation in multivariate log-concave density estimation
• Max-affine regression via first-order methods
• Functional covering numbers
• Global rates of convergence of the MLEs of log-concave and \(s\)-concave densities
• Learning rates for the kernel regularized regression with a differentiable strongly convex loss
• 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 for bounded variation functions
• Covering numbers of \(L_{p}\)-balls of convex functions and sets
• On convex least squares estimation when the truth is linear
• 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)