We extend a recently proposed 1-nearest-neighbor based multiclass learning algorithm and prove that our modification is universally strongly Bayes-consistent in all metric spaces admitting any such learner, making it an "optimistically universal" Bayes-consistent learner. This is the first learning algorithm known to e…
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.
168,657 papers · 148 categories
Trend · papers per month
34 results for “Bayes-consistent”
Research on nearest-neighbor methods tends to focus somewhat dichotomously either on the statistical or the computational aspects -- either on, say, Bayes consistency and rates of convergence or on techniques for speeding up the proximity search. This paper aims at bridging these realms: to reap the advantages of fast …
We show that a simple modification of the 1-nearest neighbor classifier yields a strongly Bayes consistent learner. Prior to this work, the only strongly Bayes consistent proximity-based method was the k-nearest neighbor classifier, for k growing appropriately with sample size. We will argue that a margin-regularized 1…
Differentially-private Bayes consistency rule for binary classification and density estimation.
problem Privacy constraints limit private learning in the distribution-free PAC model.
method Constructs a universally Bayes consistent learning rule that satisfies differential privacy.
result Private learning is possible for arbitrary distributions, even with a single algorithm.
New algorithm learns mappings between metric spaces, achieving strong consistency.
problem Learning mappings between metric spaces with unbounded loss.
method Metric medoids and semi-stable compression.
result Strong Bayes-consistency for topologically separable spaces and bounded labels.
Study of loss functions for learning to defer, proving consistency.
problem Learning to defer in machine learning.
method Introduced a family of surrogate losses parameterized by and proved their consistency.
result Proved realizable -consistency and Bayes-consistency of specific surrogate losses.
Separable losses are inconsistent for structured prediction models.
problem Inconsistency of separable losses in structured prediction models.
method Analysis of separable negative log-likelihood losses for structured prediction.
result Separable losses are not Bayes consistent and may not predict the most probable structure.
Bayes-consistent disagreement discrepancy loss improves model robustness.
problem Distribution shift in real-world neural network deployment.
method Introducing a novel disagreement loss that is Bayes consistent.
result Proves existing surrogates for disagreement discrepancy are not Bayes consistent.
Unified surrogate loss framework for multi-label learning with strong consistency guarantees.
problem Improving consistency and accounting for label correlations in multi-label learning.
method Introducing multi-label logistic loss and extending it to comprehensive multi-label comp-sum losses, proving strong consistency guarantees for any multi-label loss.
result Unified surrogate loss framework benefiting from strong consistency guarantees for any multi-label loss.
SARD improves adversarial robustness in two-stage L2D systems.
problem Adversarial attacks can manipulate query allocation in two-stage L2D systems.
method Introduces SARD, a convex learning algorithm with provable guarantees.
result SARD significantly improves robustness under adversarial attacks while maintaining strong clean performance.
New method learns multi-class from single-class data with confidences.
problem Learning multi-class from single-class data without additional data.
method Empirical risk minimization framework for multi-class classification.
result Method achieves Bayes-consistency with noisy confidences.
A new framework integrates classification and regression tasks in multi-task learning.
problem Jointly solving classification and regression tasks in multi-task scenarios.
method Two-Stage Learning-to-Defer (L2D) framework with a unified deferral mechanism.
result Unified deferral mechanism ensures convergence to the Bayes-optimal rejector.
Study on top- classification with new loss functions and algorithms.
problem Improving multi-class classification accuracy and cardinality trade-off.
method Introducing cardinality-aware loss functions and deriving their consistency bounds.
result New cardinality-aware algorithms for top- classification.
DCC separates marginal estimation from dependence modeling for improved classification accuracy.
problem Classifying with strong dependence between features.
method Deep Copula Classifier using neural copula densities.
result Achieves excess-risk for -smooth copulas.
Solves open problem on universally consistent online learning with unbounded losses.
problem Open problem on universally consistent online learning with unbounded losses.
method Constructs random measurable partitions of the instance space.
result Simple memorization rule is optimistically universal for any unbounded loss.
Unified model for prediction and deferral selects top-k entities efficiently.
problem Efficiently selecting top-k entities for deferral in machine learning.
method One-stage Top- Learning-to-Defer framework with a convex surrogate.
result Unified model achieves superior accuracy-cost trade-offs.
This paper tackles deferral learning with multiple experts, providing strong theoretical guarantees.
problem Optimizing input assignment to experts balancing accuracy and computational cost.
method Introducing new surrogate loss functions and efficient algorithms with strong theoretical learning guarantees.
result Realizable -consistency, -consistency bounds, and Bayes-consistency for deferral learning.
Unified framework for deferring queries to top-k experts, improving accuracy-cost trade-offs.
problem Limitation of existing L2D frameworks to single-expert deferral.
method Top- Learning-to-Defer framework, including adaptive Top- variant.
result Superior accuracy-cost trade-offs with multi-expert deferral.
We provide a formulation for Local Support Vector Machines (LSVMs) that generalizes previous formulations, and brings out the explicit connections to local polynomial learning used in nonparametric estimation literature. We investigate the simplest type of LSVMs called Local Linear Support Vector Machines (LLSVMs). For…
This work studies learning curves for revenue maximization algorithms.
problem Understanding the performance of revenue-maximizing algorithms as they learn from more data.
method Initiates the study of learning curves for revenue maximization, providing a near-complete characterization of their rate of decay.
result Learning curves for revenue maximization can decay arbitrarily slowly or almost exponentially fast, depending on the distribution and optimal revenue.
Ensemble techniques are powerful approaches that combine several weak learners to build a stronger one. As a meta-learning framework, ensemble techniques can easily be applied to many machine learning methods. Inspired by ensemble techniques, in this paper we propose an ensemble loss functions applied to a simple regre…
New framework improves adversarial robustness in one-stage L2D.
problem Adversarial robustness in one-stage Learning-to-Defer (L2D).
method Formalizes attacks, proposes cost-sensitive adversarial surrogate losses, establishes theoretical guarantees.
result Improves robustness against untargeted and targeted attacks while preserving clean performance.
Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Datacs.LG
New framework for learning from imbalanced data with theoretical guarantees.
problem Class imbalance in machine learning, especially in multi-class problems.
method Theoretical framework and new margin loss function for imbalanced classification.
result Proves strong -consistency of the proposed margin loss function.
We propose a procedure for supervised classification that is based on potential functions. The potential of a class is defined as a kernel density estimate multiplied by the class's prior probability. The method transforms the data to a potential-potential (pot-pot) plot, where each data point is mapped to a vector of …
Bayesian principles improve agentic AI decision-making.
problem Decision-making under uncertainty in agentic AI systems.
method Bayesian decision theory applied to the orchestration layer of agentic AI.
result Bayesian principles enhance agentic AI's ability to make decisions under uncertainty.
Develops algorithms for optimizing multi-label metrics with provable guarantees.
problem Optimizing complex multi-label metrics like F-measure and Jaccard index.
method Principled learning algorithms based on H-consistency for generalized metrics.
result Provable -consistency bounds for multi-label metric optimization.
Paper proves fair classification can be done via simple thresholding.
problem Achieving fair binary classification subject to group fairness constraints.
method Proves Bayes optimal fair learning rule is a group-wise thresholding rule over the Bayes regressor with randomization.
result Proposes an efficient unconstrained optimization algorithm for post-processing fair classification.
Random Forests are reinterpreted as generative models to handle missing data and detect outliers.
problem Handling missing features and detecting outliers in Random Forests.
method Interpreting Random Forests as Probabilistic Circuits and applying marginalisation for missing data.
result GeDTs and GeFs can handle missing data and detect outliers under certain assumptions.
Paper tackles noisy labels for non-decomposable performance measures.
problem Learning from noisy labels for non-decomposable performance measures.
method Designs algorithms for multiclass non-decomposable performance measures using Frank-Wolfe and Bisection methods, corrected for class-conditional noise.
result Noise-corrected algorithms are Bayes consistent, converging to optimal performance.
The paper revisits discriminative vs. generative classifiers, showing naive Bayes requires fewer samples.
problem Comparing discriminative and generative classifiers in multiclass settings.
method Theoretical analysis and simulations of naive Bayes vs. logistic regression.
result Multiclass naive Bayes requires fewer samples to approach asymptotic error compared to logistic regression.
Study on -consistency bounds for machine learning surrogates.
problem Estimating target loss error relative to surrogate loss error in machine learning.
method Developed -consistency bounds for various surrogates and loss functions.
result Stronger guarantees than existing methods, offering distribution-dependent and -independent bounds.
A novel framework for regression with multiple experts, addressing challenges in infinite and continuous label spaces.
problem Challenges in regression with multiple experts due to the infinite and continuous nature of the label space.
method Introduces a novel framework for regression with deferral, analyzing both single-stage and two-stage scenarios with new surrogate loss functions.
result Proves -consistency bounds for both single-stage and two-stage methods, providing stronger guarantees than Bayes consistency.
We develop a variant of multiclass logistic regression that is significantly more robust to noise. The algorithm has one weight vector per class and the surrogate loss is a function of the linear activations (one per class). The surrogate loss of an example with linear activation vector and class has t…
This paper introduces new loss functions for balanced multi-class classification.
problem Balancing class imbalance in multi-class classification.
method Introduces two new surrogate loss families: GLA and GCA.
result GCA losses offer stronger theoretical guarantees in imbalanced settings.