New DP algorithms with margin guarantees for various hypothesis sets.
problem Differential privacy in machine learning with margin guarantees.
method Developed pure and efficient DP learning algorithms for linear, kernel-based, and neural network hypotheses.
result Margin guarantees are independent of input dimension and hypothesis type.
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.
This manuscript shows that AdaBoost and its immediate variants can produce approximate maximum margin classifiers simply by scaling step size choices with a fixed small constant. In this way, when the unscaled step size is an optimal choice, these results provide guarantees for Friedman's empirically successful "shrink…
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.
RLCP improves localized conformal prediction for covariate-specific miscalibration.
problem Localized conformal prediction struggles with covariate-specific miscalibration.
method Randomly localized conformal prediction (RLCP) calibrates near the test point while preserving marginal coverage.
result We provide finite-sample guarantees for RLCP, controlling conditional validity and oracle efficiency.
The paper analyzes structured prediction with new margin guarantees and learning algorithms.
problem Structured prediction with arbitrary factor graphs and complex loss functions.
method Data-dependent margin guarantees and Voted Risk Minimization principle.
result New learning bounds and algorithms (VCRF, StructBoost) for complex factor graphs.
Constructs tail-specific prediction intervals for financial applications
problem Financial applications require strict control on the left tail
method Extends classical conformal frameworks to provide explicit tail-specific guarantees
result Improved directional calibration in skewed data
A new approach for instance-optimal learning that bypasses impossibility results.
problem Impossibility of achieving marginal-by-marginal guarantees for all marginals.
method Introduces relatively smart learning, which requires competition only with certifiable semi-supervised guarantees.
result One-Inclusion Graph learner is relatively smart up to squaring the sample complexity.
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 H-consistency of the proposed margin loss function. Paper provides exponential convergence guarantees for Iterative Markovian Fitting.
problem Addressing the Schrödinger Bridge problem in computational optimal transport and generative modeling.
method Develops non-asymptotic exponential convergence guarantees for Iterative Markovian Fitting.
result First non-asymptotic exponential convergence guarantees for IMF under mild structural assumptions.
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.
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
New method improves consistency in preference learning for neural networks.
problem Inconsistent surrogate losses in preference learning for neural networks.
method Formulated a margin-shifted ranking framework and introduced Structure-Aware H-consistency. result Proved superior consistency guarantees for capacity-bounded models using heavy-tailed surrogates.
Paper shows SVM can achieve super fast convergence rates.
problem Understanding fast convergence rates for SVM.
method Presented a simple mechanism to obtain fast convergence rates for SVM.
result SVM can exhibit exponential convergence rates without hard Tsybakov margin condition.
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 method bounds causal effects using local consistency of marginals.
problem Bounding causal effects due to unmeasured confounding.
method Enforces compatibility between marginals of causal models and data.
result Explicit algorithm and implementation of causal marginal polytope.
Semi-supervised learning can't improve with certain loss functions.
problem Limiting improvement in semi-supervised learning with specific loss functions.
method Analysis of convex margin-based losses that are either decreasing or increasing.
result Safe improvements possible with increasing margin-based losses.
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.
Improves Gaussian process regression without bias.
problem Bias in Gaussian process regression estimates.
method Adaptive computation selection to minimize bias.
result Guaranteed small bias in log marginal likelihood estimates.
Adapts conformal prediction for missing data, ensuring valid coverage.
problem Uncertainty quantification with missing covariates.
method Proposes a reweighted conformal prediction procedure for handling missing values.
result Guaranteed Marginal Coverage and Mask-Conditional Validity for general missing data mechanisms.
This work introduces a noise-adaptive conformal inference method for better prediction sets in noisy data.
problem Real-world complications like random label noise limit the effectiveness of conformal inference.
method An adaptive conformal inference method capable of handling deviations from exchangeability.
result Informative prediction sets with tight marginal coverage guarantees in noisy data.
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 method improves MAP inference efficiency and reliability.
problem Efficient inference in systems with latent variables or missing data.
method Generalized dual decomposition on a convex decomposition bound.
result Framework converges monotonically and is faster/reliable than previous methods.
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 findings on the max margin problem in neural networks.
problem Understanding the max margin problem in neural networks.
method Analyzing gradient flow and max margin problem in linear and ReLU networks.
result The KKT point is not always an optimum of the max margin problem.
The marginal maximum a posteriori probability (MAP) estimation problem, which calculates the mode of the marginal posterior distribution of a subset of variables with the remaining variables marginalized, is an important inference problem in many models, such as those with hidden variables or uncertain parameters. Unfo…
This work proposes a new method to estimate joint probability from pairwise marginals, reducing sample complexity.
problem Direct nonparametric estimation of high-dimensional joint probability is infeasible due to the curse of dimensionality.
method Developed a coupled nonnegative matrix factorization (CNMF) framework using only pairwise marginals.
result The method provably recovers the joint probability mass function up to bounded error in finite iterations under reasonable conditions.
L-ARC improves model fairness by localizing risk guarantees.
problem Improving model fairness in tasks like image segmentation and wireless networks.
method Localized Adaptive Risk Control (L-ARC) updates a threshold function in RKHS to target localized statistical risk guarantees.
result L-ARC produces prediction sets with improved fairness across different data subpopulations.
New algorithms estimate Q-functions under partial coverage and realizability, improving offline RL guarantees.
problem Offline RL with limited exploration and assumptions about data coverage and Q-function realizability.
method Proposes minimax learning algorithms to estimate soft or vanilla Q-functions with L2-convergence guarantees. result PAC guarantees for offline RL under partial coverage and realizability conditions.
Split conformal prediction provides finite-sample guarantees for black-box models without distributional assumptions.
problem Weak performance guarantees for modern predictive models under minimal assumptions.
method Develops finite-sample guarantees for split conformal prediction, a method that uses nested prediction sets and order statistics.
result The coverage of prediction sets based on order statistics stochastically dominates the Beta distribution.
We give two provably accurate feature-selection techniques for the linear SVM. The algorithms run in deterministic and randomized time respectively. Our algorithms can be used in an unsupervised or supervised setting. The supervised approach is based on sampling features from support vectors. We prove that the margin i…
The paper improves conformal prediction by analyzing the beta law of conditional coverage.
problem Improving finite-sample marginal coverage guarantees for non-i.i.d. data.
method The method uses Wasserstein distances to quantify deviations from the beta law of conditional coverage.
result The framework provides direct bounds on marginal coverage gaps and bad-calibration probabilities.
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.
Audited Conformal Prediction improves conditional coverage in pretrained models under distribution shift.
problem Uncertainty quantification for pretrained models under unknown distribution shift
method Leverages a small labeled dataset to train an audit model for marginal coverage, integrates outputs into conformal prediction framework
result Significantly higher conditional coverage than existing approaches
New framework for optimal transport with jumps over intermediate spaces.
problem Optimal transport with mass jumps over intermediate spaces.
method Hierarchical Jump multi-marginal transport (HJMOT) on Polish spaces.
result Existence and uniqueness of Monge solutions under sequential differentiability and twist condition.
Maximizing margins leads to lossless compression of training data.
problem Generalization in supervised learning.
method Information-theoretic interpretation of margin maximization.
result Margin maximization is a form of lossless maximal compression.
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.
Meta-learning reduces set prediction size in conformal prediction for few-shot calibration.
problem Inefficient set prediction in conformal prediction for limited training data.
method Meta-learning approach using cross-validation-based conformal prediction.
result Meta-learning scheme reduces set prediction size and preserves formal guarantees.
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.
We derive and analyze a new, efficient, pool-based active learning algorithm for halfspaces, called ALuMA. Most previous algorithms show exponential improvement in the label complexity assuming that the distribution over the instance space is close to uniform. This assumption rarely holds in practical applications. Ins…
Method constructs nonparametric prediction intervals with finite-sample guarantees.
problem Nonparametric instrumental variable regression with finite-sample coverage.
method Conformal inference framework applied to NPIV, combining with various estimators.
result Distribution-free, finite-sample coverage over chosen IV shifts.
Framework for private, noise-tolerant, and efficient learning algorithms.
problem Private and efficient learning of large-margin halfspaces in noisy environments.
method Simple framework using differential privacy and noise tolerance conditions.
result Noise-tolerant and private PAC learners for large-margin halfspaces with sample complexity independent of dimension.
New insights link no-regret learning to online conformal prediction in adversarial settings.
problem Understanding the relationship between no-regret learning and online conformal prediction in adversarial environments.
method Analysis of existing algorithms and new connections between no-regret learning and conformal prediction.
result No-regret learning algorithms can provide group-conditional coverage guarantees in adversarial settings.
Robust GP model detects and corrects sparse outliers.
problem Non-Gaussian noise in real-world data.
method Relevance pursuit for data-point-specific noise levels.
result Strong concavity and approximation guarantees for subset selection.
The paper improves robust optimization by introducing margin theory.
problem Improving the reliability of solutions in high-dimensional robust optimization.
method Introducing margin theory to improve sample complexity and reliability of solutions.
result The sample complexity of a class of random programs does not depend on the number of variables.
Unified framework for removing unwanted information from machine learning models.
problem Removing undesirable features or data points from machine learning models while preserving utility.
method Information-theoretic regularization approach for data point and feature unlearning.
result Unified mathematical framework with provable guarantees for both data point and feature unlearning.
We present a new family of models that is based on graphs that may have undirected, directed and bidirected edges. We name these new models marginal AMP (MAMP) chain graphs because each of them is Markov equivalent to some AMP chain graph under marginalization of some of its nodes. However, MAMP chain graphs do not onl…
New algorithm for efficient inference over tree-structured graphs.
problem Inference over probabilistic graphical models with aggregate data.
method Optimal transport theory, Sinkhorn/iterative scaling algorithm, belief propagation.
result Global convergence and polynomial computational complexity.