arXiv research

New bounds show polyhedral surrogates are optimal for generalization.

We study the rates of convergence from empirical surrogate risk minimizers to the Bayes optimal classifier. Specifically, we introduce the notion of \emph{consistency intensity} to characterize a surrogate loss function and exploit this notion to obtain the rate of convergence from an empirical surrogate risk minimizer…

Adversarial consistency depends on the uniqueness of adversarial Bayes classifiers.

We carefully study how well minimizing convex surrogate loss functions, corresponds to minimizing the misclassification error rate for the problem of binary classification with linear predictors. In particular, we show that amongst all convex surrogate losses, the hinge loss gives essentially the best possible bound, o…

The minimization of loss functions is the heart and soul of Machine Learning. In this paper, we propose an off-the-shelf optimization approach that can minimize virtually any non-differentiable and non-decomposable loss function (e.g. Miss-classification Rate, AUC, F1, Jaccard Index, Mathew Correlation Coefficient, etc…

In this dissertation, we focus on several important problems in structured prediction. In structured prediction, the label has a rich intrinsic substructure, and the loss varies with respect to the predicted label and the true label pair. Structured SVM is an extension of binary SVM to adapt to such structured tasks. I…

This research analyzes the consistency of convex and nonconvex surrogate losses for adversarially robust classification.

SAM minimizes loss sharpness, improving adversarial transferability.

The paper studies consistency of surrogate loss procedures under constrained classifiers.

We consider the problem of rank loss minimization in the setting of multilabel classification, which is usually tackled by means of convex surrogate losses defined on pairs of labels. Very recently, this approach was put into question by a negative result showing that commonly used pairwise surrogate losses, such as ex…

Study of estimation errors in surrogate loss minimizers, providing stronger guarantees than existing methods.

Paper introduces new loss functions for multi-class abstention learning.

Study on learning to defer with multiple experts using new surrogate losses.

Symmetric losses improve classifier robustness from corrupted labels.

We establish linear regret bounds for convex smooth losses using Fenchel-Young losses.

Paper analyzes proper losses and their performance in machine learning tasks.

We provide novel theoretical insights on structured prediction in the context of efficient convex surrogate loss minimization with consistency guarantees. For any task loss, we construct a convex surrogate that can be optimized via stochastic gradient descent and we prove tight bounds on the so-called "calibration func…

We propose a robust adversarial prediction framework for general multiclass classification. Our method seeks predictive distributions that robustly optimize non-convex and non-continuous multiclass loss metrics against the worst-case conditional label distributions (the adversarial distributions) that (approximately) m…

Empirical risk minimization frequently employs convex surrogates to underlying discrete loss functions in order to achieve computational tractability during optimization. However, classical convex surrogates can only tightly bound modular loss functions, sub-modular functions or supermodular functions separately while …

Proposes a method for inference in high-dimensional classification with non-differentiable surrogate losses.

Study tackles criterion collapse in learning criteria, showing conditions for loss minimization.

Unified surrogate loss framework for multi-label learning with strong consistency guarantees.

Paper extends SMM to weakly convex and multi-convex surrogates for non-convex optimization.

MRCs minimize worst-case expected 0-1 loss and provide performance guarantees.

We study consistency properties of machine learning methods based on minimizing convex surrogates. We extend the recent framework of Osokin et al. (2017) for the quantitative analysis of consistency properties to the case of inconsistent surrogates. Our key technical contribution consists in a new lower bound on the ca…

Local update methods' performance depends on learning rates, affecting convergence rates and alignment with true loss.

Conventional techniques for supervised classification constrain the classification rules considered and use surrogate losses for classification 0-1 loss. Favored families of classification rules are those that enjoy parametric representations suitable for surrogate loss minimization, and low complexity properties suita…

New algorithms for multi-class classification with abstention.

This paper improves SAM by reformulating it as a bilevel optimization problem.

STORM enables edge computing for empirical risk minimization.

This paper develops convex surrogates for optimizing the multi-label F-measure.

In classification, the de facto method for aggregating individual losses is the average loss. When the actual metric of interest is 0-1 loss, it is common to minimize the average surrogate loss for some well-behaved (e.g. convex) surrogate. Recently, several other aggregate losses such as the maximal loss and average t…

A new method SLIDE ensures fairness in AI models.

We present surrogate regret bounds for arbitrary surrogate losses in the context of binary classification with label-dependent costs. Such bounds relate a classifier's risk, assessed with respect to a surrogate loss, to its cost-sensitive classification risk. Two approaches to surrogate regret bounds are developed. The…

Study on top-$k$ classification with new loss functions and algorithms.

We formalize and study the natural approach of designing convex surrogate loss functions via embeddings, for problems such as classification, ranking, or structured prediction. In this approach, one embeds each of the finitely many predictions (e.g.\ rankings) as a point in $\mathbb{R}^d$, assigns the original loss val…

Study on calibration and consistency of adversarial surrogate losses.

EnsLoss combines multiple loss functions to prevent overfitting in classification.

New algorithm reduces online logistic regression regret without exponential constant.

Learning with non-modular losses is an important problem when sets of predictions are made simultaneously. The main tools for constructing convex surrogate loss functions for set prediction are margin rescaling and slack rescaling. In this work, we show that these strategies lead to tight convex surrogates iff the unde…

New method simplifies checking consistency of differentiable loss functions.

The problem of bipartite ranking, where instances are labeled positive or negative and the goal is to learn a scoring function that minimizes the probability of mis-ranking a pair of positive and negative instances (or equivalently, that maximizes the area under the ROC curve), has been widely studied in recent years. …

Study improves top-k set prediction with low cardinality.

Active learning is a type of sequential design for supervised machine learning, in which the learning algorithm sequentially requests the labels of selected instances from a large pool of unlabeled data points. The objective is to produce a classifier of relatively low risk, as measured under the 0-1 loss, ideally usin…

Paper establishes a universal growth rate for smooth surrogate losses in classification.

Study on $H$-consistency bounds for machine learning surrogates.

AUC (area under ROC curve) is an important evaluation criterion, which has been popularly used in many learning tasks such as class-imbalance learning, cost-sensitive learning, learning to rank, etc. Many learning approaches try to optimize AUC, while owing to the non-convexity and discontinuousness of AUC, almost all …

Study of loss functions for learning to defer, proving consistency.