Abstract: Machine learning technologies have been increasingly used in high-stakes decision making systems,which raises a new challenge of avoiding unfair and discriminatory decisions for protected classes.Among the techniques for improving the fairness of AI systems, the optimization-based method, whichtrains a model through optimizing its prediction performance subject to fairness constraints, is mostpopular because of its intuitive idea and the Pareto efficiency it provides when trading off predictionperformance against fairness. The criteria of fairness based on the area under the ROC curve (AUC) areemerging recently because they are threshold-agnostic and effective for unbalanced data. In this work,we formulate the training of a machine learning model under the AUC-based fairness constraints into amin-max optimization problem with min-max constraints. Based on this formulation, we developstochastic first-order methods for learning predictive models with a balance between accuracy andfairness. We present the theoretical complexity of the obtained methods and numerically demonstratetheir effectiveness on real-world data under different fairness metrics.