Abstract
This paper introduces Online Nonparametric Learning with Kernels (ONLK), an algorithm that bridges the gap between deep learning and classical nonparametric sequential prediction. By utilizing a deep neural network to learn data-adaptive kernels on-the-fly, ONLK achieves superior performance on finite datasets while maintaining rigorous long-term asymptotic guarantees for stationary and ergodic processes. Our results on financial datasets demonstrate that ONLK effectively tracks the best performing experts in hindsight, outperforming traditional handcrafted kernel methods.
Introduction
In online learning, data is frequently assumed to be independent and identically distributed (i.i.d.) or adversarial. However, many real-world signals, such as stock prices, are stationary and ergodic, meaning the future depends on the past in complex, non-linear ways. Traditional nonparametric methods for these processes rely on "experts" that use Kernel Density Estimation (KDE) to predict the next state based on similar past contexts.
The primary challenge in these methods is the choice of the kernel (the similarity function). A "naive" kernel, such as simple Euclidean distance, often performs poorly on finite samples, while handcrafted kernels are difficult to design and may not adapt to changing data distributions. The authors propose a framework to make sequential predictions while simultaneously learning the optimal kernel using deep learning techniques.
The ONLK Framework
The proposed Online Nonparametric Learning with Kernels (ONLK) algorithm is built upon three main pillars:
- Markovian Experts: The algorithm maintains a set of experts, each analyzing a different historical window (memory length $k$).
- Deep Kernel Learning: Instead of a fixed kernel, each Markovian expert is assigned a Deep Neural Network (DNN). Each layer of the network represents a different Mahalanobis distance metric, acting as a "kernel expert."
- Hierarchical Aggregation: The algorithm employs the Weak Aggregating Algorithm (WAA) in two stages. First, it aggregates predictions from different DNN layers to form a single prediction for each Markovian expert. Second, it aggregates all Markovian experts to produce the final output.
Unlike standard DNNs trained via batch backpropagation, ONLK utilizes online deep metric learning. It processes data "triplets" (a context, a similar example, and a dissimilar example) and updates network layers using a closed-form, Passive-Aggressive style update. This allows the model to adapt on-the-fly without requiring a separate validation set.
Experimental Evaluation
The algorithm was evaluated on the Online Portfolio Selection problem using two major financial datasets: the NYSE (2000 days, 20 stocks) and the SP500 (2000 days, 30 stocks). These datasets represent complex market conditions where statistical patterns can be exploited by a well-learned kernel.
Performance Analysis
ONLK was compared against several benchmarks, including the "Best Constant Rebalanced Portfolio" (BCRP), the market index, and the "CORN" algorithm, which utilizes handcrafted kernels.
As shown in the results table, ONLK demonstrated superior wealth generation. On the NYSE dataset, ONLK achieved a cumulative wealth of 2.48, significantly outperforming the naive kernel algorithm ($B_k$ at 1.89) and the market index (1.47). On the SP500 dataset, ONLK reached 2.91, nearly matching the "Best Markovian Expert" (2.93) and the "Best Kernel Expert" (3.01) calculated in hindsight. These results indicate that ONLK successfully tracks the best performing layers and experts without prior knowledge of their efficacy.
Discussion and Key Insights
- The "Shallow-to-Deep" Advantage: The authors exploit the property that shallow DNN layers converge faster than deeper ones. In an online setting, ONLK relies on simple patterns early on and gradually shifts weight to more complex, "deep" patterns as more data arrives.
- Theoretical Guarantees: While most deep learning models lack guarantees for non-i.i.d. data, ONLK is designed to satisfy both short-term sublinear regret and long-term asymptotic optimality ($V^*$).
- Kernel as Metric: By treating the kernel as a learned Mahalanobis metric, the model identifies which features of the historical context are relevant for future prediction, rather than treating all dimensions equally.
Conclusion and Future Work
ONLK represents a significant step in integrating deep learning with nonparametric sequential prediction. While the algorithm is computationally more intensive due to maintaining multiple DNNs and hierarchical aggregation, its ability to learn adaptive kernels provides a clear performance advantage. Future work may involve extending this "deep metric learning" approach to other nonparametric methods, such as Nearest Neighbor prediction, and addressing the memory bounds required for theoretical execution.
Summary updated