Technical Summary: Subsampling for Supervised Learning in Reproducing Kernel Hilbert Spaces

Problem Statement

In the era of big data, the computational cost and energy consumption associated with training statistical learning models on massive datasets have become critical bottlenecks. While various data reduction techniques exist (e.g., sketching, coresets, stochastic optimization), many are either task-agnostic or rely on intractable probabilities for optimal selection. Specifically, in nonparametric supervised learning where hypotheses lie in a Reproducing Kernel Hilbert Space (RKHS), existing methods often fail to provide an optimal, data-dependent subsampling scheme that minimizes the asymptotic variance of the estimator. Kernel methods typically scale poorly ($O(n^2)$ or $O(nm)$) with the original dataset size $n$, and while subsampling reduces this to $O(s^2)$ (where $s \ll n$), standard uniform subsampling ignores the informational value of individual data points, leading to suboptimal estimation precision.

Methodology

The authors propose a framework for Subsampled Risk Minimization (SRM) in RKHSs, utilizing a Horvitz-Thompson reweighting scheme to ensure unbiased estimation of the empirical risk. The core methodology involves:

1. Theoretical Framework:

   • Setting: Nonparametric supervised learning (classification and regression) with a convex, twice-differentiable loss function $\ell$ and a ridge penalty. The estimator minimizes a regularized empirical risk.
   • Subsampling Strategies: The paper analyzes two strategies:
     • Multinomial Subsampling (with replacement): Points are drawn independently with inclusion probabilities $\pi_{n,i}$.
     • Poisson Subsampling (without replacement): Points are included independently with probability $s_n \pi_{n,i}$.
   • Asymptotic Analysis: Using tools from functional probability spaces and martingale theory, the authors establish the asymptotic normality of the SRM estimator. They derive the asymptotic covariance operator $\Sigma^*$, which depends on the inclusion probabilities $\pi_{n,i}$.

2. Optimal Subsampling Scheme:

   • The authors define L-optimality as minimizing the trace of the asymptotic covariance operator (preconditioned by the inverse Hessian of the true risk).
   • They derive a closed-form expression for the L-optimal absolute interest function $\psi^*$, which dictates the optimal inclusion probabilities:
     $$\psi^*(z) = |\ell'(h_0(x), y)| \sqrt{k(x, x)}$$
     where $h_0$ is the true regularized risk minimizer, $\ell'$ is the derivative of the loss, and $k$ is the kernel.
   • This implies that data points with high prediction error (large $|\ell'|$) or high kernel self-similarity should be sampled with higher probability.

3. Practical Implementation (Piloted Estimator):

   • Since $h_0$ is unknown, the authors propose a plug-in approach:
     1. Compute a pilot estimator $\hat{h}_{k_n}$ on a small subset of the data ($k_n \ll s_n$).
     2. Estimate the optimal probabilities using $\hat{h}_{k_n}$.
     3. Smooth the estimated probabilities to ensure they satisfy technical assumptions (specifically, that they do not converge to zero too quickly) using a hyperparameter $\alpha \in (0, 1]$:
        $$\tilde{\pi}_{n,i}^\alpha = (1-\alpha)\tilde{\pi}_{n,i} + \frac{\alpha}{n}$$
     4. For Poisson subsampling, apply a post-hoc truncation to ensure probabilities remain valid ($\leq 1/s_n$).
   • Theoretical guarantees (consistency and asymptotic normality) are provided for this $\alpha$-piloted estimator.

Key Contributions

• Asymptotic Normality in RKHS: The paper establishes the asymptotic normality of subsampled estimators in infinite-dimensional RKHSs, distinguishing itself from parametric results by employing functional random probability space techniques and martingale theory.
• Optimal Scheme Derivation: It provides the first derivation of an optimal subsampling scheme specifically for nonparametric kernel methods, showing that the optimal inclusion probability is proportional to the magnitude of the loss gradient weighted by the kernel diagonal.
• Comparison of Strategies: The authors analyze the trade-offs between Multinomial and Poisson subsampling, demonstrating that the optimal choice depends on the limit ratio $c = \lim s_n/n$. Notably, due to the presence of ridge regularization, the two strategies do not have identical asymptotic efficiencies when $c=0$, differing from findings in parametric settings.
• Robust Practical Algorithm: The proposal of a two-step "piloted" algorithm that combines a pilot estimator with smoothing and truncation makes the theoretically optimal scheme implementable in practice while maintaining statistical guarantees.

Results

Numerical experiments were conducted on synthetic datasets (classification and regression) and a real-world dataset (UCI Covertype), comparing the proposed $\alpha$-piloted SRM against:

• Uniform subsampling (baseline).
• Nyström method.
• Random Fourier Features (RFF).
• Kernel sketching.

Findings:

• Smoothing Parameter: A smoothing parameter $\alpha$ between 0.1 and 0.4 yields the best generalization error, balancing the benefits of optimal subsampling with the stability of uniform sampling.
• Large Data Regime: For large datasets, the proposed SRM significantly outperforms uniform subsampling in terms of the trade-off between generalization error and computational time (CPU).
• Comparison with Approximations: On the real-world Covertype dataset, the SRM method was more efficient than Nyström, RFF, and sketching. On synthetic low-dimensional tasks, kernel approximations (Nyström, RFF) were faster, suggesting that subsampling and kernel approximation are complementary techniques.
• Hybrid Approach: Combining subsampling with the Nyström method further improved performance, indicating the method's compatibility with existing kernel approximation techniques.

Significance and Claims

The paper claims to provide a theoretically grounded and practically viable method for reducing the computational burden of kernel-based learning without sacrificing statistical efficiency. By deriving an optimal subsampling scheme based on the asymptotic covariance trace, the authors offer a way to extract "informative" individuals from large datasets.

The authors modestly frame their work as a step toward more energy-efficient learning, noting that while the method reduces the optimization problem size from $O(n^2)$ to $O(s^2)$, it relies on a pilot estimator. They acknowledge that the theory is currently based on regularized risks and that extending it to non-regularized settings or developing multi-stage online procedures are potential directions for future research. The work distinguishes itself by addressing the specific challenges of the nonparametric RKHS setting, which existing parametric subsampling theories do not fully cover.