PhD Dissertation Proposal by Jing LU

One critical deficiency of traditional online kernel learning methods is their increasing and unbounded number of support vectors (SV's), making them inefficient and non-scalable for large-scale applications. Recent studies on budget online learning have attempted to overcome this shortcoming by bounding the number of SV's. Despite extensive studied, budget algorithms usually suffer from sever drawbacks.

First, although existing algorithms attempt to bound the number of SV's at each iteration, most of them fail to bound the number of SV's for the averaged classifier, which is commonly used for online-to-batch conversation. To solve this problem, we propose a novel bounded online kernel learning method, Sparse Passive Aggressive learning (SPA), which is able to yield a final output kernel-based hypothesis with a bounded number of support vectors.

Second, existing budget learning algorithms are either too simple to achieve satisfactory approximation accuracy, or too computationally intensive to be scalable to large datasets. To overcome this limitation and make online kernel learning efficient and scalable, we explores two functional approximation based online kernel machine learning algorithms, Fourier Online Gradient Descent (FOGD) and Nystr\"{o}m Online Gradient Descent (NOGD).

We theoretically prove that the proposed algorithms achieve an optimal regret bound, and empirically show that the new algorithms outperform various bounded kernel-based online learning algorithms.