Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels

Yining Wang (), Yi Wu () and Simon S. Du ()
Additional contact information
Yining Wang: Warrington College of Business, University of Florida, Gainesville, Florida 32611
Yi Wu: Institute of Interdisciplinary Information Sciences, Tsinghua University, Beijing, 100084, China; Shanghai Qi Zhi Institute, Xuhui District, Shanghai, 200232, China
Simon S. Du: Paul G. Allen School of Computer Science and Engineering, University of Washington, Seattle, Washington 98195

INFORMS Journal on Computing, 2021, vol. 33, issue 4, 1339-1353

Abstract: Local polynomial regression is an important class of methods for nonparametric density estimation and regression problems. However, straightforward implementation of local polynomial regression has quadratic time complexity which hinders its applicability in large-scale data analysis. In this paper, we significantly accelerate the computation of local polynomial estimates by novel applications of multidimensional binary indexed trees. Both time and space complexity of our proposed algorithm is nearly linear in the number of input data points. Simulation results confirm the efficiency and effectiveness of our proposed approach. Summary of Contribution. Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods.

Keywords: local polynomial regression; nonparametric density estimation; binary indexed trees; hashing (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1021 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:4:p:1339-1353

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().