Lacasse's conjecture on the PAC-Bayesian combinatorial sum

Let ξ,ξ2:NR\xi,\xi_2:\mathbb{N}\to\mathbb{R} be defined by

ξ(m):=k=0m(mk)(km)k(1km)mk\xi(m):= \sum_{k=0}^m \binom{m}{k} \left( \frac{k}{m} \right)^k \left( 1-\frac{k}{m} \right)^{m-k}

and

ξ2(m):=j=0mk=0mj(mj)(mjk)(jm)j(km)k(1jmkm)mjk.\xi_2(m):= \sum_{j=0}^m \sum_{k=0}^{m-j} \binom{m}{j} \binom{m-j}{k} \left( \frac{j}{m} \right)^j \left( \frac{k}{m} \right)^k \left( 1-\frac{j}{m}-\frac{k}{m} \right)^{m-j-k}.

Lacasse's conjecture. For every mNm\in\mathbb{N},

ξ2(m)=ξ(m)+m.\xi_2(m)=\xi(m)+m.

This conjecture arose from numerical evidence in the study of combinatorial sums appearing in refined PAC-Bayesian bounds for majority-vote classifiers. Its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

M. Younsi and A. Lacasse, “A combinatorial conjecture from PAC-Bayesian machine learning”, arXiv:2006.01387 (2020).

Additional references

4 papers in this index state this conjecture (2012–2020). The statement above is taken from the most recent of them; the others are arXiv:1301.0679, arXiv:1212.6468, arXiv:1209.0824.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.