# Oversampling Divide-and-conquer for Response-skewed Kernel Ridge Regression

arXiv: https://arxiv.org/abs/2107.05834 · HTML: https://mlsanity.com/paper/2107.05834/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 54 references that are in the map.
- First posted on arXiv 13 Jul 2021.

## Builds on (most cited first, 10 of 10)

- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Distributed learning with regularized least squares](https://mlsanity.com/paper/1608.03339/) (2016)
- [Lecture Notes on Randomized Linear Algebra](https://mlsanity.com/paper/1608.04481/) (2016)
- [Distributed Generalized Cross-Validation for Divide-and-Conquer Kernel Ridge Regression and its Asymptotic Optimality](https://mlsanity.com/paper/1612.05907/) (2016)
- [More efficient approximation of smoothing splines via space-filling basis selection](https://mlsanity.com/paper/2003.10609/) (2020)
- [A Practical Guide to Randomized Matrix Computations with MATLAB Implementations](https://mlsanity.com/paper/1505.07570/) (2015)
- [Learning Theory of Distributed Regression with Bias Corrected Regularization Kernel Network](https://mlsanity.com/paper/1708.01960/) (2017)
- [On the Feasibility of Distributed Kernel Regression for Big Data](https://mlsanity.com/paper/1505.00869/) (2015)
- [How Many Machines Can We Use in Parallel Computing for Kernel Ridge Regression?](https://mlsanity.com/paper/1805.09948/) (2018)

## Abstract (arXiv)

The divide-and-conquer method has been widely used for estimating large-scale kernel ridge regression estimates. Unfortunately, when the response variable is highly skewed, the divide-and-conquer kernel ridge regression (dacKRR) may overlook the underrepresented region and result in unacceptable results. We combine a novel response-adaptive partition strategy with the oversampling technique synergistically to overcome the limitation. Through the proposed novel algorithm, we allocate some carefully identified informative observations to multiple nodes (local processors). Although the oversampling technique has been widely used for addressing discrete label skewness, extending it to the dacKRR setting is nontrivial. We provide both theoretical and practical guidance on how to effectively over-sample the observations under the dacKRR setting. Furthermore, we show the proposed estimate has a smaller risk than that of the classical dacKRR estimate under mild conditions. Our theoretical findings are supported by both simulated and real-data analyses.