Consider a classification problem where we have both labeled and unlabeled data available. We show that for linear classifiers defined by convex margin-based surrogate losses that are decreasing, it is impossible to construct any semi-supervised approach that is able to guarantee an improvement over the supervised clas…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,051 papers · 148 categories
Trend · papers per month
48 results for “margin-based classifiers”
Analyzes large-margin classifiers under high-dimensional data.
problem Selecting the best classifier among various margin-based methods.
method Investigates asymptotic performance of large-margin classifiers under two component mixture models.
result Analytical results closely match with Monte Carlo simulations.
Study generalization of voting classifiers using margin-based bounds.
problem Understanding the generalization of ensemble classifiers like voting.
method Proved margin-based generalization bounds using PAC-Bayes theory and Dirichlet posteriors.
result Provided state-of-the-art guarantees on classification tasks.
New margin bound improves generalization for voting classifiers.
problem Improving generalization bounds for voting classifiers.
method Established a new margin-based generalization bound.
result Derives an optimal weak-to-strong learner with matching theoretical lower bound.
New lower bounds nearly match existing upper bounds for boosted classifiers.
problem Understanding the generalization performance of boosted classifiers.
method Margin-based lower bounds on boosted classifiers.
result Lower bounds nearly match the th margin bound, settling the generalization performance of boosted classifiers.
We present a method to stop the evaluation of a decision making process when the result of the full evaluation is obvious. This trait is highly desirable for online margin-based machine learning algorithms where a classifier traditionally evaluates all the features for every example. We observe that some examples are e…
New margin-based regularization and selective sampling improve deep neural network performance.
problem Improving deep neural network performance on various classification tasks.
method Multi-margin regularization (MMR) and minimal margin score (MMS) for selective sampling.
result Improved results on multiple classification tasks across domains.
Classification is an important statistical learning tool. In real application, besides high prediction accuracy, it is often desirable to estimate class conditional probabilities for new observations. For traditional problems where the number of observations is large, there exist many well developed approaches. Recentl…
Optimized deferral improves accuracy in imbalanced settings.
problem Imbalance in expert predictions leads to suboptimal performance in two-stage learning to defer.
method Developed novel cost-sensitive learning algorithms and margin-based loss functions tailored for expert imbalance.
result MILD algorithm shows clear improvements over baselines in image classification and LLM routing tasks.
New margin-based learning guarantees improve generalization bounds.
problem Improving generalization bounds for machine learning models.
method Relative deviation margin bounds using empirical margin loss and Rademacher complexity.
result Distribution-dependent generalization bounds for unbounded loss functions.
New method prevents class collapse in metric learning with margin-based losses.
problem Class collapse in metric learning due to diverse intra-class samples.
method Proposed a sampling method to select nearest same-class samples as positive elements in tuple.
result Demonstrated clear benefits on various fine-grained image retrieval datasets.
Improves GATs by adding margin-based constraints to prevent over-fitting and over-smoothing.
problem Over-fitting and over-smoothing in GATs.
method Margin-based constraints on attention weights and graph structure.
result Significant improvements over previous GATs on various datasets.
AUC (Area under the ROC curve) is an important performance measure for applications where the data is highly imbalanced. Learning to maximize AUC performance is thus an important research problem. Using a max-margin based surrogate loss function, AUC optimization problem can be approximated as a pairwise rankSVM learni…
As deep learning methods form a critical part in commercially important applications such as autonomous driving and medical diagnostics, it is important to reliably detect out-of-distribution (OOD) inputs while employing these algorithms. In this work, we propose an OOD detection algorithm which comprises of an ensembl…
New bound on neural network generalization error using geometric complexity.
problem Understanding the generalization capabilities of deep neural networks.
method Derive a new upper bound on generalization error using margin-normalized geometric complexity.
result Empirical validation of the bound for ResNet-18 on CIFAR-10 and CIFAR-100 datasets.
Batch normalization biases linear models towards uniform margins, improving performance in binary classification.
problem Understanding the implicit bias of batch normalization in linear models and neural networks.
method Analyzing gradient descent convergence on linear models and two-layer CNNs with batch normalization.
result Gradient descent with batch normalization in linear models converges to a uniform margin classifier with an exponential convergence rate.
We address the problem of aggregating an ensemble of predictors with known loss bounds in a semi-supervised binary classification setting, to minimize prediction loss incurred on the unlabeled data. We find the minimax optimal predictions for a very general class of loss functions including all convex and many non-conv…
Large scale analysis of generalization error in learning using margin based classification methodsstat.ML
Derives asymptotic generalization error for large-margin classifiers.
problem Understanding the generalization error of large-margin classifiers.
method Statistical physics replica method for deriving asymptotic expression.
result Establishes phase transition boundary for class separability.
We present a simple noise-robust margin-based active learning algorithm to find homogeneous (passing the origin) linear separators and analyze its error convergence when labels are corrupted by noise. We show that when the imposed noise satisfies the Tsybakov low noise condition (Mammen, Tsybakov, and others 1999; Tsyb…
The paper improves SVM margin-based generalization bounds.
problem Improving generalization bounds for SVMs.
method Revisiting and improving classic generalization bounds in terms of margins, complementing with a nearly matching lower bound.
result Almost settles the generalization performance of SVMs in terms of margins.
Develops active learning method for linear optimization with margin-based criterion.
problem Optimizing decisions in linear optimization problems with limited labeled data.
method Smart Predict-then-Optimize (SPO) loss and margin-based active learning algorithm.
result Algorithm achieves significantly fewer labels than naive supervised learning, especially for minimizing SPO loss.
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.
Paper studies statistical properties of DP data synthesis algorithms based on Bayesian networks.
problem Ensuring differential privacy in synthetic data generation for high-dimensional data.
method Introduces random noise to low-dimensional marginals of a probabilistic graphical model (BN) to achieve differential privacy.
result Establishes a rigorous accuracy guarantee for BN-based DP synthetic data generators using total variation (TV) distance.
We study agnostic active learning, where the goal is to learn a classifier in a pre-specified hypothesis class interactively with as few label queries as possible, while making no assumptions on the true function generating the labels. The main algorithms for this problem are {\em{disagreement-based active learning}}, …
Optimizes classifiers for varying levels of automation.
problem Supervised learning models often perform worse than human experts on specific instances.
method Focuses on convex margin-based classifiers, showing the problem is NP-hard. For SVMs, the objective function is decomposed into monotone and modular components, allowing efficient algorithms to solve the problem.
result The approach demonstrates that classifiers optimized for varying levels of automation can outperform full automation and human-only models.
New findings show margins are not sufficient for explaining gradient boosting performance.
problem The inadequacy of margin explanations in explaining the performance of gradient boosting.
method Demonstrated and proved a stronger margin-based generalization bound for boosted classifiers.
result Proved a stronger margin-based generalization bound that explains the performance of modern gradient boosters.
Study shows how classifiers can approach Bayes error in high-dimensional settings.
problem Generalization error in high-dimensional perceptrons.
method Proved a formula for generalization error using convex optimization and observed that logistic and hinge regression can approach Bayes error closely.
result Logistic and hinge regression can approach Bayes-optimal generalization error closely in high-dimensional settings.
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…
A new loss function -loss bridges log-loss and - loss for binary classification.
problem Improving binary classification performance using a tunable loss function.
method Introducing -loss, proving its margin-based form and classification-calibration, and providing an upper bound on empirical risk.
result Empirical and expected risk difference upper bound for logistic regression-based classification.
PrAda-GAN improves synthetic data generation under differential privacy.
problem Generating synthetic data under differential privacy with marginal-based methods.
method Sequential generator architecture integrating GAN and marginal-based approaches, with adaptive regularization of Bayes network structure.
result PrAda-GAN outperforms existing methods in privacy-utility trade-off on synthetic and real-world datasets.
New algorithm improves online multiclass classification with partial feedback.
problem Online multiclass classification with partial feedback.
method Inspired by complementary labels, a margin-based deterministic approach.
result Our method outperforms existing non-margin-based and stochastic methods.
New research shows SVM and related methods can overfit without harm in multiclass classification.
problem Understanding benign overfitting in multiclass classification.
method Analyzing three training algorithms: ERM with cross-entropy, least-squares, and one-vs-all SVM.
result All three algorithms can lead to classifiers that interpolate training data and have equal accuracy under high overparameterization.
Proposes adaptive method for classifying interval-valued time series.
problem Lack of classification methods for interval-valued time series.
method Represent intervals as images, classify using CNN, optimize coefficients with ADMM.
result Validated through simulations and real data, outperforming point-valued methods.
Unified binary and multiclass margin-based classification methods.
problem No consensus on multiclass loss functions analogous to binary margin loss.
method Showed multiclass loss functions can be expressed in relative margin form.
result Extended classification-calibration result to multiclass.
Given a matrix , a linear feasibility problem (of which linear classification is a special case) aims to find a solution to a primal problem or a certificate for the dual problem which is a probability distribution . Inspired by the continued importance of "large-margin cla…
A new method accelerates deep neural network training using minimal margin score.
problem Training deep neural networks is computationally expensive.
method Introduces minimal margin score (MMS) for selecting samples.
result Significant acceleration in training deep neural networks.
The adoption of automated, data-driven decision making in an ever expanding range of applications has raised concerns about its potential unfairness towards certain social groups. In this context, a number of recent studies have focused on defining, detecting, and removing unfairness from data-driven decision systems. …
SelectNet selectively adds unlabelled data to balance imbalanced training data.
problem Training from imbalanced data in machine learning.
method SelectNet trains a deep neural network to add unlabelled data with predicted labels to the training dataset.
result SelectNet effectively balances imbalanced training data, improving classifier performance.
Margin enlargement over training data has been an important strategy since perceptrons in machine learning for the purpose of boosting the robustness of classifiers toward a good generalization ability. Yet Breiman (1999) showed a dilemma that a uniform improvement on margin distribution does NOT necessarily reduces ge…
In this paper, we propose a data-adaptive non-parametric kernel learning framework in margin based kernel methods. In model formulation, given an initial kernel matrix, a data-adaptive matrix with two constraints is imposed in an entry-wise scheme. Learning this data-adaptive matrix in a formulation-free strategy enlar…
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 -consistency bounds.
A preference order or ranking aggregated from pairwise comparison data is commonly understood as a strict total order. However, in real-world scenarios, some items are intrinsically ambiguous in comparisons, which may very well be an inherent uncertainty of the data. In this case, the conventional total order ranking c…
New bounds show neural networks can resist attacks better with sparse weights.
problem Neural networks are vulnerable to small adversarial perturbations.
method Compression based on effective sparsity and joint sparsity.
result Neural networks with approximately sparse weight matrices have better robustness and generalization.
Nodes in real world networks often have class labels, or underlying attributes, that are related to the way in which they connect to other nodes. Sometimes this relationship is simple, for instance nodes of the same class are may be more likely to be connected. In other cases, however, this is not true, and the way tha…
STC systems improved deep learning for ASVspoof2019 challenge.
problem Detecting spoofing attacks in speech recognition.
method Deep learning, Light CNN architecture, angular margin based softmax activation.
result Achieved EER of 1.86% in logical access and 0.54% in physical access scenarios.
We use surrogate losses to obtain several new regret bounds and new algorithms for contextual bandit learning. Using the ramp loss, we derive new margin-based regret bounds in terms of standard sequential complexity measures of a benchmark class of real-valued regression functions. Using the hinge loss, we derive an ef…
Residuals improve deep neural networks without increasing hypothesis complexity.
problem Understanding how residual connections affect hypothesis complexity and generalization.
method Analyzing the covering number of the hypothesis space and deriving a margin-based generalization bound.
result Residual connections do not increase the hypothesis complexity of neural networks.
This work studies adversarial training in high dimensions, revealing key feature trade-offs.
problem Understanding adversarial robustness in high-dimensional settings.
method Introduces a tractable model to study the geometry of data and adversarial attacks.
result Characterizes directions in data associated with robustness vs. usefulness trade-offs.