Fractional norms and quasinorms do not help to overcome the curse of dimensionality

• URL: http://arxiv.org/abs/2004.14230v1
• Date: Wed, 29 Apr 2020 14:30:12 GMT
• Title: Fractional norms and quasinorms do not help to overcome the curse of dimensionality
• Authors: Evgeny M. Mirkes, Jeza Allohibi, and Alexander N. Gorban
• Abstract summary: Using of the Manhattan distance and even fractional quasinorms lp can help to overcome the curse of dimensionality in classification problems. A systematic comparison shows that the difference of the performance of kNN based on lp for p=2, 1, and 0.5 is statistically insignificant.
• Score: 62.997667081978825
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The curse of dimensionality causes the well-known and widely discussed problems for machine learning methods. There is a hypothesis that using of the Manhattan distance and even fractional quasinorms lp (for p less than 1) can help to overcome the curse of dimensionality in classification problems. In this study, we systematically test this hypothesis. We confirm that fractional quasinorms have a greater relative contrast or coefficient of variation than the Euclidean norm l2, but we also demonstrate that the distance concentration shows qualitatively the same behaviour for all tested norms and quasinorms and the difference between them decays as dimension tends to infinity. Estimation of classification quality for kNN based on different norms and quasinorms shows that a greater relative contrast does not mean better classifier performance and the worst performance for different databases was shown by different norms (quasinorms). A systematic comparison shows that the difference of the performance of kNN based on lp for p=2, 1, and 0.5 is statistically insignificant.

Related papers

• Learning Discretized Neural Networks under Ricci Flow [51.36292559262042]
  We study Discretized Neural Networks (DNNs) composed of low-precision weights and activations. DNNs suffer from either infinite or zero gradients due to the non-differentiable discrete function during training.
  arXiv  Detail & Related papers  (2023-02-07T10:51:53Z)
• Instance-Dependent Label-Noise Learning with Manifold-Regularized Transition Matrix Estimation [172.81824511381984]
  The transition matrix T(x) is unidentifiable under the instance-dependent noise(IDN) We propose assumption on the geometry of T(x) that "the closer two instances are, the more similar their corresponding transition matrices should be" Our method is superior to state-of-the-art approaches for label-noise learning under the challenging IDN.
  arXiv  Detail & Related papers  (2022-06-06T04:12:01Z)
• A New Central Limit Theorem for the Augmented IPW Estimator: Variance Inflation, Cross-Fit Covariance and Beyond [0.9172870611255595]
  Cross-fit inverse probability weighting (AIPW) with cross-fitting is a popular choice in practice. We study this cross-fit AIPW estimator under well-specified outcome regression and propensity score models in a high-dimensional regime. Our work utilizes a novel interplay between three distinct tools--approximate message passing theory, the theory of deterministic equivalents, and the leave-one-out approach.
  arXiv  Detail & Related papers  (2022-05-20T14:17:53Z)
• Divide-and-Conquer Hard-thresholding Rules in High-dimensional Imbalanced Classification [1.0312968200748118]
  We study the impact of imbalance class sizes on the linear discriminant analysis (LDA) in high dimensions. We show that due to data scarcity in one class, referred to as the minority class, the LDA ignores the minority class yielding a maximum misclassification rate. We propose a new construction of a hard-conquering rule based on a divide-and-conquer technique that reduces the large difference between the misclassification rates.
  arXiv  Detail & Related papers  (2021-11-05T07:44:28Z)
• Measure Twice, Cut Once: Quantifying Bias and Fairness in Deep Neural Networks [7.763173131630868]
  We propose two metrics to quantitatively evaluate the class-wise bias of two models in comparison to one another. By evaluating the performance of these new metrics and by demonstrating their practical application, we show that they can be used to measure fairness as well as bias.
  arXiv  Detail & Related papers  (2021-10-08T22:35:34Z)
• Optimization Variance: Exploring Generalization Properties of DNNs [83.78477167211315]
  The test error of a deep neural network (DNN) often demonstrates double descent. We propose a novel metric, optimization variance (OV), to measure the diversity of model updates.
  arXiv  Detail & Related papers  (2021-06-03T09:34:17Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization [39.35822033674126]
  We study binary linear classification under a generative Gaussian mixture model. We derive novel non-asymptotic bounds on the classification error of the latter. Our results extend to a noisy model with constant probability noise flips.
  arXiv  Detail & Related papers  (2020-11-18T07:59:55Z)
• Telescoping Density-Ratio Estimation [21.514983459970903]
  We introduce a new framework, telescoping density-ratio estimation (TRE) TRE enables the estimation of ratios between highly dissimilar densities in high-dimensional spaces. Our experiments demonstrate that TRE can yield substantial improvements over existing single-ratio methods.
  arXiv  Detail & Related papers  (2020-06-22T12:55:06Z)
• Learning from Aggregate Observations [82.44304647051243]
  We study the problem of learning from aggregate observations where supervision signals are given to sets of instances. We present a general probabilistic framework that accommodates a variety of aggregate observations. Simple maximum likelihood solutions can be applied to various differentiable models.
  arXiv  Detail & Related papers  (2020-04-14T06:18:50Z)

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.