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)

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

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)