Abstract: We consider sequential maximization of performance metrics being general functions of a confusion matrixof 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 studiedunder 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, which 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.We also verify the efficiency of the proposed algorithm in empirical studies.