Daniely–Shalev-Shwartz conjecture on DS dimension and risk complexity
Let be a hypothesis class with Daniely–Shalev-Shwartz dimension , and let be the associated sequence of complexity measures. For any sample size , there is an absolute constant such that
Daniely–Shalev-Shwartz conjecture. The DS dimension controls the sequence complexity measures uniformly in through the displayed bound. The conjecture seeks to replace the sequence 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.
References
- Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty and Nikita Zhivotovskiy, “Optimal PAC Bounds Without Uniform Convergence”, arXiv:2304.09167 (2023).
Progress summary
A 2026 preprint claims a complete proof of the conjecture, but no independent verification has been reported.
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 up to logarithmic factors.
April 2026 claimed proof
A 2026 preprint claims that, for every and , . Its 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.
Solutions 0
No solutions have been posted yet.