Performance-Aligned Learning Algorithms with Statistical Guarantees

The goal of many prediction tasks in machine learning is to learn a prediction function that minimizes certain loss metrics (e.g., zero-one, ordinal, and cost-sensitive loss) or maximizes certain performance metrics (e.g., accuracy, precision, recall, F1-score, and ROC curve) on the testing dataset. Unfortunately, optimizing these metrics directly via empirical risk minimization is known to be intractable. In practice, convex surrogate losses over the desired metrics are needed in order to build efficient learning algorithms. Two main paradigms for constructing learning algorithms, probabilistic and large-margin approaches, come with their own strengths and weaknesses. This thesis addresses the challenges of overcoming the weaknesses of the probabilistic and large-margin methods by constructing new learning algorithms that simultaneously satisfy the desired properties of: (1) aligning with the learning objective by incorporating customized performance/loss metrics into the learning process; (2) providing the statistical guarantee of Fisher consistency; (3) enjoying computational efficiency; and (4) performing competitively in practice. Our approach for constructing the learning algorithms is based on the robust adversarial formulation, i.e., by focusing on answering the question: “what predictor best maximizes the performance metric (or minimizes the loss metric) in the worst case given the statistical summaries of the empirical distributions?” We focus on two different areas of machine learning: general multiclass classification and structured prediction. In both areas, we demonstrate the theoretical and practical benefit of our methods.