Develops NPMC method for noisy labels, improving multiclass classification accuracy.
problem Asymmetric misclassification costs and label noise in multiclass classification.
method Empirical likelihood approach using exponential tilting density ratio model.
result Root n consistent and asymptotically normal estimators for clean labels and noise mechanism.
Adapts Neyman-Pearson classification for both source and target distribution shifts.
problem Minimizing errors while controlling both Type-I and Type-II errors under distribution shifts.
method Derives an adaptive procedure that guarantees improved error rates and adapts to uninformative sources.
result Automatic adaptation to uninformative sources avoids negative transfer.
Characterizes distribution-free rates in unbalanced classification problems.
problem Minimizing error under two different distributions in unbalanced settings.
method Characterizes minimax rates over all pairs of distributions using a geometric condition.
result Identifies a dichotomy between hard and easy classes based on a three-points-separation condition.
Combines cost-sensitive and Neyman-Pearson paradigms for better binary classification.
problem Asymmetric binary classification problems with unequal error severities.
method Develops TUBE-CS algorithm to bridge cost-sensitive and Neyman-Pearson paradigms.
result High-probability control of population type I error.
The paper tackles Neyman-Pearson classification control issues.
problem Neyman-Pearson classification's control constraint is hard to satisfy in finite samples.
method Developed refined learning procedures under two accuracy control strategies.
result Proposed methods achieve desired control levels in finite samples.
Develops algorithms for multi-class Neyman-Pearson classification with cost sensitivity.
problem Asymmetric misclassification costs in multi-class classification problems.
method Establishes connection with cost-sensitive learning, proposes two algorithms, extends NP oracle properties.
result Proposes algorithms with theoretical guarantees for multi-class Neyman-Pearson classification.
New method corrects bias in density ratio estimation for missing data.
problem Missing data bias in density ratio estimation.
method Adapted KLIEP method (M-KLIEP) for MNAR data.
result M-KLIEP restores consistency and minimax optimality.
Most existing binary classification methods target on the optimization of the overall classification risk and may fail to serve some real-world applications such as cancer diagnosis, where users are more concerned with the risk of misclassifying one specific class than the other. Neyman-Pearson (NP) paradigm was introd…
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.
Optimal selective classification using likelihood ratios improves model reliability.
problem Enhancing predictive model reliability by allowing uncertain predictions.
method Neyman--Pearson lemma applied to likelihood ratios for optimal selection.
result Neyman--Pearson-informed methods outperform existing baselines under covariate shifts.
The paper analyzes how overparameterized models can generalize well in multiclass classification.
problem Generalization in multiclass classification with overparameterized models.
method Survival/contamination analysis framework adapted for multiclass classification.
result Multiclass classification can generalize well even with many classes, unlike regression tasks.
New research determines the optimal sample complexity for multiclass and list learning.
problem Determining the optimal sample complexity for multiclass classification.
method Algebraic characterization of multiclass hypothesis classes in terms of their DS dimension.
result Proves a longstanding conjecture and determines the optimal dependence of sample complexity on DS dimension.
Study shows exponential error reduction in multiclass classification without bias-variance trade-off.
problem Multiclass classification with margin conditions.
method Analysis of classification error under hard-margin conditions.
result Exponential decrease in classification error without bias-variance trade-off.
A neural network for online NP classification with reduced complexity.
problem Online nonlinear Neyman-Pearson classification.
method Single hidden layer feedforward neural network (SLFN) initialized with random Fourier features (RFFs). Uses stochastic gradient descent for sequential learning.
result Expedited online adaptation and powerful nonlinear Neyman-Pearson modeling.
Establishes a condition for multiclass classification-calibration of Gamma-Phi losses.
problem Ensuring classification-calibration of multiclass Gamma-Phi losses.
method Develops a general sufficient condition for classification-calibration of Gamma-Phi losses.
result Proves the first family of nonconvex multiclass surrogate losses for which classification-calibration has been fully justified.
Motivated by problems of anomaly detection, this paper implements the Neyman-Pearson paradigm to deal with asymmetric errors in binary classification with a convex loss. Given a finite collection of classifiers, we combine them and obtain a new classifier that satisfies simultaneously the two following properties with …
New reformulations for multiclass classification problems using optimal transport.
problem Adversarial multiclass classification problems.
method Multimarginal optimal transport formulation.
result Reveals geometric structure and extends binary classification results.
Paper studies multiclass classifiers from binary classifiers, proving methods and demonstrating advantages.
problem Constructing efficient multiclass classifiers from binary ones.
method Two methods: one vs. all and hierarchical classification, with a new leverage-hierarchical method introduced.
result Proves upper bounds and exact formulas for multiclass regret in terms of binary regrets.
New bounds for Neyman-Pearson region using f f f -divergences.
problem Bounding the Neyman-Pearson region for hypothesis testing.
method Establishing novel lower and upper bounds using f f f -divergences. result Best possible lower bound for the Neyman-Pearson boundary using hockey-stick f f f -divergences. This work extends implicit bias analysis to multiclass classification using a new loss framework.
problem The implicit bias of gradient descent on multiclass data without explicit regularization.
method Employing the PERM framework to introduce a multiclass extension of the exponential tail property.
result Extended implicit bias result to multiclass classification using a new loss framework.
New method for multiclass classification reduces error bounds.
problem High-dimensional multiclass classification with sparse coefficients.
method Sparse multinomial logistic regression with convex penalties.
result Plug-in classifiers achieve minimax generalization error bounds.
New algorithm controls type I error in NP classification under label noise.
problem Label noise affects NP classification methods, reducing power.
method Proposes a label-noise-adjusted Neyman-Pearson algorithm.
result Improves power while controlling type I error under desired level.
Algorithm minimizes risk for multiclass classification of stochastic diffusion paths.
problem Multiclass classification of stochastic diffusion paths with distinct drift functions.
method Empirical risk minimization using L2 risk.
result Achieves fast rates of convergence under margin assumption.
Pre-trained word embeddings encode general word semantics and lexical regularities of natural language, and have proven useful across many NLP tasks, including word sense disambiguation, machine translation, and sentiment analysis, to name a few. In supervised tasks such as multiclass text classification (the focus of …
Study online multiclass classification under bandit feedback, extending previous results.
problem Online multiclass classification with bandit feedback, focusing on label space unboundedness.
method Extend Daniely and Helbertal's results, show necessity and sufficiency of Bandit Littlestone dimension for learnability.
result Sequential uniform convergence is necessary but not sufficient for bandit online learnability.
In the problem of domain adaptation for binary classification, the learner is presented with labeled examples from a source domain, and must correctly classify unlabeled examples from a target domain, which may differ from the source. Previous work on this problem has assumed that the performance measure of interest is…
Extends boosting to multiclass online agnostic classification.
problem Online multiclass classification with weak learners.
method Reduces multiclass online agnostic boosting to online convex optimization.
result First boosting algorithm for online agnostic multiclass classification.
Study proves existence of robust classifiers in multiclass adversarial training.
problem Proves existence of robust classifiers in multiclass adversarial training.
method Three models of adversarial training in multiclass classification, proving existence of Borel measurable robust classifiers.
result Proves existence of Borel measurable robust classifiers in each model.
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…
Paper analyzes multiclass classification with high-dimensional data.
problem Understanding statistical properties and behavior of multiclass classification algorithms.
method Asymptotic analysis of linear multiclass classification.
result Test error varies significantly across different training algorithms and data distributions.
New algorithm improves multiclass classification regret bound.
problem Improving multiclass classification with bandit feedback.
method Developed a new bandit classification algorithm.
result Guaranteed regret of O ~ ( ∣ H ∣ + T ) \smash{\widetilde{O}(|H|+\sqrt{T})} O ( ∣ H ∣ + T ) , improving over classical algorithms. Paper introduces exact credible sets for classification problems.
problem No general way to construct exact credible sets for classification.
method Generalized credible set with connection to Neyman--Pearson lemma and randomized decision rule.
result Achieves any preassigned credible level for classification problems.
Optimal classification requires choosing the right group symmetries, contrary to intuition.
problem Improving binary classification performance by selecting appropriate group symmetries.
method Developed a theoretical framework for designing group equivariant neural networks.
result Optimal classification performance is achieved by selecting the appropriate subgroups of symmetries, not the largest equivariant groups.
New binary classification techniques help multiclass classification by aggregating proper learners.
problem Multiclass classification faces a properness barrier that prevents optimal learning by proper learners.
method Aggregations of proper binary learners, generalized to multiclass settings, achieve optimal sample complexity.
result Optimal binary learners can achieve sample complexity $O\left(\frac{d_G + \ln(1 / δ)}ε
ight)$ for classes with finite Graph dimension d G d_G d G . Develops a functional mix-of-experts model for multiclass classification.
problem Multiclass classification with univariate functional predictors.
method Functional mix-of-experts model with regularization and sparsity constraints.
result Regularized maximum likelihood estimation yields interpretable coefficient functions.
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.
Binary and multiclass epilepsy detection methods using EEG features.
problem Epilepsy diagnosis from EEG data.
method Feature extraction from power spectrum, spectrogram, and bispectrogram; eight machine learning algorithms used.
result Random forest and backpropagation algorithms achieved highest accuracy for binary and multiclass classification.
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. Improved multiclass classification with class-weighted nearest neighbors.
problem Multiclass classification with large or imbalanced classes.
method Class-weighted k-nearest neighbors algorithm, derived bounds on accuracy and risk.
result Optimized classification metrics like F1 score or Matthew's Correlation Coefficient.
Unified SVM framework tackles multiclass and multilabel classification.
problem Extending SVM to handle multiclass and multilabel problems.
method Unified framework with class-specific weight vectors and penalizing patterns close to an origin.
result Unified framework achieves competitive performance for multiclass and multilabel classification.
Study expands multiclass classification models with new rates and partial concept classes.
problem Multiclass classification with a bounded number of labels under various conditions.
method Extends traditional PAC model to distribution-dependent and data-dependent learning rates, characterizes optimal rates for universal and partial concept classes.
result Characterizes three types of learning rates (exponential, linear, arbitrarily slow) for fixed distributions and complexity measures for partial concept classes.
Study optimal rates for multiclass classification, resolving open questions.
problem Optimal rates for multiclass classification with any label space.
method Establishes optimal rates for all hypothesis classes, defining new tree structures.
result Optimal rates for multiclass classification with no infinite DSL trees.
Paper tackles noisy bandit feedback for multiclass classification.
problem Learning multiclass classifier with corrupted feedback.
method Proposes an unbiased estimator technique to estimate noise rates and an end-to-end framework.
result Algorithm achieves mistake bounds of O ( T ) O(\sqrt{T}) O ( T ) in high noise and O ( T i c e f r a c 23 ) O(T^{
icefrac{2}{3}}) O ( T i ce f r a c 2 3 ) in worst case. Study builds a classifier for diffusions with unknown diffusion but known drifts.
problem Multiclass classification of S.D.E. paths with unknown diffusion coefficient.
method Plug-in classifier using nonparametric estimators of drift and diffusion functions.
result Consistent classification procedure with rate of convergence under different assumptions.
This work analyzes label embedding for large multiclass classification problems.
problem Label embedding for large multiclass classification problems.
method Analysis of label embedding in extreme multiclass classification, presenting an excess risk bound and showing a trade-off between computational and statistical efficiency.
result The statistical penalty for label embedding vanishes with sufficiently low coherence under the Massart noise condition.
One-bit quantization and sparsification improve multiclass classification with strong regularization.
problem Overfitting mislabeled data in multiclass classification.
method Linear regression with regularization and one-bit quantization/sparsification.
result Sparse and one-bit solutions perform almost as well as the optimal solution with f ( ⋅ ) = ∥ ⋅ ∥ 2 2 f(\cdot) = \|\cdot\|_2^2 f ( ⋅ ) = ∥ ⋅ ∥ 2 2 . Sparse multinomial logistic regression for multiclass classification with feature selection.
problem High-dimensional multiclass classification with a focus on sparse models.
method Penalized maximum likelihood with complexity penalty, feature selection using group Lasso and Slope classifiers.
result Achievement of minimax order in both small and large number of classes regimes.
New bounds show agnostic multiclass learning depends on two dimensions: Natarajan and Daniely-Shalev-Shwartz.
problem Understanding sample complexity in multiclass classification with agnostic learning.
method Developed a novel online procedure based on a self-adaptive multiplicative-weights algorithm.
result Agnostic sample complexity bounds are in the form of DS^(1.5)/ε + Nat/ε^2, nearly tight up to a √DS factor.