BriefGPT.xyz
Jul, 2016
分段回归的快速算法
Fast Algorithms for Segmented Regression
HTML
PDF
Jayadev Acharya, Ilias Diakonikolas, Jerry Li, Ludwig Schmidt
TL;DR
本文研究了固定设计的分段回归问题：给定一段线性函数的噪声样本，我们希望在均方误差的精度要求下，恢复该函数。本文的主要贡献是提供了新的近线性时间算法，解决了这个问题，并在大型数据集上实现了显著更好的样本时间权衡。实验结果表明，相对于动态规划方法，我们的算法在只牺牲$2$到$4$倍的收敛速度的情况下，实现了三个数量级的加速。
Abstract
We study the fixed design
segmented regression
problem: Given noisy samples from a piecewise linear function $f$, we want to recover $f$ up to a desired accuracy in mean-squared error. Previous rigorous approaches for this problem rely on
→