Publications

We develop new techniques for computing the metric entropy of ellipsoids—with polynomially decaying semi-axes—in Banach spaces. Besides leading to a unified and comprehensive framework, these tools deliver numerous novel results as well as substantial improvements and generalizations of classical results. Specifically, we characterize the constant in the leading term in the asymptotic expansion of the metric entropy of $p$-ellipsoids with respect to $q$-norm, for arbitrary $p,q \in[1,\infty]$, to date known only in the case $p= q = 2$. Moreover, for $p= q = 2$, we improve upon classical results by specifying the second-order term in the asymptotic expansion. In the case $p= q= \infty$, we obtain a complete, as opposed to asymptotic, characterization of metric entropy and explicitly construct optimal coverings. To the best of our knowledge, this is the first exact characterization of the metric entropy of an infinite-dimensional body. Application of our general results to function classes yields an improvement of the asymptotic expansion of the metric entropy of unit balls in Sobolev spaces and identifies the dependency of the metric entropy of unit balls in Besov spaces on the domain of the functions in the class. Sharp results on the metric entropy of function classes find application, e.g., in machine learning, where they allow to specify the minimum required size of deep neural networks for function approximation, nonparametric regression, and classification over these function classes.

We characterize the entropy and minimax risk of a broad class of compact pseudodifferential operators. Under suitable decay and regularity conditions on the symbol, we combine a Weyl-type asymptotic relation between the eigenvalue-counting function and the phase-space volume of the symbol with a general correspondence between spectral quantities, entropy, and minimax risk for compact operators. This approach yields explicit asymptotic formulae for both entropy and minimax risk directly in terms of the symbol. As an application, we derive sharp entropy and minimax risk asymptotics for unit balls in Sobolev spaces on unbounded domains, thereby extending Pinsker’s theorem for Sobolev classes beyond the bounded-domain setting, and showing that the sharp asymptotic constants are determined by phase-space geometry rather than domain geometry.

We study how large an $\ell^2$ ellipsoid is by introducing type-$\tau$ integrals that capture the average decay of its semi-axes. These integrals turn out to be closely related to standard complexity measures: we show that the metric entropy of the ellipsoid is asymptotically equivalent to the type-1 integral, and that the minimax risk in non-parametric estimation is asymptotically determined by the type-2 and type-3 integrals. This allows us to retrieve and sharpen classical results about metric entropy and minimax risk of ellipsoids through a systematic analysis of the type-$\tau$ integrals, and yields an explicit formula linking the two. As an application, we improve on the best-known characterization of the metric entropy of the Sobolev ellipsoid, and extend Pinsker’s Sobolev theorem in two ways: (i) to any bounded open domain in arbitrary finite dimension, and (ii) by providing the second-order term in the asymptotic expansion of the minimax risk.

We derive a precise general relation between the entropy of a compact operator and its eigenvalues. It is then shown how this result along with the underlying philosophy can be applied to improve substantially on the best known characterizations of the entropy of the Landau-PollakSlepian operator and the metric entropy of unit balls in Sobolev spaces.

This thesis is devoted to the derivation of sharp one- and two-term asymptotic characterizations for the metric entropy of ellipsoids in infinite-dimensional spaces.

We first focus on ellipsoids defined by $\ell^p$-constraints in $\ell^q$-sequence spaces–for arbitrary values of $p$ and $q\in[1,\infty]$–with semi-axes that decay polynomially or exponentially. To study their metric entropy, we develop a general methodology that combines standard tools with new techniques, such as volume and density arguments, truncation methods, and block decomposition. Upon application of this general methodology, we obtain sharp characterizations of the asymptotic behavior of the metric entropy of ellipsoids in sequence spaces, thereby improving in multiple ways on best-known results in the literature.

Our results for ellipsoids in sequence spaces extend to a variety of common function classes, including periodic complex analytic functions, complex analytic functions bounded on a disk, functions of exponential type, transfer functions in LTI systems, and a broad range of differentiability classes. In particular, for Lipschitz, Hölder, Sobolev, and Besov functions on bounded domains, our results capture the exact dependence of the first-order term of the asymptotic behavior of the metric entropy on the volume of the domain. In fact, for Sobolev functions, we derive the exact first- and second-order terms in the asymptotic behavior of the metric entropy, incidentally showing that the second-order term is proportional to the perimeter of the domain.

Adopting a dual perspective, we also characterize the entropy of compact linear operators. In particular, we derive a precise one- and two-term asymptotic relation between a compact operator’s entropy and its eigenvalues. This spectral approach provides new insights into the Landau-Pollak-Slepian theory and extends the aforementioned results on Sobolev spaces to the more general framework of pseudo-differential operators.

Finally, we apply the results of this thesis to learning theory. Specifically, we first establish a correspondence between the asymptotic behavior of the minimax risk in the Gaussian sequence model and that of metric entropy, which allows for the transfer of the one- and two-term asymptotics between the two. To illustrate the importance of this correspondence, we use it to derive the second-order term in Pinsker’s theorem for Sobolev spaces. Furthermore, our derivations allow us to introduce a natural metric-entropy-based optimality criterion for estimators and learning algorithms, which we argue to be satisfied by the stochastic gradient descent algorithm in neural network theory.

We present a new methodology for the characterization of the metric entropy of infinite-dimensional ellipsoids with exponentially decaying semi-axes. This procedure does not rely on the explicit construction of coverings or packings and provides a unified framework for the derivation of the metric entropy of a wide variety of analytic function classes, such as periodic functions analytic on a strip, analytic functions bounded on a disk, and functions of exponential type. In each of these cases, our results improve upon the best known results in the literature.