Unsaturated Multi-Kernel Multi-Task Regression

Many multi-output regression problems, such as decoding finger movements from brain signals or predicting a vehicle's unmeasured sensors from its measured ones, are solved well by kernel methods that blend several similarity measures instead of picking one. The best current versions keep weight on all the candidate kernels rather than zeroing most of them out. They then fit the model with ridge regression, which theory shows hits a performance ceiling: once the target function is smooth enough, more data stops helping at the optimal rate. This proposal replaces ridge regression with early-stopped gradient descent, a fitting procedure without that ceiling, and learns the dense kernel weights and the stopping time together. It also adds one ingredient ridge regression does not need. The weights are treated as per-kernel learning rates, so each kernel's contribution is fit on its own schedule. Relatedness between tasks enters through the same shrinkage, so weakly shared directions across tasks are fit last.

In two sentences: combining many kernels with dense weights helps multi-task regression, and gradient-descent-style fitting avoids the saturation of ridge regression. Nobody has done both at once, and we test whether the gains compound or cancel on real recorded signals, not only on the synthetic problems where the theory lives.

Background and the gap

Three bodies of work meet here, and each stops short of the others.

The first concerns kernel weighting. Multiple kernel learning fits a combination $K=\sum_m \mu_m K_m$ of base similarity matrices. L2 Regularization for Learning Kernels showed that an $\ell_2$ constraint on $\mu$ keeps useful secondary kernels that the sparse $\ell_1$ simplex discards. Unifying Framework for Fast Learning Rate of Non-Sparse Multiple Kernel Learning proved that when kernels have different eigenvalue decay rates, dense weighting can converge up to $M^{2s/(1+s)}$ times faster than sparse weighting. These papers motivate dense weights, but both analyze a single-output, ridge-type estimator. The closest existing method is Multiple Operator-valued Kernel Learning (MovKL), which extends $\ell_r$-norm kernel learning to vector-valued outputs. Its $\ell_2$ weighting beat $\ell_1$ on brain-signal decoding. It is still a Tikhonov (ridge) solver, and it supplies both our strongest baseline and our main dataset.

The second concerns spectral filtering, meaning regularization that rescales each eigen-direction of the kernel matrix. Ridge regression, truncated eigen-decomposition and gradient descent are all instances. Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms proves that vector-valued ridge regression saturates once smoothness $\beta\ge 2$, while filters with higher "qualification" (roughly, how much smoothness a filter can exploit), such as gradient flow, stay minimax optimal. On the Saturation Effects of Spectral Algorithms in Large Dimensions shows that saturation arrives even earlier in high dimensions. These results supply the method, but both assume one fixed kernel and report no real-data experiments. Kernel Mean Estimation via Spectral Filtering is further evidence that direction-aware shrinkage beats plain empirical estimates, again with a single kernel.

The third concerns multi-task structure. A Spectral Regularization Framework for Multi-Task Structure Learning shrinks the singular values of the task weight matrix, but only for linear features. Catastrophic Forgetting Meets Negative Transfer: Batch Spectral Shrinkage for Safe Transfer Learning suppresses small singular values of neural features to limit negative transfer, meaning the case where training on one task hurts another. This paper constrains our design: blunt spectral penalties can also remove directions that one of the tasks needs. That argues for a smooth, data-scheduled shrinkage rather than a hard penalty.

No paper in this file puts a filter with qualification above one inside dense multi-kernel, multi-task learning. The file also contains no answer to the question in Gap 4: does high qualification compound or cancel the advantage dense weighting has when kernel decay rates differ?

Core Claim

Let $n$ be the number of samples and $T$ the number of tasks. We model outputs with a separable operator $(\sum_m \mu_m K_m)\otimes B$, where $K_m$ are the $n\times n$ base Gram matrices, $\mu\ge 0$ with $\|\mu\|_p\le 1$ and $p>1$, and $B$ is a $T\times T$ positive semidefinite task-relatedness matrix. We fit the $n\times T$ coefficient matrix $A$ by gradient descent from zero for $t$ steps:

$$A^{(t+1)} = A^{(t)} + \frac{\eta}{n}\Big(Y - \textstyle\sum_m \mu_m K_m A^{(t)} B\Big),$$

where $Y$ is the $n\times T$ target matrix and $\eta$ a step size.

Two facts make this more than a swap of solvers. First, the update to the predictions is $\sum_m \mu_m K_m r B$, where $r$ is the current residual. So $\mu_m$ acts as kernel $m$'s learning rate: a kernel with small weight still contributes, just later in training. That is the direct analogue of dense rather than sparse weighting. Second, the eigenvalues of the operator are products $\lambda_i\nu_k$ of a combined-kernel eigenvalue and a task eigenvalue. The gradient descent filter $1-(1-\eta\lambda_i\nu_k)^t$ therefore fits strongly shared task directions early and weakly shared ones late or never. This is a soft version of the Schatten shrinkage of Argyriou et al., carried over into a nonlinear, multi-kernel space.

We claim three things. On smooth multi-output targets, this estimator beats MovKL-style ridge regression with the same learned dense weights. Learned dense weights beat uniform weights under this filter exactly when base kernels decay at different rates. And the ranking of methods observed in controlled synthetic problems carries over to real recorded data. We treat that last claim as a hypothesis to be tested, not an assumption.

Research Program

