# Second-Order Kernel Online Convex Optimization with Adaptive Sketching

arXiv: https://arxiv.org/abs/1706.04892 · HTML: https://mlsanity.com/paper/1706.04892/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2017.

## Built on by (most cited first, 13 of 13)

- [Communication Efficient Distributed Learning for Kernelized Contextual Bandits](https://mlsanity.com/paper/2206.04835/) (2022)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness](https://mlsanity.com/paper/2603.20826/) (2026)
- [Dynamic Regret Reduces to Kernelized Static Regret](https://mlsanity.com/paper/2507.05478/) (2025)
- [Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR](https://mlsanity.com/paper/2111.11550/) (2021)
- [Provably Efficient Kernelized Q-Learning](https://mlsanity.com/paper/2204.10349/) (2022)
- [Efficient Kernel UCB for Contextual Bandits](https://mlsanity.com/paper/2202.05638/) (2022)
- [Policy Newton Algorithm in Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2506.01597/) (2025)
- [Improved Kernel Alignment Regret Bound for Online Kernel Learning](https://mlsanity.com/paper/2212.12989/) (2022)
- [Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback](https://mlsanity.com/paper/2207.03091/) (2022)
- [Minimax Adaptive Online Nonparametric Regression over Besov Spaces](https://mlsanity.com/paper/2505.19741/) (2025)
- [Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression](https://mlsanity.com/paper/2306.08320/) (2023)
- [Fast Second-Order Online Kernel Learning through Incremental Matrix Sketching and Decomposition](https://mlsanity.com/paper/2410.11188/) (2024)

## Abstract (arXiv)

Kernel online convex optimization (KOCO) is a framework combining the expressiveness of non-parametric kernel models with the regret guarantees of online learning. First-order KOCO methods such as functional gradient descent require only O(t) time and space per iteration, and, when the only information on the losses is their convexity, achieve a minimax optimal O(√T) regret. Nonetheless, many common losses in kernel problems, such as squared loss, logistic loss, and squared hinge loss posses stronger curvature that can be exploited. In this case, second-order KOCO methods achieve O(log(Det(boldsymbolK))) regret, which we show scales as O(defflog T), where deff is the effective dimension of the problem and is usually much smaller than O(√T). The main drawback of second-order methods is their much higher O(t2) space and time complexity. In this paper, we introduce kernel online Newton step (KONS), a new second-order KOCO method that also achieves O(defflog T) regret. To address the computational complexity of second-order methods, we introduce a new matrix sketching algorithm for the kernel matrix boldsymbolKt, and show that for a chosen parameter γ ≤ 1 our Sketched-KONS reduces the space and time complexity by a factor of γ2 to O(t2γ2) space and time per iteration, while incurring only 1/γ times more regret.