Transductive Learning Over Unbounded Losses: An Unbounded Transductive Local Complexity Approach

We develop Unbounded Transductive Local Complexity (UTLC) for transductive learning with unbounded losses, such as squared-loss regression without norm constraints. We first develop a novel variance rescaling method to extend the existing Sharper Transductive Local Complexity (STLC) yang2026stlc concentration to unbounded loss functions. Under standard localization and Bernstein conditions, a single complexity fixed point controls empirical risk minimization. UTLC is applied to two transductive learning problems with squared-loss. For Transductive Kernel Learning (TKL) over an unbounded set in a Reproducing Kernel Hilbert Space (RKHS), UTLC gives spectral excess-risk rates for unbounded squared loss, including controlled positive ridge chosen from training labels. UTLC with bounded loss on a fixed RKHS ball recovers the rate of \citet[Theorem 5.2]yang2026stlc only as a special case under the same assumptions for \citet[Theorem 5.2]yang2026stlc. UTLC also renders a sharp rate for noisy unbounded TKL with i.i.d. sub-Gaussian noise in labels. With independent inputs and a two-sided polynomial population Eigenvalue Decay Rate (EDR), UTLC attains the minimax optimal rate on bounded RKHS signal sets, matching a Gaussian-noise lower bound under the same polynomial population EDR. The learner optimizes over an unbounded RKHS set, and its squared loss is unbounded. To the best of our knowledge, this is the first transductive local-complexity analysis to establish minimax optimal bounds for noisy TKL with unbounded squared loss.