Robust and Fast Measure of Information via Low-rank Representation

• URL: http://arxiv.org/abs/2211.16784v1
• Date: Wed, 30 Nov 2022 06:49:56 GMT
• Title: Robust and Fast Measure of Information via Low-rank Representation
• Authors: Yuxin Dong and Tieliang Gong and Shujian Yu and Hong Chen and Chen Li
• Abstract summary: We propose a novel measure of information, termed low-rank matrix-based R'enyi's entropy. Low-rank variant is more sensitive to informative perturbations induced by changes in underlying distributions. We conduct large-scale experiments to evaluate the effectiveness of this new information measure.
• Score: 20.1194871649588
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The matrix-based R\'enyi's entropy allows us to directly quantify information measures from given data, without explicit estimation of the underlying probability distribution. This intriguing property makes it widely applied in statistical inference and machine learning tasks. However, this information theoretical quantity is not robust against noise in the data, and is computationally prohibitive in large-scale applications. To address these issues, we propose a novel measure of information, termed low-rank matrix-based R\'enyi's entropy, based on low-rank representations of infinitely divisible kernel matrices. The proposed entropy functional inherits the specialty of of the original definition to directly quantify information from data, but enjoys additional advantages including robustness and effective calculation. Specifically, our low-rank variant is more sensitive to informative perturbations induced by changes in underlying distributions, while being insensitive to uninformative ones caused by noises. Moreover, low-rank R\'enyi's entropy can be efficiently approximated by random projection and Lanczos iteration techniques, reducing the overall complexity from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2 s)$ or even $\mathcal{O}(ns^2)$, where $n$ is the number of data samples and $s \ll n$. We conduct large-scale experiments to evaluate the effectiveness of this new information measure, demonstrating superior results compared to matrix-based R\'enyi's entropy in terms of both performance and computational efficiency.

Related papers

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data [4.971690889257356]
  We introduce an adaptation of the alternating minimization-descent scheme proposed by Collins and Nayer and Vaswani. We show that vanilla alternating-minimization descent fails catastrophically even for iid, but mildly non-isotropic data. Our analysis unifies and generalizes prior work, and provides a flexible framework for a wider range of applications.
  arXiv  Detail & Related papers  (2023-08-08T17:56:20Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  Existing theories on deep nonparametric regression have shown that when the input data lie on a low-dimensional manifold, deep neural networks can adapt to intrinsic data structures. This paper introduces a relaxed assumption that input data are concentrated around a subset of $mathbbRd$ denoted by $mathcalS$, and the intrinsic dimension $mathcalS$ can be characterized by a new complexity notation -- effective Minkowski dimension.
  arXiv  Detail & Related papers  (2023-06-26T17:13:31Z)
• Distributed Semi-Supervised Sparse Statistical Inference [6.685997976921953]
  A debiased estimator is a crucial tool in statistical inference for high-dimensional model parameters. Traditional methods require computing a debiased estimator on every machine. An efficient multi-round distributed debiased estimator, which integrates both labeled and unlabelled data, is developed.
  arXiv  Detail & Related papers  (2023-06-17T17:30:43Z)
• High-Dimensional Smoothed Entropy Estimation via Dimensionality Reduction [14.53979700025531]
  We consider the estimation of the differential entropy $h(X+Z)$ via $n$ independently and identically distributed samples of $X$. Under the absolute-error loss, the above problem has a parametric estimation rate of $fraccDsqrtn$. We overcome this exponential sample complexity by projecting $X$ to a low-dimensional space via principal component analysis (PCA) before the entropy estimation.
  arXiv  Detail & Related papers  (2023-05-08T13:51:48Z)
• Score-based Diffusion Models in Function Space [140.792362459734]
  Diffusion models have recently emerged as a powerful framework for generative modeling. We introduce a mathematically rigorous framework called Denoising Diffusion Operators (DDOs) for training diffusion models in function space. We show that the corresponding discretized algorithm generates accurate samples at a fixed cost independent of the data resolution.
  arXiv  Detail & Related papers  (2023-02-14T23:50:53Z)
• Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
  We develop random approximations for integer order $alpha$ cases and series approximations for non-integer $alpha$ cases. Large-scale simulations and real-world applications validate the effectiveness of the developed approximations.
  arXiv  Detail & Related papers  (2022-05-16T02:24:52Z)
• Learning Summary Statistics for Bayesian Inference with Autoencoders [58.720142291102135]
  We use the inner dimension of deep neural network based Autoencoders as summary statistics. To create an incentive for the encoder to encode all the parameter-related information but not the noise, we give the decoder access to explicit or implicit information that has been used to generate the training data.
  arXiv  Detail & Related papers  (2022-01-28T12:00:31Z)
• Computationally Efficient Approximations for Matrix-based Renyi's Entropy [33.72108955447222]
  Recently developed matrix based Renyi's entropy enables measurement of information in data. computation of such quantity involves the trace operator on a PSD matrix $G$ to power $alpha$(i.e., $tr(Galpha)$. We present computationally efficient approximations to this new entropy functional that can reduce its complexity to even significantly less than $O(n2)$.
  arXiv  Detail & Related papers  (2021-12-27T14:59:52Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Evaluating representations by the complexity of learning low-loss predictors [55.94170724668857]
  We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learning a predictor on top of the representation that achieves low loss on a task of interest.
  arXiv  Detail & Related papers  (2020-09-15T22:06:58Z)

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.