Solving Kernel Ridge Regression with Gradient Descent for a Non-Constant Kernel

• URL: http://arxiv.org/abs/2311.01762v2
• Date: Mon, 11 Nov 2024 10:43:06 GMT
• Title: Solving Kernel Ridge Regression with Gradient Descent for a Non-Constant Kernel
• Authors: Oskar Allerbo,
• Abstract summary: KRR is a generalization of linear ridge regression that is non-linear in the data, but linear in the parameters. We address the effects of changing the kernel during training, something that is investigated in this paper. We show theoretically and empirically that using a decreasing bandwidth, we are able to achieve both zero training error in combination with good generalization, and a double descent behavior.
• Score: 1.5229257192293204
• License:
• Abstract: Kernel ridge regression, KRR, is a generalization of linear ridge regression that is non-linear in the data, but linear in the parameters. The solution can be obtained either as a closed-form solution, which includes solving a system of linear equations, or iteratively through gradient descent. Using the iterative approach opens up for changing the kernel during training, something that is investigated in this paper. We theoretically address the effects this has on model complexity and generalization. Based on our findings, we propose an update scheme for the bandwidth of translational-invariant kernels, where we let the bandwidth decrease to zero during training, thus circumventing the need for hyper-parameter selection. We demonstrate on real and synthetic data how decreasing the bandwidth during training outperforms using a constant bandwidth, selected by cross-validation and marginal likelihood maximization. We also show theoretically and empirically that using a decreasing bandwidth, we are able to achieve both zero training error in combination with good generalization, and a double descent behavior, phenomena that do not occur for KRR with constant bandwidth but are known to appear for neural networks.

Related papers

• Highly Adaptive Ridge [84.38107748875144]
  We propose a regression method that achieves a $n-2/3$ dimension-free L2 convergence rate in the class of right-continuous functions with square-integrable sectional derivatives. Har is exactly kernel ridge regression with a specific data-adaptive kernel based on a saturated zero-order tensor-product spline basis expansion. We demonstrate empirical performance better than state-of-the-art algorithms for small datasets in particular.
  arXiv  Detail & Related papers  (2024-10-03T17:06:06Z)
• Learning Analysis of Kernel Ridgeless Regression with Asymmetric Kernel Learning [33.34053480377887]
  This paper enhances kernel ridgeless regression with Locally-Adaptive-Bandwidths (LAB) RBF kernels. For the first time, we demonstrate that functions learned from LAB RBF kernels belong to an integral space of Reproducible Kernel Hilbert Spaces (RKHSs)
  arXiv  Detail & Related papers  (2024-06-03T15:28:12Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrum [18.10812063219831]
  We introduce Modified Spectrum Kernels (MSKs) to approximate kernels with desired eigenvalues. We propose a preconditioned gradient descent method, which alters the trajectory of gradient descent. Our method is both computationally efficient and simple to implement.
  arXiv  Detail & Related papers  (2023-07-26T22:39:47Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Bandwidth Selection for Gaussian Kernel Ridge Regression via Jacobian Control [1.5229257192293204]
  We propose a closed-form, feather-light, bandwidth selection based on controlling the Jacobian. We show on real and synthetic data that compared to cross-validation and marginal likelihood, our method is on pair in terms of model performance, but up to six orders of magnitude faster.
  arXiv  Detail & Related papers  (2022-05-24T10:36:05Z)
• Error-Correcting Neural Networks for Two-Dimensional Curvature Computation in the Level-Set Method [0.0]
  We present an error-neural-modeling-based strategy for approximating two-dimensional curvature in the level-set method. Our main contribution is a redesigned hybrid solver that relies on numerical schemes to enable machine-learning operations on demand.
  arXiv  Detail & Related papers  (2022-01-22T05:14:40Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks [56.084798078072396]
  We take a step towards closing the gap between theory and practice by significantly improving the known theoretical bounds on both the network width and the convergence time. We show that convergence to a global minimum is guaranteed for networks with quadratic widths in the sample size and linear in their depth at a time logarithmic in both. Our analysis and convergence bounds are derived via the construction of a surrogate network with fixed activation patterns that can be transformed at any time to an equivalent ReLU network of a reasonable size.
  arXiv  Detail & Related papers  (2021-01-12T00:40:45Z)
• Optimal Rates of Distributed Regression with Imperfect Kernels [0.0]
  We study the distributed kernel regression via the divide conquer and conquer approach. We show that the kernel ridge regression can achieve rates faster than $N-1$ in the noise free setting.
  arXiv  Detail & Related papers  (2020-06-30T13:00:16Z)
• Kernel and Rich Regimes in Overparametrized Models [69.40899443842443]
  We show that gradient descent on overparametrized multilayer networks can induce rich implicit biases that are not RKHS norms. We also demonstrate this transition empirically for more complex matrix factorization models and multilayer non-linear networks.
  arXiv  Detail & Related papers  (2020-02-20T15:43:02Z)

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.