Research map / Learning theory and algorithms / Kernels and regression theory

Anchor-based Maximum Discrepancy for Relative Similarity Testing

NeurIPS 2025 · Learning theory and algorithms › Kernels and regression theory · approach: Kernel two-sample testing · 0 citations (OpenAlex)

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.

Proposes anchor-based maximum discrepancy (AMD), which learns a deep kernel and the inferred relative-similarity hypothesis jointly, then runs a wild-bootstrap test that controls type-I error for relative similarity testing of three distributions.

Problem

Relative similarity testing asks which of two distributions P or Q is closer to an anchor U. Prior kernel tests fix a manually specified alternative hypothesis, so kernel selection after that choice is ill-posed and can miss the true relationship.

Approach

Define the relative similarity as the maximum discrepancy between the (U,P) and (U,Q) distances over a space of deep kernels, estimate the sign and kernel jointly from data (Phase I), then test the inferred direction with a wild-bootstrap threshold (Phase II).

Key results

• On MNIST with m=160, AMD test power is 0.409 vs 0.353 for AMD without augmentation (AMD-NA).
• On CIFAR10 with m=20 to 160, AMD test power rises from 0.306 to 0.968, outperforming AMD-NA at most sample sizes.
• Type-I error is controlled at alpha=0.05 when P and Q are equally close to U (nu=0.5), per the reported experiments.

Measured effects reported in the paper

Surprising findings

• Once the alternative hypothesis is fixed first, a kernel can always be found that rejects it, so kernel selection after hypothesis specification is ill-defined.

Limitations

• Augmentation-based optimization increases time complexity and overfitting risk remains with small samples.
• Theoretical guarantees rely on assumptions such as covering number and bounded kernels.
• Only three-distribution relative similarity is handled; extension to multiple distributions is left open.

Experimental setup

Datasets: MNIST CIFAR10 ImageNet ImageNet variants (SK, R, V2, A)

Benchmarks: MNIST CIFAR10 ImageNet variants

Metrics: test power type-I error rejection rate p-value

Baselines: MMD-D KLFI MMD-H UME SHCE LBI

Builds on: maximum mean discrepancy deep kernel (Liu et al. MMD-D) integral probability metric wild bootstrap

Closest papers by meaning

• DUAL: Learning Diverse Kernels for Aggregated Two-sample and Independence Testing (NeurIPS 2025 · similarity 0.85)
• Kernel Selection is Model Selection: A Unified Complexity-Penalised Approach for MMD Two-Sample Tests (NeurIPS 2026 · similarity 0.84)
• Kernel Quantile Embeddings and Associated Probability Metrics (ICML 2025 · similarity 0.84)
• On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity (NeurIPS 2024 · similarity 0.83)
• Data-centric Prediction Explanation via Kernelized Stein Discrepancy (ICLR 2025 · similarity 0.83)
• The Polynomial Stein Discrepancy for Assessing Moment Convergence (ICML 2025 · similarity 0.83)