Papers PAC learning
“PAC learning” 태그가 달린 논문 289편 · 필터 해제
Computational-Statistical Tradeoffs from NP-hardness
A central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems. Many computational-statistical tradeoffs have been shown under a…
Computational EfficiencyPAC learningA Distributional-Lifting Theorem for PAC Learning
The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the design of efficient algorithms but also lim…
PAC learningConservative classifiers do consistently well with improving agents: characterizing statistical and online learning
Machine learning is now ubiquitous in societal decision-making, for example in evaluating job candidates or loan applications, and it is increasingly important to take into account how classified agents will react to the…
PAC learningAlgorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-index Models
We study the complexity of learning real-valued Multi-Index Models (MIMs) under the Gaussian distribution. A $K$-MIM is a function $f:\mathbb{R}^d\to \mathbb{R}$ that depends only on the projection of its input onto a $K…
PAC learningAttribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
Attribute-efficient learning of sparse halfspaces has been a fundamental problem in machine learning theory. In recent years, machine learning algorithms are faced with prevalent data corruptions or even adversarial atta…
AttributeLearning TheoryPAC learningA packing lemma for VCN${}_k$-dimension and learning high-dimensional data
Recently, the authors introduced the theory of high-arity PAC learning, which is well-suited for learning graphs, hypergraphs and relational structures. In the same initial work, the authors proved a high-arity analogue …
LEMMAPAC learningFrom learnable objects to learnable random objects
We consider the relationship between learnability of a "base class" of functions on a set $X$, and learnability of a class of statistical functions derived from the base class. For example, we refine results showing that…
PAC learningLean Formalization of Generalization Error Bound by Rademacher Complexity
We formalize the generalization error bound using Rademacher complexity in the Lean 4 theorem prover. Generalization error quantifies the gap between a learning machine's performance on given training data versus unseen …
LEMMAPAC learningNumerical and statistical analysis of NeuralODE with Runge-Kutta time integration
NeuralODE is one example for generative machine learning based on the push forward of a simple source measure with a bijective mapping, which in the case of NeuralODE is given by the flow of a ordinary differential equat…
Learning TheoryPAC learningPAC Learning with Improvements
One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes $\textit{at least}$ $1/\epsilon$ samples to learn to error $\epsilon$ (and more, if the classifier being learned i…
PAC learningA Linear Theory of Multi-Winner Voting
We introduces a general linear framework that unifies the study of multi-winner voting rules and proportionality axioms, demonstrating that many prominent multi-winner voting rules-including Thiele methods, their sequent…
Learning TheoryPAC learningTowards Understanding Multi-Round Large Language Model Reasoning: Approximability, Learnability and Generalizability
Recent advancements in cognitive science and multi-round reasoning techniques for Large Language Models (LLMs) suggest that iterative thinking processes improve problem-solving performance in complex tasks. Inspired by t…
Language ModelingLanguage ModellingLarge Language ModelMathematical Reasoning+3Contrastive Learning with Nasty Noise
Contrastive learning has emerged as a powerful paradigm for self-supervised representation learning. This work analyzes the theoretical limits of contrastive learning under nasty noise, where an adversary modifies or rep…
Contrastive LearningPAC learningRepresentation LearningTowards Efficient Contrastive PAC Learning
We study contrastive learning under the PAC learning framework. While a series of recent works have shown statistical results for learning under contrastive loss, based either on the VC-dimension or Rademacher complexity…
Contrastive LearningPAC learningBandit Multiclass List Classification
We study the problem of multiclass list classification with (semi-)bandit feedback, where input examples are mapped into subsets of size $m$ of a collection of $K$ possible labels, and the feedback consists of the predic…
ClassificationPAC learningOn Agnostic PAC Learning in the Small Error Regime
Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the agnostic case. Roughly speaking, this owes…
Binary ClassificationPAC learningSimplifying Adversarially Robust PAC Learning with Tolerance
Adversarially robust PAC learning has proved to be challenging, with the currently best known learners [Montasser et al., 2021a] relying on improper methods based on intricate compression schemes, resulting in sample com…
PAC learningOn the Computability of Multiclass PAC Learning
We study the problem of computable multiclass learnability within the Probably Approximately Correct (PAC) learning framework of Valiant (1984). In the recently introduced computable PAC (CPAC) learning framework of Agar…
PAC learningData-Driven Neural Certificate Synthesis
We investigate the problem of verifying different properties of discrete time dynamical systems, namely, reachability, safety and reach-while-avoid. To achieve this, we adopt a data driven perspective and using past syst…
Generalization BoundsPAC learningEfficient Optimal PAC Learning
Recent advances in the binary classification setting by Hanneke [2016b] and Larsen [2023] have resulted in optimal PAC learners. These learners leverage, respectively, a clever deterministic subsampling scheme and the cl…
Binary ClassificationPAC learning