Stochastic Online AUC Maximization
Area under ROC (AUC) is a metric which is widely used for measuring the classification performance for imbalanced data. It is of theoretical and practical interest to develop online learning algorithms that maximizes AUC for large-scale data. A specific challenge in developing online AUC maximization algorithm is that the learning objective function is usually defined over a pair of training examples of opposite classes, and existing methods achieves on-line processing with higher space and time complexity. In this work, we propose a new stochastic online algorithm for AUC maximization. In particular, we show that AUC optimization can be equivalently formulated as a convex-concave saddle point problem. From this saddle representation, a stochastic online algorithm (SOLAM) is proposed which has time and space complexity of one datum. We establish theoretical convergence of SOLAM with high probability and demonstrate its effectiveness on standard benchmark datasets.
This paper proposes an online algorithm for AUC maximization with low per-iteration space and time complexity.  The numerical experiments also suggest the performance of the proposed algorithm is comparable with existing algorithms with higher complexity.  
1. I doubt whether the first equality of (8) holds:   In the first equality, the authors were assuming E[(wx)(wx') | y=1, y'=-1] = E[wx | y=1] E[wx' | y'=-1]. I guess the authors believe this is true because (x,y) and (x',y') are independent samples. However, two independent random variables are not necessarily conditional independent.   For instance, let X1 and X2 be two i.i.d. sample from distribution X= 1 with prob 1/2 and X=-1 with prob 1/2. Then, conditional on X1 = X2, they are no longer independent. Note E[X1 X2 | X1=X2] = 1 while E[X1 | X1 = X2] = E[X2| X1=X2] = 0.   Of course, my example above does not imply this paper could not have the independence for wx and wx' conditional on (y=1, y=-1). Maybe the authors have a different reason for the expectation identity, e.g., conditional uncorrelated? The authors should justify this step.  2. Related to the above, it is very surprising that the independence between (x,y) and (x', y') disappear in the saddle point function. Remember that the argument in (8) requires the independence of (x,y) and (x, y'). But in the end when everything is written as integration, this information is gone. The authors just treat two integration variables as the same thing! This is how they got equation (6). However, by doing so, the physical meaning of indicator functions inside the integration are changed. Some of the indicator functions should be defined in one label y and some should be defined in another label y'. (So when you run an online gradient type alg, you need two samples to evaluate the point gradient.) But this paper just define all indicator functions in terms of the same y at the end of the proof for Thm 1. That's why their alg only need one sample to have online update.   So I think even if (8) is correct, the authors can not simply write two expectations conditional on two different y as integrations with respect to the same variable. The original utility (4) by nature involves two samples and so should the reformulation in Thm 1.  3 Another comment on the proof of Thm 1 is:  The saddle point argument from equation (8) in the proof for Thm 1 can be better explained. If we define the objective function in (3) as h(w), then the proof starting from (8) is to show "by introducing other (dummy) variables, h(w) is equal to min_{a,b} max_{alpha} F(w,a,b, alpha) for any w." (Although, given w, the minimizing and maximizing points (a,b) and (alpha) are actually fixed,  F is preferred because expectations conditional on two labels are now decoupled as the sum of two expectations conditional on a single label.)  Now if we minimize w on both sides, min_w h(w) is equivalent to min_{w,a,b} max_{alpha} F(w,a,b, alpha) and the solutions with respect to w on both sides are the same. The solution w to min_{w,a,b} max_{alpha} F(w,a,b, alpha) is given by a saddle point because F is convex-concave function.