Abstract: The loss function of AUC optimization involves pair-wise instances coming from different classes, so the objective functions of AUC methods, depending on the sum of pair-wise losses, are quadratic in the number of training examples. As a result, the objective functions of this type can not be directly solved through conventional online learning methods. The existing online AUC maximization methods focus on avoiding the direct calculation of all pair-wise loss functions, in order to reduce the problem sizes and achieve the online AUC optimization. To further solve the AUC optimization problems described above, we propose a novel AUC objective function that is only linear in the number of training examples. Theoretical analysis shows the minimization of the proposed objective function is equivalent to that of the objective function for AUC optimization by the combination of L2 regularization and least square surrogate loss. Based on this new objective function, we obtain the method named linear online AUC maximization (LOAM). According to different updating strategies for classifiers, we develop two algorithms for LOAM method: LOAM\-ILSC and LOAM\-Ada. Experimental results show that, compared with the rival methods, LOAM\-ILSC can achieve better AUC performance, and LOAM\-Ada is more effective and efficient to handle real-time or high dimensional learning tasks.