Computational learning theory is an area of algorithms research devoted to the following task: given a source of “examples” $(x, f(x))$ from an unknown function $f$, compute a “hypothesis” function $h$ which is good at predicting $f(y)$ on future inputs $y$. We will focus on just one possible formulation of the task:

[...]

## Recent comments

Ryan O'Donnell: Yes, thanks!Dmitry Sokolov: Exercise 28. Maybe $A \in \{-1, 1\}$ istead of $A \in \mathb...Ryan O'Donnell: Fixed, thanks!Ryan O'Donnell: It's the Holder conjugate of $q$ (i.e., the number satisfyin...Gautam Kamath: Is $q'$ defined here?Gautam Kamath: On this page, Hölder is displaying for me as H{ö}lder - is t...Ryan O'Donnell: Yes, you're right. This is not a well-written proof by the ...