Exercise 2.2 (b)
The question is asking if there is a hypothesis set for which m_H(N) = N + 2^floor(N/2).
Theorem 2.4 states that m_H(N) <= sum{0 to k1} (N choose i) if k is a breakpoint. My understanding is that m_H(N) = 2^k or it is bounded by a polynomial. However, the given growth function m_H(N) = N + 2^floor(N/2) seems exponential because of 2^(N/2). Therefore my answer is NO, it does not make sense to look for such hypothesis set. Can someone clarify if this is correct? Edit: Indeed, it is possible to show that m_H(N) is not bounded by a polynomial. 
Re: Exercise 2.2 (b)
Your understanding seems very reasonable!

Re: Exercise 2.2 (b)
m_H(N) = 2^k  This is perfect

All times are GMT 7. The time now is 09:10 PM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2020, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. AbuMostafa, Malik MagdonIsmail, and HsuanTien Lin, and participants in the Learning From Data MOOC by Yaser S. AbuMostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.