View Single Post
Old 05-01-2013, 05:35 PM
marek marek is offline
Join Date: Apr 2013
Posts: 31
Default Re: Q10 higher bound

Originally Posted by OlivierB View Post
@ marek, TTHotShot: Well, I agree with your remark, I was too quick: I have not explored the link between a hypothesis set and the dichotomies it generates on a set of points well enough. As a consequence the assertion that m_{H}(N)=m_{H'_1}(N)+m_{H'_2}(N) in general is wrong in general. Instead, it should be an inequality (≤), and probably quite a loose one, since there can be an overlap in the dichotomies generated by H_1 and H_2. Additionally, the definition of m_{H}(N) involves the determination of a maximum, and the independent search of 2 max on the RHS is a lot less constraining than one max on the LHS.
I agree that the inequality here feels rather loose, as that is what troubled me initially (since it feels like we can do better). However once we were able to generate examples of hypothesis sets that did result in disjoint dichotomies, and since those examples could readily be extended to broad families of such examples, that seals the deal. We are proving a general case argument. So even though many times we should expect to be well under the bound, those special examples that reach equality prevent us from making the bound any tighter.
Reply With Quote