# American Institute of Mathematical Sciences

• Previous Article
Approximation by multivariate max-product Kantorovich-type operators and learning rates of least-squares regularized regression
• CPAA Home
• This Issue
• Next Article
A numerical method to compute Fisher information for a special case of heterogeneous negative binomial regression
August  2020, 19(8): 4191-4212. doi: 10.3934/cpaa.2020188

## Stochastic AUC optimization with general loss

 1 Department of Mathematics and Statistics, State University of New York at Albany, Albany, NY 12206, USA 2 Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Kowloon, Hong Kong, China 3 Department of Mathematics, The University of Hong Kong, Hong Kong, China

* Corresponding author

Received  October 2019 Revised  January 2020 Published  May 2020

Fund Project: This work was completed when Wei Shen was a visiting student at SUNY Albany. Yiming Ying is supported by the National Science Foundation (NSF, Grant IIS1816227)

Recently, there is considerable work on developing efficient stochastic optimization algorithms for AUC maximization. However, most of them focus on the least square loss which may be not the best option in practice. The main difficulty for dealing with the general convex loss is the pairwise nonlinearity w.r.t. the sampling distribution generating the data. In this paper, we use Bernstein polynomials to uniformly approximate the general losses which are able to decouple the pairwise nonlinearity. In particular, we show that this reduction for AUC maximization with a general loss is equivalent to a weakly convex (nonconvex) min-max formulation. Then, we develop a novel SGD algorithm for AUC maximization with per-iteration cost linearly w.r.t. the data dimension, making it amenable for streaming data analysis. Despite its non-convexity, we prove its global convergence by exploring the appealing convexity-preserving property of Bernstein polynomials and the intrinsic structure of the min-max formulation. Experiments are performed to validate the effectiveness of the proposed approach.

Citation: Zhenhuan Yang, Wei Shen, Yiming Ying, Xiaoming Yuan. Stochastic AUC optimization with general loss. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4191-4212. doi: 10.3934/cpaa.2020188
##### References:

show all references

##### References:
Comparison of convergence speed between SAUC-H and $\text{OAM}_{gra}$
Evaluation of AUC scores vesus the degree of the Bernstein polynomial
 Algorithm 1: Stochastic AUC Optimization (SAUC) 1: Input: $R>0$, $\gamma\geq\gamma_0$ and $\beta>0$. 2: Initialize $\bar{{\mathbf{v}}}_0 = 0$ and $\bar{{\mathit{\boldsymbol{\alpha}}}}_0 = 0$. 3: for $t=1$ to $T-1$ do4: Set ${\mathbf{v}}_0^t = \bar{{\mathbf{v}}}_{t-1}, {\mathit{\boldsymbol{\alpha}}}_0^t = \bar{{\mathit{\boldsymbol{\alpha}}}}_{t-1}$ and $\eta_t = \frac{\beta}{\sqrt{t}}.$ 5: for $j=1$ to $t$ do 6: Randomly sample $z_j^t = (x_j^t,y_j^t)$ and compute \begin{align*} &{\mathbf{v}}_{j}^t = {{\bf Proj}}_{{\Omega}_1} \bigl({\mathbf{v}}_{j-1}^t - \eta_t \nabla_{{\mathbf{v}}} \varPhi_{\gamma}^t({\mathbf{v}}_{j-1}^t,{\mathit{\boldsymbol{\alpha}}}_{j-1}^t;z_j^t)\bigr), &{\mathit{\boldsymbol{\alpha}}}_{j}^t = {{\bf Proj}}_{{\Omega}_2} \bigl({\mathit{\boldsymbol{\alpha}}}_{j-1}^t + \eta_t \nabla_{{\mathit{\boldsymbol{\alpha}}}} \varPhi_{\gamma}^t({\mathbf{v}}_{j-1}^t,{\mathit{\boldsymbol{\alpha}}}_{j-1}^t;z_j^t)\bigr) \end{align*} 7: end for 8: Compute $\bar{{\mathbf{v}}}_{t} = \frac{1}{t}\sum_{j=0}^{t-1} {\mathbf{v}}_j^t$ and $\bar{{\mathit{\boldsymbol{\alpha}}}}_{t} = \frac{1}{t}\sum_{j=0}^{t-1} {\mathit{\boldsymbol{\alpha}}}_j^t.$9: end for 10: Output: $\widetilde{{\mathbf{v}}}_T:=\frac{1}{T}\sum_{t=0}^{T-1}\bar{{\mathbf{v}}}_{t}$ and $\widetilde{{\mathit{\boldsymbol{\alpha}}}}_T:=\frac{1}{T}\sum_{t=0}^{T-1}\bar{{\mathit{\boldsymbol{\alpha}}}}_{t}.$
 Algorithm 1: Stochastic AUC Optimization (SAUC) 1: Input: $R>0$, $\gamma\geq\gamma_0$ and $\beta>0$. 2: Initialize $\bar{{\mathbf{v}}}_0 = 0$ and $\bar{{\mathit{\boldsymbol{\alpha}}}}_0 = 0$. 3: for $t=1$ to $T-1$ do4: Set ${\mathbf{v}}_0^t = \bar{{\mathbf{v}}}_{t-1}, {\mathit{\boldsymbol{\alpha}}}_0^t = \bar{{\mathit{\boldsymbol{\alpha}}}}_{t-1}$ and $\eta_t = \frac{\beta}{\sqrt{t}}.$ 5: for $j=1$ to $t$ do 6: Randomly sample $z_j^t = (x_j^t,y_j^t)$ and compute \begin{align*} &{\mathbf{v}}_{j}^t = {{\bf Proj}}_{{\Omega}_1} \bigl({\mathbf{v}}_{j-1}^t - \eta_t \nabla_{{\mathbf{v}}} \varPhi_{\gamma}^t({\mathbf{v}}_{j-1}^t,{\mathit{\boldsymbol{\alpha}}}_{j-1}^t;z_j^t)\bigr), &{\mathit{\boldsymbol{\alpha}}}_{j}^t = {{\bf Proj}}_{{\Omega}_2} \bigl({\mathit{\boldsymbol{\alpha}}}_{j-1}^t + \eta_t \nabla_{{\mathit{\boldsymbol{\alpha}}}} \varPhi_{\gamma}^t({\mathbf{v}}_{j-1}^t,{\mathit{\boldsymbol{\alpha}}}_{j-1}^t;z_j^t)\bigr) \end{align*} 7: end for 8: Compute $\bar{{\mathbf{v}}}_{t} = \frac{1}{t}\sum_{j=0}^{t-1} {\mathbf{v}}_j^t$ and $\bar{{\mathit{\boldsymbol{\alpha}}}}_{t} = \frac{1}{t}\sum_{j=0}^{t-1} {\mathit{\boldsymbol{\alpha}}}_j^t.$9: end for 10: Output: $\widetilde{{\mathbf{v}}}_T:=\frac{1}{T}\sum_{t=0}^{T-1}\bar{{\mathbf{v}}}_{t}$ and $\widetilde{{\mathit{\boldsymbol{\alpha}}}}_T:=\frac{1}{T}\sum_{t=0}^{T-1}\bar{{\mathit{\boldsymbol{\alpha}}}}_{t}.$
