New bounds show polyhedral surrogates are optimal for generalization.
problem Proving generalization rates for polyhedral loss functions.
method Developed two general results for polyhedral surrogates.
result Polyhedral surrogates provide linear surrogate regret bounds, translating directly to target rates.
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…
We establish linear regret bounds for convex smooth losses using Fenchel-Young losses.
problem Establishing linear regret bounds for convex smooth losses.
method Constructing a convex smooth surrogate loss using Fenchel-Young losses generated by the convolutional negentropy.
result We derive a smooth loss with a linear surrogate regret bound.
Paper introduces new loss functions for multi-class abstention learning.
problem Learning with multi-class classification and the ability to abstain.
method Developed new families of surrogate losses for abstention.
result Proved strong consistency guarantees for new surrogate losses.
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 Rd, assigns the original loss val…
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…
Study on calibration and consistency of adversarial surrogate losses.
problem Designing robust classifiers with theoretical guarantees.
method Extensive analysis of H-calibration and H-consistency of adversarial surrogate losses.
result Some convex loss functions and supremum-based convex losses are not H-calibrated for important hypothesis sets.
Study on learning to defer with multiple experts using new surrogate losses.
problem Learning to defer with multiple experts in a machine learning context.
method Introducing a new family of surrogate losses for the multiple-expert setting, proving H-consistency bounds, and designing learning algorithms. result Explicit guarantees for new learning to defer algorithms based on minimization of these surrogate losses.
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…
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.
problem Verifying consistency of differentiable loss functions is difficult.
method Developed a new approach called strong indirect elicitation (strong IE) to simplify checking consistency.
result Strong IE is equivalent to calibration for strongly convex, differentiable surrogates.
The paper studies consistency of surrogate loss procedures under constrained classifiers.
problem Consistency of surrogate loss approaches under constrained classifiers without correct specification.
method The paper develops theoretical results and hinge loss based procedures for a constrained classification problem.
result Hinge losses are the only surrogate losses that preserve consistency in second-best scenarios.
Adversarial consistency depends on the uniqueness of adversarial Bayes classifiers.
problem Consistency of adversarial surrogate losses is not guaranteed.
method Connected consistency of adversarial surrogate losses to the uniqueness of adversarial Bayes classifiers.
result A convex surrogate loss is statistically consistent for adversarial learning if and only if the adversarial Bayes classifier is unique.
Unified surrogate loss framework for multi-label learning with strong consistency guarantees.
problem Improving consistency and accounting for label correlations in multi-label learning.
method Introducing multi-label logistic loss and extending it to comprehensive multi-label comp-sum losses, proving strong consistency guarantees for any multi-label loss.
result Unified surrogate loss framework benefiting from strong consistency guarantees for any multi-label loss.
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…
This research analyzes the consistency of convex and nonconvex surrogate losses for adversarially robust classification.
problem Ensuring classifiers are robust to adversarial perturbations.
method Analysis of convex and nonconvex surrogate losses through the lens of calibration.
result No convex surrogate loss is calibrated with respect to the adversarial 0-1 loss for linear models, but nonconvex losses can be calibrated under certain conditions.
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…
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.
problem Analyzing growth rates of consistency bounds for various surrogate losses.
method Proves square-root growth rate for smooth margin-based losses; extends to multi-class classification.
result Demonstrates a universal square-root growth rate for smooth comp-sum and constrained losses.
Study on H-consistency bounds for machine learning surrogates.
problem Estimating target loss error relative to surrogate loss error in machine learning.
method Developed H-consistency bounds for various surrogates and loss functions. result Stronger guarantees than existing methods, offering distribution-dependent and -independent bounds.
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 …
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.
problem Learning to defer in machine learning.
method Introduced a family of surrogate losses parameterized by Ψ and proved their consistency. result Proved realizable H-consistency and Bayes-consistency of specific surrogate losses. Proposes a method for inference in high-dimensional classification with non-differentiable surrogate losses.
problem Lack of inference procedures for identifying driving factors in high-dimensional classification with non-differentiable surrogate losses.
method Kernel-smoothed decorrelated score and cross-fitted version for hypothesis tests and interval estimators.
result Valid and superior inference methods for high-dimensional classification with non-differentiable surrogate losses.
We study consistency properties of surrogate loss functions for general multiclass learning problems, defined by a general multiclass loss matrix. We extend the notion of classification calibration, which has been studied for binary and multiclass 0-1 classification problems (and for certain other specific learning pro…
Symmetric losses improve classifier robustness from corrupted labels.
problem Improving classifier performance from corrupted labels.
method Symmetric losses that satisfy a certain condition.
result Symmetric losses enhance robust classification from corrupted labels.
In this paper we refine the process of computing calibration functions for a number of multiclass classification surrogate losses. Calibration functions are a powerful tool for easily converting bounds for the surrogate risk (which can be computed through well-known methods) into bounds for the true risk, the probabili…
Study proposes a differentiable surrogate loss function for optimizing Fβ score in binary classification with imbalanced data.
problem Non-differentiability of Fβ score makes it unsuitable for optimization by gradient-based learning. method Investigated relationship between Fβ score and loss functions, proposed a differentiable surrogate loss function. result Gradient paths of the proposed surrogate Fβ loss function approximate the gradient paths of the Fβ score. 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…
New PG losses improve decision optimization in misspecified models.
problem Improving decision optimization in models that are not perfectly specified.
method Introducing Perturbation Gradient (PG) losses to connect decision loss with directional derivatives and optimizing using gradient techniques.
result PG losses yield best-in-class policies asymptotically, even in misspecified settings.
Bayes-consistent disagreement discrepancy loss improves model robustness.
problem Distribution shift in real-world neural network deployment.
method Introducing a novel disagreement loss that is Bayes consistent.
result Proves existing surrogates for disagreement discrepancy are not Bayes consistent.
Study of estimation errors in surrogate loss minimizers, providing stronger guarantees than existing methods.
problem Estimation errors in surrogate loss minimizers for various hypothesis sets.
method Detailed study of H-consistency estimation error bounds, proving general theorems for distribution-dependent and independent settings. result Explicit bounds for zero-one and adversarial losses, showing enhancements under distributional assumptions.
Paper analyzes proper losses and their performance in machine learning tasks.
problem Understanding the performance of estimators and forecasters in machine learning tasks.
method Analyzes surrogate regret and convergence rates for strictly proper losses.
result Strongly proper losses achieve the optimal convergence rate.
Area under ROC (AUC) is an important metric for binary classification and bipartite ranking problems. However, it is difficult to directly optimizing AUC as a learning objective, so most existing algorithms are based on optimizing a surrogate loss to AUC. One significant drawback of these surrogate losses is that they …
New algorithms for multi-class classification with abstention.
problem Learning with abstention in multi-class classification.
method Introducing new surrogate losses and analyzing predictor-rejector framework.
result Strong consistency guarantees for abstention loss function.
Linear-Core Surrogates combine fast optimization and statistical efficiency in classification and structured prediction.
problem The trade-off between smoothness and margin-based losses in classification and structured prediction.
method Linear-Core (LC) Surrogates, a family of convex loss functions that stitch a linear core to a smooth tail.
result LC Surrogates achieve fast linear consistency rates while maintaining differentiability and strict H-consistency bounds. Local update methods' performance depends on learning rates, affecting convergence rates and alignment with true loss.
problem The performance of local update methods in federated learning and meta-learning is sensitive to learning rates.
method Proved that local update methods perform SGD on a surrogate loss function, characterized the surrogate loss, and derived convergence rates.
result Proper learning rate tuning is crucial for near-optimal behavior in communication-limited settings.
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…
This work improves neural likelihood surrogates for stochastic models with a score-augmented loss.
problem Efficient parameter inference for stochastic models with computationally expensive likelihood functions.
method Score-augmented loss function for neural network likelihood surrogates.
result Improves surrogate quality at a lower computational cost compared to generating more data.
This paper tackles deferral learning with multiple experts, providing strong theoretical guarantees.
problem Optimizing input assignment to experts balancing accuracy and computational cost.
method Introducing new surrogate loss functions and efficient algorithms with strong theoretical learning guarantees.
result Realizable H-consistency, H-consistency bounds, and Bayes-consistency for deferral learning. A new framework learns differentiable structured losses from data.
problem Learning effective losses for complex structured prediction tasks.
method Contrastive learning to learn differentiable structured losses from output data.
result Achieves similar or better performance than kernel-based methods.
Study on learning to defer to multiple experts with consistent surrogates and confidence calibration.
problem Addressing the open problems of consistent surrogates, confidence calibration, and ensembling of experts.
method Derive two consistent surrogates (softmax and OvA) and propose a conformal inference technique for choosing experts.
result The OvA-based loss does not cause mis-calibration propagation, while the softmax-based loss does.
We study losses for binary classification and class probability estimation and extend the understanding of them from margin losses to general composite losses which are the composition of a proper loss with a link function. We characterise when margin losses can be proper composite losses, explicitly show how to determ…
The paper explores trading off consistency and dimensionality in convex surrogates for multiclass classification.
problem Designing consistent surrogate losses for multiclass classification with high-dimensional outcomes.
method Investigates embedding outcomes into convex polytopes and examining consistency under low-noise assumptions.
result Consistency can be achieved with less than n−1 dimensions, but hallucination occurs for some distributions. In this work we provide a theoretical framework for structured prediction that generalizes the existing theory of surrogate methods for binary and multiclass classification based on estimating conditional probabilities with smooth convex surrogates (e.g. logistic regression). The theory relies on a natural characteriza…
This research improves PAC-Bayesian bounds for classification tasks using convexified loss.
problem Deriving generalization bounds for classification tasks with non-convex loss functions.
method Shift focus to misclassification excess risk bounds for PAC-Bayesian classification using convex surrogate loss and leveraging PAC-Bayesian relative bounds in expectation.
result Improved PAC-Bayesian bounds for classification tasks with convex surrogate loss.
Study improves H-consistency bounds for regression analysis.
problem Improving H-consistency bounds for regression analysis. method Generalized theorems and novel H-consistency bounds for various surrogate loss functions. result Derives principled surrogate losses for adversarial regression.