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

The optimality of kernel classifiers in Sobolev space

ICLR 2024 · Learning theory and algorithms › Kernels and regression theory · approach: RKHS kernel methods · 1 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.

Derives an upper bound on the classification excess risk of gradient-flow kernel classifiers (spectral algorithms) under source condition on the Bayes classifier, proves a matching minimax lower bound for Sobolev RKHS, extends to overparameterized NTK-based neural network classifiers, and proposes a truncation-based estimator of interpolation smoothness s.

Problem

Convergence rates and optimality of kernel classifiers for binary classification in RKHS/Sobolev spaces, where the Bayes classifier 2η(x)-1 lies in an interpolation space of the kernel, and how to estimate that smoothness in practice.

Approach

Extends recent kernel regression spectral-algorithm theory to classification by bounding excess 0-1 risk via L2 distance to the Bayes classifier, derives a matching minimax lower bound on Sobolev RKHS via a Varshamov-Gilbert construction, transfers the bound to NTK-based overparameterized networks, and estimates smoothness s by log-log regression of projections onto eigenfunctions with truncation.

Key results

• Gradient-flow kernel classifier excess risk bounded by O(n^{-sβ/(2sβ+2)}) under f* in [H]^s, with Sobolev RKHS minimax lower bound of the same rate (Theorem 3.1 and 3.2).
• Truncation estimation of relative smoothness s with respect to NTKs gives about 0.486 for MNIST, 0.442 for Fashion-MNIST, and 0.199 for CIFAR-10 (binary subsets, NTK-1).
• Simulated min-kernel experiment recovers s ≈ 0.53 versus true 0.5 with truncation point 100 at sigma = 0.1.

Surprising findings

• The naive log-log slope estimator of smoothness is inaccurate under noise, while truncation at a fixed index recovers it well.

Limitations

• Mixed-smoothness functions make the truncation-based smoothness estimate fall between the two smoothness levels rather than the lower one.
• Theory does not cover low intrinsic dimension settings or well-separated (discontinuous f*) data in high dimension.
• Theory for neural networks relies on overparameterization (width poly in n) and uniform convergence to the NTK predictor.

Experimental setup

Datasets: MNIST Fashion-MNIST CIFAR-10

Benchmarks: MNIST Fashion-MNIST CIFAR-10

Metrics: estimated relative smoothness s (truncation estimation) convergence rate exponent

Builds on: spectral algorithms neural tangent kernel misspecified spectral algorithms (Lin & Cevher 2020) Tsybakov/Zhang classification excess risk bound

Closest papers by meaning

• Optimality Implies Kernel Sum Classifiers are Statistically Efficient (ICML 2019 · similarity 0.88)
• Infinite Kernel Learning: Generalization Bounds and Algorithms (AAAI 2017 · similarity 0.88)
• Consistent Interpolating Ensembles via the Manifold-Hilbert Kernel (NeurIPS 2022 · similarity 0.87)
• Improved Learning Rates of a Functional Lasso-type SVM with Sparse Multi-Kernel Representation (NeurIPS 2021 · similarity 0.87)
• Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.87)
• Harmful Overfitting in Sobolev Spaces (ICML 2026 · similarity 0.87)