5 problems

Aden Ali–Hogsgaard–Larsen–Zhivotovskiy conjecture on majority-of-three PAC optimality
arXiv@arxiv
In the realizable PAC setting, split a labeled sample into three equal blocks and train one independently chosen consistent classifier on each block. The majority-of-three conjectu…
Conjectureopenpac-learning sample-complexity voting-classifiers
0
Warmuth's conjecture on optimal PAC bounds for the one-inclusion graph algorithm
arXiv@arxiv
Consider the one-inclusion graph algorithm for realizable classification, which uses a labeled sample with one point held out and has leave-one-out performance bounded by the relev…
Conjecturerefutedlearning-theory one-inclusion-graph pac-learning
0
Daniely–Shalev-Shwartz conjecture on DS dimension and risk complexity
arXiv@arxiv
Let $\mathcal{H} \subseteq \mathcal{Y}^{\mathcal{X}}$ be a hypothesis class with Daniely–Shalev-Shwartz dimension $d_{\operatorname{DS}}$ , and let $(d_n)_{n \in \mathbb{N}}$ be the…
Conjecturerefutedcomplexity-dimensions pac-learning statistical-learning-theory
1
The conjecture that logarithmic factors are unnecessary for PAC bounds
arXiv@arxiv
In binary classification, let $d$ denote the relevant complexity parameter and let $n$ be the sample size. The one-inclusion graph approach gives an in-expectation PAC error bound…
Conjecturerefutedonline-learning pac-learning uniform-convergence
0
Computational hardness of improving error guarantees for Massart-noise halfspace learning
arXiv@arxiv
Computational hardness conjecture. Obtaining better error guarantees than the algorithm's guarantee is computationally intractable.
Conjectureopenhalfspaces massart-noise pac-learning
0

5 problems

Aden Ali–Hogsgaard–Larsen–Zhivotovskiy conjecture on majority-of-three PAC optimality

Warmuth's conjecture on optimal PAC bounds for the one-inclusion graph algorithm

Daniely–Shalev-Shwartz conjecture on DS dimension and risk complexity

The conjecture that logarithmic factors are unnecessary for PAC bounds

Computational hardness of improving error guarantees for Massart-noise halfspace learning