Efficient Algorithms for Multidimensional Segmented Regression
Efficient Algorithms for Multidimensional Segmented Regression
复制标题
多维分段回归的高效算法
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Anastasia Voloshinov
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;Jerry Li;Anastasia Voloshinov
我们研究固定设计{\em多维分段回归}的基本问题：给定来自函数f$的噪声样本，承诺在一组未知的k$矩形上是分段线性的，我们希望恢复f$到期望的均方误差精度。我们提供了第一个样本和计算效率高的算法，这个问题在任何固定的尺寸。我们的算法依赖于一个简单的迭代合并方法，这是新颖的多维设置。我们在合成和真实的数据集上的实验评估表明，我们的算法具有竞争力，在某些情况下优于最先进的算法。我们实现的代码可以在\url{this https URL}上找到。
We study the fundamental problem of fixed design {\em multidimensional segmented regression}: Given noisy samples from a function $f$, promised to be piecewise linear on an unknown set of $k$ rectangles, we want to recover $f$ up to a desired accuracy in mean-squared error. We provide the first sample and computationally efficient algorithm for this problem in any fixed dimension. Our algorithm relies on a simple iterative merging approach, which is novel in the multidimensional setting. Our experimental evaluation on both synthetic and real datasets shows that our algorithm is competitive and in some cases outperforms state-of-the-art heuristics. Code of our implementation is available at \url{this https URL}.
登录
查看更多内容
用于学习多维直方图的快速和样本近最优算法
DOI：
--
发表时间：
2018
期刊：
PMLR
影响因子：
--
作者：
Diakonikolas, Ilias;Li, Jerry;Schmidt, Ludwig
通讯作者：
Schmidt, Ludwig
DOI：
--
发表时间：
2016-06
期刊：
ArXiv
影响因子：
--
作者：
Jayadev Acharya;Ilias Diakonikolas;Jerry Li;Ludwig Schmidt
通讯作者：
Jayadev Acharya;Ilias Diakonikolas;Jerry Li;Ludwig Schmidt
近线性时间内的样本最优密度估计
DOI：
10.48550/arxiv.1506.00671
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Acharya J
通讯作者：
Acharya J
影响因子：
7.5
作者：
Blanchard, G.;Schaefer, C.;Mueller, K. -R.
通讯作者：
Mueller, K. -R.