The estimator needs a way to choose $\mu$, $t$ and $B$. For a fixed $\mu$ and $B$, one eigendecomposition of the combined Gram matrix and of $B$ gives the entire gradient descent path in closed form. The stopping time $t$ is then picked on a validation fold at negligible cost. We learn $\mu$ by differentiating the validation loss at the chosen $t$ through that closed-form path, then projecting onto the $\ell_p$ ball. We learn $B$ by alternating with a shrunk estimate of the residual task covariance. For $n$ beyond a few thousand we use Nyström approximations with a shared set of landmark points.

The theory component is deliberately narrow. We extend the vector-valued rates of Meunier et al. to a combined kernel whose components have decays $s_m$. The goal is a bound showing whether the dense-versus-sparse speedup of Suzuki survives when ridge regression is replaced by gradient flow. Our conjecture is that it does, and that the benefit from qualification appears as an extra factor only when $\beta\ge 2$. We treat the correct-specification and incoherence assumptions flagged in Suzuki's work as explicit limits. We do not attempt to remove them.

The simulation direction enters as a methodological constraint rather than an application. The spectral-filtering literature here is validated almost entirely by theory or synthetic data, and the reality-gap literature (Quantifying the Reality Gap in Robotic Manipulation Tasks; A Behavioral Algorithm for State of Charge Estimation) shows how synthetic conclusions fail on physical systems. We therefore write down in advance, from synthetic experiments, which method should win under which conditions. We then report whether those predictions hold on real recordings, where noise is structured, drifting and not Gaussian.

Baselines

The naive reference is independent single-task kernel ridge regression. Each output gets its own model with the best single kernel chosen by cross-validation. This is the "do nothing clever" point: no weighting, no task sharing, a saturating filter. On BCI Competition IV Dataset 4, Kadri et al. report scalar ridge regression at RSSE (residual sum of squares) 68.32 and movement-state classification accuracy 72.91%. We rerun it on our splits rather than quoting that figure as our own number.

The strongest existing method is MovKL with $\ell_2$ weights (Multiple Operator-valued Kernel Learning). It is the only method in the file that already combines dense weighting with multi-output kernels, and it reports RSSE 39.36 and 84.72% on BCI Dataset 4. We reimplement it with the identical kernel dictionary, identical train/test partition, and the same number of hyperparameter evaluations as our method, and we confirm our rerun lands near the published figure. Beating it means lower RSSE and at least equal classification accuracy across repeated splits, with the difference exceeding split-to-split variation.

Three ablations isolate the key ingredients. Uniform-weight gradient flow, the mean kernel of Online Mean Kernel Learning for Object Tracking run with our filter, isolates whether learning $\mu$ matters. Learned-$\mu$ ridge regression with our weight learner isolates the qualification of the filter. $\ell_1$-constrained gradient flow isolates density. A variant with $B=I$ (tasks independent) isolates the task-spectral shrinkage. Every variant receives the same tuning budget, counted in validation evaluations.

Why not just…?

Why not just average the kernels uniformly and run gradient descent on the mean kernel? This is the most serious threat, because it gives dense weights and an unsaturated filter with no weight learning. Suzuki's analysis predicts it falls short only when kernel decay rates differ. When they are similar, we expect the mean kernel to tie, and we will report that. The synthetic sweep varies decay inhomogeneity directly, and the real-data ablation measures the gap. If uniform weighting ties on BCI and on the vehicle data, we will conclude that weight learning is unnecessary in practice and narrow the claim to the filter.

Why not just tune ridge regression's regularization harder, as MovKL does? Saturation is a statement about rates, not tuning: no ridge penalty recovers the optimal rate once $\beta\ge 2$ (Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms). But with only 487 BCI signal pairs, rates may be invisible and a well-tuned ridge solver may match us. The learning-curve experiment below settles this. If the curves do not separate as $n$ grows on real data, the qualification argument has no practical force in this setting.

Why not train separate models per task, or a neural network with Batch Spectral Shrinkage? Separate models give up coupled dynamics. In A Foundation Model for Virtual Sensors, joint training gave MSE 0.121 against 0.177 for isolated models on vehicle bus data. Batch Spectral Shrinkage is known to strip features some tasks rely on. We include the single-task baseline directly. On the vehicle subset we also report a small multi-task neural network with that shrinkage penalty as a reference, without claiming the kernel method must beat large networks at full scale.

Proposed Experiments

The first experiment is a synthetic study. We build multi-task targets on spheres and product spaces with controlled smoothness $\beta$, controlled per-kernel decay $s_m$, and a task matrix of controlled rank. All methods run with $n$ swept over two orders of magnitude, and the log-error slopes are compared with the conjectured rates. From these runs we write down which method should win in each regime before touching real data.

The second experiment uses BCI Competition IV Dataset 4, with finger-flexion trajectories and movement state treated as multiple outputs. We report RSSE and classification accuracy against the rerun MovKL. We also run learning curves on nested subsamples, to see whether the gap to ridge regression widens with $n$ as saturation theory predicts.

The third experiment uses a subsample of the Audi e-tron bus data, predicting a group of held-out sensors from the rest. There the signal noise is real and structured. Our subsampled MSE is not comparable to the 0.121 reported for the full-scale transformer, and we will say so.

Two checks are decisive. One is whether learned-$\mu$ gradient flow beats both learned-$\mu$ ridge regression and uniform-$\mu$ gradient flow on real data, with each margin matching the direction predicted from the synthetic regime closest to that dataset's estimated decay spectra. The other is the agreement rate between synthetic-predicted and real-observed rankings, reported as a headline number. A low agreement rate would itself be a finding about how far this literature's synthetic validation can be trusted.