Gradient descent converges to max-margin solution for hinge loss.
problem Applying gradient descent to the hinge loss for linear classifiers.
method Homotopic gradient descent applied to the hinge loss.
result Explicit convergence rates to max-margin solution for separable data.
Improves GANs by incorporating class information with a multi-hinge loss.
problem Improving GANs to better respect class information.
method Proposes a multi-class generalization of the Hinge loss for GANs.
result Improves Inception Scores and Frechet Inception Distance on Imagenet.
New loss function calibrates WW-hinge loss for multiclass SVM.
problem WW-hinge loss not calibrated with 0-1 loss.
method Introduced ordered partition loss and proved WW-hinge loss is calibrated.
result WW-hinge loss is calibrated with ordered partition loss.
New loss function improves convergence rate for neural networks.
problem Improving convergence speed of neural networks for classification tasks.
method Proposes a modified hinge loss function with gradients to critical points.
result Margin converges to max-margin at O ( 1 / t ) \mathcal{O}(1/t) O ( 1/ t ) rate, faster than exponential losses. MAGAN improves GANs stability and performance with adaptive hinge loss.
problem Improving stability and performance of GANs.
method Adaptive hinge loss function with estimated margin based on target distribution energy.
result MAGAN converges to global optimum under certain assumptions.
New approach uses hinge loss for iterative regularization in classification.
problem Improving classification accuracy through regularization.
method Develops an iterative regularization approach based on hinge loss.
result Proves convergence and rates of convergence for classification.
New robust metric learning method improves performance in noisy data.
problem Label noise and outliers in training data degrade metric learning performance.
method Rescaled Hinge loss function and HQ algorithm.
result New method outperforms state-of-the-art methods in noisy data.
A new procedure for learning cost-sensitive SVM(CS-SVM) classifiers is proposed. The SVM hinge loss is extended to the cost sensitive setting, and the CS-SVM is derived as the minimizer of the associated risk. The extension of the hinge loss draws on recent connections between risk minimization and probability elicitat…
The paper analyzes top-k classification and proposes consistent loss functions.
problem Understanding consistency of top-k classification in challenging tasks.
method Theoretical analysis, defining top-k calibration, proposing new loss functions.
result Proposes a new consistent hinge loss and a top-k calibrated convex loss.
Logitron combines Perceptron and logistic loss for improved classification.
problem Non-convex and non-smooth zero-one loss function in classification models.
method Introduces a Perceptron-augmented convex classification framework with an extended logistic loss function.
result Hinge-Logitron outperforms logistic regression and SVM in classification accuracy.
Deep neural networks converge quickly for classification tasks.
problem Classifying data with smooth decision boundaries, probabilities, or margins.
method Hinge loss and cross-entropy for training; analysis of convergence rates.
result DNNs achieve fast convergence rates under various conditions.
Study efficient learning of halfspaces with constant noise tolerance.
problem Learning halfspaces in the presence of both instance and label corruption.
method Develops an algorithm to minimize reweighted hinge loss for robustness.
result Achieves constant noise tolerance for halfspace learning.
Introduces Soft-SVM for binary classification bridging logistic and SVM.
problem Data separability issues in binary classification.
method Soft-SVM regression using convex relaxation of hinge loss with softness and class-separation parameters.
result Soft-SVM performs well in classification and prediction errors.
Neural networks for binary classification have zero training error at all local minima under certain conditions.
problem Understanding the loss surface of neural networks for binary classification.
method Analyzing single-layered neural networks with smooth hinge loss function, providing conditions for zero training error at all local minima.
result Zero training error at all local minima is achieved under specific conditions (strict convexity of neurons and smooth hinge loss).
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.
New algorithms and bounds for contextual bandits using surrogate losses.
problem Efficiently solving contextual bandit problems with margin-based regret bounds.
method Use of surrogate losses (ramp and hinge) to derive new regret bounds and algorithms.
result Derives new margin-based regret bounds and efficient algorithms for contextual bandits.
New method learns distances and similarities robustly from noisy data.
problem Scalability and robustness in metric learning for large datasets.
method Robust online Distance-Similarity learning with Rescaled hinge loss.
result Significantly outperforms state-of-the-art methods in noisy data.
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 …
The paper analyzes the dynamics of a simple neural network using a mean-field approach.
problem Understanding the training dynamics of neural networks, especially in classification tasks.
method Developed an analytic theory using a mean-field limit for a simple neural network.
result Explicitly solved the dynamics of a linearly separable dataset with a linear hinge loss.
Paper introduces a new loss function for deep imbalanced classification.
problem Class ambiguity and imbalance in large datasets.
method Stochastic top-K hinge loss based on smoothed top-K operator.
result Our loss function significantly outperforms other baseline loss functions in imbalanced datasets.
Study on benign overfitting in leaky ReLUs with moderate input dimensions.
problem Understanding when overfitting is beneficial in neural networks.
method Two-layer leaky ReLU networks trained with hinge loss, considering signal-to-noise ratio.
result Characterization of conditions for benign overfitting based on signal-to-noise ratio.
The paper explores symmetric losses for better learning from corrupted labels.
problem Learning from corrupted labels with balanced error rate or AUC maximization.
method Proves theoretical properties of symmetric losses and proposes a convex barrier hinge loss.
result Symmetric losses are advantageous in BER minimization and AUC maximization from corrupted labels.
Efficient algorithm reduces online multiclass prediction regret to sqrt(T).
problem Online multiclass prediction with bandit feedback.
method Second-order algorithm with regret bound of O(1/η√T).
result Regret bound holds for a range of loss functions.
Graphical models for structured domains are powerful tools, but the computational complexities of combinatorial prediction spaces can force restrictions on models, or require approximate inference in order to be tractable. Instead of working in a combinatorial space, we use hinge-loss Markov random fields (HL-MRFs), an…
Efficient algorithms for large-scale multiclass classification with linear classifiers.
problem Training ℓ 1 \ell_1 ℓ 1 -regularized linear classifiers with high dimensionality and many classes. method Combines quasi-bilinear objective, stochastic mirror descent, and non-uniform sampling.
result Proposes a sublinear algorithm for multiclass hinge loss.
New loss functions improve extreme classification with missing labels.
problem Large number of infrequent labels and missing labels in XMC.
method Derive unbiased loss functions for XMC, incorporating them into existing algorithms.
result Significant improvement in extreme classification performance (up to 20%) over existing methods.
New test for SGD in binary classification reduces computation time.
problem Determining optimal stopping for SGD in binary classification.
method Proposes a new, simple, computationally inexpensive termination criterion for SGD.
result Termination criterion reduces expected misclassification probability.
Support vector machines (SVMs) naturally embody sparseness due to their use of hinge loss functions. However, SVMs can not directly estimate conditional class probabilities. In this paper we propose and study a family of coherence functions, which are convex and differentiable, as surrogates of the hinge function. The …
The paper proposes a method to infer user profiles from multiple sources of social media data.
problem Mining user profiles from social media data using a single type of information.
method Hinge-loss Markov Random Fields (HL-MRFs) integrated with multiple sources of UGC and social relations.
result HL-MRFs successfully incorporate multiple sources of information and outperform competing methods.
End-to-end training improves segmental models for speech recognition.
problem Training segmental models is challenging and lacks understanding under different settings and losses.
method Investigated a model class based on recent successful approaches, trained end-to-end with various losses.
result Marginal log loss provides the most consistent strong performance without requiring ground-truth alignments.
Paper studies convergence rates from surrogate risk minimizers to Bayes optimal classifier.
problem Analyzing the convergence rates of surrogate risk minimizers to the Bayes optimal classifier.
method Introducing consistency intensity to characterize surrogate loss functions and using it to derive convergence rates.
result Empirical surrogate risk minimizers converge faster to the Bayes optimal classifier under certain conditions.
Paper proposes a boosting method with fast learning rates and early stopping.
problem Missing theoretical guarantees for boosting methods in binary classification.
method Fully-corrective gradient boosting with squared hinge loss and ADMM algorithm.
result Derives fast learning rates of O ( ( m / log m ) − 1 / 4 ) {\cal O}((m/\log m)^{-1/4}) O (( m / log m ) − 1/4 ) and O ( ( m / log m ) − 1 / 2 ) {\cal O}((m/\log m)^{-1/2}) O (( m / log m ) − 1/2 ) . Classification and regression tasks in overparameterized models show different generalization properties.
problem Comparing classification and regression in overparameterized models.
method Comparison of least-squares minimum-norm interpolation and hard-margin SVM using different loss functions.
result Interpolating solutions generalize well with 0-1 loss but not with square loss.
New approach estimates personalized treatment effects using surrogate losses.
problem Estimating personalized treatment effects with binary outcomes and limited data.
method Proposes surrogate loss functions that incorporate both treatment and control data.
result Minimax support vector machine formulation yields tighter bounds.
The Support Vector Machine (SVM) has been used in a wide variety of classification problems. The original SVM uses the hinge loss function, which is non-differentiable and makes the problem difficult to solve in particular for regularized SVMs, such as with ℓ 1 \ell_1 ℓ 1 -regularization. This paper considers the Huberized SV…
Gaptron algorithm reduces mistakes in online multiclass classification.
problem Online multiclass classification with limited information.
method Randomized first-order algorithm exploiting the gap between zero-one loss and surrogate losses.
result First linear time algorithm with O ( K T ) O(K\sqrt{T}) O ( K T ) expected regret. New models improve classification model performance, especially robust to small training sets.
problem Improving classification model performance, especially robust to small training sets.
method Distributionally robust AUC maximization models using Kantorovich metric and hinge loss function.
result The proposed DR-AUC models outperform standard models in general and worst-case out-of-sample performance.
Quantum SVM uses fewer features for faster training.
problem Training high-dimensional SVMs efficiently.
method Quantum linear programming for sparse SVM training.
result Quantum sparse SVM can be trained in sublinear time.
Gradient penalty improves GAN performance by inducing a large-margin classifier.
problem Improving GAN performance and addressing vanishing gradients.
method A unifying framework of expected margin maximization, showing gradient penalties induce large-margin classifiers.
result Gradient penalties reduce vanishing gradients and produce better generated outputs.
Study on using random subspaces for ERM with various loss functions.
problem Improving learning accuracy with computational savings from random subspaces.
method Random subspaces of a hypothesis space, considering data-dependent subspaces.
result Unified analysis showing computational efficiency can be improved without performance loss.
Deep neural networks outperform traditional methods in high-dimensional classification.
problem Understanding the empirical success of deep neural networks in high-dimensional classification.
method Proposed a teacher-student framework with Bayes classifier as ReLU neural networks, derived convergence rates for 0-1 and hinge losses.
result Sharp rate of convergence for classifiers trained using 0-1 or hinge loss, with O d ( n − 2 / 3 ) O_d(n^{-2/3}) O d ( n − 2/3 ) or O d ( n − 1 ) O_d(n^{-1}) O d ( n − 1 ) under separable data distribution. Efficient algorithm for evaluating hierarchical classification methods at multiple operating points.
problem Evaluating hierarchical classification methods at multiple operating points.
method Efficient algorithm to produce operating characteristic curves for any method that assigns scores to every class in the hierarchy.
result Top-down classifiers are dominated by a naive flat softmax classifier across the entire operating range.
Multithreshold Entropy Linear Classifier (MELC) is a recent classifier idea which employs information theoretic concept in order to create a multithreshold maximum margin model. In this paper we analyze its consistency over multithreshold linear models and show that its objective function upper bounds the amount of mis…
The study provides a sample complexity estimate for multi-category classifiers with bounded variation.
problem Controlling the deviation between empirical and generalization performances of multi-category classifiers.
method Using the empirical L1-norm covering number and fat-shattering dimension, the study derives a sample size estimate for classifiers of bounded variation.
result The sample size estimate is sufficient for the performances to be close with high probability, improving the dependency on the number of classes.
Max-margin method for nonparametric latent feature models improves link prediction.
problem Link prediction in statistical networks.
method Max-margin learning combined with Bayesian nonparametrics.
result Improved link prediction accuracy on large-scale networks.
Deep neural networks achieve optimal classification rates in high dimensions.
problem Binary classification on high-dimensional data with specific smoothness and composition properties.
method Proved optimal convergence rate for ReLU DNNs trained with hinge loss.
result ReLU DNNs achieve optimal classification rates up to a logarithmic factor.
New method optimizes lossy compression models more effectively.
problem Difficulty in manually setting a tradeoff parameter for lossy compression models.
method Constrained optimization method of Rezende and Viola, 2018.
result The method enables pointwise model comparisons and outperforms existing methods.
Paper tackles clipped matrix recovery from scientific areas with theoretical and practical methods.
problem Recovering low-rank matrices from clipped observations in scientific areas.
method Trace-norm minimization algorithm and squared hinge loss with a novel regularization term.
result Theoretical guarantee and practical algorithms for exact recovery of clipped matrix completion.