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

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 associated sequence of complexity measures. For any sample size $n \ge d_{\operatorname{DS}}$ , there is an absolute constant $c>0$ such that

d_n \le c\,d_{\operatorname{DS}}.

Daniely–Shalev-Shwartz conjecture. The DS dimension controls the sequence complexity measures uniformly in $n$ through the displayed bound. The conjecture seeks to replace the sequence $(d_n)_{n \in \mathbb{N}}$ by a single dimension; it is equivalent to the VC dimension in the binary setting, while its general status is not resolved in the supplied text.

Daniely and Shalev-Shwartz posed the conjecture in 2014: the complexity sequence should be bounded by a constant multiple of the DS dimension once the sample is sufficiently large. The binary case is settled, while the multiclass quantitative statement was previously open.

Known results

Binary classes: the DS dimension equals VC dimension, and the one-inclusion bound gives the desired control (Haussler, Littlestone, and Warmuth, 1994).
Finite DS dimension characterizes multiclass PAC learnability (Brukhim, Carmon, Dinur, Moran, and Yehudayoff, 2022).
Earlier quantitative bounds were roughly $d_{\mathrm{DS}}^{3/2}$ up to logarithmic factors.

April 2026 claimed proof

A 2026 preprint claims that, for every $\ell\ge1$ and $n>0$ , $\lceil\mu_{\mathcal H}^{\ell}(n)\rceil\le d_{\mathrm{DS}}^{\ell}$ . Its $\ell=1$ case implies the conjectured uniform bound and removes the previous superlinear gap. This is a claim, not an independently verified result.

Current status (as of August 2026): The binary case and qualitative learnability characterization are settled, while the general uniform bound is claimed by the April 2026 preprint and remains unverified.

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

Primary source

Progress summary

Solutions 0