Modern classification problems frequently present mild to severe label
imbalance as well as specific requirements on classification characteristics,
and require optimizing performance measures that are non-decomposable over the
dataset, such as F-measure. Such measures have spurred much interest and pose
specific challenges to learning algorithms since their non-additive nature
precludes a direct application of well-studied large scale optimization methods
such as stochastic gradient descent.
In this paper we reveal that for two large families of performance measures
that can be expressed as functions of true positive/negative rates, it is
indeed possible to implement point stochastic updates. The families we consider
are concave and pseudo-linear functions of TPR, TNR which cover several
popularly used performance measures such as F-measure, G-mean and H-mean.
Our core contribution is an adaptive linearization scheme for these families,
using which we develop optimization techniques that enable truly point-based
stochastic updates. For concave performance measures we propose SPADE, a
stochastic primal dual solver; for pseudo-linear measures we propose STAMP, a
stochastic alternate maximization procedure. Both methods have crisp
convergence guarantees, demonstrate significant speedups over existing methods
- often by an order of magnitude or more, and give similar or more accurate
predictions on test data.

本文提出一种自适应线性化技术，实现了基于 TPR 和 TNR 的点随机更新，通过提出 SPADE 和 STAMP 方法，可以应对实际中出现的数据标签不平衡及其他特殊要求，并获得了显着的速度优势和精准度，同时确保了收敛性。