Kernel methods (models that predict by comparing a new point to training points through a similarity function) scale badly. The standard fix is the Nyström approximation: choose a small set of $m$ representative training points, called landmarks, and express every prediction through similarities to those points only. Which landmarks you pick decides what the compact model can represent at all. The best current selection rules are unsupervised: they spread landmarks across the data geometry, and some deliberately seek sparse regions and outliers. Supervised selection is the obvious improvement. It works by greedily adding the point where the current model's error on the labels is largest. Under label noise, though, it has a built-in flaw: the largest errors sit on mislabeled points, so the selection spends its limited budget on noise.
We propose to steer landmark selection with a teacher's predictions instead of the raw labels. The teacher is a larger, well-regularized kernel model, and we use its leave-one-out predictions, which can be computed in closed form and are statistically independent of each point's own label noise. The compact student then picks landmarks where the teacher's function is still poorly represented, not where the labels happen to be corrupted. The core claim is about where distillation should act. When $m \ll n$, distilling into the compact model's coefficients barely helps, because those coefficients already have very low variance. Distillation pays off when it cleans the signal that decides which points become landmarks.
Where the two directions actually meet
Work on landmark selection shows that the choice matters a great deal. Uniform sampling misses small or isolated clusters (Bouneffouf et al.) and fails to find the few high-coherence columns that carry most of the structure (Affandi et al.). On the representation-learning side, switching from uniform to k-means++ landmarks raised SimCLR accuracy on MNIST from 95.35% to 98.90% in KREPES. The best rules we build on are kernel k-means++ seeding (Oglic & Gärtner), which comes with approximation bounds, and the Christoffel-function samplers of Fanuel et al.. The latter come in two forms: DAS, a greedy rule that adds the least-represented point, and RAS, a randomized one-pass sampler that deliberately captures tail points. All of these ignore the prediction target. That is the "decoupled two-step" limitation the file flags, and it also appears in Zhan's prior-steered Nyström. Zhan does inject supervision, but into the core matrix through a costly semidefinite program, and leaves the landmarks themselves unchanged.
Work on distillation as regularization supplies the denoising mechanism. Moniri et al. show that a properly regularized student can filter out a teacher's idiosyncratic noise. Dang, Patil and Rinaldo show that in ridge regression, mixing labels with the teacher's predictions using an unconstrained weight (possibly negative) strictly improves any teacher whose risk is not at a stationary point in $\lambda$, and that this weight can be tuned in one shot by generalized cross-validation (GCV). GCV estimates leave-one-out error in closed form for any predictor that is linear in the labels.
Two observations shape the design. First, a Nyström model with fixed landmarks is ridge regression on $m$ derived features. The noise variance of its fit scales roughly as $\sigma^2 m/n$, so Dang et al.'s self-distillation acting on the coefficients should give negligible gains when $m \ll n$. That paper constrains our design as much as it motivates it: we use its tuning only for the teacher, and we treat student-side mixing as an ablation we expect to fail. Second, the tension the research file identifies is real, but it is often misplaced. Nyström regression uses all $n$ labels regardless of which points are landmarks, so noisy labels hurt mainly through supervised selection criteria, not through the fit. That is exactly where we intervene.
The closest cross-direction work differs in purpose. KDA uses Nyström with supervised class-mean landmarks to transfer a neural teacher's similarity structure. There, landmarks are a tool for computing a distillation loss; they are not the student's basis, and no noise filtering is involved. Influence Distillation propagates influence scores from a static landmark subset. Kernel dataset distillation synthesizes artificial points rather than selecting real ones. None of these uses a teacher to decide which real points become the basis of a deployed kernel model.
Method
We first fit a teacher: Nyström kernel ridge regression with a large landmark budget $m_T$ (chosen by RAS), with $\lambda$ tuned by GCV. We optionally apply Dang et al.'s GCV-tuned self-distillation, because in the teacher $m_T$ can be comparable to the effective degrees of freedom. The teacher is a linear smoother $\hat y = S y$, so its leave-one-out predictions come in closed form:
$$\tilde y_i = \frac{\hat y_i - S_{ii}\, y_i}{1 - S_{ii}},$$
where $S_{ii}$ is the teacher's leverage on point $i$ and $\tilde y_i$ does not depend on $y_i$.
The student grows its landmark set $L$ greedily from a candidate pool $\mathcal{C}$. At each step it adds
$$j^\star = \arg\max_{j \in \mathcal{C}} \frac{\langle r, \, P_L^\perp k_j \rangle^2}{\| P_L^\perp k_j \|^2},$$
where $k_j$ is the kernel column of candidate $j$ over the training points, $P_L^\perp$ projects out the span of the current landmarks' columns, and $r = \tilde y - \text{(current student fit to } \tilde y)$ is the residual on teacher targets. This is orthogonal matching pursuit on teacher targets. With incremental Cholesky updates it costs $O(nm^2)$ overall plus the candidate scoring. After selection, the student fits its coefficients on the true labels with GCV-tuned $\lambda$.
There is a subtlety that justifies the leave-one-out step. The teacher's in-sample predictions still contain $S_{ii}\,\varepsilon_i$, the leaked label noise, and $S_{ii}$ is largest at exactly the tail points that diversity-seeking teachers emphasize. Using in-sample predictions should therefore re-introduce noise-chasing at the tails. Comparing labels, in-sample teacher predictions and leave-one-out teacher predictions tests this mechanism directly.
Baselines
The naive reference is uniform landmarks with GCV-tuned $\lambda$ at the same budget $m$. The strongest unsupervised competitors are RAS and DAS (Fanuel et al.) and kernel k-means++ (Oglic & Gärtner). They are strongest because they carry approximation guarantees and were shown to beat uniform sampling on the same UCI suites and on Covertype, including the distribution tail. We found no reported result on Lacuna for their test error on these UCI regression sets: Oglic & Gärtner report lift only in plots, and Fanuel et al. report tail SMAPE without numbers in the file. We therefore rerun both ourselves.
The strongest supervised competitor is label-greedy selection, which is our algorithm with $r$ computed from $y$. We also run a robust variant with Huber-clipped residuals, because down-weighting outliers is the cheap alternative to a teacher. Ensemble Nyström reported 10% relative kernel approximation error using about 1% of columns on SIFT-1M. It serves as a reference that uses more total landmarks at inference, not as a same-budget competitor.
Three ablations isolate the key ingredient: in-sample teacher targets versus leave-one-out teacher targets; student-side unconstrained self-distillation with the mixing weight tuned by GCV; and teacher strength, swept through $m_T$. For fairness, every method shares the same kernel, candidate pool, bandwidth selection, GCV-tuned $\lambda$ and final budget $m$. The teacher's cost is counted in wall-clock comparisons. We will call it a win if teacher-guided selection beats the best of the unsupervised and label-greedy baselines on test MSE at matched $m$ on a majority of datasets under noise, and recovers most of the teacher's accuracy at $m = m_T/10$.
Why not just…?
Why not just use the teacher, or give the student more landmarks? We are targeting deployments where the budget $m$ is fixed by inference memory or latency. The teacher's accuracy is reported as the ceiling, and the gap closed at fixed $m$ is the quantity of interest.
Why not just use RAS or DAS with a well-tuned $\lambda$? This is a real threat. When the target's complexity tracks data density, geometry-only selection should already place landmarks well, and we predict little or no gain. The advantage should appear when the function varies in regions that geometry does not flag, or when tail points are mislabeled. We will construct both regimes on semi-synthetic targets and report where the crossover falls, rather than claiming uniform superiority.
Why not just clip residuals in label-greedy selection? Clipping suppresses gross outliers but not moderate noise that is spread across points. It also cannot tell a mislabeled point from a genuinely sharp feature of the function. The teacher's leave-one-out prediction can. The Huber baseline and the noise-type sweep (heavy-tailed versus Gaussian) will settle this.
Why not just apply Dang et al.'s self-distillation to the compact model? The variance argument predicts negligible gain when $m \ll n$. We run it anyway, and we would count a large gain as evidence against our account of where distillation acts.
Proposed Experiments
We use the UCI suite from Oglic & Gärtner (ailerons, parkinsons, elevators, ujil, cal-housing, ct-slice), Covertype and Higgs as large tabular sets, and BlogFeedback and Communities and Crime from Dang et al. We inject label noise at 0%, 10% and 30%, both heavy-tailed and Gaussian, with and without concentrating the noise on low-density points. The metrics are test MSE and tail SMAPE across the budget sweep $m \in \{50, \dots, 1000\}$, plus the fraction of selected landmarks that are corrupted points.
Four checks are decisive. The fraction of corrupted landmarks should be highest for label-greedy selection, intermediate for in-sample teacher targets and lowest for leave-one-out teacher targets. The advantage over label-greedy selection should vanish at 0% noise. The advantage should shrink as $m_T$ approaches $m$, which is the weak-teacher regime of Moniri et al.. Finally, student-side self-distillation should add essentially nothing. If the leave-one-out ablation shows no difference from in-sample targets, the leverage-leak mechanism is wrong and we would report the method as plain teacher-greedy selection.
References
- Sampling with Minimum Sum of Squared Similarities for Nystrom-Based Large Scale Spectral Clustering
- Nystrom Approximation for Large-Scale Determinantal Processes
- Interpretable Kernel Representation Learning at Scale: A Unified Framework Utilizing Nyström Approximation
- Nyström Method with Kernel K-means++ Samples as Landmarks
- Nyström landmark sampling and regularized Christoffel functions
- Improved Nystrom Low-rank Decomposition with Priors
- On the Mechanisms of Weak-to-Strong Generalization: A Theoretical Perspective
- Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning
- Improved Knowledge Distillation via Full Kernel Matrix Transfer
- Efficient Data Selection at Scale via Influence Distillation
- Provable and Efficient Dataset Distillation for Kernel Ridge Regression
- Ensemble Nystrom Method