Efficient Second-Order Online Kernel Learning with Adaptive Embedding
Online kernel learning (OKL) is a flexible framework for prediction problems, since the large approximation space provided by reproducing kernel Hilbert spaces often contains an accurate function for the problem. Nonetheless, optimizing over this space is computationally expensive. Not only first order methods accumulate O( √ T ) more loss than the optimal function, but the curse of kernelization results in a O(t) per-step complexity. Second-order methods get closer to the optimum much faster, suffering only O(log T ) regret, but second-order updates are even more expensive with their O(t 2 ) per-step cost. Existing approximate OKL methods reduce this complexity either by limiting the support vectors (SV) used by the predictor, or by avoiding the kernelization process altogether using embedding. Nonetheless, as long as the size of the approximation space or the number of SV does not grow over time, an adversarial environment can always exploit the approximation process. In this paper, we propose PROS-N-KONS, a method that combines Nyström sketching to project the input point to a small and accurate embedded space; and to perform efficient second-order updates in this space. The embedded space is continuously updated to guarantee that the embedding remains accurate. We show that the per-step cost only grows with the effective dimension of the problem and not with T . Moreover, the second-order updated allows us to achieve the logarithmic regret. We empirically compare our algorithm on recent large-scales benchmarks and show it performs favorably.
The paper proposes an efficient second-order online kernel learning mainly by combining KONS and Nystrom method.
      NOVELTY
      The novelty is limited on both the methodological and theoretical contributions. The achieved results do not have profound implication for the advancement of theory and practice.
      WRITING QUALITY
      The English writing and organization of this paper are relatively good.  The reviewer strongly suggests the authors arrange Table 2 in the main paper rather than in Appendix because the experimental results in Table 2 are the core material. 
      COMMENTS
      This paper works on accelerating second-order online kernel learning and matches the desired state-of-the-art regret bound. The proposed method improves KNOS by using some efficient Nystrom methods instead of the true kernel matrix. However, it seems that this manuscript has not been completed, and many time and accuracy comparisons in Table 1 have not been reported. Although this paper claims that the effective dimension is too large to complete the results in line 341, this explanation for the incomplete experiments is not convincing. If the effective dimension is the concern, this paper should provide more theoretical and practical analysis to show how it affects the PROS-N-KONS. In addition, the reviewer does not find the complexity comparisons among the compared methods. Thus, it is not convincing at all t that the proposed method is efficient.
      Also, the reviewer has three concerns on this paper: 
      1) In the experimental setup, how to determine the values of beta, epsilon, and bandwidth in the kernel matrix? For beta and epsilon, the related parameter selection will take much time. If the learning performance is very sensitive to these two parameters, the efficiency of the proposed method decreases. Regarding the bandwidth, it has an effect on both the effective dimension and the learning accuracy. 
      2) The experimental comparison is not convincing. The efficiency is the key contribution of the proposed methods, but the run time comparison with baselines is missing. Moreover, the Dual-SGD is conducted in only one selected dataset, which makes the model comparison less reasonable.
      
      3) For the ridge leverage scores, it is surprising to find that the paper does not cite paper [Alaoui], which originally proposes the ridge leverage scores in Nystrom approximation with the application to regression analysis. Actually, to my understanding,  [Alaoui] only shows the size in Nystrom approximation could be reduced while does not claim their method would be faster than previous methods, and therein the leverage score approximation in  Theorem 4 could cost much time even more than the time spent in Theorem 3 (just check how to satisfy the condition of his Theorem 3 and 4). Hope this concern could be helpful to tackle your negative claim and results in line 341. 
      [Alaoui] El Alaoui, A., Mahoney, M. W. (2014). Fast randomized kernel methods with statistical guarantees. Advances in Neural Information Processing Systems.