  We consider sequential maximization of performance metrics that are general
functions of a confusion matrix of a classifier (such as precision, F-measure,
or G-mean). Such metrics are, in general, non-decomposable over individual
instances, making their optimization very challenging. While they have been
extensively studied under different frameworks in the batch setting, their
analysis in the online learning regime is very limited, with only a few
distinguished exceptions. In this paper, we introduce and analyze a general
online algorithm that can be used in a straightforward way with a variety of
complex performance metrics in binary, multi-class, and multi-label
classification problems. The algorithm's update and prediction rules are
appealingly simple and computationally efficient without the need to store any
past data. We show the algorithm attains $\mathcal{O}(\frac{\ln n}{n})$ regret
for concave and smooth metrics and verify the efficiency of the proposed
algorithm in empirical studies.
