Research map / Learning theory and algorithms / Kernels and regression theory
Efficiently Learning Significant Fourier Feature Pairs for Statistical Independence Testing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Learns random Fourier feature pairs (via learnable variable transforms) end-to-end to maximize the test power of an HSIC-based independence test, achieving linear-time computation in sample size.
Problem
HSIC-based independence tests have limited power because fixed kernel configurations cannot adapt to frequency-domain features, and existing adaptive kernel tests are quadratic-time in sample size.
Approach
Reinterpret HSIC in the frequency domain, parameterize random Fourier features with learnable variable transforms (Gaussian or diagonal Mahalanobis kernel classes), and optimize a linear-time differentiable test-power objective (normalized statistic minus gamma-approximated threshold) on a held-out training split.
Key results
- On the ISA large-scale setting (d=32, n=60000), LFHSIC-M stably outperforms linear-time baselines as the rotation angle increases, while LFHSIC-G degrades as dimension grows.
- On synthetic SD/Sin/GSign with D=100, LFHSIC-G/M and NFSIC and HSICAgg perform much better than other methods, with LFHSIC-G/M having the largest advantage when D is small.
- On 3DShapes (12,288-dim images, n=128), all methods except BHSIC and NFSIC control Type I error, and LFHSIC-M is the only linear-time test competitive with quadratic-time tests.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Learn significant Fourier feature pairs (LFHSIC-G/M) instead of using fixed features | HSIC-based independence tests · SD, Sin, and GSign | test power | Helped |
| Learn significant Fourier feature pairs (LFHSIC-G/M) instead of using fixed features | HSIC-based independence tests · ISA | test power | Helped |
| Use LFHSIC-M rather than other methods | Independence tests · 3DShapes | test power | Helped |
| Use LFHSIC-M rather than other methods | Independence tests · MSD | test power | Helped |
| Use LFHSIC-M rather than LFHSIC-G (optimize per-dimension scales instead of global bandwidth) (ablation) | LFHSIC · ISA, higher-dimensional setting | test power | Helped |
| Increase the number of Fourier features D (ablation) | LFHSIC-M · ISA | test power | Helped |
| Use LFHSIC-M rather than LFHSIC-G (more flexible per-dimension scales) (ablation) | LFHSIC · MSD | test power | Helped |
| Use LFHSIC-G/M rather than fixed-kernel linear-time tests | HSIC-based independence tests · SD, Sin, and GSign, D=100 and D=500 | test power | Helped |
| Use LFHSIC-M rather than LFHSIC-G (ablation) | LFHSIC · ISA, increasing dimension | test power | Helped |
| Use LFHSIC-M rather than BHSIC or NFSIC | Independence tests · 3DShapes | Type I error rate | Helped |
Surprising findings
- Linear-time learnable test (LFHSIC-M) with D=10 on 3DShapes is competitive with quadratic-time tests, while other linear-time tests lag.
Limitations
- Data splitting (50/50) reduces effective sample size for testing and is needed for Type I error validity in continuous kernel learning.
- Only smooth kernel classes (Gaussian and diagonal Mahalanobis) are considered; more flexible (e.g., neural) transforms are only discussed as remarks.
- Gamma approximation for the null threshold is used rather than exact null distribution.
Experimental setup
Datasets: Sine Dependency (SD) Sinusoid (Sin) Gaussian Sign (GSign) ISA 3DShapes Million Song Dataset (MSD)
Benchmarks: SD Sin GSign ISA 3DShapes MSD
Metrics: average test power Type I error rate Type II error rate
Baselines: dCor QHSIC RDC NyHSIC FHSIC BHSIC HSICAgg NFSIC
Builds on: HSIC random Fourier features FHSIC NFSIC HSICAgg Gamma approximation for HSIC
Closest papers by meaning
- Sharp Analysis of Random Fourier Features in Classification (AAAI 2022 · similarity 0.88)
- A random matrix analysis of random Fourier features: beyond the Gaussian kernel, a precise phase transition, and the corresponding double descent (NeurIPS 2020 · similarity 0.88)
- An Adaptive Test of Independence with Analytic Kernel Embeddings (ICML 2017 · similarity 0.88)
- Learning Adaptive Random Features (AAAI 2019 · similarity 0.87)
- Towards a Unified Analysis of Random Fourier Features (ICML 2019 · similarity 0.87)
- Learning High-Frequency Functions Made Easy with Sinusoidal Positional Encoding (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.