Unhinged loss minimization fails to improve classifier accuracy for simple data.
problem Accuracy of classifiers minimizing the unhinged loss.
method Minimizing the unhinged loss function.
result Minimizing the unhinged loss yields classifiers with accuracy no better than random guessing for simple data.
The paper tackles multi-armed bandits with vector losses, focusing on minimizing the ℓ∞-norm of relative losses.
problem Minimizing the ℓ∞-norm of relative losses in multi-armed bandits with multiple losses. method Defines relative loss vector, derives lower bounds, and provides matching algorithms for both fixed-confidence best-arm identification and regret minimization.
result Derives problem-dependent sample complexity lower bound and matching algorithms for fixed-confidence best-arm identification.
The paper proves deep learning can be robust with certain loss functions.
problem The robustness of deep learning models under flawed data.
method Empirical-risk minimization with unbounded, Lipschitz-continuous loss functions.
result These loss functions provide efficient prediction under minimal data assumptions.
Proposes a new Huber loss combining absolute and quadratic properties.
problem Improving robustness in learning models.
method Introduces a generalized Huber loss with a log-exp transform and provides an efficient minimization algorithm.
result Shows that the new loss function can be minimized efficiently.
Zero loss is achievable in overparametrized DL networks under specific conditions.
problem Achieving zero loss in overparametrized deep learning networks.
method Determine sufficient conditions for zero loss attainability and present an explicit construction of zero loss minimizers.
result Explicit minimizers for zero loss in overparametrized DL networks are constructed without gradient descent.
DLM for BNNs fails to improve over ELBO optimization.
problem Performance of DLM for Bayesian Neural Networks (BNNs).
method Direct Loss Minimization (DLM) compared to ELBO optimization.
result DLM does not significantly improve over ELBO optimization for BNNs.
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 paper studies the loss landscape of regularized deep matrix factorization, revealing unique and sharp minimizers.
problem Understanding the loss landscape and minimizers of regularized deep matrix factorization problems.
method Theoretical analysis of ℓ2-regularized deep matrix factorization/deep linear network training problems with squared-error loss. result The unique end-to-end minimizer exists for all target matrices except for a set of Lebesgue measure zero.
Boosted CVaR Classification improves tail performance in classification tasks.
problem Maximizing tail performance in classification tasks.
method Proposed Boosted CVaR Classification framework using randomized classifiers and LPBoost algorithm.
result Minimizing CVaR loss over randomized classifiers leads to better tail performance.
Unified framework for fair regression under demographic parity.
problem Ensuring fairness in regression tasks subject to demographic parity constraints.
method Proposes a unified framework applicable to various regression tasks with a broad spectrum of loss functions, derived a novel characterization of the fair risk minimizer, and established theoretical consistency and convergence rates.
result Effective minimization of risk while satisfying fairness constraints across various regression settings.
Loss minimization leads to multicalibration for neural networks.
problem Ensuring fairness in predictions across multiple protected groups.
method Minimizing squared loss over neural networks of size n.
result Minimizing loss over neural nets of size n implies multicalibration for most values of n.
The paper improves sparse Gaussian processes by optimizing predictive loss.
problem Optimizing predictive loss in sparse Gaussian processes.
method Direct loss minimization (DLM) for log-loss and square loss, with product sampling (uPS) and biased Monte Carlo (bMC) for non-conjugate cases.
result DLM shows significant performance improvement in both log-loss and square loss cases.
Neural network training relies on our ability to find "good" minimizers of highly non-convex loss functions. It is well-known that certain network architecture designs (e.g., skip connections) produce loss functions that train easier, and well-chosen training parameters (batch size, learning rate, optimizer) produce mi…
In this work, we study data preconditioning, a well-known and long-existing technique, for boosting the convergence of first-order methods for regularized loss minimization. It is well understood that the condition number of the problem, i.e., the ratio of the Lipschitz constant to the strong convexity modulus, has a h…
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…
The probability minimizing problem of large losses of portfolio in discrete and continuous time models is studied. This gives a generalization of quantile hedging presented in [3].
New machine learning paradigm ignores loss function until action time.
problem Learning with unknown loss functions.
method Introduces omnipredictors for any loss function.
result Extracts predictive power from any class, ignoring loss function.
The one-bit quantization is implemented by one single comparator that operates at low power and a high rate. Hence one-bit compressive sensing (1bit-CS) becomes attractive in signal processing. When measurements are corrupted by noise during signal acquisition and transmission, 1bit-CS is usually modeled as minimizing …
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.
Gradient descent implicitly follows regularization for general losses.
problem The implicit bias of gradient descent methods in machine learning.
method Empirical risk minimization over linear predictors with arbitrary convex, strictly decreasing losses.
result Gradient descent and regularization paths converge to the same direction for non-attained risks.
Cross-entropy loss linked to metric learning, outperforming complex pairwise losses.
problem Improving metric learning performance without complex optimization schemes.
method Theoretical analysis linking cross-entropy to pairwise losses, showing cross-entropy as an upper bound and equivalent to mutual information maximization.
result Minimizing cross-entropy is equivalent to maximizing mutual information, leading to state-of-the-art performance.
Gradient descent struggles to achieve zero loss in deep learning models due to non-generic data distributions.
problem Achieving zero loss minimizers in deep learning networks.
method Analysis of gradient descent algorithm in deep learning, focusing on underparametrized networks.
result Zero loss minimization cannot be achieved generically in deep learning networks.
Enhances linear regression with Kalman filter for loss minimization.
problem Minimizing loss in linear regression models.
method Integrates Kalman filter and SGD for optimal weight updates.
result Develops optimal linear regression equation with minimum area under curve.
A method to identify important features without solving the full problem.
problem Identifying important features in high-dimensional data.
method Persistent reduction using extreme ray identification on a polyhedral cone.
result A subset of features can be guaranteed to have zero coefficients in all optimal solutions.
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…
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 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.
Improves model generalization by minimizing loss sharpness.
problem Overparameterized models often fail to generalize well despite low training loss.
method Sharpness-Aware Minimization (SAM) minimizes both loss value and sharpness.
result SAM improves model generalization across various datasets and models.
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…
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.
This paper aims to provide a better understanding of a symmetric loss. First, we emphasize that using a symmetric loss is advantageous in the balanced error rate (BER) minimization and area under the receiver operating characteristic curve (AUC) maximization from corrupted labels. Second, we prove general theoretical p…
This paper improves SAM by reformulating it as a bilevel optimization problem.
problem Improving Sharpness-Aware Minimization (SAM) for better performance.
method Reformulate SAM as a bilevel optimization problem using a 0-1 loss surrogate.
result BiSAM consistently results in improved performance compared to SAM and its variants.
A new method for forming learning objectives using the sum of ranked range.
problem Forming learning objectives from aggregated values.
method Sum of ranked range (SoRR) minimization with DCA.
result The proposed method effectively forms learning objectives and is applicable to binary and multi-label/multi-class classification.
We consider the problem of learning a loss function which, when minimized over a training dataset, yields a model that approximately minimizes a validation error metric. Though learning an optimal loss function is NP-hard, we present an anytime algorithm that is asymptotically optimal in the worst case, and is provably…
Improves deep learning models by blending gradients from training loss and auxiliary objective.
problem Minimizing a single training loss while encouraging desirable model properties.
method Solves a bilevel optimization problem by combining training loss gradients and orthogonal projections of auxiliary gradients.
result Bloop method leads to better performance than other gradient surgery methods without EMA.
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…
In this work we consider the stochastic minimization of nonsmooth convex loss functions, a central problem in machine learning. We propose a novel algorithm called Accelerated Nonsmooth Stochastic Gradient Descent (ANSGD), which exploits the structure of common nonsmooth loss functions to achieve optimal convergence ra…
We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sa…
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.
Simplifies risk minimization combining mean and standard deviation.
problem Minimizing mean and standard deviation under heavy-tailed losses.
method Adapting robust mean estimation technique to include standard deviation.
result Simple approach performs as well or better than alternative risk criteria.
Paper explores connections between loss functions and consistency in binary classification and regression.
problem Consistency in binary classification and regression applications.
method Characterization of conformable loss functions and derivation of a new Huber-type loss function.
result Margin-based loss functions are equivalent to loss functions of squared standardized logistic regression residuals.
Generative adversarial networks (GANs) can be interpreted as an adversarial game between two players, a discriminator D and a generator G, in which D learns to classify real from fake data and G learns to generate realistic data by "fooling" D into thinking that fake data is actually real data. Currently, a dominating …
Near-optimal algorithms for predicting across multiple loss functions efficiently.
problem Predicting optimally across various loss functions simultaneously.
method Developed near-optimal online and offline learning algorithms for omniprediction.
result Achieved near-optimal complexity for both online and offline settings.
Optimizes exp-concave losses with a new risk bound.
problem Optimizing exp-concave losses with stochastic convex optimization.
method Empirical Risk Minimization with a unified geometric assumption and local norms.
result Provides an O(d/n+log(1/δ)/n) excess risk bound. The past decade has witnessed a successful application of deep learning to solving many challenging problems in machine learning and artificial intelligence. However, the loss functions of deep neural networks (especially nonlinear networks) are still far from being well understood from a theoretical aspect. In this pa…
Study improves adversarial classification using distributionally robust models.
problem Improving robustness against adversarial attacks in classification models.
method Distributionally robust chance constraints with Wasserstein ambiguity, reformulated as a regularized ramp loss minimization problem.
result Standard descent methods can converge to the global minimizer for the distributionally robust adversarial classification model.
This work improves structured prediction by learning the balance between signal and random noise.
problem Structured prediction with random perturbations.
method Learning the variance of randomized structured predictors to balance signal and noise.
result Learning the balance improves structured prediction effectiveness.
We propose a new stochastic optimization framework for empirical risk minimization problems such as those that arise in machine learning. The traditional approaches, such as (mini-batch) stochastic gradient descent (SGD), utilize an unbiased gradient estimator of the empirical average loss. In contrast, we develop a co…