Limited stochastic meta-descent for kernel-based online learning

A Note on the Unification of Adaptive Online Learning

In online convex optimization, adaptive algorithms, which can utilize the second-order information of the loss function's (sub)gradient, have shown improvements over standard gradient methods. This paper presents a framework Follow the Bregman Divergence Leader that unifies various existing adaptive algorithms from which new insights are revealed. Under the proposed framework, two simple adaptive online algorithms with improvable performance guarantee are derived. Furthermore, a general equation derived from a matrix analysis generalizes the adaptive learning to nonlinear case with kernel trick.

Model-based online learning with kernels

New optimization models and algorithms for online learning with Kernels (OLK) in classification, regression, and novelty detection are proposed in a reproducing Kernel Hilbert space. Unlike the stochastic gradient descent algorithm, called the naive online Reg minimization algorithm (NORMA), OLK algorithms are obtained by solving a constrained optimization problem based on the proposed models. By exploiting the techniques of the Lagrange dual problem like Vapnik's support vector machine (SVM), the solution of the optimization problem can be obtained iteratively and the iteration process is similar to that of the NORMA. This further strengthens the foundation of OLK and enriches the research area of SVM. We also apply the obtained OLK algorithms to problems in classification, regression, and novelty detection, including real time background substraction, to show their effectiveness. It is illustrated that, based on the experimental results of both classification and regression, the accuracy of OLK algorithms is comparable with traditional SVM-based algorithms, such as SVM and least square SVM (LS-SVM), and with the state-of-the-art algorithms, such as Kernel recursive least square (KRLS) method and projectron method, while it is slightly higher than that of NORMA. On the other hand, the computational cost of the OLK algorithm is comparable with or slightly lower than existing online methods, such as above mentioned NORMA, KRLS, and projectron methods, but much lower than that of SVM-based algorithms. In addition, different from SVM and LS-SVM, it is possible for OLK algorithms to be applied to non-stationary problems. Also, the applicability of OLK in novelty detection is illustrated by simulation results.

A kernel-based perceptron with dynamic memory

In this study, we propose a dynamical memory strategy to efficiently control the size of the support set in a kernel-based Perceptron learning algorithm. The method consists of two operations, namely, the incremental and decremental projections. In the incremental projection, a new presented instance is either added to the support set or discarded depending on a predefined rule. To diminish information loss, we do not throw away those discarded examples cheaply, instead their impact to the discriminative function is sustained by a projection technique, which maps the modified discriminative function into the space spanned by the original support set. When a new example is added to the support set, the algorithm moves to the decremental projection. We evaluate the minimum information loss by deleting one instance from the support set. If this minimum information loss is less than a tolerable threshold, then the corresponding instance is removed, however, its contribution to the discriminative function is reserved by the projection technique. By this, our method can on one hand keep a relatively small size of the support set and on the other hand achieve a high classification accuracy. We also develop a method which sets a budget for the size of the support set. We test our approaches to four benchmark data sets, and find that our methods outperform others in either having higher classification accuracies when the sizes of their support sets are comparable or having smaller sizes of the support sets when their classification accuracies are similar.