Is margin preserved after random projection?

Abstract

Random projections have been applied in many machine learning algorithms. However, whether margin is preserved after random projection is non-trivial and not well studied. In this paper we analyse margin distortion after random projection, and give the conditions of margin preservation for binary classification problems. We also extend our analysis to margin for multiclass problems, and provide theoretical bounds on multiclass margin on the projected data.

ICML2012

Cited by in corpus (13)

• Recovering the Optimal Solution by Dual Random Projection
• Random Projections on Manifolds of Symmetric Positive Definite Matrices for Image Classification
• Theory of Dual-sparse Regularized Randomized Reduction
• An Analysis of Random Projections in Cancelable Biometrics
• Billion-scale Network Embedding with Iterative Random Projection
• Friction from Reflectance: Deep Reflectance Codes for Predicting Physical Surface Properties from One-Shot In-Field Reflectance
• Regularizing Neural Networks via Minimizing Hyperspherical Energy
• Compressed Subspace Learning Based on Canonical Angle Preserving Property
• Random Projections for Linear Support Vector Machines
• The Effectiveness of Johnson-Lindenstrauss Transform for High Dimensional Optimization With Adversarial Outliers, and the Recovery
• Sparse Learning for Large-scale and High-dimensional Data: A Randomized Convex-concave Optimization Approach
• Learning Data-adaptive Nonparametric Kernels
• On Learning from Ghost Imaging without Imaging