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

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

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

(28)

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

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)