Statistics of datasets
Comparison of AUC score (mean$\pm$std) on test data; OPAUC on news20 and sector does not converge in a reasonable time limit. Best AUC value on each dataset is in bold and second is underlined
 [1] Lu Han, Min Li, Dachuan Xu, Dongmei Zhang. Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2607-2614. doi: 10.3934/jimo.2020085 [2] David Yang Gao, Changzhi Wu. On the triality theory for a quartic polynomial optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (1) : 229-242. doi: 10.3934/jimo.2012.8.229 [3] Jong Uhn Kim. On the stochastic Burgers equation with a polynomial nonlinearity in the real line. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 835-866. doi: 10.3934/dcdsb.2006.6.835 [4] Shenggui Zhang. A sufficient condition of Euclidean rings given by polynomial optimization over a box. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 93-101. doi: 10.3934/naco.2014.4.93 [5] Reza Kamyar, Matthew M. Peet. Polynomial optimization with applications to stability analysis and control - Alternatives to sum of squares. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2383-2417. doi: 10.3934/dcdsb.2015.20.2383 [6] Qi Zhang, Huaizhong Zhao. Backward doubly stochastic differential equations with polynomial growth coefficients. Discrete & Continuous Dynamical Systems, 2015, 35 (11) : 5285-5315. doi: 10.3934/dcds.2015.35.5285 [7] Mingshang Hu. Stochastic global maximum principle for optimization with recursive utilities. Probability, Uncertainty and Quantitative Risk, 2017, 2 (0) : 1-. doi: 10.1186/s41546-017-0014-7 [8] Feng Bao, Thomas Maier. Stochastic gradient descent algorithm for stochastic optimization in solving analytic continuation problems. Foundations of Data Science, 2020, 2 (1) : 1-17. doi: 10.3934/fods.2020001 [9] Jingzhen Liu, Yike Wang, Ming Zhou. Utility maximization with habit formation of interaction. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1451-1469. doi: 10.3934/jimo.2020029 [10] Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021030 [11] Wei Mao, Liangjian Hu, Xuerong Mao. Razumikhin-type theorems on polynomial stability of hybrid stochastic systems with pantograph delay. Discrete & Continuous Dynamical Systems - B, 2020, 25 (8) : 3217-3232. doi: 10.3934/dcdsb.2020059 [12] Tijana Levajković, Hermann Mena, Amjad Tuffaha. The stochastic linear quadratic optimal control problem in Hilbert spaces: A polynomial chaos approach. Evolution Equations & Control Theory, 2016, 5 (1) : 105-134. doi: 10.3934/eect.2016.5.105 [13] Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 [14] Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100 [15] Xuepeng Zhang, Zhibin Liang. Optimal layer reinsurance on the maximization of the adjustment coefficient. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 21-34. doi: 10.3934/naco.2016.6.21 [16] Diogo A. Gomes, Gabriele Terrone. Bernstein estimates: weakly coupled systems and integral equations. Communications on Pure & Applied Analysis, 2012, 11 (3) : 861-883. doi: 10.3934/cpaa.2012.11.861 [17] Nicholas Westray, Harry Zheng. Constrained nonsmooth utility maximization on the positive real line. Mathematical Control & Related Fields, 2015, 5 (3) : 679-695. doi: 10.3934/mcrf.2015.5.679 [18] Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215 [19] Lucian Coroianu, Sorin G. Gal. New approximation properties of the Bernstein max-min operators and Bernstein max-product operators. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021034 [20] Cheng-Kang Chen, Yi-Xiang Liao. A deteriorating inventory model for an intermediary firm under return on inventory investment maximization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 989-1000. doi: 10.3934/jimo.2014.10.989

2020 Impact Factor: 1.916