Research map / Learning theory and algorithms / Kernels and regression theory
Inverse M-Kernels for Linear Universal Approximators of Non-Negative Functions
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.
Introduces inverse M-kernels, a sufficient condition on positive definite kernels for linear kernel approximators to be non-negative, and shows exponential/Abel kernels in 1D yield linear universal approximators of non-negative functions.
Problem
Kernel methods with non-negativity constraints on outputs face a trade-off: linear approximators (NCM) have limited representation power, while universal nonlinear alternatives (QNM, SNF) are costly and non-convex. No linear universal approximator of non-negative functions was known.
Approach
Defines inverse M-kernels (kernels whose gram matrix plus a diagonal term is an inverse M-matrix), which guarantee that linear kernel models with weak coefficient constraints (K+s(N+1)I)α ≥ 0 are non-negative; shows exponential kernels in 1D are strict inverse M-kernels and universal, giving linear universal approximators of non-negative functions.
Key results
- On KdV regression with sigma=0.01, IMK achieves l2 .011 ± .001 versus NCM .074 ± .044 and QNM .002 ± .002, with QNM slowest (3.49 s vs 0.003 s).
- On density estimation, IMK achieves dKL .053 ± .021 versus NCM .163 ± .154, SNF .452 ± .291 and QNM .123 ± .049, while being far faster than QNM.
- On intensity estimation IMK attains l2 1.74e3 ± 0.504e3 versus IEK 7.50e3 and STVB 2.01e3, and runs in 4.53 s versus STVB's 1006 s.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IMK instead of NCM | Non-negativity-constrained regression · KdV data, σ=0.1 and σ=0.01 | l2: .078 -> .047; .074 -> .011 | Helped |
| Use IMK instead of QNM | Non-negativity-constrained regression · KdV data, σ=0.1 | cpu (sec): .634 -> .002 | Helped |
| Use IMK instead of QNM | Non-negativity-constrained regression · KdV data, σ=0.01 | l2: .002 -> .011 | Hurt |
| Use IMK instead of NCM | Density estimation · Density estimation | dKL: .163±.154 -> .123±.049 | Helped |
| Use IMK instead of QNM | Density estimation · Density estimation | dKL: .163±.064 -> .123±.049 | No clear effect |
| Use IMK instead of QNM | Density estimation · Density estimation | cpu (sec): .483±.136 -> .053±.021 | Helped |
| Use IMK instead of IEK | Intensity estimation · Intensity estimation | l2 (×103): 7.50 ± 3.06 -> 2.01 ± 0.678 | Helped |
| Use IMK instead of STVB | Intensity estimation · Intensity estimation | l2 (×103): 1.74 ± 0.504 -> 2.01 ± 0.678 | No clear effect |
| Use IMK instead of STVB | Intensity estimation · Intensity estimation | cpu (sec): 1006 ± 54.5 -> 4.53 ± 3.15 | Helped |
Surprising findings
- Gaussian kernels, despite popularity, are not inverse M-kernels and so cannot yield linear universal non-negative approximators under this framework.
- QNM achieved the best regression accuracy on KdV data, though IMK was far faster.
Limitations
- Result limited to one-dimensional input spaces; strict inverse M-kernels for multi-dimensional inputs not found (only inverse M-kernels with a shift s(N)=N-3).
- Exponential kernel models are not smooth at data points.
- Multi-dimensional multiplicative exponential kernel bound on the diagonal shift is not tight.
Experimental setup
Datasets: KdV 2-soliton synthetic data Gaussian mixture synthetic samples synthetic intensity sin^2 event sequences
Benchmarks: KdV 2-soliton regression Gaussian mixture density estimation intensity estimation synthetic
Metrics: integrated squared error (l2) Kullback-Leibler distance CPU time
Baselines: NCM QNM SNF IEK STVB
Builds on: Non-negative coefficients model (NCM) Quadratic form of non-negative model (QNM) Squared neural family M-matrix theory permanental process intensity estimation
Closest papers by meaning
- Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.85)
- Scalable Kernel Inverse Optimization (NeurIPS 2024 · similarity 0.85)
- On Statistical Learning Theory for Distributional Inputs (ICML 2024 · similarity 0.85)
- Improving Adaptivity via Over-Parameterization in Sequence Models (NeurIPS 2024 · similarity 0.85)
- Spectrally Transformed Kernel Regression (ICLR 2024 · similarity 0.84)
- On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity (NeurIPS 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.