Adaptive Metric Dimensionality Reduction

2013/02/12 by Lee-Ad Gottlieb, Gottlieb, Lee-Ad, Aryeh Kontorovich +3 · 1 citation
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.DS #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1302.2752

arxiv created 2015/03/25 · arxiv updated 2015/03/26

Abstract

We study adaptive data-dependent dimensionality reduction in the context of supervised learning in general metric spaces. Our main statistical contribution is a generalization bound for Lipschitz functions in metric spaces that are doubling, or nearly doubling. On the algorithmic front, we describe an analogue of PCA for metric spaces: namely an efficient procedure that approximates the data's intrinsic dimension, which is often much lower than the ambient dimension. Our approach thus leverages the dual benefits of low dimensionality: (1) more efficient algorithms, e.g., for proximity search, and (2) more optimistic generalization bounds.

Cited by

• Private Evolution Converges

Related

• Efficient Classification for Metric Data
• Learning Low-Dimensional Metrics
• Dimension Free Generalization Bounds for Non Linear Metric Learning
• Compressive Mahalanobis Metric Learning Adapts to Intrinsic Dimension
• Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces