Problem 2.14(c)

mileschen · #1 09-30-2012, 11:50 PM

For Problem 2.14(c), to determine the min value, the way I think would be try to solve the equation in (b) and get L. Maybe L is the second part of the min. However, how to solve the equation is a really hard question. Thus, could anyone tell me how to solve the equation or give me a hint on how to get the right answer?

magdon · #2 10-01-2012, 05:46 AM

Yes, solving the equation is really hard. It is simpler to show that if $\ell$ takes on the value in the second part of the min, the condition in (b) is satisfied.

Quote:

Originally Posted by mileschen

For Problem 2.14(c), to determine the min value, the way I think would be try to solve the equation in (b) and get L. Maybe L is the second part of the min. However, how to solve the equation is a really hard question. Thus, could anyone tell me how to solve the equation or give me a hint on how to get the right answer?

BojanVujatovic · #3 07-14-2014, 06:29 PM

Quote:

Originally Posted by magdon

It is simpler to show that if $\ell$ takes on the value in the second part of the min, the condition in (b) is satisfied.

I have difficulties solving this problem. If I assume that $\ell=d_{VC} \log_2 d_{VC} + (d_{VC}+1) \log_2 K$ , then the condition in (b) $2^\ell>K\ell^{d_{VC}+1}$ is not satisfied.
(e.g. when $d_{VC}=2, K=2$ , then $\ell=5$ and $2^5=32 \ngtr 2 \cdot 5^3=250$ ).

I believe the right thing to do would be to assume that $\ell \geq d_{VC} \log_2 d_{VC} + (d_{VC}+1) \log_2 K$ because the min bound will still hold and I believe the condition in (b) is then satisfied? But how do I prove that?

I appreciate any help.

magdon · #4 07-17-2014, 09:26 AM

There is a typo in the equation, sorry.

The second term in the minimum should be

$7(d_{VC}+K)\log_2(d_{VC}K)$ .

Rather than solve the inequality in (b) to get this bound, you may rather just verify that this is a bound by showing that if $\ell=7(d_{VC}+K)\log_2(d_{VC}K)$ , then the inequality in (b) is satisfied, namely $2^\ell>2K\ell^{d_{VC}}$ .

Quote:

Originally Posted by mileschen

For Problem 2.14(c), to determine the min value, the way I think would be try to solve the equation in (b) and get L. Maybe L is the second part of the min. However, how to solve the equation is a really hard question. Thus, could anyone tell me how to solve the equation or give me a hint on how to get the right answer?

BojanVujatovic · #5 07-20-2014, 09:48 AM

Thank you for your reply!

zhaozb15 · #6 10-01-2015, 08:46 AM

Quote:

Originally Posted by magdon

There is a typo in the equation, sorry.

The second term in the minimum should be

$7(d_{VC}+K)\log_2(d_{VC}K)$ .

Rather than solve the inequality in (b) to get this bound, you may rather just verify that this is a bound by showing that if $\ell=7(d_{VC}+K)\log_2(d_{VC}K)$ , then the inequality in (b) is satisfied, namely $2^\ell>2K\ell^{d_{VC}}$ .