Covering numbers of L_p-balls of convex functions and sets

DOI10.1007/S00365-015-9279-1MaRDI QIDQ5962919zbMATH OpenOpenAlexFDO

Authors Adityanand Guntuboyina

Publication date 25 February 2016

Published in Constructive Approximation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.6922

zbMATH Keywords

convex functionscovering numbersKolmogorov \(\varepsilon\)-entropymetric entropy

Mathematics Subject Classification ID

Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Duality and reflexivity in normed linear and Banach spaces (46B10) Convex sets in (2) dimensions (including convex curves) (52A10) Convex functions and convex programs in convex geometry (52A41) Entropy in general topology (54C70)

Abstract: We prove bounds for the covering numbers of classes of convex functions and convex sets in Euclidean space. Previous results require the underlying convex functions or sets to be uniformly bounded. We relax this assumption and replace it with weaker integral constraints. Existing results can be recovered as special cases of our results.

Review text

This paper is a natural continuation of some previous work by the author, jointly with B. Sen (see the references). It is devoted to the study of bounds for covering numbers of some classes of convex functions and convex sets of Euclidean spaces. The main contribution is that the author is able to relax a strong hypothesis on uniform boundedness to a weaker one, which involves certain integral constraints. The study of metric entropy and covering numbers, which has its roots in Kolmogorov's work in the thirties of the XXth century, is an important part of approximation theory (and functional analysis) and many works have been devoted to the finding of precise constraints to the distinct entropy numbers that can be defined. It is in fact a tricky part of analysis. To contribute here with new ideas is not an easy task. This paper has reached, from the reviewer's point of view, a new mark in this area of research. Just to see the flavor of the main results obtained in this paper, I include here one of them: {Theorem.} Fix \(d\geq 1\) and \(1\leq p\leq q\leq \infty\). There exists a positive constant \(\varepsilon_0\), depending only on \(d,p\), and \(q\), such that \(\log M(C_p(I,B),\varepsilon,L_q(I))=\infty \) whenever \(\varepsilon \leq B \varepsilon_0 (b_1-a_1)^{1/q-1/p}\cdots (b_d-a_d)^{1/q-1/p}\). Here \(I=[a_1,b_1]\times \cdots [a_d,b_d]\), \(B\) is a positive constant, \(C_p(I,B)\) is the set of all convex functions on \(I\) that satisfy the integral inequality \(\int_I|f|^p\leq B^p\).

Recommendations

• Covering numbers for real-valued function classes
• Functional covering numbers
• Weighted covering numbers of convex sets
• Estimates of covering numbers of convex sets with slowly decaying orthogonal subsets
• Bracketing numbers of convex and m-monotone functions on polytopes

Cites work

• Convex Analysis
• Covering Numbers for Convex Functions
• epsilon-entropy of convex sets and functions
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• Kolmogorov entropy for classes of convex functions
• Metric entropy of some classes of sets with differentiable boundaries

Cited in

(8)

• Estimates of covering numbers
• Entropy and the combinatorial dimension
• Entropy of convex functions on \(\mathbb R^d\)
• Fractional covers for convolution products
• Bracketing numbers of convex and m-monotone functions on polytopes
• Estimates of covering numbers of convex sets with slowly decaying orthogonal subsets
• scientific article; zbMATH DE number 3849250 (Why is no real title available?)
• Covering numbers for real-valued function classes

This page was built for publication: Covering numbers of \(L_{p}\)-balls of convex functions and sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962919)