Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:b4m36smu [2026/05/26 13:43] – [Question 10. (9 points)] jpelc | courses:b4m36smu [2026/05/27 09:37] (current) – [Other COLT] jpelc | ||
|---|---|---|---|
| Line 1307: | Line 1307: | ||
| ++++ Adapt Winnow / Halving algorithm, define $\mathcal{H}$, | ++++ Adapt Winnow / Halving algorithm, define $\mathcal{H}$, | ||
| - | MB-learning (or online learning) is bounded by the number of mistakes which it can do while learning, that is $\leq \text{poly}(n)$. | + | M-B-learning (or online learning) is bounded by the number of mistakes which it can do while learning, that is $\leq \text{poly}(n)$. |
| $\mathcal{H}$ is the hypothesis class, with the individual hypotheses being functions $X\rightarrow \left\{0, 1\right\}$ The hypothesis class is the complete set of all hypotheses that a specific learner is capable of expressing. | $\mathcal{H}$ is the hypothesis class, with the individual hypotheses being functions $X\rightarrow \left\{0, 1\right\}$ The hypothesis class is the complete set of all hypotheses that a specific learner is capable of expressing. | ||
| Line 1343: | Line 1343: | ||
| Mistake bound learnability implies PAC-learnability. | Mistake bound learnability implies PAC-learnability. | ||
| - | MB learner with $M \lt \text{poly}(n)$ can be transformed into PAC learner by running it on a batch of training examples, stopping when a hypothesis successfully survives $\frac{1}{\epsilon}\text{ln}(\frac{M}{\delta})$ consecutive examples without making a mistake. | + | M-B learner with $M \lt \text{poly}(n)$ can be transformed into PAC learner by running it on a batch of training examples, stopping when a hypothesis successfully survives $\frac{1}{\epsilon}\text{ln}(\frac{M}{\delta})$ consecutive examples without making a mistake. |
| ++++ | ++++ | ||
| Line 1349: | Line 1349: | ||
| No. | No. | ||
| - | PAC-learnability does not guarantee | + | PAC-learnability does not guarantee |
| - | If a concept class is PAC-learnable, | + | If a concept class is PAC-learnable, |
| ++++ | ++++ | ||
