Covering Numbers for Convex Functions
Authors:
- 21 December 2012
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 59 (4) , 1957-1965
Abstract
In this paper, we study the covering numbers of the space of convex and uniformly bounded functions in multidimension. We find optimal upper and lower bounds for the $\epsilon $-covering number of $ {\cal C}([a, b]^{d}, B)$, in the $L_{p}$-metric, $1 \leq p < \infty $, in terms of the relevant constants, where $d \geq 1$, $a < b \in \BBR $, $B > 0$, and $ {\cal 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.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Nonparametric least squares estimation of a multivariate convex regression functionThe Annals of Statistics, 2011
- Approximation by log-concave distributions, with applications to regressionThe Annals of Statistics, 2011
- Lower Bounds for the Minimax Risk Using $f$-Divergences, and ApplicationsIEEE Transactions on Information Theory, 2011
- Maximum Likelihood Estimation of a Multi-Dimensional Log-Concave DensityJournal of the Royal Statistical Society Series B: Statistical Methodology, 2010
- Convergence of algorithms for reconstructing convex bodies and directional measuresThe Annals of Statistics, 2006
- Information-theoretic determination of minimax rates of convergenceThe Annals of Statistics, 1999
- Rates of convergence for minimum contrast estimatorsProbability Theory and Related Fields, 1993
- Metric entropy of some classes of sets with differentiable boundariesJournal of Approximation Theory, 1974
- Convergence of Estimates Under Dimensionality RestrictionsThe Annals of Statistics, 1973
- PIECEWISE-POLYNOMIAL APPROXIMATIONS OF FUNCTIONS OF THE CLASSES $ W_{p}^{\alpha}$Mathematics of the USSR-Sbornik, 1967