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.
Paper bounds convergence rate of adversarial surrogate risk.
problem Vulnerability of binary classification models to adversarial attacks.
method Characterizes conditions for adversarial consistency and provides surrogate risk bounds.
result Surrogate risk bounds quantify the rate of convergence of adversarial classification risk.
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.
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.
STORM enables edge computing for empirical risk minimization.
problem Training models on edge devices for streaming data.
method Online sketching for empirical risk minimization.
result STORM can estimate least-squares objective accurately.
New method integrates real and synthetic data to improve machine learning models.
problem Expensive or impractical collection of high-quality data limits machine learning.
method Weighted empirical risk minimization approach for integrating surrogate data.
result Integrating surrogate data can significantly reduce test error on the original distribution.
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…
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 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.
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.
Paper extends SMM to weakly convex and multi-convex surrogates for non-convex optimization.
problem Non-convex optimization with weakly convex or multi-convex surrogates.
method Stochastic majorization-minimization with proximal regularization or block-minimization.
result Convergence rates for empirical and expected losses under non-i.i.d. data.
MRCs minimize worst-case expected 0-1 loss and provide performance guarantees.
problem Minimizing expected 0-1 loss in classification.
method Minimizes worst-case expected 0-1 loss over uncertainty sets defined by linear constraints.
result Achieves efficient learning and generalization with performance guarantees.
New algorithm reduces online logistic regression regret without exponential constant.
problem Improper learning in online logistic regression with logarithmic regret.
method Regularized empirical risk minimization with surrogate losses.
result Regret scaling as O(B log(Bn)) with low computational complexity.
New active learning framework for multiclass classification beyond realizability assumption.
problem Active learning in non-realizable settings with convex model classes.
method Surrogate risk minimization, epoch-based fitting, aggregation of models.
result Achieves label and sample complexity comparable to prior work in non-realizable settings.
We propose a general approach for supervised learning with structured output spaces, such as combinatorial and polyhedral sets, that is based on minimizing estimated conditional risk functions. Given a loss function defined over pairs of output labels, we first estimate the conditional risk function by solving a (possi…
A new method SLIDE ensures fairness in AI models.
problem Ensuring fairness in AI models while maintaining computational feasibility.
method Proposes a new surrogate fairness constraint SLIDE.
result SLIDE ensures fairness in AI models asymptotically and converges fast.
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…
UREs lead to overfitting in complex models, especially in complementary label learning.
problem Overfitting in weakly supervised learning with complementary labels.
method Proposed a surrogate complementary loss (SCL) framework to reduce gradient variance.
result SCL mitigates overfitting and improves URE-based methods.
The paper analyzes risk bounds and Rademacher complexity in batch RL.
problem Estimating/minimizing Bellman error with general value function approximation.
method Characterizes generalization performance using Rademacher complexities of function classes.
result Risk bounds and Rademacher complexities provide insights into batch RL.
Study tackles criterion collapse in learning criteria, showing conditions for loss minimization.
problem Criterion collapse in optimization, focusing on error probability minimizers.
method Analyzes various learning criteria, including DRO, OCE risks, and non-monotonic criteria.
result Non-monotonic criteria can avoid collapse, while monotonic ones cannot.
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…
We develop an approach to risk minimization and stochastic optimization that provides a convex surrogate for variance, allowing near-optimal and computationally efficient trading between approximation and estimation error. Our approach builds off of techniques for distributionally robust optimization and Owen's empiric…
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…
Develops a SAS approach for high-dimensional risk prediction using unlabeled data.
problem Challenges in risk modeling with EHR data due to lack of direct disease outcomes and high dimensionality.
method Surrogate Assisted Semi-supervised Learning (SAS) approach leveraging unlabeled and labeled data.
result Valid inference for predicted risk even when underlying model is dense and mis-specified.
Sharp analysis of knowledge distillation for high-dimensional regression.
problem Characterizing the risk of target models in high-dimensional settings.
method Sharp non-asymptotic bounds for ridgeless regression under model and distribution shifts.
result Identifies optimal surrogate models and reveals benefits and limitations of discarding weak features.
In this work we investigate to which extent one can recover class probabilities within the empirical risk minimization (ERM) paradigm. The main aim of our paper is to extend existing results and emphasize the tight relations between empirical risk minimization and class probability estimation. Based on existing literat…
New approach avoids excess empirical risk in domain generalization.
problem Learning models that generalize to unseen distributions from diverse data sets.
method Minimizes penalty under constraint of optimal empirical risk, leveraging rate-distortion theory.
result Significant improvements in domain generalization performance across multiple methods.
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 …
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.
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.
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.
This paper improves risk bounds and calibration for smart predict-then-optimize method.
problem Improving risk bounds and calibration for smart predict-then-optimize method.
method Develops risk bounds and uniform calibration results for the SPO+ loss relative to the SPO loss.
result Empirical minimizer of the SPO+ loss achieves low excess true risk with high probability.
This paper develops convex surrogates for optimizing the multi-label F-measure.
problem Optimizing the F-measure for multi-label classification is computationally hard.
method Designing convex surrogate losses calibrated for the F-measure.
result The F-measure for multi-label problems has a rank of at most s2+1. In stochastic optimization, the population risk is generally approximated by the empirical risk. However, in the large-scale setting, minimization of the empirical risk may be computationally restrictive. In this paper, we design an efficient algorithm to approximate the population risk minimizer in generalized linear …
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…
In statistical learning theory, convex surrogates of the 0-1 loss are highly preferred because of the computational and theoretical virtues that convexity brings in. This is of more importance if we consider smooth surrogates as witnessed by the fact that the smoothness is further beneficial both computationally- by at…
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…
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…
A new method for learning to defer decisions with expert advice improves over standard methods.
problem Learning to defer decisions with expert advice in systems where expert information can be modified after selection.
method An augmented surrogate that operates on the composite expert-advice action space, providing consistency guarantees and excess-risk bounds.
result The method improves over standard Learning-to-Defer and adapts its advice acquisition behavior to the cost regime.
Learning from triplet comparison data has been extensively studied in the context of metric learning, where we want to learn a distance metric between two instances, and ordinal embedding, where we want to learn an embedding in an Euclidean space of the given instances that preserves the comparison order as well as pos…
New method optimises learning via surrogate PAC-Bayes bounds.
problem Computational intractability of optimising generalisation bounds.
method Iteratively optimising surrogate training objectives derived from PAC-Bayes bounds.
result Iteratively optimising surrogates implies optimising original generalisation bounds.
We present α-loss, α∈[1,∞], a tunable loss function for binary classification that bridges log-loss (α=1) and 0-1 loss (α=∞). We prove that α-loss has an equivalent margin-based form and is classification-calibrated, two desirable properties for a good surrogate loss function for the ideal y…
Comment on entropy learning for dynamic treatment regimes.
problem Evaluating dynamic treatment regimes using entropy loss.
method Optimization-based alternative to IPW estimate.
result Suggests optimization-based approach for evaluation.
Derivative-informed models improve financial surrogates for accurate hedging and risk management.
problem Developing fast surrogate models for financial derivatives and risk quantities.
method Derivative-informed operator learning framework combining neural operators, random features, and tangent sensitivity equations.
result The framework reduces hedging and risk errors by 40-76% compared to standard surrogates.
SAM minimizes loss sharpness, improving adversarial transferability.
problem Improving adversarial transferability of deep neural networks.
method Evaluating surrogate models trained with seven minimizers, focusing on loss sharpness and flat neighborhoods.
result SAM minimizes loss sharpness, leading to better adversarial transferability.
EnsLoss combines multiple loss functions to prevent overfitting in classification.
problem Preventing overfitting in classification models.
method EnsLoss is an ensemble method that combines loss functions, ensuring calibration and consistency.
result EnsLoss improves classification accuracy compared to fixed loss methods.
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.
Ordinal regression is aimed at predicting an ordinal class label. In this paper, we consider its semi-supervised formulation, in which we have unlabeled data along with ordinal-labeled data to train an ordinal regressor. There are several metrics to evaluate the performance of ordinal regression, such as the mean absol…