Fast Algorithms for Segmented Regression
Fast Algorithms for Segmented Regression
复制标题
DOI：
--
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Jayadev Acharya;Ilias Diakonikolas;Jerry Li;Ludwig Schmidt
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;Ilias Diakonikolas;Jerry Li;Ludwig Schmidt
我们研究了固定的设计分割回归问题：给定分段线性函数$ f $的嘈杂样本，我们希望将$ f $恢复到均值错误的所需准确性。以前针对此问题的严格方法取决于动态编程（DP），虽然样本有效，但在样本量中运行时间二次。作为我们的主要贡献，我们为与DP方法相比，在大型数据集上实现了更高的样本时间折衷的问题，我们提供了新的样本近线性时间算法。我们的实验评估表明，与DP方法相比，我们的算法提供的收敛速率仅为$ 2 $至$ 4 $，同时达到了三个数量级的加速。
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 dynamic programming (DP) and, while sample efficient, have running time quadratic in the sample size. As our main contribution, we provide new sample near-linear time algorithms for the problem that -- while not being minimax optimal -- achieve a significantly better sample-time tradeoff on large datasets compared to the DP approach. Our experimental evaluation shows that, compared with the DP approach, our algorithms provide a convergence rate that is only off by a factor of $2$ to $4$, while achieving speedups of three orders of magnitude.