Robust Online Confidence-Weighted Learning in Adversarial Environment

Astract:

Online learning takes place in a sequence of consecutive rounds. On each round, the learner is given a question and is required to provide an answer to this question. The performance of an online learning algorithm is measured by the cumulative loss suffered by the prediction along the run on a sequence of question-answer pairs. The Perceptron algorithm is perhaps the first and simplest online learning algorithm designed for answering yes/no questions. The weight parameter of the Perceptron can be updated in either an additive form or a multiplicative way. The multiplicative updates are more efficient than additive updates when the instances contain many noise elements. Adaptations of the Perceptron for multiclass categorization tasks include. As the Perceptron algorithm is essentially a gradient descent (first-order) method, recent years have seen a surge of studies on the second-order online learning. For example, the confidence-weighted algorithm maintains a Gaussian distribtuion over some linear classifier hypotheses and employs it to control the online update of parameters. Several work has followed this idea and showed that parameters' confidence information can significantly improve online learning performance.