New risk bound derived for multi-category margin classifiers.
problem Guaranteed risk dependency on categories, sample size, and margin parameter.
method Derived a new risk bound using Rademacher complexity and chaining method.
result Improved dependency on categories over state of the art.
The article introduces gamma-Psi-dimensions for margin multi-category classifiers.
problem Margin multi-category classifiers' generalization performance under minimal learnability hypotheses.
method Derives gamma-Psi-dimensions, handles capacity measures, and establishes upper bounds on metric entropies and Rademacher complexity.
result Gamma-Psi-dimensions improve over fat-shattering dimension and offer a promising alternative for multi-class to binary transitions.
New NHCAs improve multi-category classification efficiency.
problem Efficient multi-category classification for real-world problems.
method Twin SVM (TWSVM), Generalized eigenvalue proximal SVM (GEPSVM), Regularized GEPSVM (RegGEPSVM), and Improved GEPSVM (IGEPSVM) with OAA, BT, and TDS approaches.
result TDS-TWSVM outperforms other methods in classification accuracy.
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.
New Frank-Wolfe algorithm speeds up SVM-type multi-category learning.
problem Improving pattern recognition performance in multi-category SVM learning.
method Developed a new optimization algorithm based on Frank-Wolfe framework for MC-SVM variants.
result Closed-form solutions for direction finding and line search in the Frank-Wolfe framework for MC-SVM.
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…
XTNet estimates complex cross-treatment effects in multi-category, multi-valued settings.
problem Challenges in estimating causal effects for multi-category, multi-valued treatments.
method Dynamic Neural Masking for capturing treatment interactions without restrictive assumptions.
result XTNet consistently outperforms state-of-the-art baselines in multi-category, multi-valued treatment effect estimation.
We present a framework to derive risk bounds for vector-valued learning with a broad class of feature maps and loss functions. Multi-task learning and one-vs-all multi-category learning are treated as examples. We discuss in detail vector-valued functions with one hidden layer, and demonstrate that the conditions under…
Bayesian semi-supervised learning for multi-class classification.
problem Classification with missing labels using unlabeled data.
method Bayesian approach with B-splines and conjugate priors.
result Proposed method outperforms other methods in prediction accuracy.
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.
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.
Proposes CORAL framework for consistent ordinal regression in neural networks.
problem Inconsistencies in ordinal regression with neural networks.
method Transforms ordinal targets into binary classification subtasks and applies CORAL framework for rank-monotonicity and consistent confidence scores.
result Reduction of prediction error in age prediction tasks.
AdaBoost's classifier and margins converge to a known value.
problem Convergence properties of AdaBoost algorithm.
method Formal proofs of convergence properties of AdaBoost's classifier and margins.
result AdaBoost's classifier and margins converge to a known value.
New theorem for deep neural networks improves classification margins.
problem Improving classification margins in deep neural networks.
method Local class-purity theorem and margin p-values for training and testing samples.
result Enhanced understanding and computation of classification margins.
The contraction inequality for Rademacher averages is extended to Lipschitz functions with vector-valued domains, and it is also shown that in the bounding expression the Rademacher variables can be replaced by arbitrary iid symmetric and sub-gaussian variables. Example applications are given for multi-category learnin…
New research shows the maximum ℓ1-margin classifier doesn't adapt to sparse ground truths.
problem Understanding the limitations of the maximum ℓ1-margin classifier in high-dimensional settings.
method Analyzing convergence and prediction error rates of the maximum ℓ1-margin classifier.
result Proves tight upper and lower bounds for prediction error, showing benign overfitting.
New AM regularization improves both accuracy and robustness.
problem Lack of robustness in deep neural networks.
method Average margin (AM) regularization for margin classifiers or deep neural networks.
result AM regularization can improve both accuracy and robustness to adversarial attacks.
Theory for soft-margin classifiers on object manifolds.
problem Classifying object manifolds with variability.
method Mean-field theory of soft-margin classifiers applied to object manifolds.
result Prediction of classification errors and their dependence on regularization.
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 kth margin bound, settling the generalization performance of boosted classifiers. Paper proposes a new classifier for hyperbolic spaces using horospherical boundaries.
problem Optimization of large margin classifiers in hyperbolic spaces.
method Horospherical decision boundaries for geodesically convex optimization.
result Geodesically convex optimization leads to globally optimal solutions.
We consider a problem of risk estimation for large-margin multi-class classifiers. We propose a novel risk bound for the multi-class classification problem. The bound involves the marginal distribution of the classifier and the Rademacher complexity of the hypothesis class. We prove that our bound is tight in the numbe…
Neural networks can approximate high-dimensional classifiers with ReLU networks under margin conditions.
problem Approximating high-dimensional discontinuous classifiers with neural networks.
method Using ReLU neural networks with three hidden layers, approximating a classifier with a Barron-regular decision boundary.
result High-dimensional discontinuous classifiers can be approximated with a rate of n−1 under strong margin conditions. We define a generalized likelihood function based on uncertainty measures and show that maximizing such a likelihood function for different measures induces different types of classifiers. In the probabilistic framework, we obtain classifiers that optimize the cross-entropy function. In the possibilistic framework, we …
The paper derives a formula for factorizing categorical data to improve Bayes classifiers.
problem Improving the accuracy of Bayes classifiers by effectively factoring multidimensional data.
method Derives an explicit formula for calculating the marginal likelihood of a factorized categorical dataset.
result The derived formula can be used to select the best factorization for constructing a Bayes classifier.
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.
Near-Exponential Convergence Rates for kNN Classification
problem Convergence rates for kNN classification
method Introducing Boltzmann margin
result First near-exponential convergence rates for kNN classification
In many real-world applications, data is not collected as one batch, but sequentially over time, and often it is not possible or desirable to wait until the data is completely gathered before analyzing it. Thus, we propose a framework to sequentially update a maximum margin classifier by taking advantage of the Maximum…
Study shows how over-parameterized classifiers can still perform well on noisy data.
problem Understanding how maximum margin classifiers perform in over-parameterized settings with noisy data.
method Analyzes maximum margin classifiers on sub-Gaussian mixtures, providing risk bounds.
result Characterizes conditions for 'benign overfitting' in linear classification problems.
Paper analyzes GMM for separable data with various parameter structures.
problem Classifying separable data with logistic models and their generalizations.
method Introduces and analyzes Generalized Margin Maximizer (GMM) for logistic models with specific parameter structures.
result GMM outperforms max-margin classifiers in various parameter settings and structures.
The paper introduces a new bias measure, infra-marginality, to quantify unfairness in group fairness.
problem The trade-off between group fairness and individual-level bias in decision-making.
method Proposes a new notion of η-infra-marginality, proves its independence from accuracy, and provides practical methods to measure and avoid it. result High accuracy does not lead to high infra-marginality, but maximizing group fairness often increases infra-marginality.
Study minimax rates for binary classifier estimation with margin conditions.
problem Estimating binary classifiers with geometric margin conditions.
method Derive lower bounds for worst-case learning rates over various function classes.
result Identify optimal rates close to O(n−1) for different function classes. A fast method for training linear classifiers maximizes margins.
problem Training linear classifiers with maximum margins.
method Momentum-based gradient method derived from convex dual with Nesterov acceleration.
result Exponentially faster convergence rate compared to standard methods.
New insights into how linear classifiers and leaky ReLU networks can overfit without harming generalization.
problem Understanding conditions for benign overfitting in linear classifiers and leaky ReLU networks.
method Utilizing Karush--Kuhn--Tucker (KKT) conditions for margin maximization.
result Satisfaction of KKT conditions leads to benign overfitting in linear classifiers and leaky ReLU networks.
Active learning can't improve over passive in certain settings.
problem Active learning vs. passive learning in nonparametric settings.
method Analyzing margin conditions and their effects on active learning performance.
result Nuances in margin conditions determine whether active learning can outperform passive learning.
This paper resolves Breiman's dilemma in neural networks by analyzing phase transitions of margin dynamics.
problem Breiman's dilemma in neural networks: uniform margin improvement does not guarantee reduced generalization errors.
method Revisiting Breiman's dilemma in deep neural networks with spectrally normalized margins, analyzing phase transitions of normalized margin distributions.
result Margin-based generalization bounds can predict test error trends during training phase transitions.
Paper provides first theoretical guarantees for hyperbolic space learning.
problem Learning a classifier in hyperbolic space for hierarchical data.
method Efficient algorithm for large-margin hyperplane learning in hyperbolic space.
result The low embedding dimension in hyperbolic space leads to superior classifier learning guarantees.
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.
New classifiers converge under large data, simplifying complex models.
problem Complex predictive models under large datasets.
method Convergence of simultaneous and marginal classifiers under partition exchangeability.
result Asymptotic convergence of classifiers with large data reduces computational complexity.
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 study the implicit bias of gradient descent methods in solving a binary classification problem over a linearly separable dataset. The classifier is described by a nonlinear ReLU model and the objective function adopts the exponential loss function. We first characterize the landscape of the loss function and show th…
Paper interprets ResNets via gate-network controls and deep-layer classifications.
problem Understanding the performance mechanism of ResNets.
method Constructs typical solutions using gate-network controls and deep-layer classifications.
result Proves the universal-approximation capability of ResNets.
This work tackles robust multi-source domain adaptation under label shift.
problem Label shift and data contamination in multi-source domain adaptation.
method Domain-weighted empirical risk minimization framework with refinement procedure.
result The proposed method achieves superior performance in multi-category classification problems.
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…
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.
New algorithm optimizes margin distribution in binary classifiers.
problem Optimizing margin distribution in binary classifiers.
method Proposes an algorithm that searches the hypothesis space to ensure a pre-set margin level is a robust estimator of the margin location.
result Empirical tests show the method is effective and promising for classification.
New findings show the large margins theory is insufficient for explaining ensemble methods.
problem Explaining the performance of ensemble methods, especially boosting.
method Illustrated by counterexamples that show how to improve margin distribution without improving test set performance.
result The large margins theory is not sufficient to explain the performance of ensemble methods.
Gradient descent-based adversarial training converges to robust classifiers on linearly separable data.
problem Understanding the inductive bias of adversarial training for robustness.
method Gradient descent on binary classification tasks with linearly separable data, focusing on inductive bias and convergence rates.
result Gradient descent-based adversarial training converges to the maximum margin classifier at a faster rate than clean data training.