PAC learning simplified as bipartite matching.
problem Efficiently solving PAC learning problems.
method Transductive learning and one-inclusion graphs.
result PAC learning can be reduced to bipartite matching.
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
48 results for “PAC Model Learning”
A new framework for robustness analysis of deep neural networks using PAC-model learning.
problem Analyzing local robustness of deep neural networks.
method Black-box model learning with scenario optimisation to abstract DNN behaviour via an affine model with PAC guarantee.
result DeepPAC outperforms state-of-the-art statistical methods in practical robustness analysis.
Study shows transductive learning is equivalent to PAC learning for most natural loss functions.
problem Understanding the relationship between transductive and PAC learning models.
method Extending existing results and developing new techniques to analyze the equivalence of the two models.
result Transductive learning is essentially equivalent to PAC learning for realizable learning with most natural loss functions.
New hybrid RL algorithm outperforms model-free and model-based methods.
problem Improving reinforcement learning algorithms for MDPs.
method Combines model-free and model-based learning, with a PAC analysis.
result Outperforms both model-free and model-based methods in most cases.
Efficient PAC learning for contrastive linear representations is achieved.
problem Efficient PAC learning for contrastive linear representations.
method Relaxing the problem to a semi-definite program and using Rademacher complexity.
result First efficient PAC learning algorithm for contrastive learning.
New PAC-Bayes meta-learning method improves few-shot learning accuracy and calibration.
problem Few-shot learning with limited data.
method PAC-Bayes framework extended to meta-learning, estimating task-specific posteriors.
result State-of-the-art calibration and classification results on benchmarks.
Enhances predictive models against misspecification and outliers.
problem Suboptimal generalization under misspecification and outliers.
method Combines PAC ensemble bounds with a generalized logarithm score function.
result Produces predictive distributions resistant to both misspecification and outliers.
Meta-learning bounds derived using PAC-Bayes theory for improved generalization.
problem Uncertainty in generalization performance for meta-learning with new tasks.
method PAC-Bayes relative entropy bounds and empirical risk minimization (ERM) method.
result Competitive generalization performance and rapid convergence with data-dependent prior.
New algorithm constructs PAC prediction sets for meta-learning.
problem Uncertainty quantification in safety-critical systems.
method Proposes a novel algorithm to construct PAC prediction sets.
result Prediction sets satisfy a PAC guarantee with high probability over future tasks.
Paper develops PAC verification for hypothesis classes and statistical algorithms.
problem Verifying machine learning models interactively.
method Develops interactive proof for PAC verification, proves lower bounds, and introduces a generalization.
result Improved protocol for verifying unions of intervals and statistical query algorithms.
PAC-Bayesian bounds estimate adversarial robustness.
problem Estimating robustness to imperceptible input perturbations.
method PAC-Bayesian framework for averaging over hypotheses.
result General bounds valid for any type of adversarial attacks.
Survey and compare PAC-Bayes bounds for bandit problems.
problem Designing and evaluating bandit algorithms with strong performance guarantees.
method PAC-Bayes bounds applied to bandit problems.
result PAC-Bayes bounds useful for offline bandit algorithms, but loose for online algorithms.
Paper derives PAC-Bayesian bounds for LTI systems learning from empirical data.
problem Characterizing predictive power of LTI systems learned from data.
method PAC-Bayesian bounds for LTI stochastic dynamical systems with inputs.
result Finite-sample error bounds for learning algorithms of LTI systems.
PAC-Net prunes deep models for better transfer learning.
problem Improving transfer learning with over-parameterized models.
method Prune, Allocate, Calibrate (PAC) approach.
result PAC-Net achieves state-of-the-art performance in inductive transfer learning.
New algorithms reduce communication costs in collaborative learning.
problem Reducing communication costs in collaborative learning.
method Distributed boosting and adaptation to classification noise.
result Communication-efficient algorithms for collaborative PAC learning robust to noise.
PAC-Bayesian bounds for stochastic LTI systems derived.
problem Error bounds for stochastic LTI systems.
method PAC-Bayesian theory applied to autonomous stochastic LTI models.
result Error bounds for stochastic LTI systems derived.
New PAC-Bayesian bounds for online learning with data streams.
problem Challenges of traditional PAC-Bayesian bounds in dynamic data collection.
method Developed new PAC-Bayesian bounds in online learning framework, using updated regret definition and batch-to-online conversion.
result PAC-Bayesian bounds hold for online learning with dependent data and non-convex losses.
This work extends PAC-Bayesian learning guarantees to non-compact symmetries and non-invariant data.
problem Lack of theoretical guarantees explaining the benefits of symmetries in machine learning models.
method Adapting and tightening PAC-Bayes bounds for non-compact symmetries and non-invariant data distributions.
result Theoretical evidence that symmetric models are preferable for symmetric data, beyond compact groups and invariant distributions.
Survey on learning Boolean functions in computational theory.
problem Learning Boolean function classes in computational theory.
method Overview of known results in PAC and related models.
result Discussion of various learning results for Boolean functions.
The paper improves PAC-Bayes bounds for data-dependent predictors.
problem Guaranteeing the quality of predictions on unseen examples.
method Basic PAC-Bayes inequality for stochastic kernels, leading to various bounds.
result Validates PAC-Bayes bounds without fixed 'data-free' priors and bounded losses.
This paper improves meta-learning by developing new PAC-Bayes bounds.
problem Meta-learning generalization gap across multiple tasks.
method Upper bounding convex functions linking environment and task-level losses.
result New PAC-Bayes bounds for meta-learning with improved algorithms.
We propose an algorithm combining calibrated prediction and generalization bounds from learning theory to construct confidence sets for deep neural networks with PAC guarantees---i.e., the confidence set for a given input contains the true label with high probability. We demonstrate how our approach can be used to cons…
PAC-Bayes bounds for Gibbs posteriors derived via singular learning theory.
problem Generalization bounds for overparameterized models with data-dependent priors.
method Explicit non-asymptotic PAC-Bayes bounds using singular learning theory.
result Explicit posterior-averaged risk bounds for overparameterized models.
PAC-Bayesian Generalization Guarantees for Fairness on Stochastic and Deterministic Classifiersstat.ML
PAC-Bayesian framework for fairness in stochastic and deterministic classifiers.
problem Theoretical guarantees on fairness for balancing predictive risk and fairness constraints.
method PAC-Bayesian framework for both stochastic and deterministic classifiers, covering a broad class of fairness measures.
result Derives generalization bounds for fairness, demonstrating tightness with empirical evaluation.
New PAC-Bayes training method improves model generalization for unbounded loss.
problem Improving generalization of complex models under unbounded loss.
method Established new PAC-Bayes bound for unbounded loss, jointly training prior and posterior.
result Outperforms existing PAC-Bayes training algorithms and matches ERM accuracy.
Bayesian priors offer a compact yet general means of incorporating domain knowledge into many learning tasks. The correctness of the Bayesian analysis and inference, however, largely depends on accuracy and correctness of these priors. PAC-Bayesian methods overcome this problem by providing bounds that hold regardless …
Statistical performance bounds for reinforcement learning (RL) algorithms can be critical for high-stakes applications like healthcare. This paper introduces a new framework for theoretically measuring the performance of such algorithms called Uniform-PAC, which is a strengthening of the classical Probably Approximatel…
New PAC-Bayesian bounds for multi-view learning using Rényi divergence.
problem Applying PAC-Bayesian theory to multi-view learning.
method Introducing novel PAC-Bayesian bounds based on Rényi divergence for multi-view learning.
result Efficient optimization algorithms that align with theoretical bounds.
Introduces PAC-Bayes bounds for understanding learning procedures.
problem Understanding the generalization ability of learning procedures.
method PAC-Bayesian bounds and their applications to neural networks.
result Simplified version of localization technique described.
New algorithms achieve uniform-PAC guarantees for RL with bounded eluder dimension.
problem Achieving strong performance guarantees in reinforcement learning.
method Proposes algorithms for nonlinear bandits and model-based episodic RL with a bounded eluder dimension.
result Achieves uniform-PAC sample complexity that matches state-of-the-art regret bounds or sample complexity guarantees.
New PAC-Bayes bounds use Wasserstein distances to improve generalization.
problem Lack of geometric properties in existing PAC-Bayes bounds.
method Developed new PAC-Bayes bounds with Wasserstein distances.
result Optimization guarantees translate to good generalization abilities.
New PAC-Bayesian bounds provide practical guarantees for neural networks.
problem Loose derandomization step in PAC-Bayesian bounds for deterministic models.
method Introduce disintegrated PAC-Bayesian bounds for deterministic models.
result Significant practical improvement over state-of-the-art bounds.
New findings on PAC learning and marginal distribution estimation.
problem Understanding how PAC learning relates to marginal distribution estimation under distributional constraints.
method Revisited the connection between PAC learning, uniform convergence, and density estimation, considering a known family of marginal distributions.
result PAC learning is sandwiched between two refined models of density estimation, differing only in whether the learner knows the set of well-estimated events in H.
Generalised Bayesian learning algorithms are increasingly popular in machine learning, due to their PAC generalisation properties and flexibility. The present paper aims at providing a self-contained survey on the resulting PAC-Bayes framework and some of its main theoretical and algorithmic developments.
PAC-Bayes bound requires prior to place mass on high-performing predictors.
problem Explaining generalization in machine learning.
method Analyzing necessary conditions for PAC-Bayes bounds to provide meaningful generalization guarantees.
result Achieving a target generalisation level requires the prior to place sufficient mass on high-performing predictors.
This research improves PAC-Bayesian bounds for classification tasks using convexified loss.
problem Deriving generalization bounds for classification tasks with non-convex loss functions.
method Shift focus to misclassification excess risk bounds for PAC-Bayesian classification using convex surrogate loss and leveraging PAC-Bayesian relative bounds in expectation.
result Improved PAC-Bayesian bounds for classification tasks with convex surrogate loss.
Study shows semi-supervised learning can be more robust with fewer labeled examples.
problem Learning robust predictors in semi-supervised PAC model with minimal labeled data.
method Characterizes the minimal labeled and unlabeled data required for robust learning.
result Proves nearly matching upper and lower bounds on labeled sample complexity.
Paper analyzes error exponent in agnostic PAC learning.
problem Analyzing performance of agnostic PAC learning.
method Using error exponent from Information Theory to analyze PAC learning.
result Improved distribution-dependent error exponent for agnostic learning.
Study computable multiclass learning within PAC framework.
problem Computable multiclass learnability in finite label space.
method Proposed computable version of Natarajan dimension and generalized to distinguishers.
result Characterizes CPAC learnability for certain dimensions and embeddings.
Extends PAC learning theory to handle partial concepts with special properties.
problem Traditional PAC learning theory cannot handle tasks with special data properties.
method Introduces partial concepts and new PAC learning framework.
result Partial concept classes cannot be captured by traditional PAC theory.
PAC-Bayes framework fails on simple 1D linear classification task.
problem Proving the learnability of simple 1D linear classification tasks using PAC-Bayes bounds.
method Demonstrated a specific 1D linear classification task that PAC-Bayes cannot analyze.
result PAC-Bayes framework cannot prove learnability of simple 1D linear classification tasks.
New PAC-Bayesian framework for flexible meta-learning.
problem Limitations in transferring knowledge between tasks in meta-learning.
method PAC-Bayesian theory applied to learning the learning algorithm.
result Flexibility in meta-learning mechanisms and improved prediction quality.
PAC-Bayesian theory applied to learning optimization algorithms with generalization guarantees.
problem Learning optimization algorithms with provable generalization guarantees and explicit trade-offs.
method PAC-Bayes theory applied to learning-to-optimize, reformulating the learning procedure into a one-dimensional minimization problem.
result Learned optimization algorithms outperform deterministic worst-case analysis algorithms, even in the limit case of guaranteed convergence.
New algorithm FLUTE achieves uniform-PAC convergence in RL with linear approx.
problem RL with linear function approximation lacks uniform-PAC guarantees.
method FLUTE algorithm with minimax value function estimator and multi-level partition scheme.
result Uniform-PAC convergence to optimal policy with high probability.
Paper develops tighter risk certificates for contrastive learning models.
problem Statistical theory for contrastive learning is lacking, especially for practical models like SimCLR.
method Develops non-vacuous PAC-Bayesian risk certificates considering practical SimCLR factors.
result Risk certificates for contrastive loss and downstream prediction are much tighter than previous results.
The paper explores learning from label proportions, showing differences in efficiency between LLP and PAC learning.
problem Learning from label proportions (LLP) in unlabeled data with given label proportions.
method Formal definition and computational complexity analysis of LLP learning.
result LLP learning is more restrictive than PAC learning for finite VC classes, and some classes are uncharacterizable.
New PAC-Bayes bounds for unbounded loss functions.
problem Generalization bounds for learning problems with unbounded loss functions.
method Introducing HYPE, a new notion for loss range, and deriving a novel PAC-Bayesian generalization bound.
result PAC-Bayes framework extended to unbounded loss functions.
Defines computable learning for binary classification over metric spaces.
problem Defines computable PAC learning for binary classification over computable metric spaces.
method Provides sufficient conditions for ERM learners to be computable and bounds the strong Weihrauch degree of an ERM learner.
result Gives a hypothesis class that does not admit any proper computable PAC learner with computable sample function.