Skip to main content

Time-Accuracy Tradeoffs in Kernel Prediction: Controlling Prediction Quality

Author(s): Kpotufe, S; Verma, N

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1hp3q
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKpotufe, S-
dc.contributor.authorVerma, N-
dc.date.accessioned2021-10-11T14:17:15Z-
dc.date.available2021-10-11T14:17:15Z-
dc.date.issued2017en_US
dc.identifier.citationKpotufe, Samory, and Nakul Verma. "Time-Accuracy Tradeoffs in Kernel Prediction: Controlling Prediction Quality." Journal of Machine Learning Research 18, no. 44 (2017): 1-29.en_US
dc.identifier.issn1532-4435-
dc.identifier.urihttp://www.jmlr.org/papers/v18/16-538.html-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1hp3q-
dc.description.abstractKernel regression or classification (also referred to as weighted ϵ-NN methods in Machine Learning) are appealing for their simplicity and therefore ubiquitous in data analysis. However, practical implementations of kernel regression or classification consist of quantizing or sub- sampling data for improving time efficiency, often at the cost of prediction quality. While such tradeoffs are necessary in practice, their statistical implications are generally not well understood, hence practical implementations come with few performance guarantees. In particular, it is unclear whether it is possible to maintain the statistical accuracy of kernel prediction---crucial in some applications---while improving prediction time. The present work provides guiding principles for combining kernel prediction with data- quantization so as to guarantee good tradeoffs between prediction time and accuracy, and in particular so as to approximately maintain the good accuracy of vanilla kernel prediction. Furthermore, our tradeoff guarantees are worked out explicitly in terms of a tuning parameter which acts as a knob that favors either time or accuracy depending on practical needs. On one end of the knob, prediction time is of the same order as that of single -nearest-neighbor prediction (which is statistically inconsistent) while maintaining consistency; on the other end of the knob, the prediction risk is nearly minimax-optimal (in terms of the original data size) while still reducing time complexity. The analysis thus reveals the interaction between the data- quantization approach and the kernel prediction method, and most importantly gives explicit control of the tradeoff to the practitioner rather than fixing the tradeoff in advance or leaving it opaque. The theoretical results are validated on data from a range of real-world application domains; in particular we demonstrate that the theoretical knob performs as expected.en_US
dc.format.extent1 - 29en_US
dc.language.isoen_USen_US
dc.relation.ispartofJournal of Machine Learning Researchen_US
dc.rightsFinal published version. Article is made available in OAR by the publisher's permission or policy.en_US
dc.titleTime-Accuracy Tradeoffs in Kernel Prediction: Controlling Prediction Qualityen_US
dc.typeJournal Articleen_US
dc.identifier.eissn1533-7928-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
TradeoffsKernelPredictionControlQuality.pdf437.07 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.