# An Accurate and Efficient Large-scale Regression Method through Best Friend Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 67 references that are in the map.
- First posted on arXiv 22 Apr 2021.

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

- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Distributed k-Means and k-Median Clustering on General Topologies](https://mlsanity.com/paper/1306.0604/) (2013)
- [Scene Recognition with Prototype-agnostic Scene Layout](https://mlsanity.com/paper/1909.03234/) (2019)
- [A Divide-and-Conquer Solver for Kernel Support Vector Machines](https://mlsanity.com/paper/1311.0914/) (2013)
- [Parallel Algorithms for Geometric Graph Problems](https://mlsanity.com/paper/1401.0042/) (2013)
- [Accurate, Fast and Scalable Kernel Ridge Regression on Parallel and Distributed Systems](https://mlsanity.com/paper/1805.00569/) (2018)
- [Reducing Redundancy in Data Organization and Arithmetic Calculation for Stencil Computations](https://mlsanity.com/paper/2103.09235/) (2021)

## Abstract (arXiv)

As the data size in Machine Learning fields grows exponentially, it is inevitable to accelerate the computation by utilizing the ever-growing large number of available cores provided by high-performance computing hardware. However, existing parallel methods for clustering or regression often suffer from problems of low accuracy, slow convergence, and complex hyperparameter-tuning. Furthermore, the parallel efficiency is usually difficult to improve while striking a balance between preserving model properties and partitioning computing workloads on distributed systems. In this paper, we propose a novel and simple data structure capturing the most important information among data samples. It has several advantageous properties supporting a hierarchical clustering strategy that is irrelevant to the hardware parallelism, well-defined metrics for determining optimal clustering, balanced partition for maintaining the compactness property, and efficient parallelization for accelerating computation phases. Then we combine the clustering with regression techniques as a parallel library and utilize a hybrid structure of data and model parallelism to make predictions. Experiments illustrate that our library obtains remarkable performance on convergence, accuracy, and scalability.