Paper analyzes conditions for clustering BMMs with unknown clusters.
problem Clustering Bernoulli Mixture Models (BMMs) with unknown number of clusters.
method Theoretical analysis of sample complexity and dimensionality for PAC-clusterability.
result First non-asymptotic bounds on sample complexity for learning or clustering BMMs.
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.
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.
PACC Discovery improves causal inference from limited data.
problem Inferring causal relationships from finite data.
method Extends PAC learning principles to causal inference.
result Theoretical guarantees for various causal methods.
Paper introduces Uniform-PAC framework for RL, bridging PAC and regret.
problem Measuring and guaranteeing performance in reinforcement learning.
method Introduces Uniform-PAC framework, derives high probability regret guarantees.
result Demonstrates new algorithm achieving optimal regret and PAC guarantees.
Formally proves machine learning for simple classifiers.
problem Proving PAC learnability for decision stumps.
method Formal proof in Lean, separating deterministic and probabilistic proofs.
result Formal proof of PAC learnability for decision stumps.
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.
Develops a theory to make learning solutions fair and safe.
problem Ensuring learning solutions are unbiased and safe in critical applications.
method Generates a generalization theory based on PAC learning framework, introduces constrained learning algorithm.
result Proves that constrained learning is as learnable as unconstrained learning, provides practical algorithm.
Paper tackles one-bit compressed sensing using PAC learning theory.
problem One-bit compressed sensing problem.
method Formulated as PAC learning problem, uses VC-dimension and PAC learning theory.
result Consistent algorithm can recover k-sparse vectors with O(klg(n/k)) measurements. 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.
Paper proposes efficient algorithms for bandit problems with costly sampling.
problem Maximizing expectation function over a finite set with high sampling cost.
method Proposes naive and adaptive stochastic bandit algorithms for PAC solution.
result Adaptive algorithm outperforms naive in terms of number of samples.
New PAC-Bayesian approach stabilizes actor-critic learning.
problem Training instability in actor-critic algorithms.
method Employing PAC-Bayesian bound as the critic training objective.
result Significant improvement in online learning performance.
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.
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.
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.
The study analyzes group testing algorithms for identifying defective items with high confidence.
problem Identifying defective items from a population using group testing with high confidence.
method Formulated as a function learning problem using the PAC framework, analyzed three algorithms: column matching, combinatorial basis pursuit, and definite defectives.
result Derived bounds on the number of tests needed for approximate set identification, comparing with existing bounds and simulating performance.
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.
Paper bounds PAC RL sample complexity in deterministic MDPs.
problem Identify ε-optimal policy with high probability.
method Proposes nearly matching upper and lower bounds on sample complexity, introduces deterministic return gap, uses graph-theoretical concepts and maximum-coverage exploration.
result First nearly matching upper and lower bounds on sample complexity for PAC RL in deterministic MDPs.
A new model clusters multi-faceted data with uncertainty quantification.
problem Uncertainty in multi-view clustering of high-dimensional data.
method Approximate Bayes approach, treating similarity matrices as rough estimates, refining with low-rank matrix.
result Each simplex coordinate encodes cluster assignment uncertainty.
Data-dependent PAC-Bayes priors via differential privacy improve generalization bounds.
problem Creating valid generalization bounds for unknown data distributions.
method Using ε-differential privacy to construct data-dependent priors, leading to valid PAC-Bayes bounds.
result Data-dependent priors via differential privacy yield nonvacuous generalization 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.
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 …
The paper improves off-policy evaluation in contextual bandits using conformal prediction.
problem Quantifying the performance of a target policy using data from a different behavior policy.
method Proposes a novel algorithm based on a PAC-valid conformal prediction framework to construct probably approximately correct prediction intervals.
result Establishes PAC-type bounds on coverage, improving theoretical guarantees.
Formulates a Dueling Bandits problem for eliciting Kemeny rankings.
problem Eliciting preferences to find a Kemeny ranking.
method Formulates the problem as a Dueling Bandits problem, considering sampling with and without replacement.
result Approximation bounds and algorithms for finding PAC solutions with sample complexity.
Proposes a method to quantify uncertainty in predictions under covariate shift.
problem Uncertainty quantification challenges in machine learning with covariate shifts.
method Constructs PAC prediction sets with given importance weights and confidence intervals for weights.
result Algorithm gives prediction sets with the smallest average normalized size.
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.
We introduce a technique to compute probably approximately correct (PAC) bounds on precision and recall for matching algorithms. The bounds require some verified matches, but those matches may be used to develop the algorithms. The bounds can be applied to network reconciliation or entity resolution algorithms, which i…
The paper improves confidence ellipsoids for ridge regression with PAC bounds.
problem Uncertainty quantification in ridge regression for insufficiently exciting inputs.
method Extension of SPS EOA algorithm to ridge regression with PAC bounds.
result Explicitly shows how regularization parameter affects region sizes and provides tighter bounds.
New PAC bound for meta-learning improves generalization guarantees.
problem Provide strong generalization guarantees in meta-learning.
method PAC-Bayes and uniform stability frameworks applied to gradient-based meta-learning.
result Derives a tighter PAC bound for gradient-based meta-learning.
New bounds using samplewise evaluated CMI for deep neural networks.
problem Improving generalization bounds for deep neural networks.
method Introduced a new family of information-theoretic generalization bounds using samplewise evaluated conditional mutual information (CMI).
result The new bounds can be tighter than previous ones for deep neural networks.
Efficient algorithms learn non-binary concepts from random counter-examples.
problem Learning non-binary concepts from random counter-examples efficiently.
method Two simple LRC algorithms: deterministic and randomized.
result Both algorithms achieve optimal average learning time of O(log|H|).
Develops anytime-valid conformal and PAC prediction for streaming data.
problem Lack of guarantee in traditional conformal methods for sequential settings.
method Extends conformal and PAC prediction frameworks to handle streaming data.
result Provides anytime-valid prediction sets for sequential settings.
New bounds show covariate shift doesn't make PAC learning impossible.
problem Learning under different distributions with same labels.
method Recontextualizing PAC learning bounds for covariate shift.
result PAC learnable concepts are still learnable under covariate shift with polynomial sample increase.
The paper addresses the reliability of conformal prediction under covariate shift.
problem Ensuring reliable prediction sets under covariate shift.
method Derives upper bounds on training-conditional coverage.
result Offers PAC guarantees for conformal prediction methods.
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.
New algorithm tackles constrained Markov decision processes with peak constraints.
problem Optimizing dynamic systems with peak constraints.
method Model-free algorithm converting PCMDP to unconstrained problem, applying Q-learning.
result Algorithm achieves (ε,p)-PAC policy under certain conditions. A new hyperparameter optimization method reduces overfitting.
problem Overfitting in hyperparameter optimization.
method PAC-Bayes bound minimization using gradient-based algorithm.
result Significant reduction in out-of-sample error.
New method calibrates machine learning models with theoretical guarantees.
problem Lack of theoretical guarantees for recalibration in multiclass classification.
method PAC-Bayes analysis for generalization error in calibration.
result First optimizable upper bound for generalization error in calibration.
The paper optimizes identifying top k arms from a fraction of ρ arms in stochastic bandits.
problem Identifying k distinct arms among the top ρ fraction of arms in stochastic bandits with a PAC tolerance. method The paper considers two cases: known and unknown threshold of top arms' expected rewards. It proves lower bounds and proposes algorithms for each case, showing sample complexity optimality for two algorithms.
result Two algorithms are sample complexity optimal (up to constant factors) and the other two are optimal up to a log factor.
Proposes a new approach to regression learning that addresses overfitting and underfitting.
problem Regression learning issues, including overfitting and underfitting.
method Introduces epsilon-Confidence Approximately Correct (epsilon CoAC) framework using Kullback Leibler divergence.
result Demonstrates improved learnability and accuracy compared to cross-validation.
The paper explores how machine learning models can be learnable despite label shifts.
problem Learnability of binary classification models in the presence of label shifts.
method Developed a performative empirical risk function that is an unbiased estimate of the true risk on the shifted distribution.
result PAC-learnable hypothesis spaces remain PAC-learnable for performative scenarios.
Theorem ensures superior learning outcomes for authorized learners with quantum label encoding.
problem Ensuring data security for authorized learners in machine learning.
method Quantum label encoding and PAC learning framework.
result Authorized learners achieve superior learning outcomes while eavesdroppers do not.
We consider the problem of Probably Approximate Correct (PAC) learning of a binary classifier from noisy labeled examples acquired from multiple annotators (each characterized by a respective classification noise rate). First, we consider the complete information scenario, where the learner knows the noise rates of all…
Develops a new learning framework for dynamic data.
problem Poor performance of existing strategies in dynamic data and goals.
method Prospective Learning framework and Prospective ERM algorithm.
result Prospective ERM converges to Bayes risk under certain assumptions.
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.
The paper studies ranking algorithms from pairwise and listwise comparisons, deriving lower bounds and optimal algorithms.
problem Designing efficient ranking algorithms from pairwise and listwise comparisons.
method Deriving lower bounds and proposing optimal algorithms for top-k and total ranking problems.
result The proposed algorithms match the derived lower bounds and are optimal up to a logarithmic factor.
The paper bridges theory and practice in query-driven selectivity learning.
problem Insufficient theoretical understanding of query-driven selectivity learning.
method Demonstrates learnability of selectivity predictors and establishes favorable OOD generalization error bounds.
result Theoretical advances improve OOD generalization of query-driven selectivity models.
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.