61 problems

Let $P_{\operatorname{PFIN}}$ be the probability hierarchy for probabilistic finite learning, and let $A$ be the set defined immediately after the conjecture in the source. PFIN hi…

Let $\mathcal{C}$ be a category equipped with learning sketches and admissible models. A Lincs completion of $\mathcal{C}$ is a tangent category $\mathsf{LINCS}(\mathcal{C})$ toget…

In the proper positive-only learning model, let a concept class be intersection-closed if it is closed under arbitrary intersections of its concepts. Natarajan's characterization c…

Let $A$ be an $N \times M$ sign matrix, and let $\operatorname{\textnormal{\textsc{lr}}}(A)$ denote its list replicability number. List-replicability conjecture. Every $N \times M$…

The transformer architecture is used to estimate a context function $\mathbf{h}$, with smoothness index $\beta_2\leq 1$, and can represent a Nadaraya--Watson estimator. If the data…

Let $0C$ be a concept class of VC-dimension $d$. A concept class is maximum when, for every finite subset of its domain, it realizes all traces permitted by its VC-dimension.…

Let $H$ be a hypergraph of VC-dimension $d$. A sample compression scheme for $H$ consists of a compression map and reconstruction map that encode every finite sample from $H$ using…

Exact-cost computational conjecture. With a sharper choice of the enlarged regression supports, one can improve the computational-cost bound and achieve the exact optimal computati…

Bounded VCN-dimension conjecture. The resulting hypothesis class should have bounded $\operatorname{VCN}_{2,2}$-dimension.

Let $L\subseteq\mathbb{Z}^k$ be a lattice and let $B_{r,1}(\vec{0})$ denote the allowed ball used in the preceding reduction. Lattice-learning reduction conjecture. There are simil…

Let $\mathcal{C}$ be a concept class of VC dimension $d$ defined on a finite domain $\mathcal{X}$. The Recursive Teaching Dimension is the parameter obtained by recursively removin…

Let $\mathcal{C}$ be a concept class of VC dimension $d$ defined on a finite domain $\mathcal{X}$. The best-case teaching dimension $\operatorname{TS}_{\min}$ is the minimum, over…

Let $(\gamma_n)_n$ be the sequence of news-reaction parameters, let $p^*$ be the data-generating distribution, and let $\mathcal{P}$ be the model's set of distributions. Convergenc…

Abbe–Bengio–Cornacchia–Kleinberg–Lotfi–Raghu–Zhang extension conjecture. The lower bounds of Abbe, Bengio, Cornacchiam, Kleinberg, Lotfi, Raghu and Zhang should extend in a straigh…

Fixed-target-function conjecture. The results of the paper should hold for any fixed target function $f_* \in L^2(\mathbb{S}^{d-1}(\sqrt{d}))$.

A function class is a collection of functions subject to specified constraints, including symmetry constraints. Natural-data representation conjecture. Such function classes should…

Let $p$ be a low-degree polynomial on the unit sphere. Sphere-optimization hardness conjecture. Approximately optimizing $p$ over the unit sphere is conjectured to be computational…

Let Boolean parity functions be learned under the uniform distribution on the hypercube, with either query access or random samples. Hardness conjecture. Learning parities with noi…

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…

Let $C_{\!X\!X}$ be the covariance operator of the covariate random variable $X$, and consider high-probability learning rates for infinite-dimensional linear regression. A suffici…

Let $Gamma$ be a constraint language, and let $r(n)$ be the logarithm of the number of distinct $n$-variable relations definable by primitive positive formulas over $Gamma$. Chen's…

Quantum Bohnenblust–Hille conjecture. Fix $d\ge 1$. There exists $C_d>0$, depending only on $d$, such that for all $n\ge 1$ and every degree-at-most-$d$ operator…

Let $K$ denote the size of the partition (or covering number) used in an algorithmic robustness bound, and let $\boldsymbol{adaptive\ partitioning}$ mean choosing that partition in…

A learning rule is Bayes-consistent if its risk converges to the Bayes risk, and it is monotone if its population loss does not increase as the number of training examples grows. D…

Let a VC class have VC dimension $d$, and consider the randomized one-inclusion graph prediction rule together with a probability assignment for that randomized graph. eCMI conject…