On Linear Separability under Linear Compression with Applications to Hard Support Vector Machine

• URL: http://arxiv.org/abs/2202.01118v1
• Date: Wed, 2 Feb 2022 16:23:01 GMT
• Title: On Linear Separability under Linear Compression with Applications to Hard Support Vector Machine
• Authors: Paul McVay, Dr. Tie Liu, Dr. Krishna Narayanan
• Abstract summary: We show that linear separability is maintained as long as the distortion of the inner products is smaller than the squared margin of the original data-generating distribution. As applications, we derive bounds on the (i) compression length of random sub-Gaussian matrices; and (ii) generalization error for compressive learning with hard-SVM.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper investigates the theoretical problem of maintaining linear separability of the data-generating distribution under linear compression. While it has been long known that linear separability may be maintained by linear transformations that approximately preserve the inner products between the domain points, the limit to which the inner products are preserved in order to maintain linear separability was unknown. In this paper, we show that linear separability is maintained as long as the distortion of the inner products is smaller than the squared margin of the original data-generating distribution. The proof is mainly based on the geometry of hard support vector machines (SVM) extended from the finite set of training examples to the (possibly) infinite domain of the data-generating distribution. As applications, we derive bounds on the (i) compression length of random sub-Gaussian matrices; and (ii) generalization error for compressive learning with hard-SVM.

Related papers

• Projected Tensor-Tensor Products for Efficient Computation of Optimal Multiway Data Representations [0.0]
  We propose a new projected tensor-tensor product that relaxes the invertibility restriction to reduce computational overhead. We provide theory to prove the matrix mimeticity and the optimality of compressed representations within the projected product framework.
  arXiv  Detail & Related papers  (2024-09-28T16:29:54Z)
• Fading memory and the convolution theorem [5.248564173595025]
  topological and analytical notions of continuity and fading memory for causal and time-invariant filters are introduced. Main theorem shows that the availability of convolution representations can be characterized, at least when the codomain is finite-dimensional. When the input space and the codomain of a linear functional are Hilbert spaces, it is shown that minimal continuity and the minimal fading memory property guarantee the existence of interesting embeddings of the associated kernel Hilbert spaces.
  arXiv  Detail & Related papers  (2024-08-14T09:06:25Z)
• Separation capacity of linear reservoirs with random connectivity matrix [0.0]
  We show the expected separation capacity of random linear reservoirs is fully characterised by the spectral decomposition of an associated generalised matrix of moments. In the symmetric case, we prove that the separation capacity always deteriorates with time. In the i.i.d. case, we establish that optimal separation with large reservoirs is consistently achieved when the entries of the reservoir matrix are scaled with the exact factor $1/sqrtN$.
  arXiv  Detail & Related papers  (2024-04-26T14:10:55Z)
• Linear Regression on Manifold Structured Data: the Impact of Extrinsic Geometry on Solutions [4.8234611688915665]
  We study linear regression applied to data structured on a manifold. We analyze the impact of the manifold's curvatures on the uniqueness of the regression solution.
  arXiv  Detail & Related papers  (2023-07-05T17:51:26Z)
• Learning Linear Causal Representations from Interventions under General Nonlinear Mixing [52.66151568785088]
  We prove strong identifiability results given unknown single-node interventions without access to the intervention targets. This is the first instance of causal identifiability from non-paired interventions for deep neural network embeddings.
  arXiv  Detail & Related papers  (2023-06-04T02:32:12Z)
• Theoretical Connection between Locally Linear Embedding, Factor Analysis, and Probabilistic PCA [13.753161236029328]
  Linear Embedding (LLE) is a nonlinear spectral dimensionality reduction and manifold learning method. In this work, we look at the linear reconstruction step from a perspective where it is assumed that every data point is conditioned on its linear reconstruction weights as latent factors.
  arXiv  Detail & Related papers  (2022-03-25T21:07:20Z)
• Robust Differentiable SVD [117.35644933471401]
  Eigendecomposition of symmetric matrices is at the heart of many computer vision algorithms. Instability arises in the presence of eigenvalues that are close to each other. We show that the Taylor expansion of the SVD gradient is theoretically equivalent to the gradient obtained using PI without relying on an iterative process.
  arXiv  Detail & Related papers  (2021-04-08T15:04:15Z)
• Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps [95.62172085878132]
  Eigenvector perturbation analysis plays a vital role in various statistical data science applications. We develop a suite of statistical theory that characterizes the perturbation of arbitrary linear functions of an unknown eigenvector. In order to mitigate a non-negligible bias issue inherent to the natural "plug-in" estimator, we develop de-biased estimators.
  arXiv  Detail & Related papers  (2021-04-07T17:55:10Z)
• Sparse Quantized Spectral Clustering [85.77233010209368]
  We exploit tools from random matrix theory to make precise statements about how the eigenspectrum of a matrix changes under such nonlinear transformations. We show that very little change occurs in the informative eigenstructure even under drastic sparsification/quantization.
  arXiv  Detail & Related papers  (2020-10-03T15:58:07Z)
• From deep to Shallow: Equivalent Forms of Deep Networks in Reproducing Kernel Krein Space and Indefinite Support Vector Machines [63.011641517977644]
  We take a deep network and convert it to an equivalent (indefinite) kernel machine. We then investigate the implications of this transformation for capacity control and uniform convergence. Finally, we analyse the sparsity properties of the flat representation, showing that the flat weights are (effectively) Lp-"norm" regularised with 0p1.
  arXiv  Detail & Related papers  (2020-07-15T03:21:35Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  We introduce an eigendecomposition-free approach to training a deep network. We show that our approach is much more robust than explicit differentiation of the eigendecomposition. Our method has better convergence properties and yields state-of-the-art results.
  arXiv  Detail & Related papers  (2020-04-15T04:29:34Z)

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.