New answers tagged machine-learning
1
Well, we wrote a paper on it, so now it's definitely known:
https://arxiv.org/abs/2010.09886
1
As far as I have understood, you aim to develop a framework to capture the hardness of combinatorial problems in 3D.
However, there are major problems in your question.
Your first sentence lacks a couple of technical definitions:
For a specific f(), I'm defining a term 'complexity', estimating how
difficult is the given function to optimize.
First, and the ...
5
For distributions with finite support of size $d$, when the error metric is the $\ell_1$ distance, the analogue of VC dimension is exactly $d$. (In fact, it's pretty much the VC dimension -- since to estimate a distribution over $d$ in $\ell_1$ is equivalent to agnostically PAC-learning the concept class $2^{[d]}$).
For discrete distributions with infinite ...
2
It is shown here (slide 10) that if $H_{d,k}$ is the number of depth-$k$ decision trees over $d$ input bits, then
$$v:=\log_2(H_{d,k})=
(2^k-1)(1+\log_2(d))+1
.
$$
So $v$ is an upper bound on the VC-dimension of your class. I don't know how tight it is, since you have the additional constraint of the trees being balanced.
Top 50 recent answers are included
