FORKS: Fast Second-Order Online Kernel Learning using Incremental Sketching

This paper considers how to speed up the second-order method for online kernel learning using sketching. To achieve a logarithmic regret bound, it is common to deploy Newton-type method for OKL, but second-order methods are usually computationally inefficient. This paper attempts to address the issue by using sketching and better algorithms. To this end, they provide an algorithm with update time $O(Bk+k^2)$, when $k$ is small this is a strict improvement from prior works that rely on computing the Newton direction exactly. They also conduct extensive experiments to show that the proposed method is faster than other second-order methods and has a better error rate than first-order methods.

This paper propose FORKS:Fast Second-Order Online Kernel Learning using Incremental Sketching, a fast and effective second-order online kernel learning method. FORKS use efficient low-rank modifications to maintain incremental randomized sketches and apply it to second-order online kernel learning, which makes FORKS have linear time complexity w.r.t. the budget, and enjoy a logarithmic regret bound for online kernel learning. The proposed TISVD : Truncated Incremental SVD, is a novel incremental singular value decomposition based method adapting to matrix decomposition problems. The paper conducts an extensive experimental study to demonstrate the superior performance of FORKS on several datasets and validate the robustness and scalability of FORKS on large-scale datasets.

This paper considers kernel learning in the online setting. The main goal is to give an algorithm with logarithmic regret that is also efficient. It is well known that online gradient descent based methods only achieve square root regret, while exact second order optimization methods achieve logarithmic regret. Thus, the paper proposes a new approximate second order method, which approximates the kernel matrix at any time step using an online variant of CUR Decomposition/Nystrom approximation, proposed by Wang et al. 2016. This method is similar to others that have been proposed in the literature that use Nystrom based kernel matrix approximation to speed up second second order online kernel learning.

Naively, applying this Nystrom decomposition method requires time roughly s^3 per iteration where s is the number of landmark points sampled. This is due to having to perform a truncated SVD of an s x s sampled matrix to reduce it to some rank k < s. To address this, the paper proposes an incremental SVD approach which improves the s^3 runtime to O(sk+k^3).

The paper provides a regret analysis for their approach, as well as experiments. The paper also claims that the proposed algorithm is more robust in adversarial settings than existing approaches. However, it was unclear to me why this was — given that the algorithm largely follows the same blueprint as related prior work. No guarantees on robustness are given.

I have two related major concerns about the presented results.

1. The relationship between the proposed truncated incremental SVD (TISVD), (which seems to be the main algorithmic contribution of the work) and existing work on incremental SVD was unclear to me. Existing work on incremental SVD updates the SVD of a s x s rank-k matrix with a constant rank update in O(sk+k^3) time. Once this update is performed, the matrix may no-longer be rank-k. However, one can trivially truncate the new SVD back to rank-k if desired. This seems to be the only difference proposed by TISVD? It would be helpful if the authors could explain why the given O(sk+k^3) runtime then just doesn’t directly follow from existing work on Incremental SVD. There is an extensive discussion in appendix D, but it is not clear and does not address my question above.

2. Of course, truncating the SVD after each low-rank update, as is done in this paper has a cost. It means that after all the updates have been performed the output is not equivalent to just performing a truncated SVD on the sum of updates. Consider a simple example where I have a diagonal 2 x 2 matrix A. And rank parameter k = 1. Then say initially A_1,1 = 1, A_2,2 = 0. My rank-1 approximation to A (i.e. truncated rank-1 SVD) will be [1,0,0,0]. Now say I repeatedly make rank-1 updates where I increment A_2,2 by .5. Then every time I make a rank-1 update and then truncate back to rank-1, I will truncate A back to [1,0,0,0]. This will be a very poor approximation to my matrix, which after t updates will have A_11 = 1 and A_22 = t/2.

This issue is known in the literature. For example, it is addressed by work on Frequent Directions sketching — see https://arxiv.org/abs/1501.01711, which performs a different type of truncation that prevent losing large weight of accumulated updates.

Critically, the main regret bound of the paper Theorem 1, must depend then on some sort of accuracy guarantee for TISVD, since the algorithm it applies to uses TISVD. However, if one inspects the proof of Theorem 1, there is no mention of TISVD. From what I understand, it is simply assumed that TISVD does in fact output an optimal rank-k approximation to the accumulated updates (I believe specifically in equation (16)).

It would be very helpful if the authors could address the above concerns during the author response period and correct me if I am mistaken.

This paper proposes a novel variant of second-order online sketched kernel learning with a reduced complexity in time and memory. The approach exploits a key ingredient, the so-called Truncated Incremental SV, when updating the approximated sketched feature map. TiSVD allows to incrementally modify a SVD matrix (when new data arrives) by directly modifying its different components and consequently update at a lower price the approximated sketched feature map. This trick is used in association with second order corrections of the weight w_t. The contribution is simple to understand when reading appendix C and it nicely completes the literature. A regret analysis is developed with an assumption about directional curvature of the Lipchitz continuous loss (no strong convexity is required) additionally to classic assumptions about polynomial weight decay of the base kernel. Experimental results include comparisons between this algorithm and competitors with fixed budget (nb of streaming data with non-zero loss for which corrections have to be made). Moreover, FORK is also empirically shown to be robust against adversarial attacks.

This paper proposes a fast second-order approach, called FORKS, for online kernel learning. The FORKS method leverages incremental sketching to reduce the computational cost. The authors provide both theoretical and empirical analysis for the proposed method.

The paper proposes a sketched second-order approach to online kernel learning, and establishes that it has logarithmic regret similar to second-order approaches, while being more computationally efficient due to the use of incremental low-rank approximations. Although experimental evidence is provided to show that the proposed algorithm has a favorable trade-off between accuracy and computation, the novelty of the method relative both to prior approaches to truncated incremental SVD algorithms and applications of Nystrom sketching to online kernel leanring is limited. The regret analysis is also inaccurate, as it does not account for the fact that the incremental low-rank approximation used in the algorithm may not track the true exact low-rank approximation.

Reject