Spectrally Transformed Kernel Regression

Unlabeled data is a key component of modern machine learning. In general, the role of unlabeled data is to impose a form of smoothness, usually from the similarity information encoded in a base kernel, such as the ϵ-neighbor kernel or the adjacency matrix of a graph. This work revisits the classical idea of spectrally transformed kernel regression (STKR), and provides a new class of general and scalable STKR estimators able to leverage unlabeled data. Intuitively, via spectral transformation, STKR exploits the data distribution for which unlabeled data can provide additional information. First, we show that STKR is a principled and general approach, by characterizing a universal type of "target smoothness", and proving that any sufficiently smooth function can be learned by STKR. Second, we provide scalable STKR implementations for the inductive setting and a general transformation function, while prior work is mostly limited to the transductive setting. Third, we derive statistical guarantees for two scenarios: STKR with a known polynomial transformation, and STKR with kernel PCA when the transformation is unknown. Overall, we believe that this work helps deepen our understanding of how to work with unlabeled data, and its generality makes it easier to inspire new methods. DERIVING STKR FROM DIFFUSION INDUCED MULTISCALE SMOOTHNESS Let the input space X be a compact Hausdorff space, Y = R be the label space, and P X Y be the underlying data distribution over X × Y, whose marginal distribution P X is a Borel measure with support X . We will use the shorthand dp(x) to denote dP X (x). Let L 2 (P X ) be the Hilbert space of L 2 functions w.r.t. exists and is finite. Let a base kernel K(x, x ′ ) encode inter-sample similarity information over X . We assume full access to K (i.e. we can compute K(x, x ′ ) for all x, x ′ ), and that K satisfies: (i) K is a Mercer kernel, so it has the spectral decomposition: where the convergence is absolute and uniform. Here λ i , ψ i are the eigenvalues and orthonormal eigenfunctions of the integral operator T K : L 2 (P X ) → L 2 (P X ) defined as and ⟨ψ i , ψ j ⟩ P X = δ i,j = 1 i=j . (ii) K is centered: Defined as T K 1 = 0, where 1(x) ≡ 1 and 0(x) ≡ 0. One can center any K by K(x 0 , y 0 ) = K(x 0 , y 0 ) -K(x, y 0 )dp(x) -K(x 0 , y)dp(y) + K(x, y)dp(x)dp(y).