Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression
Jul 24, 2023
Speakers
Shizhong Liao
Speaker · 0 followers
About
The trade-off between regret and computational cost is a fundamental problem for online kernel regression, and previous algorithms worked on the trade-off can not keep optimal regret bounds at a sublinear computational complexity. In this paper, we propose two new algorithms, AOGD-ALD and NONS-ALD, which can keep nearly optimal regret bounds at a sublinear computational complexity, and give sufficient conditions under which our algorithms work. Both algorithms dynamically maintain a group of nearly orthogonal basis used to approximate the kernel mapping, and keep nearly optimal regret bounds by controlling the approximate error. The number of basis depends on the approximate error and the decay rate of eigenvalues of the kernel matrix. If the eigenvalues decay exponentially, then AOGD-ALD and NONS-ALD separately achieves a regret of O(√(L(f))) and O(d_eff(μ)lnT) at a computational complexity in O(ln^2T). If the eigenvalues decay polynomially with degree p≥ 1, then our algorithms keep the same regret bounds at a computational complexity in o(T) in the case of p>4 and p≥ 10, respectively. L(f) is the cumulative losses of f and d_eff(μ) is the effective dimension of the problem. The two regret bounds are nearly optimal and are not comparable.The trade-off between regret and computational cost is a fundamental problem for online kernel regression, and previous algorithms worked on the trade-off can not keep optimal regret bounds at a sublinear computational complexity. In this paper, we propose two new algorithms, AOGD-ALD and NONS-ALD, which can keep nearly optimal regret bounds at a sublinear computational complexity, and give sufficient conditions under which our algorithms work. Both algorithms dynamically maintain a group of ne…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Learning Optimal Advantage from Preferences and Mistaking it for Reward
Watch later
Learning Physical Models that Can Respect Conservation Laws
Watch later
Derek Hansen, …
Adversarial Policies Beat Superhuman Go AIs
Watch later
Tony Wang, …
Hierarchies of Reward Machines
Watch later
Learning Affinity with Hyperbolic Representation for Spatial Propagation
Watch later
Jin-Hwi Park, …
GNN and GBDT-Guided Fast Optimizing Framework for Large-scale Integer Programming
Watch later
Huigen Ye, …