Covering Numbers for Convex Functions

By Adityanand Guntuboyina, Bodhisattva Sen. 2012

76 citations recorded by the source corpus.

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 <formula formulatype="inline"> <tex Notation="TeX">$\epsilon $</tex></formula>-covering number of <formula formulatype="inline"><tex Notation="TeX">$ {\cal C}([a, b]^{d}, B)$</tex></formula>, in the <formula formulatype="inline"><tex Notation="TeX">$L_{p}$</tex></formula>-metric, <formula formulatype="inline"><tex Notation="TeX">$1 \leq p < \infty $</tex></formula>, in terms of the relevant constants, where <formula formulatype="inline"> <tex Notation="TeX">$d \geq 1$</tex></formula>, <formula formulatype="inline"><tex Notation="TeX">$a < b \in \BBR $</tex></formula>, <formula formulatype="inline"><tex Notation="TeX">$B > 0$</tex></formula>, and <formula formulatype="inline"><tex Notation="TeX">$ {\cal C}([a,b]^{d}, B)$</tex></formula> denotes the set of all convex functions on <formula formulatype="inline"><tex Notation="TeX">$[a, b]^{d}$</tex></formula> that are uniformly bounded by <formula formulatype="inline"> <tex Notation="TeX">$B$</tex></formula>. 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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Convex-constrained Sparse Additive Modeling and Its Extensions (2017, background): “…C j , their “sizes” are quite diﬀerent: the metric entropy of M j (under the ∞ distance) is known to be of the order (cid:15) − 1 [vdVW00, Theorem 2.7.5], while the metric entropy of the class of convex and uniformly bounded functions is of the signiﬁcantly smaller order (cid:15) − 1 / 2 [GS13].”
Global rates of convergence in log-concave density estimation (2014, background): “The main challenge here is that the effective domain of f̃ is unknown, and indeed the shape of this domain affects the bracketing entropy significantly [Gao and Wellner (2015), Guntuboyina and Sen (2013)].”
Near-optimal max-affine estimators for convex regression (2015, background): “= E f (X 0 ) − g(X 0 ) 2 , where X 0 is uniformly distributed on X. Guntuboyina and Sen (2013) proved 4 that c l,d (B//) d/2 ≤ H(, C X,B,L , ·· X0 ) ≤ c u,d (B//) d/2 , for X = [0] [1] d , L ≥ 2/d and ∈ (0, 0,d B], where c l,d , c u,d , 0,d are positive constants depending on the domain dimension d.”
Semiconvex Regression for Metamodeling-Based Optimization (2014, methodology): “Convexity does reduce the data requirements: lower bounds dictated by the −covering number of the set of convex functions scale with p/2 rather than p, like unconstrained functions [30].”
Global risk bounds and adaptation in univariate convex regression (2013, methodology): “Unlike other methods for function estimation such as those based on kernels which depend on tuning parameters such as smoothing bandwidths, the LSE has the obvious advantage of being completely automated.”
Bayesian fractional posteriors (2016, background): “Our fractional posterior framework becomes especially attractive in such problems, since it obviates the need to compute entropy numbers in restricted spaces, which can be a challenging exercise in itself [28].”