Universal coding, intrinsic volumes, and metric complexity

• URL: http://arxiv.org/abs/2303.07279v2
• Date: Mon, 07 Apr 2025 13:06:40 GMT
• Title: Universal coding, intrinsic volumes, and metric complexity
• Authors: Jaouad Mourtada,
• Abstract summary: In this assignment, the goal is to predict, or equivalently, a sequence of real-valued observations almost as well as the best distribution with mean-valued subsets of $mathbbRn.<n>As part of our analysis, we also characterize the minimax redundancy for a general constraint set.<n>We contrast our findings with classical results in information theory.
• Score: 3.4265828682659705
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\mathbb{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 sharp estimates, of metric nature, on 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.

Related papers

• Evolution of Gaussians in the Hellinger-Kantorovich-Boltzmann gradient flow [44.500314182711236]
  We derive explicit ordinary equations govern the evolution of mean, covariance, and mass under HK-Boltzmann flow. We demonstrate exponential convergence to equilibrium through constructing a gradient structure associated with a Polyak-Lojasiewicz-type inequalities. We extend our analysis to non-Gaussian targets exhibiting strong log-lambda-concavity.
  arXiv  Detail & Related papers  (2025-04-29T03:54:56Z)
• Statistical Inference in Classification of High-dimensional Gaussian Mixture [1.2354076490479515]
  We investigate the behavior of a general class of regularized convex classifiers in the high-dimensional limit. Our focus is on the generalization error and variable selection properties of the estimators.
  arXiv  Detail & Related papers  (2024-10-25T19:58:36Z)
• Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
  This paper presents a new performance bound for estimation problems where the parameter to estimate lies in a smooth manifold. It induces a geometry for the parameter manifold, as well as an intrinsic notion of the estimation error measure.
  arXiv  Detail & Related papers  (2023-11-08T15:17:13Z)
• Regular Variation in Hilbert Spaces and Principal Component Analysis for Functional Extremes [1.6734018640023431]
  We place ourselves in a Peaks-Over-Threshold framework where a functional extreme is defined as an observation $X$ whose $L2$-norm $|X|$ is comparatively large. Our goal is to propose a dimension reduction framework resulting into finite dimensional projections for such extreme observations.
  arXiv  Detail & Related papers  (2023-08-02T09:12:03Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• Efficient CDF Approximations for Normalizing Flows [64.60846767084877]
  We build upon the diffeomorphic properties of normalizing flows to estimate the cumulative distribution function (CDF) over a closed region. Our experiments on popular flow architectures and UCI datasets show a marked improvement in sample efficiency as compared to traditional estimators.
  arXiv  Detail & Related papers  (2022-02-23T06:11:49Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  We provide a framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2022-02-02T20:11:33Z)
• Generalization in Supervised Learning Through Riemannian Contraction [4.3604518673788135]
  In a supervised learning setting, we show that if an metric 0 is contracting in someian rate $lambda, it is uniformly uniformly rate with $math. The results hold for gradient and deterministic loss surfaces, in both continuous and stable $-time. They can be shown to be optimal in certain linear settings, such as over Descent$ convex or strongly convex loss surfaces.
  arXiv  Detail & Related papers  (2022-01-17T23:08:47Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation [17.199023009789308]
  The Expected assumption of SGD (SGD) is being used routinely for non-artisan functions. In this paper, we show a paradigms for convergence to a smooth non-linear setting. We also provide theoretical guarantees for different step-size conditions.
  arXiv  Detail & Related papers  (2020-06-18T07:05:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.