Timezone: »
Poster
Rehashing Kernel Evaluation in High Dimensions
Paris Siminelakis · Kexin Rong · Peter Bailis · Moses Charikar · Philip Levis
Kernel methods are effective but do not scale well to large scale data, especially in high dimensions where the geometric data structures used to accelerate kernel evaluation suffer from the curse of dimensionality.
Recent theoretical advances have proposed fast kernel evaluation algorithms leveraging hashing techniques with worst-case asymptotic improvements. However, these advances are largely confined to the theoretical realm due to concerns such as super-linear preprocessing time and diminishing gains in non-worst case datasets. In this paper, we close the gap between theory and practice by addressing these challenges via provable and practical procedures for adaptive sample size selection, preprocessing time reduction, and refined variance bounds that quantify the data-dependent performance of random sampling and hashing-based kernel evaluation methods. Our experiments show that these new tools offer up to $10\times$ improvement in evaluation time on a range of synthetic and real-world datasets.
Author Information
Paris Siminelakis (Stanford University)
Kexin Rong (Stanford University)
Peter Bailis (Stanford University)
Moses Charikar (Stanford University)
Philip Levis (Stanford University)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Oral: Rehashing Kernel Evaluation in High Dimensions »
Tue Jun 11th 09:40 -- 10:00 PM Room Room 101
More from the Same Authors
-
2019 Poster: LIT: Learned Intermediate Representation Training for Model Compression »
Animesh Koratana · Daniel Kang · Peter Bailis · Matei Zaharia -
2019 Oral: LIT: Learned Intermediate Representation Training for Model Compression »
Animesh Koratana · Daniel Kang · Peter Bailis · Matei Zaharia -
2019 Poster: Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data »
Vatsal Sharan · Kai Sheng Tai · Peter Bailis · Gregory Valiant -
2019 Poster: Equivariant Transformer Networks »
Kai Sheng Tai · Peter Bailis · Gregory Valiant -
2019 Oral: Equivariant Transformer Networks »
Kai Sheng Tai · Peter Bailis · Gregory Valiant -
2019 Oral: Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data »
Vatsal Sharan · Kai Sheng Tai · Peter Bailis · Gregory Valiant -
2018 Poster: Local Density Estimation in High Dimensions »
Xian Wu · Moses Charikar · Vishnu Natchu -
2018 Oral: Local Density Estimation in High Dimensions »
Xian Wu · Moses Charikar · Vishnu Natchu -
2018 Poster: Hierarchical Clustering with Structural Constraints »
Evangelos Chatziafratis · Rad Niazadeh · Moses Charikar -
2018 Oral: Hierarchical Clustering with Structural Constraints »
Evangelos Chatziafratis · Rad Niazadeh · Moses Charikar