Optimality and complexity of classification by random projection
- URL: http://arxiv.org/abs/2108.06339v3
- Date: Thu, 18 May 2023 15:51:02 GMT
- Title: Optimality and complexity of classification by random projection
- Authors: Mireille Boutin, Evzenie Coupkova
- Abstract summary: The generalization error of a classifier is related to the complexity of the set of functions among which the classifier is chosen.
We show that this type of classifier is extremely flexible, as it is likely to approximate an arbitrary precision.
In particular, given full knowledge of the class conditional densities, the error of these low-complexity classifiers would converge to the optimal (Bayes) error as k and n go to infinity.
- Score: 1.5229257192293197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The generalization error of a classifier is related to the complexity of the
set of functions among which the classifier is chosen. We study a family of
low-complexity classifiers consisting of thresholding a random one-dimensional
feature. The feature is obtained by projecting the data on a random line after
embedding it into a higher-dimensional space parametrized by monomials of order
up to k. More specifically, the extended data is projected n-times and the best
classifier among those n, based on its performance on training data, is chosen.
We show that this type of classifier is extremely flexible, as it is likely to
approximate, to an arbitrary precision, any continuous function on a compact
set as well as any boolean function on a compact set that splits the support
into measurable subsets. In particular, given full knowledge of the class
conditional densities, the error of these low-complexity classifiers would
converge to the optimal (Bayes) error as k and n go to infinity. On the other
hand, if only a training dataset is given, we show that the classifiers will
perfectly classify all the training points as k and n go to infinity. We also
bound the generalization error of our random classifiers. In general, our
bounds are better than those for any classifier with VC dimension greater than
O (ln n) . In particular, our bounds imply that, unless the number of
projections n is extremely large, there is a significant advantageous gap
between the generalization error of the random projection approach and that of
a linear classifier in the extended space. Asymptotically, as the number of
samples approaches infinity, the gap persists for any such n. Thus, there is a
potentially large gain in generalization properties by selecting parameters at
random, rather than optimization.
Related papers
- Classification Using Global and Local Mahalanobis Distances [1.7811840395202345]
We propose a novel semi-parametric classifier based on Mahalanobis distances of an observation from the competing classes.
Our tool is a generalized additive model with the logistic link function that uses these distances as features to estimate the posterior probabilities of the different classes.
arXiv Detail & Related papers (2024-02-13T08:22:42Z) - Precise Asymptotic Generalization for Multiclass Classification with
Overparameterized Linear Models [4.093769373833101]
We resolve the conjecture posed in Subramanian et al.'22, where the number of data points, features, and classes all grow together.
Our new lower bounds are akin to an information-theoretic strong converse: they establish that the misclassification rate goes to 0 or 1ally.
The key to our tight analysis is a new variant of the Hanson-Wright inequality which is broadly useful for multiclass problems with sparse labels.
arXiv Detail & Related papers (2023-06-23T00:59:15Z) - Soft-margin classification of object manifolds [0.0]
A neural population responding to multiple appearances of a single object defines a manifold in the neural response space.
The ability to classify such manifold is of interest, as object recognition and other computational tasks require a response that is insensitive to variability within a manifold.
Soft-margin classifiers are a larger class of algorithms and provide an additional regularization parameter used in applications to optimize performance outside the training set.
arXiv Detail & Related papers (2022-03-14T12:23:36Z) - Local versions of sum-of-norms clustering [77.34726150561087]
We show that our method can separate arbitrarily close balls in the ball model.
We prove a quantitative bound on the error incurred in the clustering of disjoint connected sets.
arXiv Detail & Related papers (2021-09-20T14:45:29Z) - 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) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
We propose a generalization extraient spaces which converges to a stationary point.
The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
arXiv Detail & Related papers (2020-10-31T21:35:42Z) - On Supervised Classification of Feature Vectors with Independent and
Non-Identically Distributed Elements [10.52087851034255]
We investigate the problem of classifying feature vectors with mutually independent but non-identically distributed elements.
We show that the error probability goes to zero as the length of the feature vectors grows, even when there is only one training feature vector per label available.
arXiv Detail & Related papers (2020-08-01T06:49:50Z) - Random extrapolation for primal-dual coordinate descent [61.55967255151027]
We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function.
We show almost sure convergence of the sequence and optimal sublinear convergence rates for the primal-dual gap and objective values, in the general convex-concave case.
arXiv Detail & Related papers (2020-07-13T17:39:35Z) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers.
We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model.
Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
arXiv Detail & Related papers (2020-06-22T21:12:31Z) - Asymptotic Analysis of an Ensemble of Randomly Projected Linear
Discriminants [94.46276668068327]
In [1], an ensemble of randomly projected linear discriminants is used to classify datasets.
We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator.
We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
arXiv Detail & Related papers (2020-04-17T12:47:04Z) - Intrinsic Dimension Estimation via Nearest Constrained Subspace
Classifier [7.028302194243312]
A new subspace based classifier is proposed for supervised classification or intrinsic dimension estimation.
The distribution of the data in each class is modeled by a union of a finite number ofaffine subspaces of the feature space.
The proposed method is a generalisation of classical NN (Nearest Neighbor), NFL (Nearest Feature Line) and has a close relationship to NS (Nearest Subspace)
The proposed classifier with an accurately estimated dimension parameter generally outperforms its competitors in terms of classification accuracy.
arXiv Detail & Related papers (2020-02-08T20:54:42Z)
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.