Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation

• URL: http://arxiv.org/abs/2604.25021v1
• Date: Mon, 27 Apr 2026 21:53:54 GMT
• Title: Dynamic Regret for Online Regression in RKHS via Discounted VAW and Subspace Approximation
• Abstract summary: We study online regression with the square loss in a kernel reproducing a Hilbert space under a dynamic regret criterion.<n>The proposed method transfers the finite-dimensional discounted Vovk--Azoury--Warmuth approach of Jacobsen & Cutkosky (2024) to the RKHS setting.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online regression with the square loss in a reproducing kernel Hilbert space under a dynamic regret criterion. The learner is compared with a time-varying comparator sequence, and the bounds depend on its path length in the RKHS norm. The proposed method transfers the finite-dimensional discounted Vovk--Azoury--Warmuth approach of Jacobsen \& Cutkosky (2024) to the RKHS setting by means of finite-dimensional subspace approximations. For a fixed subspace, we run a VAW-based ensemble of discounted VAW forecasters over a geometric grid of discount factors. The additional approximation error is controlled by the uniform projection error of kernel sections. We then introduce a general orthogonal truncation method: starting from a feature expansion of the kernel, we construct the associated RKHS by introducing an inner product that makes the feature functions orthonormal, and then use the spans of the first basis functions as finite-dimensional approximation spaces. The resulting subspace reduction is applied to several approximation schemes. Explicit feature expansions yield fast-regime bounds for Gaussian and analytic dot-product kernels. Mercer truncations provide a spectral approximation method and lead to dynamic regret bounds in fast and slow regimes, depending on the eigenvalue decay. Finally, we study subspaces spanned by kernel sections and apply this construction to Matérn kernels.

Related papers

• Koopman Subspace Pruning in Reproducing Kernel Hilbert Spaces via Principal Vectors [5.373672902884401]
  This paper presents an approach for computing principal angles and vectors to enable Koopman subspace pruning within a Reproducing Kernel Hilbert Space (RKHS) geometry.<n>We first outline an exact computational routine, which is subsequently scaled for large datasets using randomized Nystrom approximations.<n>Based on these foundations, we introduce the Kernel-SPV and Approximate Kernel-SPV algorithms for targeted subspace refinement via principal vectors.
  arXiv  Detail & Related papers  (2026-04-01T23:13:13Z)
• KROM: Kernelized Reduced Order Modeling [3.988493458010939]
  KROM formulates PDE solution as a minimum-norm (Gaussian-process) recovery problem in an RKHS.<n>A central ingredient is an empirical kernel constructed from a snapshot library of PDE solutions.
  arXiv  Detail & Related papers  (2026-02-27T22:52:22Z)
• NeuraLSP: An Efficient and Rigorous Neural Left Singular Subspace Preconditioner for Conjugate Gradient Methods [49.84495044725856]
  NeuraLSP is a novel neural preconditioner combined with a novel loss metric.<n>Our method exhibits both theoretical guarantees and empirical robustness to rank inflation, up to a 53% speedup.
  arXiv  Detail & Related papers  (2026-01-28T02:15:16Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• On the Convergence of Irregular Sampling in Reproducing Kernel Hilbert Spaces [0.0]
  We discuss approximation properties of kernel regression under minimalistic assumptions on both the kernel and the input data.<n>We first prove error estimates in the kernel's RKHS norm.<n>This leads to new results concerning uniform convergence of kernel regression on compact domains.
  arXiv  Detail & Related papers  (2025-04-18T10:57:16Z)
• Mirror Descent on Reproducing Kernel Banach Spaces [12.716091600034543]
  This paper addresses a learning problem on Banach spaces endowed with a reproducing kernel. We propose an algorithm that employs gradient steps in the dual space of the Banach space using the reproducing kernel. To instantiate this algorithm in practice, we introduce a novel family of RKBSs with $p$-norm.
  arXiv  Detail & Related papers  (2024-11-18T02:18:32Z)
• Decomposed Diffusion Sampler for Accelerating Large-Scale Inverse Problems [64.29491112653905]
  We propose a novel and efficient diffusion sampling strategy that synergistically combines the diffusion sampling and Krylov subspace methods. Specifically, we prove that if tangent space at a denoised sample by Tweedie's formula forms a Krylov subspace, then the CG with the denoised data ensures the data consistency update to remain in the tangent space. Our proposed method achieves more than 80 times faster inference time than the previous state-of-the-art method.
  arXiv  Detail & Related papers  (2023-03-10T07:42:49Z)
• Experimental Design for Linear Functionals in Reproducing Kernel Hilbert Spaces [102.08678737900541]
  We provide algorithms for constructing bias-aware designs for linear functionals. We derive non-asymptotic confidence sets for fixed and adaptive designs under sub-Gaussian noise.
  arXiv  Detail & Related papers  (2022-05-26T20:56:25Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• Early stopping and polynomial smoothing in regression with reproducing kernels [2.0411082897313984]
  We study the problem of early stopping for iterative learning algorithms in a reproducing kernel Hilbert space (RKHS) We present a data-driven rule to perform early stopping without a validation set that is based on the so-called minimum discrepancy principle. The proposed rule is proved to be minimax-optimal over different types of kernel spaces.
  arXiv  Detail & Related papers  (2020-07-14T05:27:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.