IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v426y2022ics0096300322001965.html
   My bibliography  Save this article

StreaMRAK a streaming multi-resolution adaptive kernel algorithm

Author

Listed:
  • Oslandsbotn, Andreas
  • Kereta, Željko
  • Naumova, Valeriya
  • Freund, Yoav
  • Cloninger, Alexander

Abstract

Kernel ridge regression (KRR) is a popular scheme for non-linear non-parametric learning. However, existing implementations of KRR require that all the data is stored in the main memory, which severely limits the use of KRR in contexts where data size far exceeds the memory size. Such applications are increasingly common in data mining, bioinformatics, and control. A powerful paradigm for computing on data sets that are too large for memory is the streaming model of computation, where we process one data sample at a time, discarding each sample before moving on to the next one. In this paper, we propose StreaMRAK - a streaming version of KRR. StreaMRAK improves on existing KRR schemes by dividing the problem into several levels of resolution, which allows continual refinement to the predictions. The algorithm reduces the memory requirement by continuously and efficiently integrating new samples into the training model. With a novel sub-sampling scheme, StreaMRAK reduces memory and computational complexities by creating a sketch of the original data, where the sub-sampling density is adapted to the bandwidth of the kernel and the local dimensionality of the data. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum. The results show that the proposed algorithm is fast and accurate.

Suggested Citation

  • Oslandsbotn, Andreas & Kereta, Željko & Naumova, Valeriya & Freund, Yoav & Cloninger, Alexander, 2022. "StreaMRAK a streaming multi-resolution adaptive kernel algorithm," Applied Mathematics and Computation, Elsevier, vol. 426(C).
    • Handle: RePEc:eee:apmaco:v:426:y:2022:i:c:s0096300322001965
    DOI: 10.1016/j.amc.2022.127112
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300322001965
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2022.127112?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Exterkate, Peter & Groenen, Patrick J.F. & Heij, Christiaan & van Dijk, Dick, 2016. "Nonlinear forecasting with many predictors using kernel ridge regression," International Journal of Forecasting, Elsevier, vol. 32(3), pages 736-753.
    2. Mhand Hifi & Rym M'Hallah, 2009. "A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies," Advances in Operations Research, Hindawi, vol. 2009, pages 1-22, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Philippe Goulet Coulombe & Maxime Leroux & Dalibor Stevanovic & Stéphane Surprenant, 2022. "How is machine learning useful for macroeconomic forecasting?," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 37(5), pages 920-964, August.
    2. Thierry Moudiki & Frédéric Planchet & Areski Cousin, 2018. "Multiple Time Series Forecasting Using Quasi-Randomized Functional Link Neural Networks," Risks, MDPI, vol. 6(1), pages 1-20, March.
    3. Cheng, Kai & Lu, Zhenzhou, 2018. "Sparse polynomial chaos expansion based on D-MORPH regression," Applied Mathematics and Computation, Elsevier, vol. 323(C), pages 17-30.
    4. Xiangyang Huang & LiGuo Huang, 2023. "Spreading Points Using Gradient and Tabu," SN Operations Research Forum, Springer, vol. 4(2), pages 1-11, June.
    5. Sergei V. Akopov, 2018. "“Duty” and “Blame” in Russian Official Symbolic Representations of Sovereignty (1994-2018)," HSE Working papers WP BRP 61/PS/2018, National Research University Higher School of Economics.
    6. Peter Exterkate, 2011. "Modelling Issues in Kernel Ridge Regression," Tinbergen Institute Discussion Papers 11-138/4, Tinbergen Institute.
    7. Wojciech Victor Fulmyk, 2023. "Nonlinear Granger Causality using Kernel Ridge Regression," Papers 2309.05107, arXiv.org.
    8. Hifi, Mhand & Yousef, Labib, 2019. "A local search-based method for sphere packing problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 482-500.
    9. Frank J. Kampas & János D. Pintér & Ignacio Castillo, 2023. "Model Development and Solver Demonstrations Using Randomized Test Problems," SN Operations Research Forum, Springer, vol. 4(1), pages 1-15, March.
    10. Hauzenberger, Niko & Huber, Florian & Klieber, Karin, 2023. "Real-time inflation forecasting using non-linear dimension reduction techniques," International Journal of Forecasting, Elsevier, vol. 39(2), pages 901-921.
    11. Milan Fičura, 2019. "Forecasting Foreign Exchange Rate Movements with k-Nearest-Neighbour, Ridge Regression and Feed-Forward Neural Networks," FFA Working Papers 1.001, Prague University of Economics and Business, revised 24 Nov 2019.
    12. Andreas Fischer & Igor Litvinchev & Tetyana Romanova & Petro Stetsyuk & Georgiy Yaskov, 2023. "Quasi-Packing Different Spheres with Ratio Conditions in a Spherical Container," Mathematics, MDPI, vol. 11(9), pages 1-19, April.
    13. Wei, Yu & Liang, Chao & Li, Yan & Zhang, Xunhui & Wei, Guiwu, 2020. "Can CBOE gold and silver implied volatility help to forecast gold futures volatility in China? Evidence based on HAR and Ridge regression models," Finance Research Letters, Elsevier, vol. 35(C).
    14. Kutateladze, Varlam, 2022. "The kernel trick for nonlinear factor modeling," International Journal of Forecasting, Elsevier, vol. 38(1), pages 165-177.
    15. Xu Gong & Boqiang Lin, 2018. "Structural breaks and volatility forecasting in the copper futures market," Journal of Futures Markets, John Wiley & Sons, Ltd., vol. 38(3), pages 290-339, March.
    16. Daiki Maki & Yasushi Ota, 2019. "Robust tests for ARCH in the presence of the misspecified conditional mean: A comparison of nonparametric approches," Papers 1907.12752, arXiv.org, revised Sep 2019.
    17. Yoshiki Nakajima & Naoya Sueishi, 2022. "Forecasting the Japanese macroeconomy using high-dimensional data," The Japanese Economic Review, Springer, vol. 73(2), pages 299-324, April.
    18. Alessandro Giovannelli, 2012. "Nonlinear Forecasting Using Large Datasets: Evidences on US and Euro Area Economies," CEIS Research Paper 255, Tor Vergata University, CEIS, revised 08 Nov 2012.
    19. Peter Exterkate, 2012. "Model Selection in Kernel Ridge Regression," CREATES Research Papers 2012-10, Department of Economics and Business Economics, Aarhus University.
    20. Saeed Salah & Husain R. Alsamamra & Jawad H. Shoqeir, 2022. "Exploring Wind Speed for Energy Considerations in Eastern Jerusalem-Palestine Using Machine-Learning Algorithms," Energies, MDPI, vol. 15(7), pages 1-16, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:apmaco:v:426:y:2022:i:c:s0096300322001965. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.