Compact Nonlinear Maps and Circulant Extensions

Abstract

Kernel approximation via nonlinear random feature maps is widely used in speeding up kernel machines. There are two main challenges for the conventional kernel approximation methods. First, before performing kernel approximation, a good kernel has to be chosen. Picking a good kernel is a very challenging problem in itself. Second, high-dimensional maps are often required in order to achieve good performance. This leads to high computational cost in both generating the nonlinear maps, and in the subsequent learning and prediction process. In this work, we propose to optimize the nonlinear maps directly with respect to the classification objective in a data-dependent fashion. The proposed approach achieves kernel approximation and kernel learning in a joint framework. This leads to much more compact maps without hurting the performance. As a by-product, the same framework can also be used to achieve more compact kernel maps to approximate a known kernel. We also introduce Circulant Nonlinear Maps, which uses a circulant-structured projection matrix to speed up the nonlinear maps for high-dimensional data.

References in corpus (6)

• A Divide-and-Conquer Solver for Kernel Support Vector Machines
• Circulant Binary Embedding
• Compact Random Feature Maps
• Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels
• An exploration of parameter redundancy in deep networks with circulant projections
• New bounds for circulant Johnson-Lindenstrauss embeddings

Cited by in corpus (13)

• An exploration of parameter redundancy in deep networks with circulant projections
• Recycling Randomness with Structure for Sublinear time Kernel Expansions
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps
• Tensor machines for learning target-specific polynomial features
• On Binary Embedding using Circulant Matrices
• On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees
• Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features
• Data Dependent Kernel Approximation using Pseudo Random Fourier Features
• ORCCA: Optimal Randomized Canonical Correlation Analysis
• Building Compact and Robust Deep Neural Networks with Toeplitz Matrices
• Learning Random Fourier Features by Hybrid Constrained Optimization
• HD-cos Networks: Efficient Neural Architectures for Secure Multi-Party Computation