Report
Universal coding, intrinsic volumes, and metric complexity
| العنوان: | Universal coding, intrinsic volumes, and metric complexity |
|---|---|
| المؤلفون: | Mourtada, Jaouad |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics Statistics |
| مصطلحات موضوعية: | Computer Science - Information Theory, Mathematics - Metric Geometry, Mathematics - Statistics Theory, Statistics - Machine Learning, 94A29, 52A39, 62C20, 62B10, 60G15 |
| الوصف: | We study sequential probability assignment in the Gaussian setting, where the goal is to predict, or equivalently compress, a sequence of real-valued observations almost as well as the best Gaussian distribution with mean constrained to a given subset of $\mathbf{R}^n$. First, in the case of a convex constraint set $K$, we express the hardness of the prediction problem (the minimax regret) in terms of the intrinsic volumes of $K$; specifically, it equals the logarithm of the Wills functional from convex geometry. We then establish a comparison inequality for the Wills functional in the general nonconvex case, which underlines the metric nature of this quantity and generalizes the Slepian-Sudakov-Fernique comparison principle for the Gaussian width. Motivated by this inequality, we characterize the exact order of magnitude of the considered functional for a general nonconvex set, in terms of global covering numbers and local Gaussian widths. This implies metric isomorphic estimates for the log-Laplace transform of the intrinsic volume sequence of a convex body. As part of our analysis, we also characterize the minimax redundancy for a general constraint set. We finally relate and contrast our findings with classical asymptotic results in information theory. Comment: 51 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2303.07279 |
| رقم الانضمام: | edsarx.2303.07279 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |