Orthogonal Random Features

Abstract

We present an intriguing discovery related to Random Fourier Features: in Gaussian kernel approximation, replacing the random Gaussian matrix by a properly scaled random orthogonal matrix significantly decreases kernel approximation error. We call this technique Orthogonal Random Features (ORF), and provide theoretical and empirical justification for this behavior. Motivated by this discovery, we further propose Structured Orthogonal Random Features (SORF), which uses a class of structured discrete orthogonal matrices to speed up the computation. The method reduces the time cost from $\mathcal{O}(d^2)$ to $\mathcal{O}(d\log d)$, where $d$ is the data dimensionality, with almost no compromise in kernel approximation quality compared to ORF. Experiments on several datasets verify the effectiveness of ORF and SORF over the existing methods. We also provide discussions on using the same type of discrete orthogonal structure for a broader range of applications.

NIPS 2016

Cited by in corpus (52)

• Random Feature Attention
• Rethinking Attention with Performers
• The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings
• Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers
• Learning with Density Matrices and Random Features
• Bolt: Accelerated Data Mining with Fast Vector Compression
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Efficient Nonlinear RX Anomaly Detectors
• Calibrating Deep Convolutional Gaussian Processes
• Kernel regression in high dimensions: Refined analysis beyond double descent
• Understanding the 2016 US Presidential Election using ecological inference and distribution regression with census microdata
• Reservoir Computing meets Recurrent Kernels and Structured Transforms
• Random Feature-based Online Multi-kernel Learning in Environments with Unknown Dynamics
• Deep Kernel Learning via Random Fourier Features
• Provably Robust Blackbox Optimization for Reinforcement Learning
• Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps
• Efficient Multitask Feature and Relationship Learning
• Implicit Regularization of Random Feature Models
• Don't take it lightly: Phasing optical random projections with unknown operators
• On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees
• COKE: Communication-Censored Decentralized Kernel Learning
• Probabilistic Neighbourhood Component Analysis: Sample Efficient Uncertainty Estimation in Deep Learning
• Walsh-Hadamard Variational Inference for Bayesian Deep Learning
• Sketching Datasets for Large-Scale Learning (long version)
• Learning Self-Modulating Attention in Continuous Time Space with Applications to Sequential Recommendation
• Structured Monte Carlo Sampling for Nonisotropic Distributions via Determinantal Point Processes
• Sampled Softmax with Random Fourier Features
• Data Dependent Kernel Approximation using Pseudo Random Fourier Features
• Manifold Regularization for Kernelized LSTD
• Generalization Guarantees for Sparse Kernel Approximation with Entropic Optimal Features
• On Learning the Transformer Kernel
• Unlocking Pixels for Reinforcement Learning via Implicit Attention
• Towards a Unified Quadrature Framework for Large-Scale Kernel Machines
• Graph Random Neural Features for Distance-Preserving Graph Representations
• Online Learning for Distribution-Free Prediction
• Frontal Low-rank Random Tensors for Fine-grained Action Segmentation
• Pseudo-Bayesian Learning with Kernel Fourier Transform as Prior
• Kernelized Hashcode Representations for Relation Extraction
• Space-efficient Feature Maps for String Alignment Kernels
• Demystifying Orthogonal Monte Carlo and Beyond
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition
• Breaking the curse of dimensionality with Isolation Kernel
• ORCCA: Optimal Randomized Canonical Correlation Analysis
• Efficient Approximate Inference with Walsh-Hadamard Variational Inference
• Towards Unbiased Random Features with Lower Variance For Stationary Indefinite Kernels
• Index Set Fourier Series Features for Approximating Multi-dimensional Periodic Kernels
• ES-ENAS: Efficient Evolutionary Optimization for Large Hybrid Search Spaces
• HD-cos Networks: Efficient Neural Architectures for Secure Multi-Party Computation
• Cell Association via Boundary Detection: A Scalable Approach Based on Data-Driven Random Features
• Isolation Kernel: The X Factor in Efficient and Effective Large Scale Online Kernel Learning
• Random Fourier Features via Fast Surrogate Leverage Weighted Sampling
• Denoising Score Matching with Random Fourier Features