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,742 papers · 148 categories
Trend · papers per month
48 results for “PAC model”
Large language models can't efficiently reason conditionally in a distribution-free setting.
problem Impossibility of conditional PAC-efficient reasoning in large language models.
method Proof of impossibility in a distribution-free setting for non-atomic input spaces.
result Any algorithm achieving conditional PAC efficiency must defer to the expert model with high probability.
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.
Algorithm constructs confidence sets for deep neural networks with PAC guarantees.
problem Ensuring reliable predictions for deep neural networks with high confidence.
method Combines calibrated prediction and learning theory bounds.
result Constructs PAC confidence sets for various deep models.
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.
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.
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.
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.
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.
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.
The study improves PAC-Bayesian bounds for adversarial generative models.
problem Improving generalization bounds for adversarial generative models.
method Extending PAC-Bayesian theory to generative models, developing bounds for Wasserstein and total variation distances.
result New training objectives for Wasserstein and Energy-Based GANs.
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 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.
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.
PAC-Bayesian bounds for MLPs with cross entropy loss validated.
problem Generalization bounds for MLPs with cross entropy loss.
method Introduced probabilistic explanations and proved PAC-Bayesian bounds using ELBO.
result MLPs with cross entropy loss inherently guarantee PAC-Bayesian generalization bounds.
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.
The study examines how equivariance in networks affects generalization error using PAC-Bayesian bounds.
problem Understanding how equivariance in networks impacts generalization error.
method Utilized PAC-Bayesian analysis for equivariant networks, deriving norm-based bounds for generalization error.
result The bound indicates that using larger group size in the model improves generalization error.
New bounds for model generalization under deterministic gradient descent.
problem Establishing generalization bounds for models trained with gradient descent methods.
method PAC-Bayesian bounds for deterministic optimisation algorithms.
result Fully computable bounds that depend on initial distribution and Hessian.
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.
Unified derivation of PAC-Bayes and MI bounds for general VC classes with fast rates.
problem Generalization bounds for machine learning models with VC classes.
method Unified derivation of conditional PAC-Bayesian and mutual information bounds, including MAC-Bayesian bounds.
result Nontrivial bounds for general VC classes and faster rates for specific conditions.
The developments of Rademacher complexity and PAC-Bayesian theory have been largely independent. One exception is the PAC-Bayes theorem of Kakade, Sridharan, and Tewari (2008), which is established via Rademacher complexity theory by viewing Gibbs classifiers as linear operators. The goal of this paper is to extend thi…
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-Wrap provides provable guarantees for semi-supervised anomaly detection.
problem Ensuring reliable anomaly detection in safety-critical applications.
method PAC-Wrap wraps around existing anomaly detection methods to provide PAC guarantees.
result PAC-Wrap effectively provides rigorous guarantees for various anomaly detectors.
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…
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.
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.
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 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.
This work provides statistical guarantees for VAEs using PAC-Bayesian theory.
problem Theoretical properties of VAEs remain open questions.
method PAC-Bayesian theory to derive statistical guarantees.
result Upper bounds on Wasserstein distance between input and generative model.
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 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.
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.
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.
PAC-Bayesian-Like Error Bound for a Class of Linear Time-Invariant Stochastic State-Space Modelsstat.ML
Paper derives an error bound for stochastic LTI systems.
problem Stochastic LTI systems with inputs in control engineering and econometrics.
method PAC-Bayesian-Like error bound derivation.
result Derived an error bound for stochastic LTI systems.
New algorithm optimizes PAC-Bayes bound without surrogate loss.
problem Mismatch between optimisation objective and generalisation bound in stochastic neural networks.
method Proposes a novel training algorithm that optimizes the PAC-Bayesian bound directly.
result Empirical results show improved performance over existing PAC-Bayesian training methods.
New PAC-Bayes bounds for unbounded losses using Cramér-Chernoff techniques.
problem Developing bounds for unbounded losses in PAC-Bayesian settings.
method Introducing a new PAC-Bayes oracle bound using Cramér-Chernoff bounds and controlling random variable tails.
result Our bounds generalize and improve upon previous results, providing more informative and potentially tighter bounds.
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.
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.
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.
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.
PAC learning sample complexity is decidable with finite support bounds.
problem Determining the exact sample complexity for PAC learning concepts.
method Observation and proof of decidability with a-priori bounds.
result Sample complexity can be exactly determined for various concepts with finite support bounds.
New risk measures control subgroup imbalances, improving PAC-Bayesian bounds.
problem Insufficient risk bounds for subgroup imbalances in data.
method Introduce constrained f-entropic risk measures and derive PAC-Bayesian bounds.
result First disintegrated PAC-Bayesian guarantees beyond standard risks.
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.
New method reduces computational cost for estimating PAC-Bayes bounds.
problem High computational cost in estimating PAC-Bayes bounds.
method General alternative method that makes computational savings.
result Reduces computational cost on the order of the dataset size.
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.
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.
PAC-Bayesian matrix completion with a spectral scaled Student prior offers efficient inference.
problem Matrix completion with underlying low-rank structure.
method Spectral scaled Student prior and PAC-Bayesian bounds.
result Minimax-optimal oracle inequality for model misspecification and general sampling distribution.
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 …